小町算 in Ruby 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個の解答が得られました。

枝狩り一切無し。効率悪いと思ふ。

require "mathn"
(5**8).times do |i|
  s=("2".."9").inject("1") do |r,e|
    r+=["","+","-","*","/"][i%5]+e;i/=5;r
  end
  puts s if eval(s)==100
end

演算子配列の重複順列と数字とを`zip'を利用して交互に配置して`eval'で評価しました. 実行時間はP4 2.4GHzで3分間程度.

module Enumerable
  def rperm(n=size, out=[], &block) #重複順列生成
    n <= 0 ? (yield out) : each{|x| rperm(n-1, [x,*out], &block)}
  end
end
def komachi(n=9)
  soln = []
  seq = (1..n-1).to_a
  ['+', '-', '*', '/', ''].rperm(n-1){|opr|
    eqn = "#{seq.zip(opr).to_a.join}#{n}"
    eqn.gsub!(/\/(\d+)/){"\/#{$1}.0"} #floatとして計算させるため
    soln << eqn if eval(eqn) == 100}
  soln
end

def komachi(n = 2, e = "1")
  if n == 10
    p e if eval(e.gsub(' ','.0')) == 100
  else
    "+-*/".split("").each{|i|
      komachi(n + 1, e + " " + i + n.to_s)
    }
    komachi(n + 1, e + n.to_s)
  end
end

komachi

DouKaku?

小町算

Posted feedbacks - Ruby

Index

Feed

Other

Link

Pathtraq