Project Euler 34

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

これもProblem 30とほとんど同じです。
重複組合せを使う方法に対して、8倍くらい速かったです。

from itertools import *
import time

def digits(n):
    while n > 0:
        yield n % 10
        n /= 10

def factorial(n):
    return reduce(lambda x, y: x * y, range(1, n + 1), 1)

def calc_limit():
    n = next(n for n in count(1) if factorials[9] * n < 10 ** n)
    return factorials[9] * n

def sum_facts(n):
    return sum(factorials[d] for d in digits(n))

# 123 -> 1 1234 -> 2
def num_half_digits(n):
    return len(list(digits(n))) / 2

def divide():
    def group(iterable):
        return [ (d, list(a)) for d, a in
                    groupby(sorted(iterable), key = lambda x: x[0]) ]
    
    limit = calc_limit()
    half = num_half_digits(limit)
    D = 10 ** half
    lowers = group((sum_facts(n) - n, n) for n in xrange(D))
    uppers = group((n * D - sum_facts(n), n * D) for n in xrange(limit / D + 1))
    return lowers, uppers

def merge(a, b):
    k, l = 0, 0
    m, n = a[k][0], b[l][0]
    while True:
        if m == n:
            u, v = a[k][1], b[l][1]
            yield sum(n for _, n in u) * len(v) + sum(n for _, n in v) * len(u)
            k, l = k + 1, l + 1
            if k == len(a) or l == len(b):
                break
            m, n = a[k][0], b[l][0]
        elif m < n:
            k += 1
            if k == len(a):
                break
            m = a[k][0]
        else:
            l += 1
            if l == len(b):
                break
            n = b[l][0]

t0 = time.clock()
factorials = [ factorial(d) for d in xrange(10) ]
lowers, uppers = divide()
print sum(merge(lowers, uppers)) - 1
print time.clock() - t0