Python 覆面式ソルバー 続続

前回からの続き。

というわけで総当たり形式をやめて、なるべく制約を加えることで評価する文字：数字マッピングの総量を絞ってみる。

具体的には

for numbers in permutations(range(10), len(characters)):

この部分をやめるわけである。じつはこの部分も、

for numbers in product(range(10), repeat=len(characters)):

という真の総当たりよりはよっぽどいいわけだが。文字数^10ではなく文字数!に減っているわけである。

しかし、人間がこの手の問題を解く時に使う規則性などを持ち込めば、文字列!を何分の一にも減らすことができる。例えば演算子が＋か－である縛りなら、三つの数字のうち一つの桁が他の二つより多かった場合、一番上の一桁は1以外ありえない。そのルールがあてはまるケースでは一気に問題の大きさが10分の1になるのである。

まずは、そういったルールを適用できるような形式にコードを書き直してみる。

from string import ascii_letters
from operator import add, sub

def solve(input_string):
    bracket_list = [bracket_letter(c) for c in input_string]
    bracket_string = ''.join(bracket_list)

    num1, operator, num2, _, num3 = input_string.split()
    op = {'+':add, '-':sub}[operator]

    characters = list(set(num1+num2+num3))
    alpha_dict = {c:None for c in characters}

    b1, _, b2, _, b3 = bracket_string.split()

    numbers = list(range(10))

    for alpha_dict in recurse(0, numbers,
            characters, alpha_dict, b1, b2, b3, op):
        print(bracket_string.format(**alpha_dict))


def bracket_letter(c):
    if c in ascii_letters:
        c = '{'+c+'}'
    return c


def recurse(i, remaining_numbers, 
            characters, alpha_dict, b1, b2, b3, op):
    c = characters[i]
    for num1 in remaining_numbers:
        alpha_dict[c] = num1
        last_character_index = len(characters) - 1
        if i == last_character_index:
            if any(alpha_dict[s[1]]==0 for s in (b1, b2, b3)):
                continue
            n1 = int(b1.format(**alpha_dict))
            n2 = int(b2.format(**alpha_dict))
            n3 = int(b3.format(**alpha_dict))
            if op(n1, n2) == n3:
                yield alpha_dict.copy()
        else:
            numbers = [n for n in remaining_numbers 
                            if n != num1]
            yield from recurse(i+1, numbers,
                    characters, alpha_dict, b1, b2, b3, op)
    alpha_dict[c] = None

はい、再帰です。

再帰階層の深さをi、使われていない数字をremaining_numbersという引数で入れて、iが文字数のインデックスの最大値に到達した時点で数式が成り立っているかを評価している（評価方法は以前と全く同じ）。

すこし気の利いたところとしては、ただの再帰ではなく、再帰的ジェネレータ関数になっていて、さらにPython 3の新機能であるyield fromも使っている。これ使うと再帰的関数から結果を逐次報告できてものすごく便利。入れ子状態の関数の一番奥で算出された結果が、上位の関数までyieldされ、それがさらに上にyieldされていって・・・となってrecurse関数の外に出力されていく。

もしこの問題が「すべての文字・数字マップを発見」から「条件を満たすものが一つ以上あるか」に変わった場合、

    for alpha_dict in recurse(0, numbers,
            characters, alpha_dict, b1, b2, b3, op):
        print(bracket_string.format(**alpha_dict))

これを

    try:
        alpha_dict = next(recurse(0, numbers,
            characters, alpha_dict, b1, b2, b3, op))
        print(bracket_string.format(**alpha_dict))
    except StopIteration:
        print("None found")        

これで条件に合致するマッピングが一個見つかった時点で実行が止まる。

さらに、時間を測ってみたところ、関数内でprintするのとyieldするのとで時間差はほぼなかった。どうなってんだこれ、と言いたくもなるがとりあえずPython万歳。

大体10秒と24秒前後で、再帰を使わないコードより少し早いくらい。

ちょっと不満なのは不変の引数が多いこと。create_recurse関数を作って不変の引数は全部デフォルトにしてしまおうかとも思ったが、やってみたらさらにコードがややこしくなったのでやめた。引数をさらに増やしたくなかったのでfirst_charactersリストを作らず

if any(alpha_dict[s[1]]==0 for s in (b1, b2, b3)):

こういう風に算出しているのもうれしくない。まあここはルールに組み込んでいけば現状よりはすっきりするので気にしなくてもいいかも。

ここから

    for num1 in remaining_numbers:

この部分にルールを組み込んでいく。（続く）