# 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.

• (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: