#!/usr/bin/env python

"""
Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are
all figurate (polygonal) numbers and are generated by the following formulae:

Triangle        P3(n)=n(n+1)/2       1, 3, 6, 10, 15, ...
Square          P4(n)=n^2            1, 4, 9, 16, 25, ...
Pentagonal      P5(n)=n(3n-1)/2      1, 5, 12, 22, 35, ...
Hexagonal       P6(n)=n(2n-1)        1, 6, 15, 28, 45, ...
Heptagonal      P7(n)=n(5n-3)/2      1, 7, 18, 34, 55, ...
Octagonal       P8(n)=n(3n-2)        1, 8, 21, 40, 65, ...

The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three
interesting properties:

1. The set is cyclic, in that the last two digits of each number is the first
   two digits of the next number (including the last number with the first).
2. Each polygonal type: triangle (P3(127)=8128), square (P4(91)=8281), and
   pentagonal (P5(44)=2882), is represented by a different number in the set.
3. This is the only set of 4-digit numbers with this property.

Find the sum of the only ordered set of six cyclic 4-digit numbers for which
each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and
octagonal, is represented by a different number in the set.
"""

from itertools import count

def p3(n): return n*(n+1)/2
def p4(n): return n**2
def p5(n): return n*(3*n-1)/2
def p6(n): return n*(2*n-1)
def p7(n): return n*(5*n-3)/2
def p8(n): return n*(3*n-2)

def f_range(f):
    "Call the function f and return list of values between 1000 and 9999."
    result = []
    for n in count(1):
        value = f(n)
        if value >= 10000:
            break
        if value >= 1000:
            result.append(value)
    return result

def find_sequence(functions, seed=None, suffix=None):
    if len(functions) == 1:
        value = int(seed + suffix)
        if value in functions.values()[0]:
            return [value]
        else:
            return None
    for function, values in functions.iteritems():
        new_functions = dict(functions)
        del new_functions[function]
        for value in values:
            if not seed:
                suffix = str(value)[:2]
            if not seed or str(value)[:2] == seed:
                result = find_sequence(
                        new_functions, str(value)[-2:], suffix)
                if result:
                    return [value] + result
    return None

if __name__ == '__main__':
    functions = {
        p3 : f_range(p3),
        p4 : f_range(p4),
        p5 : f_range(p5),
        # To solve the example problem, comment out p6, p7, and p8 here
        p6 : f_range(p6),
        p7 : f_range(p7),
        p8 : f_range(p8),
    }
    result = find_sequence(functions)
    print 'Result:', result
    print 'Sum:', sum(result)
