【Ruby】【アルゴリズム】バックトラックはややこしい。 川渡り問題（リファクタリング後）

　
川渡りが解けたよーって師匠にメールしたら

おれも解いてみました
1時間くらいかな、ちょっと時間かかった

ってメールが来た。

むきー！

　
このサンプルを参考にブラッシュアップ。

以前のコードはこちら
　
　

改善ポイント

状態遷移図をビット化する

@_members = ["dack", "corn", "wolf"]
↓
START ="0000" # master, fox, duck, corn

学んだこと

include?はコストが高いので なるべく最後に持ってくる

return false if status[1] == status[2] && status[0] != status[1]
return false if status[2] == status[3] && status[0] != status[2]
return false if history.include?(status)　←ココに
true

バックトラッシュ法は履歴もバックさせる

頭で考えてたら分かるんだけど、再帰を書いてると混乱してしまう。
今回のコードはhistoryを全体で参照しているので、
history を戻す必要がある。
each文の中で都度historyをdupしていたら必要ないけど。

結果、こういうコードになりました。
0<=>1の反転は立っちゃんのコードから盗みました。

あえて一つ目の答えを却下しているので、
バックトラックしている様子がよく分かるとおもいます。

START="0000" #master, fox, duck, corn
GOAL = "1111"

def accept(history, status)
  return false if status[1] == status[2] && status[0] != status[1]
  return false if status[2] == status[3] && status[0] != status[2]
  return false if history.include?(status)
  true
end

def search(history, status)
  history << status
  return true if status == GOAL && history != ["0000", "1010", "0010", "1110", "0100", "1101", "0101", "1111"]
  arr = status.split("")
  arr.each_with_index do |a, idx|
    next_status = arr.dup
    next if next_status[0] != a
    a = (1 - a.to_i).to_s
    next_status[idx] = a
    next_status[0] = (1 - next_status[0].to_i).to_s if idx != 0
    next_status = next_status.join("")
    next if !accept(history, next_status)
    return true if search(history, next_status) == true
  end
  history.pop
  p history
end

history =[]
search(history, START)
p history

　
■実行結果

["0000", "1010", "0010", "1110", "0100", "1101", "0101"]
["0000", "1010", "0010", "1110", "0100", "1101"]
["0000", "1010", "0010", "1110", "0100", "1101", "0001"]
["0000", "1010", "0010", "1110", "0100", "1101"]
["0000", "1010", "0010", "1110", "0100"]
["0000", "1010", "0010", "1110"]
["0000", "1010", "0010"]
["0000", "1010", "0010", "1011", "0001", "1101", "0101", "1111"]

　
むきー！
うきー！