Python 覆面式ソルバー
気がついたら前回の更新から四半期が過ぎようとしている。恐ろしいことだ。
IT速報でまた面白そうな問題があった。
複数の文字が同じ数字にマップしないと仮定するなら、そもそも問題の大きさが最大で10!(~360万通り)なので、ちょっと時間をかけていいなら総当たりで解けてしまう。
コードの簡潔さ重視で書くなら例えば以下のようになる。
from string import ascii_letters from itertools import permutations def solve(input_string): bracketed_list = [bracket_letter(c) for c in input_string] bracketed_string = ''.join(bracketed_list) bracketed_string = bracketed_string.replace('=', '==') characters = set(c for c in input_string if (c in ascii_letters)) n1, _, n2, _, n3 = input_string.split() first_characters = [n[0] for n in (n1, n2, n3)] for numbers in permutations(range(10), len(characters)): alpha_dict = dict(zip(characters, numbers)) if any(alpha_dict[c]==0 for c in first_characters): continue output_string = bracketed_string.format(**alpha_dict) if eval(output_string): print(output_string) def bracket_letter(c): if c in ascii_letters: c = '{'+c+'}' return c
言語はPython 3だが、ぱっと見たところPython 2.xでも少なくとも2.5以降ならそのまま走りそうである。range
やprint
が実は微妙に違う挙動なのだが、実行速度に大きく影響を与えるような違いはないし、表示される結果は同じだ。
eval
があるのが少し心配だが、入力された文字列を直接評価しているのではなく、まずすべての英字(ascii_letters)を置換のために{}括弧でくくって、string.format(**dict)
で辞書に含まれている英字⇒数字マッピングで数字に変換しているのでセキュリティ的にも大丈夫なはず。
決して効率のいい方法ではないが、数分以内には結果が出る。
さて、次は効率化について考えていきたい。(続く)