#!/usr/bin/python3
#coding:utf8

# http://projecteuler.net/problem=61
#
# PROBLEM CONTENT:
# 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
# Square:       P4,n = n*n
# Pentagonal:   P5,n = 2*(3n-1)/2
# Hexagonal:    P6,n = n*(2n-1)
# Heptagonal:   P7,n = n*(5n-3)/2
# Octagonal:    P8,n = n*(3n-2)
#
# 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.

# EXPLANATION:
# Iteratively place the numbers where they could fit in the graph. If at some
# point we can't add any more numbers, go back to the previous number and try
# to place it somewhere else.

import time

LOWER_LIMIT = 10**3
UPPER_LIMIT = 10**4

def get_triangular():
    n = 0
    r = []
    while True:
        n += 1
        next_element = int(n*(n+1)/2)
        if LOWER_LIMIT <= next_element < UPPER_LIMIT:
            r.append(next_element)
        elif next_element >= UPPER_LIMIT:
            break
    return r

def get_square():
    n = 0
    r = []
    while True:
        n += 1
        next_element = n*n
        if LOWER_LIMIT <= next_element < UPPER_LIMIT:
            r.append(next_element)
        elif next_element >= UPPER_LIMIT:
            break
    return r

def get_pentagonal():
    n = 0
    r = []
    while True:
        n += 1
        next_element = int(n*(3*n-1)/2)
        if LOWER_LIMIT <= next_element < UPPER_LIMIT:
            r.append(next_element)
        elif next_element >= UPPER_LIMIT:
            break
    return r

def get_hexagonal():
    n = 0
    r = []
    while True:
        n += 1
        next_element = n*(2*n-1)
        if LOWER_LIMIT <= next_element < UPPER_LIMIT:
            r.append(next_element)
        elif next_element >= UPPER_LIMIT:
            break
    return r

def get_heptagonal():
    n = 0
    r = []
    while True:
        n += 1
        next_element = int(n*(5*n-3)/2)
        if LOWER_LIMIT <= next_element < UPPER_LIMIT:
            r.append(next_element)
        elif next_element >= UPPER_LIMIT:
            break
    return r

def get_octogonal():
    n = 0
    r = []
    while True:
        n += 1
        next_element = n*(3*n-2)
        if LOWER_LIMIT <= next_element < UPPER_LIMIT:
            r.append(next_element)
        elif next_element >= UPPER_LIMIT:
            break
    return r

def index_to_insert(group, n, last_index = None):
    if n in group:
        return None

    for i,m in enumerate(group):
        if last_index != None and i <= last_index:
            continue

        if m == None:
            if group[i-1] == None or int(n/100) == group[i-1]%100:
                if group[(i+1)%6] == None or int(group[(i+1)%6]/100) == n%100:
                    return i
    return None

def main():
    triangular = get_triangular()
    square = get_square()
    pentagonal = get_pentagonal()
    hexagonal = get_hexagonal()
    heptagonal = get_heptagonal()
    octogonal = get_octogonal()

    c = [None for i in range(0, 6)]
    for o in octogonal:
        c[0] = o

        for hep in heptagonal:
            ihep = index_to_insert(c, hep)
            while ihep != None:
                c[ihep] = hep

                for h in hexagonal:
                    ih = index_to_insert(c, h)
                    while ih != None:
                        c[ih] = h

                        for p in pentagonal:
                            ip = index_to_insert(c, p)
                            while ip != None:
                                c[ip] = p

                                for s in square:
                                    isq = index_to_insert(c, s)
                                    while isq != None:
                                        c[isq] = s

                                        for t in triangular:
                                            it = index_to_insert(c, t)
                                            if it != None:
                                                c[it] = t
                                                print('{}: {}'.format(c, sum(c)))
                                                return

                                        c[isq] = None
                                        isq = index_to_insert(c, s, isq)

                                c[ip] = None
                                ip = index_to_insert(c, p, ip)

                        c[ih] = None
                        ih = index_to_insert(c, h, ih)

                c[ihep] = None
                ihep = index_to_insert(c, hep, ihep)

if __name__ == '__main__':
    start = time.time()
    main()
    elapsed = time.time() - start
    print('Solved in %.2f seconds' % elapsed)
