開発未経験者が覆面算ソルバーを作ったはなし

4831 ワード
HTML CSS Python Flask Python テキストリンク

はじめに

　こんにちは。0kayu806059です。
　この記事がQiita初投稿となります。
　タイトルにもある通り、この度私は、覆面算ソルバーを作りました。
　とても簡単なWebアプリですが、完成までに至った経緯をここに残したいと思います。

そもそも覆面算とは？

　覆面算とは、数字の一部（または全部）がアルファベットに置き換えられた数式が与えられるので、各アルファベットに当てはまる数字を見つけて数式が成り立つようにするパズルです。
　例えば、
ABC + BAC = CACA
といった数式が与えられます。この場合A、B、Cにどんな数字が入るかを考えるといった感じです。中学受験とかで見るやつですね。ちなみに答えは、A = 2, B = 9, C = 1 となります。実際に数を代入してみると、
291 + 921 = 1212 となり、確かに成り立っていることがわかります。
　基本的なルールとしては3つあります。
1. 各文字には0〜9までの1つの数字が入ります。
2. 同じ数字が別の文字にはいうことはありません。（つまり、A = 1, B = 1というのはダメ）
3. 各項の先頭にある文字に'0'が入ることはありません。（先程の例で言うと、A、B、Cはいずれも項の先頭にあるため'0'は入りません。）

作ろうと思ったきっかけ

　私は普段、競技プログラミングをしています。レートを上げるためにプログラミングの勉強をしているうちに、せっかくだから何か作ってみよう！と思ったことがきっかけです。
　何を作ろうかと考えたときに、そのとき読んでいたアルゴリズムの本に、虫食い算（覆面算のアルファベットが全て□に置き換わったもの）はDFSで作れると言うようなことが書いてありました。それを読んで、「虫食い算の作り方はわかった。じゃあ覆面算は作れるだろうか？」と思ったので作ってみました。

苦労した点

　苦労したところは2つあります。覆面算ソルバーのアルゴリズムとWebアプリにする際の答えの出力方法です。

　1.　覆面算ソルバーのアルゴリズム
　はじめに考えたのは、虫食い算と同様にDFSで解くことです。しかし、上手い実装方法が思い浮かばずにかなり悩みました。そこで、ルールを見返してみると、各文字には1つの数字しか入らず、違う文字に同じ数が入ることはないので、登場する文字の種類は高々10種類であることに気づきました。そしたら答えの候補は高々10!（= 3628800）個なので答えは数秒で求められることになります。実際に書いたコードがこれです。

def solver(s):
    s = s.replace(" ", "")
    left_terms = []
    now = 0
    alphabet = []
    equal = 0
    right_term = ""
    operation = ['+', '-', 'x', '/']
    ope_num = [0]
    ZeroNine = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']

    # 式に含まれる項と登場する文字をリスト化
    for i in range(len(s)):
        if s[i] not in alphabet and s[i] not in operation and s[i] != '=' and s[i] not in ZeroNine:
            alphabet.append(s[i])
        if s[i] in operation:
            tmp = s[now:i]
            left_terms.append(tmp)
            now = i + 1
            if s[i] == '+':
                ope_num.append(0)
            elif s[i] == '-':
                ope_num.append(1)
            elif s[i] == 'x':
                ope_num.append(2)
            else:
                ope_num.append(3)
        if s[i] == '=':
            equal = i
            left_terms.append(s[now:equal])
            right_term = s[equal+1:]

    # 登場した文字をソート
    alphabet = sorted(alphabet) 

    number = len(alphabet)
    # ０〜９の中から答えの候補を全探索
    for i in itertools.permutations(ZeroNine, number):
        cur = list(i)
        answer = {}

        # 各文字についての対応表を作る
        for j in range(number):
            answer[alphabet[j]] = cur[j]
        # 対応表に基づき、数式を作る
        ok = 1

        # 左辺の計算
        Leftside, Rightside = 0, 0
        for j in range(len(left_terms)):
            # 数式の復元
            tmp = ""
            for k in left_terms[j]:
                if k in ZeroNine:
                    tmp += k
                else:
                    tmp += answer[k]
            if tmp[0] == '0':
                ok = 0
            else:
                if ope_num[j] == 0:
                    Leftside += int(tmp)
                elif ope_num[j] == 1:
                    Leftside -= int(tmp)
                elif ope_num[j] == 2:
                    Leftside *= int(tmp)
                else:
                    Leftside /= int(tmp)

        # 右辺の計算
        tmp = ""
        for k in right_term:
            if k in ZeroNine:
                tmp += k
            else:
                tmp += answer[k]
        if tmp[0] == '0':
            ok = 0
        Rightside += int(tmp)

        # ok では、最高位が0出ないという条件を満たしているかを確認している
        if ok == 1:
            if Leftside == Rightside:
                res = ""
                for key in answer:
                    res += str(key)
                    res += ": "
                    res += str(answer[key])
                    res += " "
                return res
    return "答えが見つかりませんでした"

　2.　Webアプリにしたときの答えの出力方法
　自分でWebアプリを作った経験がないため、どのようにアプリにするのかとても苦労しました。フレームワークにはFlaskを使いました。Pythonの有名なフレームワークとしてFlaskの他にDjangoがあり、どちらを使うか悩みましたが、小規模な開発にはFlaskを用いることが多いといったことや、今回の自分の開発に、フルスタックフレームワークは必要ないといった理由からFlaskを選びました。
　どう出力するかと言うのはググってなんとか解決しました。ググるの大事ですね〜（自力で解決しようとして1日溶かしました...）自分にはHTMLとCSSの知識が欠けているようです。Webアプリを作っていく上での今後の課題です。

最後に

　実際に動かしてみるとこのようになります。
　ここでは入力として、最初にあげた例を入れています。

　実はこの覆面算ソルバーには欠点があります。括弧がついた式はそのまま計算できないのです。括弧を外してやれば良いのだけなのですが入力する側からすると割と面倒かもしれません。
　今までWebアプリというと、本を写経したり、動画の真似をして作ったりといったことしかなく、自分で考えて作ったことはなかったので、非常に良い経験になりました。読んでいただきありがとうございました。