Project Euler 209

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

Q209.
τ(a, b, c, d, e, f) AND τ(b, c, d, e, f, a XOR (b AND c)) = 0
を常に満たす、真偽表τはいくつあるか

6つの変数をまとめて6ビットの整数として考えると分かりやすくなる。その整数に対して0か1を対応させるのが真偽表、ということになる。
上の式に対応する2つの整数の組は、少なくともどちらかが0でなければならない。この対応をグラフで表す。そうすると、グラフの点の次数は2以下であることが確認できる。よって、グラフはループになっている。今回の場合、いくつかのループに分かれている。それらのループの大きさに対して、隣同士が1にならないような組合せが分かる。これは適当に調べればいい。

def convert(n):

    a = (n & 32) >> 5

    b = (n & 16) >> 4

    c = (n &  8) >> 3

    return ( (n & 31) << 1) | (a ^ (b & c))
def make_graph():

    g = [ [ ] for i in range(64) ]

    for n in range(64):

        m = convert(n)

        g[n].append(m)

        g[m].append(n)

    return g
def C(n, m):

    if m == 0:

        return 1

    return C(n, m - 1) * (n - m + 1) / m
def H(n, m):

    return C(n + m - 1, m)
def count_valid_loop(n):

    s = 0

    for m in range(n / 2 + 1):

        if m == 0:

            s += 1

        elif m == 1:

            s += n

        else:

            s += 2 * H(m, n - 2 * m)

            if n >= 2 * m + 1:

                s += H(m + 1, n - 2 * m - 1)

    return s
def gen_connected_subgraph(g):

    unused = set(range(64))

    while len(unused):

        s = set()

        e0 = unused.pop()

        while True:

            s.add(e0)

            unused.discard(e0)

            e1 = g[e0][0]

            if e1 not in unused:

                e1 = g[e0][1]

                if e1 not in unused:

                    yield s

                    break

            e0 = e1
g = make_graph()

print reduce(max, map(len, g))

def mul(x, y): return x * y

print reduce(mul, map(count_valid_loop, map(len, gen_connected_subgraph(g))))