#!/usr/bin/env python
import operator
import sys
# Recursive combinations function
def combs_aux(elems, comb_len, depth, start_at, cur_comb, output):
if depth >= comb_len:
output.append(tuple(cur_comb))
return
for x in xrange(start_at, len(elems) - (comb_len - depth) + 1):
cur_comb[depth] = elems[x]
combs_aux(elems, comb_len, depth + 1, x + 1, cur_comb, output)
# Wrapper to ease calls
def combinations(elems, comb_len):
elems = list(elems)
output = []
combs_aux(elems, comb_len, 0, 0, [None] * comb_len, output)
return output
# Auxiliar: does every edge exist?
def edges_exist((a, b, c), straights):
one = [s for s in straights if a in s and b in s]
two = [s for s in straights if a in s and c in s]
three = [s for s in straights if b in s and c in s]
return (len(one) > 0 and len(two) > 0 and len(three) > 0)
# Auxiliar: all vertex in the same straight?
def same_straight((a, b, c), straights):
return (len([s for s in straights if a in s and b in s and c in s]) > 0)
# Read files
try:
straights_str = file(sys.argv[1], 'r').read()
except (IOError, OSError, IndexError):
sys.exit('Usage: %s straights_file' % sys.argv[0])
# Straights
straights_lines = [x for x in straights_str.split('\n') if len(x) != 0]
straights_strlists = [x.split() for x in straights_lines]
straights_lists = [[long(x) for x in lst] for lst in straights_strlists]
straights = set(tuple(x) for x in straights_lists if len(x) != 0)
# Extract vertex
vertex = set(reduce(operator.concat, straights_lists, []))
# Generate combinations and filter by existing edges and straights
candidates = combinations(vertex, 3)
candidates = [x for x in candidates if edges_exist(x, straights)]
triangles = [x for x in candidates if not same_straight(x, straights)]
# Print triangles and total count
if len(triangles) > 0:
print '\n'.join('(%s, %s, %s)' % (a, b, c) for (a, b, c) in triangles)
print 'Number of triangles: %s' % len(triangles)
Counting Triangles (2)
In connection with the previous post, reader Álvaro has pointed out two easy simplifications I missed completely, and they make the program much easier from the user’s point of view.
First, the need to input segments is superfluous. Passing the straights alone is enough. You can get the segments, if you want, by combining the vertex of each straight in couples.
Second, on top of that, generating the segments isn’t really needed from the programming perspective, as you can easily test that any given segment (a, b) exists if those two vertex appear in the same straight, for any of the available straights.
Applying the changes to the source code is easy and the final result is a shorter program that only needs to be passed the list of straights in the same format as the previous program. This means the user only has to identify the vertex and enumerate the straights, writing them to a text file.
Source code (public domain)
Load comments