Project Euler 103

http://projecteuler.net/index.php?section=problems&id=103

まず、問題文にある「ルール」に従って集合を作ります。n = 6の例を参考にして、各要素を-2〜+1しかつ昇順を崩さない集合を作ります。それが題意を満たすか調べます。2つ目の性質を調べるのは簡単で、例えばn = 6なら最初の3つの要素と最後の2つの要素のそれぞれの和を取って大小を比較します。1つ目の性質は、全ての交わらない2つの部分集合を取って調べます。遅そうですが、この問題ではこれでも十分速いです。

from itertools import *

def finds_sum(a, n):
    if n == 0:
        return True
    elif len(a) == 0:
        return False
    elif n < 0:
        return False
    else:
        a2 = a[1:]
        return any((finds_sum(a2, n - a[0]), finds_sum(a2, n)))

def condition1(a):
    def c2_core(b):
        s = sum(b)
        if s % 2 == 1:
            return True
        half = s / 2
        back = b[-1]
        n = half - back
        return not finds_sum(b[:-1], n)
    
    n = len(a)
    return all(c2_core(b) for m in range(3, n + 1)
                                for b in combinations(a, m))

def condition2(a):
    n = len(a)
    return sum(a[:(n+1)/2]) > sum(a[n/2+1:])

def is_valid(a):
    return condition2(a) and condition1(a)

def gen_sets(a, prev = 0, k = 0):
    if k == len(a):
        yield []
    else:
        begin = max(a[k] - 2, prev + 1)
        if k == len(a) - 1:
            end = a[k] + 1
        else:
            end = min(a[k] + 1, a[k+1] - 1)
        for p in range(begin, end + 1):
            for b in gen_sets(a, p, k + 1):
                yield [ p ] + b

def minimize(a):
    solutions = [ b for b in gen_sets(a) if is_valid(b) ]
    return min(solutions, key = lambda a: sum(a))

def next_set(a):
    n = len(a)
    b = a[n/2]
    return minimize([ b ] + [ e + b for e in a ])

N = 7
a = reduce(lambda x, y: next_set(x), range(2, N + 1), [ 1 ])
print "".join(map(str, a))