Cup Pouring Problem

Getting a volume of water using some cups with computer science

Given two cups , with known volumes and an infinite supply of water. Is it possible to get a stated third volume by pouring, filling and emptying operations? If so , how?

It sounds simple and difficult at the same time. Simple as you can simply evaluate a possibilities, difficult as you might reevaluate a condition again with brute force (trying all conditions) techniques.

To clarify, there are six operations available (there are two ways to do the operations below)

  • Empty a cup
  • Fill a cup
  • Pour water from a cup to another

An example - we have two cups with volumes 9 units and 4 units respectively and we are trying to obtain a volume of 2 units.

In case you are not clear , you can try some operations:

  • If you fill up the first cup, you will have (9 , 0)
  • Then fill up the second cup, you will have (9 , 4)
  • Then empty the second cup, you now have (9 , 0)
  • Pour waterr from the first cup to the second cup, it becomes (5 , 4)

Read the above paragraph until you understand what is going on.

Now, let’s try solving this problem by hand.

  • (0 , 0) - We start with two empty cups
  • (9 , 0) - We fill up the first cup with water
  • (5 , 4) - We pour water from the first cup into the second cup
  • (5 , 0) - We empty the second cup
  • (1 , 4) - We pour water from the first cup into the second cup
  • (1 , 0) - We empty the second cup
  • (0 , 1) - We pour water from the first cup into the second cup
  • (9 , 1) - We fill up the first cup with water
  • (6 , 4) - We pour water from the first cup into the second cup
  • (6 , 0) - We empty the second cup
  • (4 , 2) - We pour water from the first cup into the second cup

Eureka! (Literally, as this was what archimedes discovered when he was dealng with waters too). We managed to get 2 units of water in 10 steps. For small volumes like this, it is always easy to calculate the solution. But what if I were to give you really odd values like 101ml and 79ml to form 2ml? You probably can’t and won’t do it by hand. (In case you are curious, it is feasible, 162 steps)

Here are the problems with attempting this problem by hand:

  • Too many possibilities - by doing one of the operations, and doing another one subsequently , some simple multiplication shows that there are a lot of possiblities
  • Hard (if not unable) to identify revisited conditions - by using a computer, you can easily trace a condition with O(log N) (O(1) if you are using arrays ) using the heap data structure. By hand? good luck.
  • Mindfuck - You would probably go mad before getting a solution. In the example above, we were lucky to get the correct answer on the first try. (My brother who doesn’t do computer science used something like 10 minutes, my computer took less than 0.01 seconds)

Exactly why a computer can solve the problem is inverse to those above

  • Too many possibilities don’t exist in computer science (unless you are speaking something like a googol)
  • Data structures to easily and quickly check visited conditions
  • Computer don’t have emotions (hence, won’t get mind-fuck)

To solve this problem, if you are familiar with computer science and graphs, all needed is a simple Breadth First Search technique and terminate search if we reach a familiar condition. Why? Try thinking about it :)

If you are not, try thinking this way:

  1. You start with two empty cups
  2. Is the current state the (one of the volume of the cups fulfills the target volume) intended state? If positive, go to step 6. If not, move to next step
  3. Have you visited the state before? If positive , do not try to evaluate the state and try the next state in the list
  4. Try every of the six operations. Check if the state was visited before. If positive, don't evaluate the state. Else , make a memo that you will evaluate the state in the future
  5. Go to step 2
  6. Wohoo you are done!

If you are not convivned it will work, try drawing diagrams. My friends and I (for the sake of fun) have assembled a project to solve this problems in several programming languages, including a simulation in the web browswer.

The project is open source in github, started by a friend of mine. I contributed some of the implementations and writen the simulation for a web browser (in case you are curious, in jquery)

As said, the simulation is here