Arantium Maestum

プログラミング、囲碁、読書の話題

Python 覆面式ソルバー 続続続

前回からの続き。

てなもんで、再帰的に書いたソルバーに、各段階で次のステップに使える数字を絞るルールを組み入れる仕組みを作っていく。

方式としては、入力された文字列を引数にして評価関数を返す高次関数create_rule(input_string)を作成する。その返り値を再帰関数に引数として渡して

    for num1 in remaining_numbers:

この部分を入れ替える。

とりあえずまずは仕組みを作るだけに留めておく。前回のrecurse関数における以下の部分をルール化してみよう。

    if any(alpha_dict[s[1]]==0 for s in (b1, b2, b3)):
        continue
...
    numbers = [n for n in remaining_numbers 
                    if n != num1]

つまり、先頭の数字は0以外でなければいけないという点と、他の文字にマップされている数字は使えないという点をルールとして組み込む。

def create_rules(input_string):
    num1, operator, num2, _, num3 = input_string.split()
    rule_dict = defaultdict(list)

    # 先頭の文字は1~9の数字にしかマップできない
    for first_character in (n[0] for n in (num1, num2, num3)):
        def not_zero(alpha_dict, value=set(range(1,10))):
            return value
        rule_dict[first_character].append(not_zero)

    def rules(c, alpha_dict, rule_dict=rule_dict):
        if c in rule_dict:
            possible_sets = [rule(alpha_dict) 
                                for rule in rule_dict[c]]
        else:
            possible_sets = []

        # すでにalpha_dictに使われている数字は除外
        output_set = set(n for n in range(10)
                            if n not in alpha_dict.values())
        for s in possible_sets:
            output_set = output_set.intersection(s)

        return output_set

    return rules

create_rulesという高次関数がrulesという関数を返す。rulesは引数として文字cと未完成の文字:数字マッピングalpha_dictを受け入れて、create_rulesで作られた評価関数を使ってcにマップ可能な数字をセットとして返す。今回は評価関数は非常に簡単なもので、引数であるalpha_dictの値に関係なく1~9のセットを返す。

このcreate_rules関数があることで、recurse関数を簡略化できる。まず、remaining_numbersという引数を省略できる(この変更はおおもとのsolve関数でrecurse関数が呼ばれる部分にも影響する 。さらに次のステップでのremaining_numbersを算出する部分を削除できる。そして先頭の文字が0かどうかのチェックもいらない。

これらを踏まえると全体的に以下のようになる。

from operator import add, sub
from string import ascii_letters
from collections import defaultdict

def solve(input_string):
    rules = create_rules(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()

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


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


def recurse(i, 
            characters, alpha_dict, 
            b1, b2, b3, op, rules):
    c = characters[i]
    possible_numbers = rules(c, alpha_dict)
    for num1 in possible_numbers:
        alpha_dict[c] = num1
        if i == len(characters)-1:
            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:
            yield from recurse(i+1,
                    characters, alpha_dict, 
                    b1, b2, b3, op, rules)
    alpha_dict[c] = None


def create_rules(input_string):
    num1, operator, num2, _, num3 = input_string.split()
    rule_dict = defaultdict(list)

    for first_character in (n[0] for n in (num1, num2, num3)):
        def not_zero(alpha_dict, value=set(range(1,10))):
            return value
        rule_dict[first_character].append(not_zero)

    def rules(c, alpha_dict, rule_dict=rule_dict):
        if c in rule_dict:
            possible_sets = [rule(alpha_dict) 
                                for rule in rule_dict[c]]
        else:
            possible_sets = []

        output_set = set(n for n in range(10)
                            if n not in alpha_dict.values())
        for s in possible_sets:
            output_set = output_set.intersection(s)

        return output_set

    return rules

実行速度はちょっと落ちて12秒、30秒あたりになる。以前と同じルールしか使っていないので、システムが少々煩雑になった分遅れが出てくるようだ。が、まあこれくらいなら許容範囲である。

それではついにお待ちかね、評価するマッピングを大幅に刈り込んでいくためのルールを実装していく。(続く