基礎から始める覆面算

scala

Scala の for 式で覆面算を解いているエントリを見つけた人が Haskell と Groovy で解きながらリスト内包表記について考えていた。

このようなエントリを見かけると、いつも面白いなーと感心するけど、どうも私は実戦で使いこなせていない。おそらくは、パフォーマンスと柔軟性に欠けるからだと思う。例えば、覆面算の問題パターンを変えると List comprehension を使えないんじゃないとか、パフォーマンスはバックトラックに比べてどうなるのとか。

もうちょっと詳しく考えるため、実際にコードを書いてみた。

まずは、元ネタと同じように素直に総当りをしてみる。

確かに scala の for式 は便利だなと感じる反面、実行時間は5秒も掛かっている。遅い、遅すぎる。

そこで、for式の範囲内で枝刈りをしてみることにした。

枝刈りのアイディアは、下位から順番に数字を当てはめていき、筆算が成立しなくなった時点で其の当てはめを打ち切るもの。

実行時間は20ms未満となった。なるほど、この程度の問題であれば、for式の範疇でも上手く枝刈りが出来るのか。

次は覆面算の問題を引数で与えられるように一般化してみる。枝刈りの方針については、今までと全く同じだが、任意の数の筆算を許可しようと思うと、構造が全く変わってしまった。

もはや、for式は使えない。実際、私は for式を諦めて再帰で書いた。このあたりをスマートに書きたいのだが、うまい手はないものだろうか？

ベンチマーク結果一覧。各メソッドとも5回実行、毎回の所要時間を System.nanotime()で計測。

trial12345
method #167447234006797389219678783148966217006436632244455
method #21823689518029371174583371730269417080834
method #3120678891119130650118630953119162734118002919
method #47930882179116997790931048018192578304648
method #54062666940049150405003804107312040473074

完全に自分メモエントリ OTL