小舟に乗って川を渡る #(人 狼 羊 菜) たち
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}
なーんか無駄に長くなってる気もするのだがキニシナイ;(