Python / 数字4つで10を作れ

「重複ありの4つの数と、四則演算(×÷＋−)を組み合わせて、答えが10になるような計算式を作れ」 というパズルに挑戦してみました。

切符パズルやmake10(メイクテン), 10puzzle(テンパズル)などの名前があるそうで、 GoogleのNexus7のコマーシャルに登場して、よく知られている様です。

条件として

• 単一の負符号はなし

でやります。

Python3.4で挑戦

$ ./make10.py
# Enter the 4 numbers
>>> 1
>>> 1
>>> 5
>>> 8
# 1 (8 ÷ (1 - (1 ÷ 5))) == 10

小数にも対応可能

$ ./make10.py
# Enter the 4 numbers
>>> 1
>>> 1.2
>>> 2.3
>>> 4
# 1 (4 × ((6/5 + 23/10) - 1)) == 10

10以外も作れます

$ ./make10.py -m 99
# Enter the 4 numbers
>>> 9
>>> 9
>>> 11
>>> 2
# 1 ((11 × (9 + 9)) ÷ 2) == 99
# 2 (11 × ((2 × 9) - 9)) == 99

解説

ざっと次のようなことをやっています。

割り算で誤差が出ては困るので、数字は全て有理数( fractions.Fraction )で処理しています。

式は内部的に三つ組( Triple )で表現しました。 演算子は Python3.4 で導入された enum を使用。

入力された4つの数字を使って、 鏡像, 回転を除いた数字の配置パターンと、 3つの演算子の重複する組み合わせから全ての式のパターンを作成。 これには、itertools.product, itertools.combination を使用しています。 この時、ゼロ割りがある組み合せを事前に除去する工夫をいれてあります。

手強かったのは、式の同一判定です。 式を展開して、項の大小と演算子によって並べ替え、同一形を除外しています。 この部分のデバッグには、Pythonの doctest と unittest が大変有効でした。

こうして生成した三つ組のリストを評価して、10になるものを収集しています。

余談

print ではなく sys.stdout.write を使用しているのは、 Cython を使ってC言語に変換してみたときの名残です。

make10.py