小町算

小町算を解くプログラム。とりあえず簡単に演算子は＋−のみ。

# komachi1.rb
# ops:演算子の配列
# ops[n]...数値nの前に付く演算子  ops[0]は未使用
# -1 : [-]
#  0 : [なし]（次の数字と続ける）
#  1 : [+]
ops = Array.new(10){-1}
loop do
  str = ''
  r = t = 0
  s = 1
  1.upto(9) do |n|
    case ops[n]
    when -1, 1
      r += s * t
      t = n
      s = ops[n]
      str += (s == 1)? '+' : '-'
    when 0
      t = t * 10 + n
    end
    str += n.to_s
  end
  r += s * t
  puts '%s = %d' % [str,r] if r == 100
  # 次の演算子配列へ
  9.downto(1) do |i|
    case ops[i]
    when -1, 0
      ops[i] += 1
      break
    when 1
      ops[i] = -1
    end
  end
  break if ops[1] == 1 # 1の前に付くのは[-]か[なし]の2通り
end

実行結果

-1+2-3+4+5+6+78+9 = 100
12-3-4+5-6+7+89 = 100
123-4-5-6-7+8-9 = 100
123-45-67+89 = 100
123+4-5+67-89 = 100
123+45-67+8-9 = 100
12+3-4+5+67+8+9 = 100
12+3+4+5-6-7+89 = 100
1+23-4+56+7+8+9 = 100
1+23-4+5+6+78-9 = 100
1+2+3-4+5+6+78+9 = 100
1+2+34-5+67-8+9 = 100

evalを使ってみる

# komachi2.rb
ops = Array.new(10){-1}
loop do
  str = ''
  1.upto(9) do |n|
    case ops[n]
    when -1
      str += '-'
    when 1
      str += '+'
    end
    str += n.to_s
  end
  r = eval(str)
  puts '%s = %d' % [str,r] if r == 100
  # 次の演算子配列へ
  # 中略
end

それぞれprofileを取ってみると，toplevelで
komachi1.rb ... 71203.00
komachi2.rb ... 51438.00
と，evalバージョンの方が速かった。