“Water buckets” Problem

In Solving “Water buckets” Problem Using Scala  Biju Kunjummen presented a Scala program to solve this puzzle:

You have a 12-gallon bucket, an 8-gallon bucket and a 5-gallon bucket. The 12-gallon bucket is full of water and the other two are empty. Without using any additional water (or buckets) how can you divide the twelve gallons of water equally so that two of the three buckets have exactly 6 gallons of water in them?

Not knowing Scala I present here a brief description of the algorithm that can be used to solve the puzzle. (See The Sunday Programmer for a C++ implementation)

Let us name the buckets 0,1 and 2. At any stage there are six possible actions:

  • Pour from 0 to 1 denoted as Pour(0,1)
  • Pour (0,2)
  • Pour (1,0)
  • Pour(1,2)
  • Pour (2,0)
  • Pour(2,1)

Notice that quantity is not considered because any pour action either empties the source or fills up the destination. This leads us to a depth first solution. We try each possible action until we reach the goal… with some caveats. A pour action may be invalid if the source is empty or destination is full. Secondly if the result of a pour action returns us to a state previously visited then we ignore that state as it will lead to a cycle in a depth-first search tree. Here we define a state as the triple <X,Y,Z> where X, Y and Z is the amount of water in the 12-gallon, 8-gallon and 5-gallon bucket respectively. The initial state is <12,0,0> and the goal state is <6,6,0>. This leads us to the following algorithm:

let seen-states = {start-state}

let Solve(current-state) =
  if current-state = goal-state
    return true
  else
    for-each action in possible-actions
        next-state = Do-Pour(action, current-state)
        if NOT next-state in seen-states
          add-state(next-state, seen-states)
          if Solve(next-state)
             print-output action
             return true
    return false

Solve(start-state)

Here Do-Pour returns the next state after the pour action unless the pour action is invalid in which case it returns the current state; add-state adds a state to collection of states.

Advertisements

About The Sunday Programmer

Joe is an experienced C++/C# developer on Windows. Currently looking out for an opening in C/C++ on Windows or Linux.
This entry was posted in Software Puzzle and tagged , , . Bookmark the permalink.

2 Responses to “Water buckets” Problem

  1. Pingback: Breadth First Search | The Sunday Programmer

  2. Pingback: No Raw Pointers | The Sunday Programmer

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s