四則演算クイズとその解答ジェネレータ

8月23日の日記に書いたスレッドに新たなお題が出てました。

有名な四則演算とカッコで１０を作る問題です。
二つの数を組み合わせて二桁の数にしたり、累乗、階乗は反則ですよ。
順番を変えるのはＯＫです。
例：１，２，３，３
解答例：（３−１）×（２＋３）
レベル１：
　９，９，９，９
レベル２：
　１，１，９，９
レベル３：
　１，１，５，８

レベル３が解けなかったので、腹いせに自動解答スクリプトを組んでみましたw

四則演算クイズ解答ジェネレータ

基本的にはブルートフォース（総当り）方式ですが、足し算、掛け算の交換法則(a+b=b+a)と、0除算のケースだけ枝狩りして計算量を減らしてあります。足し算、掛け算の交換法則の枝狩りは重要で、最低限これをやらないとブラウザ上のJavaScriptでは実行に耐えないです。結合法則(a+(b+c)=(a+b)+c)とかも盛り込めばもっと速くなると思います。

ソース

主な処理部分の以下のとおり。他はHTMLソースをみてちょ。

// require 'prototype.js'
OPERATOR = ['+','-','*','/'];
BOpe = Class.create();
BOpe.prototype = {
  initialize : function(ope, a, b) {
    if(!OPERATOR.include(ope)) {
      throw new Error('Illegal Operator!');
    }
    this.ope = ope;
    this.a   = a;
    this.b   = b;
    this.toNumber();
  },
  toNumber : function() {
    return eval(this.toString());
  },
  toString : function() {
    var exp = this.a + " " + this.ope + " " + this.b ;
    if(this.ope != '*') {
      exp = "(" + exp + ")";
    }
    return exp;
  }
};

function compute(exp, ans) {
  var size = exp.length;
  if (size == 1) {
    if (exp[0] == 10 || exp[0].toNumber() == 10) {
      ans.push(exp[0]);
    }
  } else {
    for(var i=0;i<size;i++) {
      for(var j=0;j<size-1;j++) {
        compute_next(exp, i, j, ans)
      }
    }
  }
  return ans;
}

function compute_next(exp, i, j, ans) {
  j = (i <= j) ? j+1 : j;
  var a, b;
  var idx=0;
  var new_exp = exp.reject(function(it) {
    switch(idx) {
      case i: 
        idx++;
        a = it; return true;
      case j:
        idx++;
        b = it; return true;
    }
    idx++;
    return false;
  });
  var bnum = (b  instanceof BOpe)? b.toNumber() : b; 
  var size = new_exp.length;
  if(exp.length != size+2) {
    throw new Error(exp + " " + i+" "+j+" "+size + " "+(exp.length - size));
  }
  OPERATOR.each(function(ope) {
    if(j<i && (ope == '+' || ope == '*')) return;
    if(j<i && (a == b)) return;
    if(bnum == 0 && ope == '/') return;
    new_exp[size] = new BOpe(ope, a, b);
    compute(new_exp, ans);
  });
  return ans;
}

Array.prototype.sortAndUniq = function() {
  if(this.length==0) return this;
  this.sort();
  var ar = [];
  var prev = this[0];
  ar[0] = prev;
  for(var i=1,n=this.length;i<n;i++) {
    if(prev != this[i]) {
      prev = this[i];
      ar.push(prev);
    }
  }
  return ar;
};

function main(num) {
  ans = compute(num, []).map(function(a){return a.toString()});
  ans = ans.sortAndUniq();
  return ans;
}

Ruby版

ちなみにもとはRubyで書いてからJavaScriptに移植しました。
Ruby版は以下。

#! ruby
require 'rational.rb'

OPERATOR = ['+','-','*','/'];

class BOpe
  attr_reader :a, :b, :ope
  def initialize(ope, a, b)
    raize RuntimeError.new('Illegal Operator!') unless OPERATOR.include?(ope)
    @ope = ope
    @a   = a
    @b   = b
    to_r
  end
  def to_r
    ai = a.to_r
    bi = b.to_r
    case @ope
      when '+'
        ai + bi
      when '-'
        ai - bi
      when '*'
        ai * bi
      when '/'
        ai / bi
      else 
        raize RuntimeError.new
    end
  end
  def to_s
    # "(#{ope} #{a} #{b})"
    case @ope
      when '*'
       "#{a} #{ope} #{b}"
      else
       "(#{a} #{ope} #{b})"
    end
  end
  def inspect
    "BOpe(#{to_s})"
  end
  alias_method :to_i, :to_r
end

def compute(exp, ans)
  size = exp.size
  if size == 1
    if exp[0].to_r == 10
      ans << exp[0] 
    end
  else
    size.times do |i|
      (size-1).times do |j|
        compute_next(exp, i, j, ans)
      end
    end
  end
  return ans
end

def compute_next(exp, i, j, ans)
  new_exp = exp.clone
  a = new_exp.delete_at(i)
  b = new_exp.delete_at(j)
  size = new_exp.size
  OPERATOR.each do |ope|
    unless ((j<i && (ope == '+' || ope == '*')) || (b.to_i == 0 && ope == '/'))
      new_exp[size] = BOpe.new(ope, a, b)
      compute(new_exp, ans) 
      #new_exp.pop
    end
  end
  return ans
end

def main(num)
  ans = compute(num, []).map{|a|a.to_s}.uniq!
  puts ans
end

main( ARGV.empty? ? [1, 2, 3, 4] : ARGV.map{|v|v.to_i})