Euler 61

gistfile1.txt

# http://projecteuler.net/problem=61
# this should run in 500ms

import itertools

# these are the formulas for the six polygonal numbers
def fn(n):
  return [n*(n+1)/2,n*n,n*(3*n-1)/2,n*(2*n-1),n*(5*n-3)/2,n*(3*n-2)]

# this is what we'll use for the cyclic pattern matching
def last2(n):
	n = str(n)
	digits = int(n[2:5])
	return digits*100	
	
# here we create a list for each number type, and then add only 4 digit numbers
tri = []
square = []
pent = []
hex = []
hept = []
oct = []

for n in range (1,141):
	if len(str(fn(n)[0])) == 4 and str(fn(n)[0])[2:5].find("0")==-1: 
 		tri.append(fn(n)[0])
 	if len(str(fn(n)[1])) == 4 and str(fn(n)[1])[2:5].find("0")==-1: 
		square.append(fn(n)[1])
	if len(str(fn(n)[2])) == 4 and str(fn(n)[2])[2:5].find("0")==-1:
		pent.append(fn(n)[2])
	if len(str(fn(n)[3])) == 4 and str(fn(n)[3])[2:5].find("0")==-1: 
		hex.append(fn(n)[3])
	if len(str(fn(n)[4])) == 4 and str(fn(n)[4])[2:5].find("0")==-1: 
		hept.append(fn(n)[4])
	if len(str(fn(n)[5])) == 4 and str(fn(n)[5])[2:5].find("0")==-1: 
		oct.append(fn(n)[5])

# we're looking for round trips between any of these six sets
# but since the sets can be in any order, we need to permute them
for h in itertools.permutations([tri,pent,square,hex,hept,oct], 6):
	a=h[0]
	b=h[1]
	c=h[2]
	d=h[3]
	e=h[4]
	f=h[5]

# then, for each permutation, we check for the roundtrip pattern
	for o in range (1,len(a)):
		if a[o] > 1000 and a[o] < 10000:
			for p in range (1,len(b)):
				if b[p] > last2(a[o]) and b[p]<last2(a[o])+100:
					for q in range (1,len(c)):
						if c[q] > last2(b[p]) and c[q]<last2(b[p])+100:
							for r in range (1, len(d)):
								if d[r] > last2(c[q]) and d[r]<last2(c[q])+100:
									for s in range (1,len(e)):
										if e[s] > last2(d[r]) and e[s]<last2(d[r])+100:
											for t in range (1,len(f)):
												if f[t] > last2(e[s]) and f[t]<last2(e[s])+100:
													if str(f[t])[2:5] == str(a[o])[0:2]:
														print a[o],b[p],c[q],d[r],e[s],f[t]
														print a[o]+b[p]+c[q]+d[r]+e[s]+f[t]
														exit()