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秒あたりになる。以前と同じルールしか使っていないので、システムが少々煩雑になった分遅れが出てくるようだ。が、まあこれくらいなら許容範囲である。