Counting Triangles (3)

Posted on . Updated on .

A few days ago a familiar problem turned up on a Spanish online newspaper, promoted as a mind game that was trending in Twitter.

Apart from the bogus IQ statement, it offered me the chance to revisit my old piece of code that brute-forced the problem easily with a few lines of code thanks to the amazing speed of computers today.

I reworked the code by using itertools.combinations instead of custom code, removing a lot of boilerplate and improving the code in general and using Python 3 instead of Python 2. The result, in the public domain as the previous ones:

#!/usr/bin/env python3
from itertools import combinations
import sys

lines = set()
vertex = set()

if len(sys.argv) != 2:
    sys.exit('Usage: %s INPUT_FILE' % (sys.argv[0], ))

try:
    with open(sys.argv[1], 'r') as stream:
        for input_line in stream:
            if not input_line.startswith('#'):
                drawing_line = tuple(input_line.split())
                if len(drawing_line) > 0:
                    lines.add(drawing_line)
except (IOError, OSError):
    sys.exit('ERROR: unable to read input file')

for l in lines:
    vertex.update(set(l))

def tuple_in_line(t, lines):
    return any(all(e in l for e in t) for l in lines)

def valid_triangle(trio, lines):
    return (all(tuple_in_line(pair, lines) for pair in combinations(trio, 2))
            and (not tuple_in_line(trio, lines)))

triangles = []
for trio in combinations(vertex, 3):
    trio = sorted(trio)
    if valid_triangle(trio, lines):
        triangles.append(trio)

for t in sorted(triangles):
    print(' '.join(t))
print('Total: %s' % (len(triangles), ))

If problems were larger, we could generate graphs with all existing 2-vertex and 3-vertex connections beforehand and enumerate triangles using that knowledge instead of just brute-forcing the problem by generating all possible triangles and checking if they’re valid for the given drawing.

Reminder: to input data to the program you need to enumerate every vertex in the image by hand (a vertex is any point where two or more lines meet) and finally list the lines in the drawing, one per input line as a list of vertex separated by spaces. If in doubt, read my two previous posts on the problem.

In the Twitter image, like other replies said, there are actually 24 triangles.

Load comments