James CookeJames Cooke

A water pouring problem sketched in Python

The problem

At the end of last year, I came across the following water pouring problem because something similar had come up in a friend’s functional programming interview:

There are three glasses on the table - 3, 5, and 8 oz. The first two are empty, the last contains 8 oz of water. By pouring water from one glass to another make at least one of them contain exactly 4 oz of water.

Source: A. Bogomolny, 3 Glasses Puzzle from Interactive Mathematics Miscellany and Puzzles, Accessed 09 January 2015

A solution using search, not algebra

At first I started to explore the problem by looking at it algebraically. What are the differences between each cup? How can those differences be summed together to give the required remainder of 4?

However this didn’t yield anything helpful. Instead, I started looking at the solution states. What do the cups have to look like for the puzzle to be solved?

Two success states

There are at least two success states. One where the 5 oz cup contains 4 oz of water and the other where the 8 oz cup contains 4 oz of water. The other two cups must contain the remaining 4 oz of water. This is the notation I’ve used for these two states, where x + y = 4:

[<Cup x/3>, <Cup 4/5>, <Cup y/8>]

And:

[<Cup x/3>, <Cup y/5>, <Cup 4/8>]

The search problem

So taking the second state, and assuming that the first cup is full, then the question becomes:

How do we get from the start state to the end state?
[<Cup 0/3>, <Cup 0/5>, <Cup 8/8>]
...
TODO: Search in here for a path
...
[<Cup 3/3>, <Cup 1/5>, <Cup 4/8>]

This is really helpful. It turns an algebra problem into a search problem. Computers are good at doing search. We can write code for this.

A Python 3 sketch

I’ve written some Python to solve this problems using a type of depth first Tree Traversal and tree generation strategy.

The code repository is available on GitHub. The README contains the installation and operating instructions.

These are some of the features of the code:

Cup and Game classes

In this code, the Cup class represents a cup in the problem. Each Cup has a certain capacity and contents. The benefit of using a Cup class as a data type is that it can perform checks that is not holding more than its capacity of water or that it’s holding a negative capacity of water either.

The Game class is more complex as it represents a single state in the tree. Each Game state has three main properties:

  • cups - The three Cups that make up this Game state.
  • parent - The Game that came before this one in the search. The starting state will have this as None, but all the rest will have a parent.
  • children - Each Game will have some or no child Game states stored in a list. These are the valid states that can be made by pouring some or all of one Cup’s contents into another Cup in the Game that haven’t already been seen during the search.

The Game’s children property makes the Game class a recursive data structure because it can contain other instances of Games. This opens the door to the recursive search described below.

Again using this Game type is really helpful because I’ve been able to write tested functions for supporting data type functions like __eq__ (which tests if two Game stats are logically the same). The most important function in Game is is_solvable which implements the search function.

As much functional style as possible

Originally I intended to write this sketch with as much functional style code as possible. However, there were certainly some functions that we not possible to achieve this without some serious hacking, and so I chose to keep those functions as simple and testable as possible.

I’d love to have the time to come back and construct a similar sketch for this problem in Haskell.

Possible improvements and follow up ideas

Apart from a fully functional rewrite, there are a couple of ways that I could see to improve the sketch. Even though it doesn’t run slowly, there are certainly some optimisations that could be made, plus some follow up ideas.

Save time by checking Cups contents when pouring

When generating child Game states by pouring from one cup to another, the system does not care if a Cup has water to give or if the recipient is full. It does the pour and then eliminates the new state because it’s a duplicate of its parent.

Instead, time could be saved by improving the pouring function so that pours only generate new Game states when there is water to give and the destination cup has space for that water.

Create a goal variable

The code could be improved to accept a goal value for the amount of water that should be in a Cup for success to be achieved.

Search for bigger solvable problems

Going meta, it would be interesting now to use this code to search for a nice big complicated water pouring problem. What’s the largest number of Cups and steps to success that can be found?