Wednesday, July 25, 2012

Three Containers

The New York Times Wordplay blog posted this puzzle.


Spoiler alert! Stop reading now if you're going to try to solve the puzzle yourself.


I ended up spending long enough on it that I manually created the complete tree of water-in-glass configurations (thank you to Beckett Madden-Woods for a correction):




Each node is a different combination of water quantities in each glass – respectively the 20, 15 and 7 ounce glasses. An edge represents pouring one glass into another glass – the source glass and the destination glass, where A = 20 oz, B = 15 oz, and C = 7 oz. So A → C means that water is poured from the 20 oz glass into the 7 oz glass.

The depth of the node is the minimum number of pours required to get to that configuration. The puzzle solution, "10,10,0" is surprisingly deep – there are two very long branches, and it takes 15 pours to get to the solution. Incidentally, every amount of water from 0 oz to 20 oz is present in a glass somewhere in the tree.

I did this manually – please let me know if you notice an error!

7 comments:

beckett said...

Nice!

I threw together some code, and got similar results:
http://moosers.org/glass-puzzle/bfs.png

Though, I have some more nodes off the early (0, 15, 5) and so my overall tree is shallower than yours.

Things get visually interesting if you draw in the edges to form cycles.
Here's where I wish I had better dot skills than I do...

http://moosers.org/glass-puzzle/cycles.png (warning: large image)

Craig Nevill-Manning said...

Thanks, Beckett – I absolutely missed two states! I've updated the post.

JMHL said...

Spoiler alert! Don't read on if you don't want to see the solution.

Here's how I solved the problem:

Draw a grid of 15 x 7 squares. Every point in the grid corresponds to a state of all three glasses, with the contents of the 20 oz glass implied by the other two values. There are three infeasible points at (7, 14), (7, 15) and (6, 15), because you only have 20 oz of water, so the top right corner is cut off the rectangle.

Now your starting point is (0, 0) and you want to get to (10, 0). Every pour is either an upward vertical move (20->7 pour), a horizontal move to the right (20->15 pour), a diagonal move up/left (15->7 pour), or the reverse of each of these. And every move has keep going in one of these directions until it hits a boundary. Then go backwards from the end point (10, 0) and every move is forced: (10, 7), (15, 2), (0, 2), (2, 0), ... etc. Eventually you have a nice cobweb picture and you hit the corner (15, 0) which is reachable from (0, 0).

JMHL said...
This comment has been removed by the author.
JMHL said...

Oops, I was wrong when I said every move is forced. There are two "first" reverse moves: (10,0) is accessible from (10, 7) but also from (3, 7). So there is a second path accessible by backtracking. But this leads to a slightly longer solution. (18 moves vs 15.)

Looks like I have recreated the two states you both found. (Shows I didn't read the earlier posts carefully, I was avoiding spoilers myself...)

And now I can enumerate all legal positions and the number of moves it takes to get there just by moving around the boundary of the rectangle (with corner cut off). There are two positions that take more moves to reach than (10, 0): they are (3, 7) and (3, 0). (16 moves each, vs 15 for (10, 0).) These correspond to (10, 3, 7) and (17, 3, 0) for the amount of water in (20, 15, 7) cups respectively. So (10, 10, 0) isn't quite the hardest puzzle possible given the constraints, but it has more aesthetic appeal than either of these.

beckett said...

Btw, here's the code for I used to output the BFS state transitions:

http://pastebin.com/q4BBhCwx

Cheers,
-Beckett

Tony Smith said...

This is similar to Towers of Hanoi, isn't it?

if isFull(C) then C->A
else if isEmpty(B) then A->B
else B->C

Or, we can transfer the other direction

if isFull(B) then B->A
else if isEmpty(C) then A->C
else C->B