Subscribed unsubscribe Subscribe Subscribe

Generalized "Make 10 with 4 numbers game" solver

Python

「4つの数字で10を作るゲーム」を一般化した、「与えられたn個の数字の四則演算(追記:および括弧)でNを作るゲーム」の解を一つ求めるコードをPythonで書きました。
ポイントは、Generator機能を再帰して使っていることです。これにより、計算式の生成がかなり簡潔に書け、更にn=100でもあまりメモリを使わずに動くようになっています。

(11/27追記:コードを簡潔に書き直しました。)

provideNumsFromUserFlag, numOfNums, randmaxをいじると色々モードが変えられます。「1から100までの(ランダムな)100個の数字で10を作るゲーム」の解の出力は

[1, 2, 3, 4, 5, 9, 10, 11, 12, 12, 13, 13, 14, 17, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 23, 23, 23, 24, 25, 26, 27, 28, 29, 30, 32, 35, 37, 37, 41, 41, 42, 43, 46, 47, 49, 50, 50, 50, 50, 50, 50, 51, 54, 54, 55, 55, 58, 59, 60, 62, 63, 64, 66, 67, 67, 67, 69, 69, 71, 72, 72, 73, 73, 75, 75, 76, 78, 80, 81, 82, 82, 82, 84, 86, 86, 86, 88, 89, 92, 94, 95, 96, 98, 98, 98, 98, 99, 99, 100, 100]
Calculating...
10 = (((((1-2)-((((3-4)-5)-9)-((10-11)-(((12-12)-(13-(13-14)))-(17-19)))))-(((20-20)-((((20-20)-(((21-(21-(21-21)))-(22-((23-23)-(23-24))))-((25-((26-27)-(28-29)))-30)))-((((32-(35-37))-(37-(41-41)))-(42-(43-46)))-(((((47-(49-50))-((50-50)-50))-(50-50))-(51-54))-54)))-((((55-55)-58)-(((59-((60-62)-63))-(64-(66-67)))-(67-67)))-(69-69))))-((71-72)-(72-73))))-73)-(((((75-75)-(((76-78)-80)-81))-82)-(((((82-82)-(84-86))-((86-86)-(((88-89)-92)-(94-95))))-(((96-98)-98)-(((98-98)/99)-99)))-100))-100))

のようになります。
かなり時間がかかると思っていたのですが、なんと数秒で結果が出たので驚きました。

関数allEquationsFromが式を(ある程度)重複無く生成する心臓部で、PythonのGeneratorを使っています。Generatorの再帰については、
再帰とジェネレータ
yieldのちょっとした理解
を参考にしました。
また、ここで使っている二分木の再帰的な構成方法については、
Enumeration of Binary Trees
をかなり参考にしました。

実行時間について

何度か試したところ、n=100でも5秒程度で解が求まる場合がほとんどでした。n=50では1秒未満で求まりました。
nが大きいと、式中の演算をほぼ全てマイナスに選び、ランダムに括弧付けを行うだけのアルゴリズムでもすぐに10が作れました。
数を多く使うと10は作りやすいそうです。

しかし、ほとんどの数が1であるような場合などは、マイナスだらけになると10にならないため、探索時に+を優先的に使って式を作らないとなかなか10になる式にたどり着かないので、数の組み合わせによっては工夫が必要です。(1が10個ある場合など。)

少し気になったので詳しく調べてみると(なぜやってしまったのか…)、数の数n=50, 目的の数N=50の場合について、演算子をマイナスだけに限定し、式の値を69937サンプル取った時の分布が下図になります。
f:id:woodrush:20141125061930p:plain
平均がほぼゼロ(-9.5949)の、正規分布に近いような分布になっています。引き算だけで式を作っているので、1から50までの50個の数を選んだとき、-25から25までの25個の数の和を得ているような感じになり、分布が正規分布に近づいているのだと思います。

ちなみに最初は木を作りやすそう&直接式を評価できる&Lisp練習しようという理由でLispで書いていたのですが、loop、let、progn、returnなどを多用していてあまりそれっぽくなりませんでした。
Lisp版
n=4ならば十分な時間で全数探索できるプログラムになっています。