【Java】小町算を解いてみた
【結論】
- 小町算をプログラムで解くには、全パターン試すしかない。
eval()は計算式を文字列で渡せば、演算子の優先順位を考慮して求めた答えを返してくれるメソッド。- JavaからJavaScriptのメソッドを呼ぶことができる。
- 小町算のパターン網羅はN進変換で実装できる。
【目次】
小町算とは？
小町算（こまちざん）は数の遊びである数学パズルの一種。1□2□3□4□5□6□7□8□9 = 100 という数式の□の中に、＋,－,×,÷,空白 のいずれかを一つずつ入れて正しい数式を完成させるというものである。
引用：ウィキペディア 小町算
アプローチ
アプローチといっても、1〜9の間の計8箇所に「＋,－,×,÷,空白」の5種類を代入してできる全パターンを計算して、合計が100の式を出力するだけです。
「＋,－,×,÷,空白」のパターン網羅は、1つのマスに5種類入り、計8マスあるので、0から390,624(5の8乗 - 1)の10進数を5進数に変換して求めることにします。
以上です。
Javaでの実装
式の計算
自力で計算すると、演算子の優先順位を判定処理の実装が面倒です。
1*2+3=5 1+2*3=7
JavaScriptには、数式の文字列を渡すと計算してくれるeval()というメソッドがあります。
同じメソッドがJavaにもないか調べてみると、ScriptEngineクラスを使えばJavaからJavaScriptのメソッドを実行し結果をObjectクラスとして受け取れるようです。
ScriptEngineManager manager = new ScriptEngineManager(); ScriptEngine engine = manager.getEngineByName("js"); Object obj = engine.eval("4*5");
今回使用するeval()は数値を返してくれるので、次のようにIntegerかDoubleでキャストすることで数値として扱えます。
double anser = (obj instanceof Integer) ? ((Integer)obj) : ((Double)obj);
10進数から5進数への変換
数値をN進数の文字列に変換する処理は、Java標準で用意されています。
//10進からN進数への変換 final int dec = 6; final int n = 5; final String num = Integer.toString(dec, n); System.out.println(num); /* [実行結果] 11 */
因みに、他の2,8,10,16,32,N進数の相互変換をJavaで行う方法は、以下の記事が綺麗にまとまっていました。
完成ソース
作成したソースは以下になります。
実行結果
timeで計測してみると20分以上かかりました。
JavaScriptを呼んでいる処理がボトルネックになっていると思われます。
$ time java Komachizan # 86通りの計算式を出力 real 20m59.220s user 22m25.774s sys 0m32.329s
参考情報
さいごに
JavaScriptはJavaの人気に乗っかったScript言語という認識だったのですが、いつの間にかJavaを追い越してしまったんですね。
と、JavaからJavaScriptのeval()を呼ぶ処理を実装していて思いました。
