waterJugProblem.rb

State = Struct.new(:pitcher, :result, :cnt, :operate)

Target  = [ 5,  5,  0]
First   = [10,  0,  0]
Pitcher = [10,  7,  3]

def check(pitcher)
    return pitcher == Target
end

def toStr(pitcher)
    pitcher[0].to_s + " " + pitcher[1].to_s + " " + pitcher[2].to_s + "\n"
end

def max(a, b)
    a = a.to_i
    b = b.to_i
    (a > b) ? a : b
end

def min(a, b)
    a = a.to_i
    b = b.to_i
    (a < b) ? a : b
end

def solve()
    flag =  Array.new(Pitcher[0] + 1){Array.new(Pitcher[1] + 1){Array.new(Pitcher[2] + 1, 10000)}}

    ans = []
    bfs = []
    bfs.push(State.new(First, toStr(First), 0))

    while !bfs.empty? do
        state = bfs.shift()
        if check(state.pitcher)
            ans.push(state)
            next
        end

        if  state.cnt > flag[state.pitcher[0]][state.pitcher[1]][state.pitcher[2]]
            next
        else
            flag[state.pitcher[0]][state.pitcher[1]][state.pitcher[2]] = state.cnt
        end

        for i in 0..2
            for j in 0..2
                if i != j
                    nextState = State.new([0, 0, 0], "", 0, "")

                    pitcher_i = max(state.pitcher[i].to_i - (Pitcher[j].to_i - state.pitcher[j].to_i), 0)
                    pitcher_j = min(state.pitcher[j].to_i + state.pitcher[i].to_i, Pitcher[j].to_i)

                    # i -> j
                    nextState.pitcher[i] = pitcher_i
                    nextState.pitcher[j] = pitcher_j
                    nextState.pitcher[3 - i - j] = state.pitcher[3 - i - j]

                    nextState.cnt = state.cnt + 1

                    nextState.result  = state.result  + toStr(nextState.pitcher)
                    nextState.operate = state.operate.to_s + (Pitcher[i]).to_s() + " -> " + (Pitcher[j]).to_s() + "\n"

                    bfs.push(nextState)
                end
            end
        end
    end

    # can't visit state
    puts "Can't visit state"
    for i in 0..10
      for j in 0..7
        for k in 0..3
          if i + j + k == 10
            if flag[i][j][k] == 10000
                puts Array[i, j, k].to_s
            end
          end
        end
      end
    end

    return ans
end

print "First State: ", Pitcher, "\n"
puts "----------"
result = solve()
print "Answer Numbver: ", result.length, "\n"
for a in result
  puts "**********"
  puts "movements: " + a.cnt.to_s
  puts a.result.to_s
  puts "----------"
  puts a.operate
end