Arantium Maestum

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

Python 覆面式ソルバー

気がついたら前回の更新から四半期が過ぎようとしている。恐ろしいことだ。

IT速報でまた面白そうな問題があった。

blog.livedoor.jp

複数の文字が同じ数字にマップしないと仮定するなら、そもそも問題の大きさが最大で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以降ならそのまま走りそうである。rangeprintが実は微妙に違う挙動なのだが、実行速度に大きく影響を与えるような違いはないし、表示される結果は同じだ。

evalがあるのが少し心配だが、入力された文字列を直接評価しているのではなく、まずすべての英字(ascii_letters)を置換のために{}括弧でくくって、string.format(**dict)で辞書に含まれている英字⇒数字マッピングで数字に変換しているのでセキュリティ的にも大丈夫なはず。

決して効率のいい方法ではないが、数分以内には結果が出る。

さて、次は効率化について考えていきたい。(続く