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!