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

本履歴

購入した古本の履歴と時々プログラミング

数学パズル本に敢てプログラムで挑戦(3)

どんどん挑戦していく。明日GCJ本番なのに目が冴えてしまってあかん。本日もAlgorithmic Puzzlesより。

49. Missionaries and Cannibals(宣教師と人食い部族)

3人の宣教師と3人の人食い族が船で川を渡る時(同時に2人まで)、両岸それぞれで人食い族の人数が宣教師よりも真に多くならないようにして渡る方法を求めよ

何処かで見たことのある問題も、結局はグラフの問題に帰着。船がどちらの岸にあるかと宣教師、人食い部族がそれぞれ左岸に何人いるかの情報を頂点とするグラフを幅優先探索すれば良い。具体的には[boat,Missionary,Cannibal]という配列で[0,3,3] -> [1,0,0]のステップ数を求める。結果は11ステップ。実際グラフを書くと相当単純(ほぼ一本道)のグラフになる。やはり数的優位が崩れると食べられてしまうという条件が厳しい。というのも、宣教師、人食い族それぞれ左右の岸にいる状態を考えると、どちらか一方は数的優位が成り立たなくなってしまうから。ちなみに4名以上でやってみたら渡る方法は無かった。

#49. Missionaries and Cannibals
#Three missionaries and three cannibals must cross a river.
#Their boat can only hold two people, and it cannot cross the river by itself
#with no people on board. Each missionary and each cannibal can row the boat.
#If present, missionaries cannot be outnumbered by cannibals.
#How can all six get across the river with the fewest crossings?

N=3
class State
    attr_reader :row_num
    def initialize(boat=0,people=[N,N],row_num=0)
        @boat=boat
        @people=people
        @row_num=row_num
    end

    def legitimate?
        rm,rc=@people
        lm,lc=N-rm,N-rc
        return false if rm>0&&rc>rm
        return false if lm>0&&lc>lm
        true
    end

    def accomplished?
        @boat==1&&@people==[0,0]
    end

    def next_move
        ret=[]
        m,c=@people
        if @boat==0
            ret<<State.new(1,[m-1,  c],@row_num+1) if m>0
            ret<<State.new(1,[m-2,  c],@row_num+1) if m>1
            ret<<State.new(1,[  m,c-1],@row_num+1) if c>0
            ret<<State.new(1,[  m,c-2],@row_num+1) if c>1
            ret<<State.new(1,[m-1,c-1],@row_num+1) if m>0&&c>0
        else
            ret<<State.new(0,[m+1,  c],@row_num+1) if m<N
            ret<<State.new(0,[m+2,  c],@row_num+1) if m<N-1
            ret<<State.new(0,[  m,c+1],@row_num+1) if c<N
            ret<<State.new(0,[  m,c+2],@row_num+1) if c<N-1
            ret<<State.new(0,[m+1,c+1],@row_num+1) if m<N&&c<N
        end
        ret
    end

    def to_code
        @boat.to_s+@people.join
    end
end


init_state=State.new
queue=Array.new
queue.push init_state
visited=Hash.new

until queue.empty?
    state=queue.shift
    next if visited[state.to_code]
    visited[state.to_code]=state.row_num
    if state.accomplished?
        puts state.row_num
        exit
    end

    state.next_move.each{|next_state|
        next unless next_state.legitimate?
        next if visited[next_state.to_code]
        queue.push next_state
    }
end

puts"impossible"