Project Euler 68 - inamori’s diary

Problem 68
"magic" 3-gon ringというものを考える。これは1から6の数で埋められており、各ラインは足すと9になる。
時計回りで考えて、外周のノードで最も小さい数を含む3つの数のグループをスタートとすると、各々の解は一意に記述される。
4つの総和9,10,11,12で解は尽くされる。8つの解がある。
Total Solution Set
9 4,2,3; 5,3,1; 6,1,2
...
各々のグループを結合して、9桁の数ができる。3-gon ringの最大は432621513である。
1から10の数を使うと、並べ方次第で、16桁と17桁の数ができる。16桁で最大の"magic" 5-gon ringはいくつか。
http://projecteuler.net/index.php?section=problems&id=68

わかりやすいように3-gonで考えます。外周の3つの数を決めます。その内の最小の数が最初のライン上ということになります。それを除いた2つの順列を決めます。そして、残りの3つの数で順列を決めます。そうして条件を満たす並びのうちで最大の数になるものを得ます（Code1）。

もっと効率のよい方法を考えましょう。最大の数を求めるので、大きい数から順に判定して最初に条件を満たすものが答えになります。

この順に大きい数を並べて順列を出せば、結合した数が大きい順に並ぶことになります。3-gonでは6から1を並べればよいですが、5-gonでは9から1、10と並べればよいです。
この順列を生成するコードを自作しましょう。単に順列を出すだけなら簡単です。リストから順番に要素を選んで、その要素を除いたリストから生成する順列と結合します。例えば、[3, 2, 1]があって、まず3を取り除いて[2, 1]とします。これは(2, 1)と(1, 2)を生成するので、これに3を前に結合して、(3, 2, 1), (3, 1, 2)とします。



def gen_perm(a):

    if len(a) == 0:

        yield ()

    else:

        for k in range(len(a)):

            n = a[k]

            for b in gen_perm(a[:k] + a[k+1:]):

                yield (n,) + b

条件に合わないものは途中で弾いていきます。例えば、外周の最小の数が4なら内周に4より大きい数を使う余裕がありません。3なら一つだけ3より大きい数を使う余裕があります。この余裕が負になったら弾きます（Code2）。



# Code1

from itertools import permutations, combinations, imap, ifilter
def all(f, a):

    for e in imap(f, a):

        if not e:

            return False

    return True
def gen_sum(a):

    for k in range(N - 1):

        yield a[k] + a[k+1] + a[k+N]

    yield a[N-1] + a[0] + a[N+N-1]
def is_valid(a):

    g = gen_sum(a)

    n = g.next()

    return all(lambda m: m == n, g)
def gen_perm():

    for a in combinations(range(1, M + 1), N):

        a_min = reduce(min, a)

        for b in permutations(filter(lambda e: e != a_min, a)):

            for c in permutations(filter(

                    lambda k: all(lambda e: e != k, a), range(1, M + 1))):

                yield c + (a_min,) + b
def gen_solutions():

    for a in ifilter(is_valid, gen_perm()):

        yield a
def numerize(a):

    def g(a):

        for k in range(N):

            yield a[k+N]

            yield a[k]

            yield a[(k+1)%N]

    

    return reduce(lambda x, y: x * (100 if y > 9 else 10) + y, g(a))
N = 5

M = N * 2

print reduce(max, ifilter(lambda n: n < 10 ** 16,

                        imap(numerize, gen_solutions())))



# Code2

from itertools import permutations, combinations, imap, ifilter
def head(a):

    for e in a:

        return e
def gen_sum(a):

    yield a[0] + a[1] + a[2]

    for k in range(3, M - 1, 2):

        yield a[k] + a[k-1] + a[k+1]

    yield a[M-1] + a[M-2] + a[1]
def is_valid(a):

    g = gen_sum(a)

    n = g.next()

    return all(imap(lambda m: m == n, g))
def is_on_inner_circle(k):

    return k == 1 or k % 2 == 0
def gen_perm(a = 0, k = 0, r0 = 0, start = 0):

    if k == M:

        yield ()

    if k == 0:

        a = range(M - 1, 0, -1) + [ M ]

    for i in range(len(a)):

        n = a[i]

        if k == 0:

            r = N + 1 - n

            start = n

        else:

            r = r0

            if is_on_inner_circle(k):

                if n > start:

                    r -= 1

                    if r < 0:

                        continue

            else:

                if n < start:

                    continue

        for b in gen_perm(a[:i] + a[i+1:], k + 1, r, start):

            yield (n,) + b
def gen_solutions():

    for a in ifilter(is_valid, gen_perm()):

        yield a
def numerize(a):

    def g(a):

        yield a[0]

        yield a[1]

        for k in range(2, M, 2):

            yield a[k]

            yield a[k+1]

            yield a[k]

        yield a[1]

    

    return reduce(lambda x, y: x * (100 if y > 9 else 10) + y, g(a))
N = 5

M = N * 2

print head(imap(numerize, gen_solutions()))