【Ruby】【アルゴリズム】宣教師と人食い問題(全列挙型Ver) ※リファクタリング後
綺麗なコードを書く勉強をしたので
まえのだめなコードをリファクタリングするぞ。
解法的には間違っている事実は変わらないので、そこは気をつけてください(?)。
コード全量
やっぱりpossible? メソッドがイケテない。
もっと綺麗にかけるのかな。
#起こりうる可能性を全て列挙(2**6通り) def make_candidate results = ["000000"] #人人人鬼鬼鬼が左岸 6.times do |i| _results = results.dup _results.each do |res| tmp2 = res.dup tmp2[i] = "1" results << tmp2 end end results end #食べられないケースだけ抽出 def make_approvals(results) apps = [] results.each do |res| data = res.split("").map{|a|a.to_i} a = data[0,3].inject(:+) b = data[3,3].inject(:+) #全員が左or右 もしくは 左岸がOK&&右岸がOK apps << res if (a==3 || a==0) || ((3-a) >= (3-b) && a>=b) end apps end def possible?(now, pat) return false if now == pat count = 0 if @history.length %2 == 0 #右から左へ now.each_with_index do |n, i| if n == 0 return false if pat[i] != 0 #0->1(右岸に移動)は出来ない else count += 1 if pat[i] != 1 #移動するものをカウント end end return false if count>2 #移動する物の数が2以上は不可能 else #左から右へ now.each_with_index do |n, i| if n == 1 return false if pat[i] != 1 #1->0(左岸に移動)は出来ない else count += 1 if pat[i] != 0 end end return false if count>2 end true end def dejavu?(pat) @history.each_with_index do |his_st, i| his = his_st.split("").map{|a|a.to_i} h1 = his[0,3].inject(:+) h2 = his[3,3].inject(:+) p1 = pat[0,3].inject(:+) p2 = pat[3,3].inject(:+) return true if (h1 == p1) && (h2 == p2) && (i%2 == (@history.length)%2) end false end @history = [] @patterns = make_approvals(make_candidate) def _solve (now) now_st = now.join("") @history << now_st return true if now_st == "111111" @patterns.each do |pat_st| pat = pat_st.split("").map{|a|a.to_i} if possible?(now, pat) && !dejavu?(pat) return true if _solve(pat) == true end end @history.pop end def solve(now_st) now = now_st.split("").map{|a|a.to_i} _solve(now) return @history end p solve("000000")