【Ruby】【アルゴリズム】10パズルを解く。ファイナルアンサー。回答全部入り。

振り返り。テンパズルとは。

1から9までの、1桁の数字がかかれたカードが4枚ある。
この数字をそれぞれ1回ずつ使い、10になるように計算する。

あれです。
駅の切符とか、ナンバープレートとかで暇つぶしにやるあれ。

方法

１．計算順序を考えるのは大変なので、逆ポーランド記法でパターンを列挙する
　⇒この記事でやりました
２．逆ポーランド記法を計算するメソッドを作る
　⇒この記事でやりました
３．4つの数の組み合わせを列挙するメソッドを作る
　⇒この記事でやりました

ここまできたらあとは計算するだけなので、先が見えています。

ポイント

0で割り算するとinfinityとなり、to_iメソッドを呼び出すとエラーになります。
0で割り算するときは答えが0になると定義しました。

コード

class Calc
  def self.make_expression(str)
    @@data = str.split("")
    @@operatars = ["+","-","*","/"]
    _make_rpn([], [], [0,0,0,0], 0, 0)
  end
  def self._make_rpn(result, candidate, is_uesd, num_count, ope_count)
    return result << candidate.join('') if num_count+ope_count == 7
    return if  num_count+ope_count > 7
    if num_count - ope_count >=2
      @@operatars.each do |ope|
        tmp = candidate.dup
        tmp << ope
        self._make_rpn(result, tmp, is_uesd, num_count, ope_count + 1)
      end
    end
    if num_count < 4
      is_uesd.each_with_index do |isused, idx|
        if isused == 0
          tmp = is_uesd.dup
          tmp2 = candidate.dup
          tmp[idx] = 1
          tmp2 << @@data[idx]
          _make_rpn(result, tmp2, tmp, num_count + 1, ope_count)
        end
      end
    end
    result
  end
  def self.exe(str)
    num_stack = []
    datas = str.split("")
    datas.each do |data|
      if data =~ /\d/
        num_stack << data 
      else
        a = num_stack.pop
        b = num_stack.pop
        tmp = _calc(b, a, data) 
        if tmp
          num_stack << tmp 
        else
          return "0"
        end
      end
    end
      raise "argument is not correct" if num_stack.length != 1
      num_stack[0]
  end
  def self._calc(num1, num2, operator)
    raise "argument is not correct" if num1.nil? || num2.nil?
    a = num1.to_f ; b = num2.to_f
    return a + b if operator == "+"
    return a - b if operator == "-"
    return a * b if operator == "*"
    if operator == "/"
      return a / b if b !=0
      return false
    end
  end
end

candidates =  Calc.make_expression("1234")
answers = []
candidates.each do |cand|
  answers << cand if Calc.exe(cand).to_i == 10
end
p "there are #{answers.length} answers"
p answers

■実行結果

"there are 48 answers"
["99*9+9/", "99*9+9/", "999*+9/", "999*+9/", "99*9+9/", "99*9+9

この答えの数から、難易度の高い組み合わせを見つけられそうですね。
「最も難しいテンパズル」。
面白そうだけどそこまで興味がないので見送ります。
と思ったけど、ついでなので全回答を作りました。

https://gist.github.com/sekaiya/6569856/

これで切符をニヤニヤみるような彼氏が出来ても、
このgistにアクセスすれば、

あ、9999？。答えは48個あるみたいだね。

ってすぐに会話が終わっちゃう。

っていうかそんな辛気臭い彼氏要らんわ。

やった！
飲んでくる！