Groovyで切符問題を解いてみた

id:nidouchiさんのところ(http://d.hatena.ne.jp/nidouchi/20090904/p1)にて切符問題というものが取り上げられていたので、私も解いてみた。

いくつかの正の整数と加算・減算・乗算 の3つの演算子（そして、括弧）を使って、ある別の正の整数を生成する方法を探し出すプログラムを書け。
例えば。{2,5,6,8}から10を生成する方法は、例えば (2+8)*(6-5) があるので、これを出力すればよい。
なお：
・解がない場合は、その旨を出力すること
・解が複数ある場合でも、ひとつだけ出力すればよい
・オーバーフローは考慮しなくてもよい
・不正な入力（負の数がある、など）への対処は不要
・括弧は無駄にたくさんついていてもよい。
・ヒント：再帰

切符問題 - nidoの雑記

ということなんですが、以下のような感じで解いています。

• 解が複数ある場合は全部出す
• 無駄な括弧は省く
• 効率は二の次
• あとは上の注意点を守る

(動作確認: Groovy Version: 1.7.2 JVM: 1.6.0_20)

ソース

実行結果

(((6 - 5) * 8) + 2) = (6 - 5) * 8 + 2 = 10
(((6 - 5) * 2) + 8) = (6 - 5) * 2 + 8 = 10
(((5 - 2) * 6) - 8) = (5 - 2) * 6 - 8 = 10