# -*- coding: utf-8 -*-
""" Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal
numbers are all figurate (polygonal) numbers and are generated by the
following formulae:

  Triangle   P(3,n) = n(n+1)/2
  Square     P(4,n) = n*n
  Pentagonal P(5,n) = n(3n−1)/2
  Hexagonal  P(6,n) = n(2n−1)
  Heptagonal P(7,n) = n(5n−3)/2
  Octagonal  P(8,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. """

import itertools
import functools
import collections


class FigurateNode(collections.namedtuple('FigurateNode',
                                          ['prefix', 'suffix', 's'])):
    def __str__(self):
        return '%s:%s%s' % (self.s, self.prefix, self.suffix)

    def __repr__(self):
        return self.__str__()

    def __int__(self):
        return int(self.prefix + self.suffix)

    def __add__(self, other):
        return int(int(other) + int(self))

    def __radd__(self, other):
        return int(int(other) + int(self))


def polygonal_number(s, n):
    """ If s is the numer of sides in a polygon, then the formula for the nth
    s-gonal number P(s,n) is:
                 n^2(s-2)-n(s-4)
        P(s,n)= -----------------
                        2

    See http://en.wikipedia.org/wiki/Polygonal_number#Formula """
    return (n*n*(s-2)-n*(s-4))/2

def polygon_gen(s):
    """ Returns an iterator generating, for a fixed s, all the s-gonal
    numbers {P(s,n): n=1, 2, ...} """
    f = functools.partial(polygonal_number, s)
    return itertools.imap(f, itertools.count(1))

def figurate_list(s):
    """ Create a list of figurate numbers for a given s, between 1000 and 9999,
    with the additional property that the third digit of each number will not
    be 0. """
    f = polygon_gen(s)
    ans = []
    c = next(f)
    while c < 999: c = next(f)
    while c < 10000:
        c = str(c)
        if c[2] != '0': ans.append(FigurateNode(c[:2], c[-2:], s))
        c = next(f)
    return ans


def figurate_cycles(*s_vals):
    """ Finds all complete figurate cycles for given s-values. """
    assert len(s_vals) > 1 #incomplete sanity check
    # Since a DFS has to start SOMEWHERE and we're looking for cycles, we
    # arbitrarily take the first list of figurates and use them as the
    # roots of our search.
    roots = figurate_list(s_vals[0])
    # Make a big list of all the rest of the figurate numbers
    candidates = []
    for s in s_vals[1:]:
        candidates.extend(figurate_list(s))
    answer = []
    # Perform a cycle-detecting DFS for every root in our list
    for root in roots:
        for cycle in find_all_cycles(candidates, root):
            answer.append(cycle)
    return answer
    

def find_all_cycles(candidates, new_elem, path=[]):
    """ Depth-first search for cycle finding """
    
    def have_cycle(candidates, path):
        """ Checks that when we have no more candidates, that our path
        'endpoints' are cyclical. """
        return (not candidates and path[0].prefix == path[-1].suffix)
    
    def have_dead_end(candidates, new_elem):
        """ Checks that we have at least one candidate whose prefix is
        cyclical with the new element's suffix. """
        return new_elem.suffix not in map(lambda x: x.prefix, candidates)
    
    def remove_sgons(s_value, candidates):
        """ Returns a new list where all s-gonal candidates have been
        removed. """
        return list(filter(lambda x: x.s != s_value,
                           candidates))
    # Append new_elem to our working path, and test for our two exit criteria:
    #   1. A complete cycle -- There are no more candidates to extend our path
    #      with and our ends wrap around prefix-suffix-cyclically
    #   2. A dead end -- There are no new candidates whose prefix match our
    #      new element's suffix
    path = path + [new_elem]
    if have_cycle(candidates, path):
        return [path]
    if have_dead_end(candidates, new_elem):
        return []
    # Now go through every candidate and find the handful of ones whose prefix
    # match our new element's suffix.
    cycles = []
    for candidate in candidates:
        if new_elem.suffix == candidate.prefix:
            # When we find a valid candidate, we remove all candidates of the
            # same figurate type as our valid candidate.
            new_candidates = remove_sgons(candidate.s, candidates)
            # We then go down the path of finding all cycles with our valid
            # candidate as the new last-element
            new_cycles = find_all_cycles(new_candidates, candidate, list(path))
            for new_cycle in new_cycles:
                cycles.append(new_cycle)
    return cycles

def TEST():
    answer = figurate_cycles(3, 4, 5)
    print 'ANSWER', answer

def ANSWER():
    from datetime import datetime
    import operator
    start = datetime.now()
    cycles = figurate_cycles(3, 4, 5, 6, 7, 8)
    print 'CYCLES: '
    for cycle in cycles:
        print cycle
    assert len(cycles) == 1
    cycle = cycles[0]
    answer = functools.reduce(operator.add, cycle)
    print 'Answer: ', answer
    end = datetime.now()
    print 'Running time: ', end - start
