読者です 読者をやめる 読者になる 読者になる

せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【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"]

 
むきー!
うきー!