Can You Pour the Water?

You have two empty pitchers, one holding $10$ litres (pitcher $A$) and one holding $3$ litres (pitcher $B$). The allowed moves are to fill a pitcher to the brim from the tap, empty a pitcher completely, or pour from one pitcher into the other until either the first is empty or the second is full. Each move counts as one step. What is the fewest steps to make one pitcher hold exactly $5$ litres?

The Fiddler, Zach Wissner-Gross, March 29, 2024(original post)

Solution

A state of the system is the pair $(a,b)$ of current volumes, and every move sends one state to another, so the fewest steps to reach a $5$ is the length of the shortest path from $(0,0)$ through this graph. One route reaches it by repeatedly filling the small pitcher and tipping it into the large one, draining the large one once it overflows: $$\begin{gather*} (0,0)\to(0,3)\to(3,0)\to(3,3)\to(6,0)\to(6,3)\to(9,0)\\ \to(9,3)\to(10,2)\to(0,2)\to(2,0)\to(2,3)\to(5,0), \end{gather*}$$ which is twelve moves. That nothing shorter works is what the search settles: every state reachable in eleven moves or fewer is enumerated below, and none holds a $5$. So the answer is $$\boxed{12}$$ steps. (Since $\gcd(10,3)=1$ every whole number of litres is eventually reachable; $5$ simply sits twelve moves deep.)

The computation

Run a breadth-first search from $(0,0)$: from each state generate the six moves (fill either pitcher, empty either, pour either way) and record the first time each new state is seen. The first distance at which a state shows a $5$ is the answer.

from collections import deque
def shortest(CA, CB, target):
    start = (0, 0); dist = {start: 0}; q = deque([start])
    while q:
        a, b = q.popleft(); d = dist[(a, b)]
        t1 = min(a, CB - b); t2 = min(b, CA - a)
        for s in [(CA, b), (a, CB), (0, b), (a, 0), (a - t1, b + t1), (a + t2, b - t2)]:
            if s not in dist: dist[s] = d + 1; q.append(s)
    return min(v for (a, b), v in dist.items() if a == target or b == target)
print(shortest(10, 3, 5))                          # 12

Extra Credit

Now the pitchers hold $100$ and $93$ litres. If $f(N)$ is the fewest steps to obtain exactly $N$ litres in one pitcher, what is the largest $f(N)$, and at which $N$?

Solution

There is no tidy formula here: pouring between a $100$- and a $93$-litre pitcher runs the Euclidean algorithm in slow motion, and how deep a given volume sits depends on the whole chain of subtractions. So the honest tool is the same search, now carried over every reachable state, recording for each volume the first step at which it appears and taking the worst. The deepest volume turns out to be the middling $50$ litres, exactly half the large pitcher, and it sits $$\boxed{\max_N f(N)=190\ \text{steps, at }N=50.}$$

The computation

The same breadth-first search as above, run to exhaustion over all states, gives the first-reached step for every volume; the maximum is $190$, at $N=50$.

from collections import deque
def all_dist(CA, CB):
    dist = {(0, 0): 0}; q = deque([(0, 0)])
    while q:
        a, b = q.popleft(); d = dist[(a, b)]
        t1 = min(a, CB - b); t2 = min(b, CA - a)
        for s in [(CA, b), (a, CB), (0, b), (a, 0), (a - t1, b + t1), (a + t2, b - t2)]:
            if s not in dist: dist[s] = d + 1; q.append(s)
    return dist
d = all_dist(100, 93)
best = {}
for (a, b), v in d.items():
    for amt in (a, b):
        if amt not in best or v < best[amt]: best[amt] = v
N = max(best, key=best.get)
print(best[N], N)                                  # 190 50