Project Euler #61 - cyclical figurate numbers

프로젝트 오일러 61번 - 순환 다항 수
세 숫자 8128, 2882, 8281 는 두가지 독특한 성질이 있다.
1. 두자리씩 끊었을 때 28, 82, 81 이렇게 연결이 되는 성질(cyclical)
2. 8128은 3각수  - n(n+1)/2의 형태, 8281은 4각수 - n^2의 형태, 2882는 5각수 - n(3n-1)/2의 형태태

네자리 숫자 6개로 아래의 성질을 갖는 경우가 단 하나 있다. 이 6개 숫자의 합은?
1. 두자리씩 끊었을 때 연결된다
2. 숫자 6개가 각각 삼각, 사각, 오각, 육각, 칠각, 팔각수


예시에도 있지만 cycle의 순서는 아직 모른다. 3각->4각->5각->... 일 수도 있고, 3각->8각->4각->...일 수도 있다. 순환의 속성상 시작을 어디로 하든 마음대로라는 점은 다행이다. 8각수의 개수가 제일 적으니 거기에서 시작해 보자.
모든 8각수에 대해, 뒤 2자리(꼬리)를 끊고,
이 2자리로 시작하는(머리가 되는) 모든 케이스를 3각~7각에서 찾고
이 때의 꼬리를 찾고,
이 꼬리가 머리가 되는 모든 케이스를 3각~7각 중에서 위에서 선택하지 않았던 곳에서 찾고,
이 때의 꼬리를 찾고,
이 꼬리가 머리가 되는.....
이렇게 3각~7각을 한번씩 돌고 나면 순환이 완성된다.

늘 그렇듯 긴 코드가 실행시간을 줄여준다.

p, ph, pt = [],[],[]

p.append([`n*(n+1)/2`   for n in range(1,200) if 1000 <= n*(n+1)/2   < 10000])
p.append([`n*n`         for n in range(1,200) if 1000 <= n*n         < 10000])
p.append([`n*(3*n-1)/2` for n in range(1,200) if 1000 <= n*(3*n-1)/2 < 10000])
p.append([`n*(2*n-1)`   for n in range(1,200) if 1000 <= n*(2*n-1)   < 10000])
p.append([`n*(5*n-3)/2` for n in range(1,200) if 1000 <= n*(5*n-3)/2 < 10000])
p.append([`n*(3*n-2)`   for n in range(1,200) if 1000 <= n*(3*n-2)   < 10000])

big = {}
#{'10': {0: ['35', '81'],  1: ['24', '89']}, '11': {0: ['28', '76'],  4: ['60']},...}

for i in range(5):
    for e in p[i]:
        head, tail = e[:2], e[-2:]
        if tail[0] != '0':
            if head in big:
                if i in big[head]: big[head][i].append(tail)
                else: big[head][i] = [tail]
            else:
                big[head] = {}
                big[head][i] = [tail]


def prob61(p,big):
    for e5 in p[5]:
        e5h, e5t = e5[:2], e5[-2:]
        if e5t in big:
            for s1 in big[e5t]:
                for h1 in big[e5t][s1]:
                    if h1 in big:
                        for s2 in big[h1]:
                            if s2 not in [s1]:
                                for h2 in big[h1][s2]:
                                    if h2 in big:
                                        for s3 in big[h2]:
                                            if s3 not in [s1,s2]:
                                                for h3 in big[h2][s3]:
                                                    if h3 in big:
                                                        for s4 in big[h3]:
                                                            if s4 not in [s1,s2,s3]:
                                                                for h4 in big[h3][s4]:
                                                                    if h4 in big:
                                                                        for s5 in big[h4]:
                                                                            if s5 not in [s1,s2,s3,s4]:
                                                                                for h5 in big[h4][s5]:
                                                                                    if h5 == e5h:
                                                                                        return int(e5)+int(e5t+h1)+int(h1+h2)+int(h2+h3)+int(h3+h4)+int(h4+h5)
                                                                                    
print prob61(p,big)

0.0015초