【Ruby】【アルゴリズム】10パズルを解く。全ての数式を逆ポーランドで作る編

4桁の数字から全ての数式のパターンを列挙する。
数式は逆ポーランド記法で記述する。
(例)"12+3+4+"

　
すごい！30分で書けた！
もう再帰は見切ったぞ。

・dupでコピーをとりながら再帰を回す（必要に応じて深いコピー）
・終了条件を満たしたものをresult配列に詰め込む

のポイントだけ押さえれば、後は応用が効く。
　
吐きながら勉強した甲斐があった＞＜

コード

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]
          self._make_rpn(result, tmp2, tmp, num_count + 1, ope_count)
        end
      end
    end
    result
  end
end

p Calc.make_expression("1234")

ポイント

・与えられた数字を、最初は定数化しようと思ったけれどもRubyはメソッド内では定数が定義できない。
　⇒クラスを作ってクラス定数に。

　
■実行結果

["12+3+4+", "12+3+4-", "12+3+4*",
 "132+/4-", "132+/4*", "132+/4/",
 "143*2**", "143*2*/", "143*2/+",
 "23*4-1/", "23*4*1+", "23*4*1-",
 "2413/-+", "2413/--", "2413/-*",
 "32-1+4-", "32-1+4*", "32-1+4/",　
などなど。