Can You Pour the Water?
This Week's Fiddler
To get to 5 liters, we first fill pitcher A with 10 liters. We then dump 3 liters from A into and out of B; we do this three times to have 1 liter left in A. Pour this liter into B, and refill A. Now we can pour just 2 liters into B to fill it up, leaving us with 8 liters in A. Pour out B and pour 3 liters from A into B.
12 steps of modular arithmetic (and many words) later and we're left with 5 liters in A, completing our goal!
Maybe an animation will help drive the point home better:
10 liters
3 liters
Step 0
Extra Credit
Lots of numbers to crunch through, so let's let code do the heavy lifting for us.
We can represent the state of the pitchers by how full they are (call these and , where and for capacities and ), and each action (e.g., adding water, moving water from one pitcher to the other, etc.) is like a state change in a finite state machine.
To minimize the number of steps it takes to get from the initial state ( and ) to a successful state ( or ), we can perform a breadth-first search of this state machine. Start with a queue q of just the initial state, add all possible actions to the queue (if they haven't been seen yet), and mark these states as seen. We want to mark cases we've seen as we don't want to waste time exploring states we've already considered.
To keep track of how many steps we've taken, we will set steps = 0 and rem = len(q), designating the next len(q) iterations as all being equally far away from the initial state. After every iteration, we decrement rem, and once rem == 0, we increment steps and reset rem = len(q).
For the sake of curiosity (and visualization!) let's also add in a trace_path option which will traverse the order of actions that got us to our goal.
The Code (including an extra bit for part 1)
from collections import deque
def solve(A: int, B: int, N: int, trace_path: bool = False) -> int:
parents: dict[tuple[int, int], tuple[int, int] | None] = {(0, 0): None}
q: deque[tuple[int, int]] = deque(parents)
rem = len(q)
steps = 0
while q:
a, b = q.popleft()
if a == N or b == N:
if trace_path:
curr = (a, b)
s = deque()
while curr is not None:
s.appendleft(list(curr))
curr = parents[curr]
print(list(s))
return steps
cands = []
if a < A:
cands.append((A, b))
if b < B:
cands.append((a, B))
if a > 0:
cands.append((0, b))
if b < B:
if a + b <= B:
cands.append((0, a + b))
else:
cands.append((a + b - B, B))
if b > 0:
cands.append((a, 0))
if a < A:
if a + b <= A:
cands.append((a + b, 0))
else:
cands.append((A, a + b - A))
for cand in cands:
if cand not in parents:
parents[cand] = (a, b)
q.append(cand)
rem -= 1
if rem == 0:
rem = len(q)
steps += 1
raise RuntimeError
print('Path:', end=' ')
print(solve(10, 3, 5, trace_path=True))
print()
A = 100
B = 93
results = [(solve(A, B, N), N) for N in range(1, 101)]
for steps, n in results:
print(f'{n: >3}: {steps}')
print('Steps for all N:', [steps for steps, _ in results])
print()
max_steps, max_n = max(results)
print('Max steps:', max_steps)
print('N:', max_n)
print('Path:', end=' ')
solve(A, B, max_n, trace_path=True)
Output
Path: [[0, 0], [10, 0], [7, 3], [7, 0], [4, 3], [4, 0], [1, 3], [1, 0], [0, 1], [10, 1], [8, 3], [8, 0], [5, 3]]
12
1: 164
2: 52
3: 110
4: 106
5: 56
6: 160
7: 2
8: 168
9: 48
10: 114
11: 102
12: 60
13: 156
14: 6
15: 172
16: 44
17: 118
18: 98
19: 64
20: 152
21: 10
22: 176
23: 40
24: 122
25: 94
26: 68
27: 148
28: 14
29: 180
30: 36
31: 126
32: 90
33: 72
34: 144
35: 18
36: 184
37: 32
38: 130
39: 86
40: 76
41: 140
42: 22
43: 188
44: 28
45: 134
46: 82
47: 80
48: 136
49: 26
50: 190
51: 24
52: 138
53: 78
54: 84
55: 132
56: 30
57: 186
58: 20
59: 142
60: 74
61: 88
62: 128
63: 34
64: 182
65: 16
66: 146
67: 70
68: 92
69: 124
70: 38
71: 178
72: 12
73: 150
74: 66
75: 96
76: 120
77: 42
78: 174
79: 8
80: 154
81: 62
82: 100
83: 116
84: 46
85: 170
86: 4
87: 158
88: 58
89: 104
90: 112
91: 50
92: 166
93: 1
94: 162
95: 56
96: 108
97: 110
98: 54
99: 164
100: 1
Steps for all N: [164, 52, 110, 106, 56, 160, 2, 168, 48, 114, 102, 60, 156, 6, 172, 44, 118, 98, 64, 152, 10, 176, 40, 122, 94, 68, 148, 14, 180, 36, 126, 90, 72, 144, 18, 184, 32, 130, 86, 76, 140, 22, 188, 28, 134, 82, 80, 136, 26, 190, 24, 138, 78, 84, 132, 30, 186, 20, 142, 74, 88, 128, 34, 182, 16, 146, 70, 92, 124, 38, 178, 12, 150, 66, 96, 120, 42, 174, 8, 154, 62, 100, 116, 46, 170, 4, 158, 58, 104, 112, 50, 166, 1, 162, 56, 108, 110, 54, 164, 1]
Max steps: 190
N: 50
Path: [[0, 0], [0, 93], [93, 0], [93, 93], [100, 86], [0, 86], [86, 0], [86, 93], [100, 79], [0, 79], [79, 0], [79, 93], [100, 72], [0, 72], [72, 0], [72, 93], [100, 65], [0, 65], [65, 0], [65, 93], [100, 58], [0, 58], [58, 0], [58, 93], [100, 51], [0, 51], [51, 0], [51, 93], [100, 44], [0, 44], [44, 0], [44, 93], [100, 37], [0, 37], [37, 0], [37, 93], [100, 30], [0, 30], [30, 0], [30, 93], [100, 23], [0, 23], [23, 0], [23, 93], [100, 16], [0, 16], [16, 0], [16, 93], [100, 9], [0, 9], [9, 0], [9, 93], [100, 2], [0, 2], [2, 0], [2, 93], [95, 0], [95, 93], [100, 88], [0, 88], [88, 0], [88, 93], [100, 81], [0, 81], [81, 0], [81, 93], [100, 74], [0, 74], [74, 0], [74, 93], [100, 67], [0, 67], [67, 0], [67, 93], [100, 60], [0, 60], [60, 0], [60, 93], [100, 53], [0, 53], [53, 0], [53, 93], [100, 46], [0, 46], [46, 0], [46, 93], [100, 39], [0, 39], [39, 0], [39, 93], [100, 32], [0, 32], [32, 0], [32, 93], [100, 25], [0, 25], [25, 0], [25, 93], [100, 18], [0, 18], [18, 0], [18, 93], [100, 11], [0, 11], [11, 0], [11, 93], [100, 4], [0, 4], [4, 0], [4, 93], [97, 0], [97, 93], [100, 90], [0, 90], [90, 0], [90, 93], [100, 83], [0, 83], [83, 0], [83, 93], [100, 76], [0, 76], [76, 0], [76, 93], [100, 69], [0, 69], [69, 0], [69, 93], [100, 62], [0, 62], [62, 0], [62, 93], [100, 55], [0, 55], [55, 0], [55, 93], [100, 48], [0, 48], [48, 0], [48, 93], [100, 41], [0, 41], [41, 0], [41, 93], [100, 34], [0, 34], [34, 0], [34, 93], [100, 27], [0, 27], [27, 0], [27, 93], [100, 20], [0, 20], [20, 0], [20, 93], [100, 13], [0, 13], [13, 0], [13, 93], [100, 6], [0, 6], [6, 0], [6, 93], [99, 0], [99, 93], [100, 92], [0, 92], [92, 0], [92, 93], [100, 85], [0, 85], [85, 0], [85, 93], [100, 78], [0, 78], [78, 0], [78, 93], [100, 71], [0, 71], [71, 0], [71, 93], [100, 64], [0, 64], [64, 0], [64, 93], [100, 57], [0, 57], [57, 0], [57, 93], [100, 50]]
Thus, with a whopping f(N) = 190 steps, N = 50 liters takes the cake for being the most time-consuming volume to achieve!
What does this data look like for all the from 1 to 100?
Seems like there's a bit of a periodicity of 7, which makes sense as we can get 7 liters of water by taking pouring out 93 liters from pitcher A.
Finally, an animation of to go alongside it!
100 liters
93 liters
Step 0
— Emily