####きっかけ
通勤の電車の中で次のような広告を見かけました。
四則演算のみを用いて下記の4つの数字で10を作ることはできますか。
1,3,3,7
また、任意の0～9の4つの数字で、上記同様の10を作る問いが与えられたとき、
その解法を出力するプログラムを作ることはできますか。
おおっ、とやる気が出ました。東急電鉄の求人広告らしいです。
電車の中のこの手の広告って小学生向け予備校の難関中学受験問題とかがほとんどじゃないですか。
そのなかでプログラマを狙い撃ちした問題、やったろうじゃないかと考え始めました。
プログラムを作り終わってから調べてみたところ、この手の問題は10パズルとかMake10とか呼ばれる問題のようですね、Qiitaにもいくつも記事がありました（←先に調べろという・・）。そのものズバリの東急線の車内広告というキーワードでも検索できたという。
いろいろみていて、式をevalで解く方法とか目ウロコでした。
####とっかかり
まず思いついたのは、数字の順列を作成し、四則演算子との全組み合わせで力技でやればいいやん！
でした。
次にこれ、演算子だけでなくて計算順がキモだよねと気づきました。
以下、A B C Dを数字、$op_n$を演算子とすると、
素の形で
A $op_1$ B $op_2$ C $op_3$ D
カッコをつけた例は
(A $op_1$ B) $op_2$ C $op_3$ D
(A $op_1$ B $op_2$ C) $op_3$ D
(A $op_1$ (B $op_2$ C)) $op_3$ D
カッコのつけ方いっぱいあるじゃん！ めんどくせえ！！
カッコ処理したくないからどうすれば？ あ、逆ポーランド記法つかえばいいじゃん！
ここまでは比較的すぐに思いついたので、前提条件を整理することにしました。
####前提条件
- すべての数字は1度登場するのみか？
- 同じ演算子の複数登場はOKか？
- 四則演算師はすべて2項演算子であるという前提でよいか？
最初の2個はそもそもYESでないと問題が成立しないのでYESです。
最後のは-が単項演算子として入れていいかどうかですが、とりあえず無視してYESということにしました。
そうすると、登場する演算子は3個になります。
問題について確認したくとも、広告には出題者への連絡先も書いてなかったみたいですしね。
ググると人材募集の連絡先しかなかったという。
そもそも、これは10パズルと呼ばれて広く知られている問題だということを私が知らなかっただけだともいいます。
まあ、それはともかく次は方針を整理します。
####方針
- いまさらだけど楽で簡単なのでpython3だよね。
- 数字の順列を全パターンを作成する。
- 3個の演算子の全組み合わせを作成する。
- 上の要素を逆ポーランド記法の全パターンで計算する。
- 解=10であればOK!とする。
最後のちょっと待った！
計算結果を整数の値と=で比較してはいけないというのは、遥か昔に計算機工学の最初の授業で先生に教わりました。
浮動小数点の丸め誤差ですね。
1 / 3 * 3が0.999999になったりするような。
ちょっとやってみっか。
$python
Python 2.7.14 (default, Jul 1 2020, 16:28:17)
[GCC 8.3.9] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 1 / 3 * 3
0
あ、あれ？ 丸め誤差ってレベルじゃねえぞ？
>>> 1.0 / 3 *3
1
んーデフォでint型とみなされてるのね。ってこれpython2じゃん！
python3で確認したところ1 / 3 * 3はちゃんと1になりました。ものぐさバンザイ！
計算機工学の先生ごめんなさい、この場は計算結果=10でやっちゃいます。
####順列作成
４つの数字のすべての順列を作成する！
4個の数字が入ったリストから、1個づつ取り出して3重のループ回せばいいよね？って直感的に思いつきました。
[A,B,C,D]
1番上のループで1個取り出し、
[B,C,D]
次のループは残りを取り出し、
[C,D]
3個めを取り出すと4個目は自動的に決定
なんか、毎回リストコピーして保持するのダサくね？ それにもっと長いリスト来たらどうするの？
というわけで、再帰で書いたら比較的短くなりました。
#問題文数字リスト
src_nums = ["1", "3", "3", "7"]
#順列ホルダー
nums_holder = [0] * len(src_nums)
#全順列格納用リスト
result_list = []
#順列を作成する
make_permutation(src_nums, 0, len(src_nums), nums_holder, result_list)
def make_permutation(src_list, depth, org_depth, nums_holder, result_list):
"""
数字の順列作成(再帰)
src_list - 問題数字列(呼び元で選択されたものは削除されていく)
depth - 再帰深さ
org_depth - 元文字列の長さ
nums_holder - 順列格納用
result_list - すべての順列を格納するリスト
"""
for idx in range(len(src_list)):
local_list = copy.copy(src_list)
nums_holder[depth] = local_list.pop(idx)
if depth < org_depth - 1:
make_permutation(local_list, depth + 1, org_depth, nums_holder, result_list)
else:
result_list.append([nums_holder[0],nums_holder[1],nums_holder[2],nums_holder[3]])
forループで現在のリストの要素を先頭から順番に取得していき、再帰するごとに深さを+1します。
下の階層で使うようにリストをcopyしているのがキモです。
最後の数を取り出したら、その順列をresult_listに追加するというコードです。
pythonは基本的に参照渡しなので楽ですね。
####演算子の全組み合わせを作成
演算子ですが、加算と乗算以外の演算子は2項が非可換なのでそれを場合分けして演算子6パターンとして処理する考え方もあるみたいですね。演算子の数を増やして、式のパターンを減らす考え方でしょうか。
- A + B
- A * B
- A - B
- B - A
- A / B
- B / A
しかし、私は逆ポーランド全パターンを力技でやる方針なので、演算子は4パターンのみで考えます。
#演算子リスト
op_list = ["+", "-", "*", "/"]
for op1 in op_list:
for op2 in op_list:
for op3 in op_list:
こんな感じですね。
####逆ポーランド記法の全パターンで計算
逆ポーランド記法ってスタックを使ってカッコいらずの計算を実現する方法です（いいかげん）。
ルールは単純で、数値が入力されればスタックに積む、演算子が入力されればスタックから数値を取り出して演算し、結果をスタックに積むです。
今回は2項演算子のみを対象にするので、次の式を例に説明します。
A B $op$
スペースで区切られた単位で処理を分解すると
- Aをスタックに積む
- Bをスタックに積む
- スタックから2つ値を散りだしてA op Bを演算し、結果をスタックに積む、となります。
4つの数字と3つの2項演算子を組み合わせる逆ポーランド記法の演算式は次の4パターンかな、と思います。
左辺が逆ポーランド記法、右辺が通常の式です。
- A B $op_1$ C D $op_2$ $op_3$ = (A $op_1$ B) $op_3$ (C $op_2$ D)
- A B $op_1$ C $op_2$ D $op_3$ = ((A $op_1$ B) $op_2$ C) $op_3$ D
- A B C $op_1$ $op_2$ D $op_3$ = (A $op_2$ (B $op_1$ C)) $op_3$ D
- A B C D $op_1$ $op_2$ $op_3$ = A $op_3$ (B $op_2$ (C $op_1$ D))
今までに求めた数字の順列と演算子の組み合わせをこの4パターンの式に当てはめて計算すればいいじゃん、ということですね。
逆ポーランド演算の呼出部は次のような感じになります。
# A B op1 サンプル
stack.append(A)
stack.append(B)
exec_revpol(op1, stack)
#A B $op_1$ C D $op_2$ $op_3$ 実際の逆ポーランド演算式その１
stack.append(A)
stack.append(B)
exec_revpol(op1, stack)
stack.append(C)
stack.append(D)
exec_revpol(op2, stack)
exec_revpol(op3, stack)
まるっと逆ポーランド記法の式を作ってパースしながら実行してもよいのですが、遅くなりそうなので、電卓的に演算子を処理する関数exec_revpolを作って、式はコードで開くことにしました。
逆ポーランド実行関数は次のようになります。
def exec_revpol(op, work_list):
"""
逆ポーランド演算を実施する
op - 演算子
work_list - 演算の要素と結果を格納するスタック
"""
s2 = work_list.pop()
s1 = work_list.pop()
if (s1 == "∞" or s2 == "∞"):
work_list.append("∞")
return
r2 = float(s2)
r1 = float(s1)
if op == "+":
work_list.append(r1 + r2)
elif op == "-":
work_list.append(r1 - r2)
elif op == "*":
work_list.append(r1 * r2)
elif op == "/":
if (0 == r2):
work_list.append("∞")
else:
work_list.append(r1 / r2)
0除算の∞で草生えますね。NaNとかInfとか分けてもいいのですが、この場合は計算結果が10になるかどうかが重要なので、一度でもゼロ除算が登場したらその式は∞で無効にする、ということにしました。
深く考えないでプログラミングしたのバレバレですね。
あと、float大事です。スタックには数値と文字列が混在することになりますので文字列の場合は数値に変更しなければなりません。数値の場合もスルーしてくれます。便利！
型厳密主義者の人は目を三角にして怒りそうです。
ちなみに、ここでint()なんてやると小数点1桁の丸め誤差が発生します。
冒頭のpython2みたいなことになります。
4パターンの逆ポーランド記法演算式がありますので、それぞれのパターンについて、上で作った数字の順列と演算子の組み合わせを当てはめて演算し、その結果が10になるパターンを探せばOKということになります。
やあ、解けた解けた。
(1 + (7 / 3)) * 3 = 10.0
####さいごに
実際のコードは式の表示や諸々を追加したのでそこそこ長くなりましたので、
githubをご参照ください。
1,3,3,7のパターンを解くプログラムを作ったあと、10になる組み合わせを数えるパズルらしい？
ということを知り適当にmain()に追加しています。
速度を上げるには二項が可換な演算子に着目してパターンを刈り込むべきなのでしょうけど、単純な四則計算なので演算しちゃったほうが速いんじゃね？ という思い込みで放置してます。
数字5個とかになったらもうちょっと考えます（笑）。
それでは、長々とお付き合いいただきありがとうございました。
P.S.
くっ、itertools.permutations()とitertools.product()というものの存在も知りませんでした。