小町算 in JavaScript DouKaku?

古典的なパズルである小町算を解くプログラムを作成してください。

小町算とは：

1□2□3□4□5□6□7□8□9＝100

四角の中に、空白、＋、－、×、÷のいずれかを一つ入れ、等式が成り立つようにするパズルです。

解答例：

1－2－3＋4×56÷7＋8×9＝100

1＋234×5÷6－7－89＝100

参考：　http://ja.wikipedia.org/wiki/%E5%B0%8F%E7%94%BA%E7%AE%97

evalやそれに類するものを使うか否かは自由です。
割り算の際には小数点以下の切捨てが起こらないのが望ましいです。(必須ではない)
- 切捨てが起こる場合の解答例：1÷2÷3＋4＋5÷6＋7＋89＝100
余裕があれば括弧を含むようにしてもいいかもしれません。

手元で20数行ほどのPythonスクリプトを書いてみたところ、101個の解答が得られました。

#4725 を参考にしました。printはRhinoのprintで。
重いので、ブラウザでは動かさないように。

function komachi() {
  var list = Array.prototype.slice.apply(arguments, [0]);
  var right = list.pop();
  var operator = ["", "+", "-", "*", "/"];
  var n = Math.pow(operator.length,list.length-1);

  for(var i=0; i<n; i++) {
    var exp = [list[0]];
    var o = (n+i).toString(5);
    for(var j=1, ii=i; j<list.length; j++) {
      exp.push(operator[o.slice(j,j+1)]);
      exp.push(list[j]);
      ii = Math.floor(i/5);
    }
    if(eval(exp.join("")) == right) print(exp.join("") + '=' + right);
  }
}
print("begin");
komachi(1,2,3,4,5,6,7,8,9,100);
print("end");

evalとreplaceの合わせ技。cscriptで26秒，Rhinoで17秒。

function doukaku104(exp, ops){
  var d = new Date, x = /□/g, f = function(t){ t = ops[i % o], i = i / o | 0; return t };
  for(var R = [], r = 0, o = ops.length, n = Math.pow(o, exp.match(x).length), i, e; i = n--;)
    if(eval(e = exp.replace(x, f))) R[r++] = e;
  return R[r] = R.length +' results / '+ (new Date - d) +'[ms]', R.join('\n');
}

(typeof print != 'undefined' ? print : function($){ WSH.echo($) })
(doukaku104('1□2□3□4□5□6□7□8□9==100', ['', '+', '-', '*', '/']));

DouKaku?

小町算

Posted feedbacks - JavaScript

Index

Feed

Other

Link

Pathtraq