#!/usr/bin/python
# encoding: latin1

#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=n2 	  	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.

#   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).

#   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.

#    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 math import floor,ceil,sqrt,log
from itertools import takewhile,imap,count


def index2type(index):
	if index==0:
		return "Triangular"
	elif index==1:
		return "Square"
	elif index==2:
		return "Pentagonal"
	elif index==3:
		return "Hexagonal"
	elif index==4:
		return "Heptagonal"
	elif index==5:
		return "Octogonal"


def depth_search(cycle=[],types=[],figurate_numbers=[],first=0):
	chain_len = 6
	if cycle==[]:
		# creating the stacks of figurate numbers
		figurate_numbers = [ 
			[ n for n in takewhile(lambda x: x<10000,imap(lambda x: x*(x+1)/2,count(1))) if n>=1000 ],
			[ n for n in takewhile(lambda x: x<10000,imap(lambda x: x**2,count(1))) if n>=1000 ],
			[ n for n in takewhile(lambda x: x<10000,imap(lambda x: x*(3*x-1)/2,count(1))) if n>=1000 ],
			[ n for n in takewhile(lambda x: x<10000,imap(lambda x: x*(2*x-1),count(1))) if n>=1000 ],
			[ n for n in takewhile(lambda x: x<10000,imap(lambda x: x*(5*x-3)/2,count(1))) if n>=1000 ],
			[ n for n in takewhile(lambda x: x<10000,imap(lambda x: x*(3*x-2),count(1))) if n>=1000 ] ]
				
		for number in figurate_numbers[0]:
			print index2type(0), "= ",number
			ret = depth_search(cycle+[number],[0],figurate_numbers,number)
			if ret == True:
				return True

		return False
	else:
		index = len(cycle)
		last_number = cycle[index-1]
		prefix = int(str(last_number)[2:])*100

		if prefix>0 and (log(prefix)/log(10))>3:
			if len(cycle)<chain_len:
				ret=False
				for Type in set(range(chain_len))-set(types):
					for number in [ x for x in figurate_numbers[Type] if x>=prefix and x<=(prefix+99) ]:
						spaces = [ ' ' for x in range(3*len(cycle)) ]
						print ''.join(spaces), index2type(Type), "= ", number
						ret = depth_search(cycle+[number],types+[Type],figurate_numbers,first)
						if ret==True:
							return ret

				return ret
			else:
				if str(first)[:2]==str(last_number)[2:]:
					print "Found cycle: ", cycle
					print "Sum: ", sum(cycle)
					return True
				else:
					return False

depth_search()




