Skip to content

Instantly share code, notes, and snippets.

@draftcode
Created March 3, 2014 10:28
Show Gist options
  • Save draftcode/9322262 to your computer and use it in GitHub Desktop.
Save draftcode/9322262 to your computer and use it in GitHub Desktop.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment