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 2 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 one from the river. The pouring data for this level-1 node is [[0 1] 3 0].
  2. Coming off the level-1 node with pitcher one containing 3 liters and pitcher two empty, fill pitcher two from pitcher one. The pouring data for this node is [[1 2] 0 3].
  3. Coming off the level-2 node with pitcher one empty and pitcher two containing 3 liters, fill pitcher one from the river. The pouring data for this level-3 node is [[0 1] 3 3].
  4. Coming off the level-3 node with pitcher one containing 3 liters and pitcher two containing 3 liters, fill pitcher two from pitcher one. The pouring data for this node is [[1 2] 0 6].
  5. Coming off the level-4 node with pitcher one empty and pitcher two containing 6 liters, fill pitcher one from the river. The pouring data for this level-3 node is [[0 1] 3 6].
  6. Coming off the level-5 node with pitcher one containing 3 liters and pitcher two containing 6 liters, fill pitcher two from pitcher one. The pouring data for this node is [[1 2] 2 7].

Here is the tree with this path and concerned nodes highlighted.