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

せかいや

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

【Ruby】【アルゴリズム】宣教師と人食い問題(全列挙型Ver) ※リファクタリング後

綺麗なコードを書く勉強をしたので
まえのだめなコードリファクタリングするぞ。

解法的には間違っている事実は変わらないので、そこは気をつけてください(?)。

 

リファクタリングした点

  • 履歴は文字列で持つけど、内部的には数値配列に変換してから処理を行うよう統一した
  • 履歴をインスタンス変数化
  • injectメソッド、配列部分切り出しを使用してコードを短く

 

コード全量

やっぱり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")