BFOIT - Introduction to Computer Programming

# Pitcher Problem Solver - Pouring Data Tree

## The Pouring Data Structure Tree, Solution Path Through Nodes

Given pitchers of sizes 3 liters and 7 liters, walk through the pouring data structures in a tree to find the solution of 5 liters. Here is the solution provided by the solver program.

Now let's walk through the tree, one level down for each pouring step.

1. Coming off the root node with both pitchers empty, fill pitcher two from the river. The pouring data for this level-1 node is [[0 2] 0 7].
2. Coming off the level-1 node with pitcher one empty and pitcher two containing 7 liters , fill pitcher one from pitcher two. The pouring data for this node is [[2 1] 3 4].
3. Coming off the level-2 node with pitcher one containing 3 liters and pitcher two containing 4 liters, empty pitcher one into the river. The pouring data for this level-3 node is [[1 0] 0 4].
4. Coming off the level-3 node with pitcher one empty and pitcher two containing 4 liters, fill pitcher one from pitcher two. The pouring data for this node is [[2 1] 3 1].
5. Coming off the level-4 node with pitcher one containing 3 liters and pitcher two containing 1 liter, empty pitcher one into the river. The pouring data for this level-5 node is [[1 0] 0 1].
6. Coming off the level-5 node with pitcher one empty and pitcher two containing 1 liter, fill pitcher one from pitcher two. The pouring data for this node is [[2 1] 1 0].
7. Coming off the level-6 node with pitcher one containing 1 liter and pitcher two empty, fill pitcher two from the river. The pouring data for this node is [[0 2] 1 7].
8. Coming off the level-7 node with pitcher one containing 1 liter and pitcher two containing 7 liters, fill pitcher one from pitcher two. The pouring data for this node is [[2 1] 3 5].

Here is the tree with the path and concerned nodes highlighted for the first six steps.

Here are the last three levels of a tree with the path and concerned nodes highlighted for steps six through eight.