two_bucket_shortest_path.rb

class TwoBucketShortestPathCalculator
  def initialize(cap_a, cap_b)
    @cap_a = cap_a
    @cap_b = cap_b
  end

  def answer
    @answer ||= calculate
  end

  def calculate
    paths = Array.new(@cap_a+1) { Array.new(@cap_b+1, nil) }
    queue = []
    check_and_push = lambda do |from_a, from_b, to_a, to_b|
      unless paths[to_a][to_b]
        paths[to_a][to_b] = paths[from_a][from_b] + [[from_a, from_b]]
        queue.push([to_a, to_b])
      end
    end
    paths[0][0] = []
    queue.push([0, 0])

    until queue.empty?
      a, b = queue.shift
      check_and_push.call(a, b, @cap_a, b)
      check_and_push.call(a, b, a, @cap_b)
      check_and_push.call(a, b, 0, b)
      check_and_push.call(a, b, a, 0)

      check_and_push.call(a, b, a-([a+b,@cap_b].min-b), [a+b,@cap_b].min)
      check_and_push.call(a, b, [a+b, @cap_a].min, b-([a+b,@cap_a].min-a))
    end

    paths
  end
end

calc = TwoBucketShortestPathCalculator.new(5, 3)

calc.answer.each_with_index do |b_paths, a|
  b_paths.each_with_index do |path, b|
    if path
      puts "#{a},#{b}: #{path + [[a, b]]}"
    end
  end
end