Tags

, , , , ,


The other day, my colleague presented to us a simple 3 jar problem.
There are 3 jars of capacity 19l, 13l and 7l with the latter two filled to its capacity (say with water).
The challenge is to transfer the liquid across these 3 jars and arrive at 10l each in the 19l and 13l jar.

This is one of those typical high school or college level puzzles that we tried and gave up out of frustration. With some perseverance, it was solvable indeed. No … this post isn’t about how to solve this by hand. Google would do a great job at that.

I sat down to write a javascript program that would solve such problems. Not just the case of 3 jars, but N jars (of course, otherwise why write a program at all). It appeared to be difficult. I thought A* search kind of a thing would be needed. But in the end, it wasn’t that complicated at all. A simple recursive solution that forbids already explored paths is all that is needed to solve such problems.

However, the solution has these limitations.
(1) Works on problems where there IS a solution. For example, a final configuration of 10, 5, 5 is not attainable. Currently I don’t know how to check for feasible goal states. So this program hangs in such cases.
(2) Basic validations and error handling not yet in place

Please find the javascript code here. I used jsenv to write and test this code.

As usual, V pointed out some improvements. V will be posting a python solution as well.

The results for this problem, as it appears in JsEnv is given below.

Running in bookmarklet mode…
Goal Achieved
0,13,7–>13,0,7–>13,7,0–>19,1,0–>12,1,7–>12,8,0–>5,8,7–>5,13,2–>
18,0,2–>18,2,0–>11,2,7–>11,9,0–>4,9,7–>4,13,3–>17,0,3–>17,3,0–>
10,3,7–>10,10,0

Suggestions, improvements most welcome.

Update : Here is a 4 jar problem. The program solve it (though not in the least number of steps.)
jars = [10, 10, 5, 4]
fill = [10,10,0,0]
goal = [4,10,3,3]

Advertisements