Given a set of n jugs of different sizes, how would you dump water between them to get a specific amount? If you have ever watched Diehard III, you might have seen this with 2 jugs. In the movie they are given 4 and 5 gallon jugs and are asked to make 3 gallons.
I originally tried to write a program to solve this problem using a brute force method. Needless to say, this was very slow and almost never ran to completion. I thought about it for a while and finally figured it out. It boils down to just solving a graph of connected nodes. Since I wanted to learn ruby, I used this to learn the language.
The basic idea to solve this is:
Have we reach the end state (desired amount)?
Loop through each from jug (i)
Loop through each to jug (j)
Calculate the new state of the jugs (water level in each)
Have we seen this “state” before? If not, store the new state. If we have, then move on
If this is a new state, go to step 1 with new state
old state, continue looping
Obviously, this wont find the optimal solution, but it will find a solution. If you want to find the optimal, you will have to store the steps to get to a state, and see if you have found a quicker path to a state. If you want, I still have the ruby file to solve this.