小舟に乗って川を渡る #(人 狼 羊 菜) たち

http://d.hatena.ne.jp/sumim/20050810

最近日本語ばっかりでコードを書いていなかったので、頭の体操代わりに。
普通に考えた方が早いのだが、あえてRubyで解いてみる。

def cmp(a, b)
  count = 0
  a.each_index do |i|
    next if a[i] == b[i]
    break if count != 0 && count *= 2
    count = a[i] <=> b[i]
  end
  return count
end

def trans1(stack, answer=[])
  (0..7).map{|x|[(x&4)>>2,(x&2)>>1,x&1]}.each do |state|
    next if state[1]==0 and (state[0]==0 || state[2]==0)
    diff = cmp(state, stack.last)
    next unless (diff == 0 && stack[-2] != state)
      || (diff == 1 && !stack.include?(state))
    if state == [1,1,1]
      answer.push(stack+[state])
    else
      trans2(stack+[state], answer)
    end
  end
  return answer
end

def trans2(stack, answer=[])
  (0..7).map{|x|[(x&4)>>2,(x&2)>>1,x&1]}.each do |state|
    next if state[1]!=0 and (state[0]!=0 || state[2]!=0)
    diff = cmp(state, stack.last)
    next unless (diff == 0 && stack[-2] != state)
      || (diff == -1 && !stack.include?(state))
    trans1(stack+[state], answer)
  end
end

answer = trans1([[0,0,0]])
answer.each{|x|p x}

なーんか無駄に長くなってる気もするのだがキニシナイ;(