実に久しぶりのエントリ。
テンパズルとは、1桁の数4つと加減乗除を組み合わせて10を作る、っていうパズル。「拡張」とついてるのはルールを拡張してるから。すなわち、
- 計算式に使う数字は4個でなくても良い。2個以上なら良いものとする
- 計算式に使う数字は二桁以上でも良い。要するに自然数なら良い
- 計算結果は10でなくても良い
元ネタはこのブログのエントリ。
さらにその元ネタはQuizKnockのYouTubeチャンネルだそうだ。面白いな、これ。
さて、これを解くプログラムを作ってみた。上に挙げたブログでは Ruby で書いているので、Python で書いた。GitHubに上げてある。
実装上の工夫はあるものの基本的なアルゴリズムは元ネタのブログと同じだ。数と加減乗除からなる計算式を木構造として扱って、その値が10になる答えを探索する。答えは複数ある可能性もあるけど、最初に見つかった答えを返す。
今のところ数4つ、合計が10、に決め打ちで「拡張」にはなってない。とはいえ、解けるようには作ったのでプログラムにオプションを追加するだけでいい。
さて、実装上の工夫について書いておこう。
元ネタの Ruby のプログラムでは、ビルトインの Numeric クラスにvalueメソッドを追加しているけど、オープンクラスでない Python ではそういうことはできない。なので、数をラップするLeafクラスにvalueメソッドを定義した。内部では数をFraction（分数）として保持している。
もうひとつは、答えの木構造を、出力のために文字列に変換するところ。足し算・引き算を掛け算・割り算よりも優先するためにカッコが必要になるんだけど、この部分は元ネタのプログラムよりもすっきりと書けてると思う。