Project Euler 112

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

増加数と減少数を昇順に生成するのは簡単です。これを合成して非バウンド数を昇順に生成します。それと自然数を同時に生成すると、例えば90%のとき、

…  2176  2177  2178  2179  2180 …
… 21100 21110 21111 22000 22100 …

上が非バウンド数の数、下が全体の数となっています。2179のところより1小さい数が2178と21999で、10倍以上になっているので、こことその前の間に最初に10倍になるところがあります。

from itertools import *

def gen_increasing():
    def gen_inc(m, d0):
        if m == 0:
            yield 0
        else:
            for d in xrange(d0, 10):
                for n in gen_inc(m - 1, d):
                    yield d * 10 ** (m - 1) + n
    
    for m in count(1):
        for n in gen_inc(m, 1):
            yield n
    
def gen_decreasing():
    def gen_dec(m, d0 = -1):
        if m == 0:
            yield 0
        else:
            min_d = 1 if d0 == -1 else 0
            max_d = 9 if d0 == -1 else d0
            for d in xrange(min_d, max_d + 1):
                for n in gen_dec(m - 1, d):
                    yield d * 10 ** (m - 1) + n
    
    for m in count(1):
        for n in gen_dec(m):
            yield n

def gen_not_bouncy():
    g_inc = gen_increasing()
    g_dec = gen_decreasing()
    a = g_inc.next()
    b = g_dec.next()
    while True:
        if a == b:
            yield a
            a = g_inc.next()
            b = g_dec.next()
        elif a < b:
            yield a
            a = g_inc.next()
        else:
            yield b
            b = g_dec.next()

N = 100
print next(q for p, q in ((num_all - 1, (num_not_bouncy - 1) * N)
    for num_not_bouncy, num_all in izip(count(1), gen_not_bouncy()))
    if p > 0 and p >= q)