You have two water containers (left and right) with given capacities. Your task is to measure a given amount of water using the containers.
Initially the containers are empty. In each step, you can fill or empty one of the containers or pour water from one container to the other. After each step, at least one of the containers must be full or empty.
What is the smallest amount of water needed to move in order to measure the given amount of water into the left container?
Example: The capacity of the left container is liters, the capacity of the right container is liters, and you need to measure liters. In this case, the smallest amount to move is liters. Here is one optimal solution:
- Fill the left container (5 liters of water moved)
- Pour from the left container to fill the right container (4 liters of water moved)
- Empty the right container (4 liters of water moved)
- Pour the contents of the left container into the right container (1 liter of water moved)
- Fill the left container (5 liters of water moved)
- Pour from the left container to fill the right container (3 liters of water moved)
In a file water.py
, implement a function min_amount
that returns the smallest amount of water to move.
You may assume that the capacity of each container is an integer in the range . The function should be efficient in all these cases. If there is no solution, the answer should be .
def min_amount(left_volume, right_volume, target): # TODO if __name__ == "__main__": print(min_amount(5, 4, 2)) # 22 print(min_amount(4, 3, 2)) # 16 print(min_amount(3, 3, 1)) # -1 print(min_amount(1, 1, 10**9)) # -1 print(min_amount(10, 9, 8)) # 46 print(min_amount(123, 456, 42)) # 10530