Used by the Imperfect Congruence website

vertex_figure_search.py

#Finds all possible regular polygon vertex types

# reduce the problem to integer math
# with a lowest common denominator
# that is divisible by all numbers up to 12

dem = 8*9*5*7*11
ang = {}
for i in range(3,13):
    ang[i] = (dem / i) * (i-2)

def compute_partitions_small(options,tree):
    global ang, dem
    if len(options) > 0:
        if tree[0] >= 2*dem:
            if tree[0] == 2*dem:
                print tree[1:]
            return tree
        else:
            tree[0] += ang[options[0]]
            tree = compute_partitions_small(options,tree + [options[0]])
            if len(tree) > 1:
                tree[0] -= ang[tree[-1]]
                return compute_partitions_small(options[1:],tree[:-1])
    return tree

def compute_partitions_large(options,tree):
    global ang,dem
    m1 = 2*dem-(10*(dem/12))
    if len(options) > 0:
        if tree[0] > dem and tree[0] < m1:
            sides = 2.0*dem/(tree[0]-dem)
            print tree[1:],sides
            return tree
        elif tree[0] >= m1:
            return tree
        else:
            tree[0] += ang[options[0]]
            tree = compute_partitions_large(options,tree + [options[0]])
            if len(tree) > 1:
                tree[0] -= ang[tree[-1]]
                return compute_partitions_large(options[1:],tree[:-1])
    return tree

# the first value of the tree array is the current angle sum

print "small polygon vertex figures"
compute_partitions_small([3,4,5,6,7,8,9,10,11,12],[0])
print "possible large polygon vertex figures"
compute_partitions_large([3,4,5,6,7,8,9,10,11,12],[0])