Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Dijkstra solution in Clear category for Water Jars by PositronicLlama
"""Return a sequence of moves that fill a jar with a given amount of water."""
import heapq
def pour(a, va, b, vb):
"""Return the amount of liquid in jars 'a' and 'b' if pouring from a to b."""
capacity = vb - b
poured = min(capacity, a)
return a - poured, b + poured
def checkio(first, second, goal):
"""
Return a list of 'ij's, where 'i' is the source index and 'j' is the destination.
first: The volume of the first jar.
second: The volume of the second jar.
goal: The goal amount of water.
"""
visited = set()
# List steps, of quantity in first jar, quantity in second, move, previous
pending = [(0, 0, 0, None, None)]
while pending:
prev = heapq.heappop(pending)
step, a, b, _, _ = prev
visited.add((a, b))
a12, b12 = pour(a, first, b, second)
b21, a21 = pour(b, second, a, first)
for move, na, nb in (('01', first, b), ('02', a, second), # Fill from lake
('10', 0, b), ('20', a, 0), # Pour into lake
('12', a12, b12), ('21', a21, b21)): # Jar to jar
if na == goal or nb == goal:
result = [move]
while prev[3]:
result.append(prev[3])
prev = prev[4]
return list(reversed(result))
if (na, nb) not in visited:
heapq.heappush(pending, (step + 1, na, nb, move, prev))
return []
if __name__ == '__main__':
print(checkio(5, 7, 6)) # ['02', '21', '10', '21', '02', '21', '10', '21', '02', '21']
print(checkio(3, 4, 1)) # ["02", "21"]
Aug. 25, 2013
Comments:
