数列の四則演算：「プログラマ脳を鍛える数学パズル」Q02の答え

問題

数字を文字列として表し、各桁の間に四則演算の演算子を入れることを考えます。（演算子は入れても入れなくても構いません。）

例）
1234 → 1 + 2 * 3 - 4 ＝ 3
9876 → 9 * 87 + 6 ＝ 789

でき上がった式を計算した結果、元の数の桁を逆から並べた数字と同じになるものを求めてください。
（式の計算は数学の順序で行います。※乗除が先、加減は後）

元ネタ：
第10回「今週のアルゴリズム：数列の四則演算」正解者発表｜CodeIQ MAGAZINE

わたしの考え方

回文を判定する関数を作る
4桁の数字のそれぞれの間に四則演算記号をいれる組み合わせを考える。
四則＋何も入れないパターンで5通り。数字の間が3ヶ所なので5³ = 125通りだが、全く何も入れないパターン（元の数字のまま）を除くと124通りある計算。

と、ここまでは考えてみたが、四則演算記号を挿入して計算結果を出す方法が考えられなかったのでちょっとだけカンニング。

evalという組み込み関数を使えと言うアドバイスがあったので取り入れてプログラムを書いた。

わたしのオリジナル解答

def arepalinrome(x, y):
        return str(x) == str(y)[::-1]

op = ['+', '-', '*', '/','']
for num in range(1000,9999):
    for i in op:
        for j in op:
            for k in op:
                the_answer = eval(str(num)[0] + i + str(num)[1] + j +str(num)[2] + k + str(num)[3])
                if arepalinrome(num, the_answer):
                    print (str(num)[0] + i + str(num)[1] + j +str(num)[2] + k + str(num)[3] + "=" + str(the_answer))

ループを深く掘り下げるコードはなかなか難しい。

だが、実はこのコードはエラーが発生して解答が出ない。0で割ってしまうのと、「08」のような数字が生じてエラーが出るようだ。

模範解答のミソ

模範解答はJavaScriptだった。
evalという関数を使っている。
入れ子構造のループで四則演算記号を挿入している。
演算子が少なくとも一つは入るように、式の文字数が5文字以上になるように条件付けしている。
じつは「*」以外を一度でも使うと4桁の数字にならないので、'+', '-', '/'は不要。
JavaScript以外の言語では、0での除算および0が頭につく数字を除外する必要がある。

修正されたわたしの解答

def arepalinrome(x, y):
        return str(x) == str(y)[::-1]

op = ['*','']
for num in range(1000,9999):
    if "0" in str(num):
        continue
    for i in op:
        for j in op:
            for k in op:
                val = str(num)[0] + i + str(num)[1] + j +str(num)[2] + k + str(num)[3]
                if len(val) > 4:
                    if arepalinrome(num, eval(val)):
                        print (val + "=" + str(eval(val)))

"*"と""のみを挿入するようにした（op = ['*','']）。これで組み合わせの数としては5³通りから2³通りに減るので処理速度は圧倒的に向上する。
0絡みの除外をうまくやる方法が思いつかなかったので、いっそのこと0を含む数字は全てスキップするようなプログラムにした（if "0" in str(num): continue）。
少なくとも一つは"*"が入るようにした（if len(val) > 4:）。