Project Euler 61

プロジェクトオイラー
http://projecteuler.net/index.php

Q61.
8128 → 2882 → 8281 → 8128
みたいに2桁がしりとりになるように巡回して、6つで巡回、それが三角数から八角数の一つずつを取る、そのときの総和

あらかじめ多角数のリストを作ってから、有向グラフを作る。そして6つで戻ってくるルートを探し、三角数から八角数の一つずつを使っているかどうか調べる。

from math import sqrt
def is_square(n):

    m = int(sqrt(n + 0.5))

    return m * m == n
def is_polygonal(n):

    for k in range(3, 9):

        if is_polygonal_type(n, k):

            return True

    return False
def is_polygonal_type(n, k):

    det = (k + 8 * (n - 1)) * k - 16 * (n - 1)

    if is_square(det):

        num = k - 4 + int(sqrt(det) + 0.5)

        den = 2 * (k - 2)

        if num % den == 0:

            return True

    return False
def get_type(p):

    return filter(lambda k: is_polygonal_type(p, k), range(3, 9))
def is_connect(p, q):

    return p % 100 == q / 100
def is_valid(n):

    if n % 100 >= 10:

        return is_polygonal(n)

    else:

        return False
def graph(poly):

    g = { }

    for p in poly:

        g[p] = filter(lambda q: is_connect(p, q), poly)

    return g
def gen(g, n):

    if n == 1:

        for p in g.keys():

            yield [ p ]

    else:

        for l in gen(g, n - 1):

            for p in g[l[n-2]]:

                yield l + [ p ]
def is_loop(l):

    return l[0] == l[len(l)-1]
def find(l, x):

    i = 0

    for a in l:

        if a == x:

            return i

        i += 1

    return -1
def gen_type(l, i):

    if i == 0:

        for k in l[i]:

            yield [ k ]

    else:

        for k in l[i]:

            for li in gen_type(l, i - 1):

                if len(li) == 0:

                    break

                if find(li, k) == -1:

                    yield li + [ k ]

    yield [ ]
def is_each_type(l):

    l = l[:-1]

    t = [ get_type(p) for p in l ]

    return len(gen_type(t, len(l) - 1).next()) > 0
def find_loop(g, n):

    for l in gen(g, n):

        if is_loop(l) and is_each_type(l):

            return l[:-1]

    return [ ]
N = 6

polygons = filter(is_valid, range(1000, 10000))

g = graph(polygons)

l = find_loop(g, N + 1)

print l

print sum(l)