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.

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.

Recursive search

As mentioned above, the Game.is_solvable function implements the tree search, so here it is in full, comments removed.

def is_solvable(self):
    if self.is_goal():
        self.print_trace()
        return True

    if self.make_children() == 0:
        return False

    return self.solvable_child()

There are two base cases to this recursive function.

• self.is_goal() : Goal has been reached. This Game contains a Cup that has 4 oz of water, success, a goal state has been found! Return True and print a trace of how the algorithm got here.
• self.make_children() == 0 : There are no child states. This Game can not generate any new states that don’t exist in the tree already, so this state is a fail, return False.

When neither of those two base cases are found, then this state is on a “success path” if one of its children “is solvable”. The recursive case is that the Game.solvable_child helper function is then used to call Game.is_solvable on each of the child Games.

Here is the helper function without comments:

def solvable_child(self):
    for child in self.children:
        if child.is_solvable():
            return True

    return False

There are two “interesting” features of this function:

• It operates like a short circuited OR reduction. This means that as soon as a solvable child is found, it stops searching and returns True.
• It has been split out from Game.is_solvable to assist with unit testing.

This short circuiting feature is important. I wasn’t able to get it to work in a reduce statement on the Game.children, so instead I wrote it out explicitly as a for-loop.

Duplicate search

When generating new Games by pouring water from Cup to Cup, only new Game states are added as children of any particular Game. This prevents duplication of Games and ensures that the search will terminate once all different possible states have been generated at the very latest.

The Game.has_game function implements this duplicate search using a recursive depth first tree search.

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.

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.

Improve the network anti-duplication search

Searching the existing Game states to ensure that the same state hasn’t already been created first runs to the top of the Game tree, then searches downwards.

Most Game states will be duplicates of a Game that’s either their parent or one Game state away from them. This means there’s an advantage, especially when running bigger problem searches, to search nearest Games first.

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?