覆面算

http://www16.atwiki.jp/tokoroten/pages/1211.html を見ていたら僕も書きたくなったので。

MacBookに10分くらい頑張ってもらって、ZERO + ZERO = ZERO から TEN + TEN == TWENTY までの全問題について総当たりをしたのだけども、結局あんまり面白い問題は見つからなかった。

答えのある問題だけ抜粋列挙しておくと:

Q: FOUR + FIVE = NINE
num_answer: 72
Q: FOUR + FOUR = EIGHT
num_answer: 56
Q: TWO + FIVE = SEVEN
num_answer: 36
Q: ONE + FOUR = FIVE
num_answer: 1200
Q: TWO + TWO = FOUR
num_answer: 19
Q: ONE + ONE = TWO
num_answer: 18

以下ソースコード。

# -*- coding: utf-8 -*-

WORDS = """ZERO ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE TEN
ELEVEN TWELVE THIRTEEN FOURTEEN FIFTEEN SIZTEEN SEVENTEEN EIGHTEEN NINETEEN TWENTY""".split()


def compile_word(w):
    "e.g. ZERO => (((Z) * 10 + E) * 10 + R) * 10 + O"
    body = w[0]
    for c in w[1:]:
        body = "(%(body)s) * 10 + %(c)s" % locals()
    return body


def perm(n, result):
    n -= 1
    for i in range(10):
        if i not in result:
            if n > 0:
                for r in perm(n, result + [i]):
                    yield r
                
            else:
                yield result + [i]


def solve(v0, v1, sum_):
    print "Q: %s + %s = %s" % (v0, v1, sum_)
    if len(sum_) > max(len(v0), len(v1)) + 1: return # no answer
    if len(sum_) < max(len(v0), len(v1)): return # no answer

    used_chars = set((v0 + v1 + sum_))
    if len(used_chars) > 10: return # unsolvable

    args = ", ".join(used_chars)
    body = "%s + %s == %s" % (
        compile_word(v0), compile_word(v1), compile_word(sum_))

    prod = eval("lambda %(args)s: %(body)s" % locals())

    _to_str = lambda w: " + ".join("str(%s)" % c for c in w)
    to_str_body = "%s + ' + ' + %s + ' = ' + %s" % (
        _to_str(v0), _to_str(v1), _to_str(sum_))
    to_str_func = eval("lambda %(args)s: %(to_str_body)s" % locals())

    num_answer = 0
    for xs in perm(len(used_chars), []):
        if prod(*xs):
            print to_str_func(*xs)
            num_answer += 1

    if num_answer: print "num_answer:", num_answer


def main():
#    for sum_ in range(10, -1, -1):# real	2m13.308s
    for sum_ in range(20, 10, -1):# real	7m20.159s
        for v0 in range(sum_ / 2 + 1):
            v1 = sum_ - v0
            # 0 <= v0 <= v1 <= N
            solve(WORDS[v0], WORDS[v1], WORDS[sum_])

main()