# do you know this water jug problem

## Recommended Posts

davidrachel    122
you have two jugs,3 gallon one and 4 gallon one ,doesn't have any markers on it,you fill this jugs with pump,how to fill 2 gallons of water in 4 gallon jug? anybody know answer plz reply..

##### Share on other sites
stevenmarky    369
What does this have to do with artificial intelligence?
I've heard variations of this puzzle before.
Interestingly (is that a word?), I don't think ai would have much trouble solving this problem (genetic algorithms/minimax would solve this easily).

1st solution: Fill the 3 gallon jug, and pour it into the 4 gallon jug.
Fill the 3 gallon jug again and begin pouring it into the 4 gallon jug but stop when the 4 gallon jug is full.

There is another solution but it's not perfect because it depends on the dimensions and mass of the jugs:

Fill the 4 gallon jug and pour it into the 3 gallon jug till there is one gallon left. Empty the 3 gallon jug, and pour the 1 gallon into it.
Fully fill the 4 gallon jug, then submerge the 3 gallon jug in it so the tops are level - it will displace roughly 3 gallons and there will be 1 gallon left in the large jug. Step 3: Profit!

Edit: Just thought of another solution:

Fill the 4 gallon jug and pour it into the 3 gallon jug till there is one gallon left. Empty the 3 gallon jug, and pour the 1 gallon into it.
Fully fill the 4 gallon jug, then pour it into the 3 gallon jug till it is full. There is now 2 gallons left.

##### Share on other sites
Quote:
 Original post by stevenmarkyWhat does this have to do with artificial intelligence?I've heard variations of this puzzle before.Interestingly (is that a word?), I don't think ai would have much trouble solving this problem (genetic algorithms/minimax would solve this easily).

Why? Why? whyyyyyy would you use genetic algorithms to solve a problem like that? Strong basics, guys. Even minimax is innapropriate. Simple state representation, very few actions possible, no good scoring/heuristic possible, solution is very short: this is the job for a simple breadth-first search.

##### Share on other sites
alvaro    21246
Quote:
 Original post by SteadtlerWhy? Why? whyyyyyy would you use genetic algorithms to solve a problem like that? Strong basics, guys. Even minimax is innapropriate. Simple state representation, very few actions possible, no good scoring/heuristic possible, solution is very short: this is the job for a simple breadth-first search.

That's my opinion too. If you prefer solutions that don't waste a lot of water, use Dijkstra's algorithm (very similar to breadth-first search).

##### Share on other sites
Sneftel    1788
Quote:
 Original post by SteadtlerWhy? Why? whyyyyyy would you use genetic algorithms to solve a problem like that? Strong basics, guys. Even minimax is innapropriate. Simple state representation, very few actions possible, no good scoring/heuristic possible, solution is very short: this is the job for a simple breadth-first search.

You're right, GAs aren't appropriate for this. So I guess NNs must be the way to go. [grin]

##### Share on other sites
CyberSlag5k    514
Die Hard 3, FTW.

I've had this come up in school, during an interview, and even as a puzzle in a D&D campaign. There's really no trick to it, just brute force your way to a solution. Either way you go (which jug you start with, I mean) will get you there.

##### Share on other sites
Quote:
 Original post by CyberSlag5kDie Hard 3, FTW.I've had this come up in school, during an interview, and even as a puzzle in a D&D campaign. There's really no trick to it, just brute force your way to a solution. Either way you go (which jug you start with, I mean) will get you there.

Wow. Im no big fan of puzzle questions in interviews, I would avoid like the plague any business that ask such a cliché puzzle.

Cheers to Sneftel who is trying to raise my temper :P

##### Share on other sites
stevenmarky    369
I guess I just meant any brutish force algorithm would solve this easily.
Quote:
 Why didn't you say that then?

Shutup!
Well anyway, I have a generic minimax algorithm which could be applied to this problem easily (you could also set the amount of players, in this case it would be one).

##### Share on other sites
Quote:
Original post by stevenmarky
I guess I just meant any brutish force algorithm would solve this easily.
Quote:
 Why didn't you say that then?

Shutup!
Well anyway, I have a generic minimax algorithm which could be applied to this problem easily (you could also set the amount of players, in this case it would be one).

How would you score each "board" for minimax? Quantity of water in each jug is no indication of or close you are to "winning"

##### Share on other sites
stevenmarky    369
I could just score 1 if either bucket contained the right amount of water.

##### Share on other sites
Sneftel    1788
A one-player minmax search with no heuristic and without iterative deepening is just depth-first search, which isn't really appropriate here.

##### Share on other sites
JBourrie    1204
Hehe, he said jugs.

##### Share on other sites
Rockoon1    104
Given practical alternatives for this class of problem:

Genetic Search
Mini-Max Search
Dijkstra Search

A few other alternatives:

Monte-Carlo Search
Beam Search
Annealing Search

Note that they are all algorithms suited to searching a state space, and they are all more or less just as easily implimented.

They each carry some garantees with them.. Not all of them can guarantee a 'best' solution in finite time. Some guarantee better "worst case" runtime than others.

Some have an implied (but not garanteed) 'early convergence' rate and will likely produce a 'good' but not necessarily 'best' solution while examining only a very small fraction of the search space. The best early convergers are (unfortunately) more oft than not the search strategies with the greatest (sometimes infinite) 'worst case's'

The 'practical meaning' of the garantees and implications are all mediated by the size of the search space.

In this specific case the search space is extremely small and I conclude that the Best(tm) algorithm here would be something of the breadth-first brute-force variety although all the methods here will produce the best solution in only a few steps.

None of these search algorithms require a great deal of effort to impliment although many 'optimisations' can significantly effect code complexity. For instance, adding a transposition table to the minimax algorithm significantly reduces the size of search space. Some of the stochastic search algorithms have parameters which can be tweaked to significantly effect the rate of early and late convergence.

Another big area of A.I. which isnt really applicable here is the Machine Learning methods, such as back propogation neural nets and actor/critic models. You would only apply these algorithms if it is impossible or impractical to trivialy assign a value to a state transition (ie, you want the algorithm to learn the value of each state transition on its way to a step-wise solution)

##### Share on other sites
Timkin    864
Quote:
 Original post by SneftelYou're right, GAs aren't appropriate for this. So I guess NNs must be the way to go. [grin]

No Sneftel... definitely not the right way to go... what this problem needs is a 5 man-year budget. Lots of researchers to ponder the problem... lots of programmers to implement the solution... and plenty of cash for beer and pizza! ;)

##### Share on other sites
Quote:
Original post by Timkin
Quote:
 Original post by SneftelYou're right, GAs aren't appropriate for this. So I guess NNs must be the way to go. [grin]

No Sneftel... definitely not the right way to go... what this problem needs is a 5 man-year budget. Lots of researchers to ponder the problem... lots of programmers to implement the solution... and plenty of cash for beer and pizza! ;)

Are you saying we need a Jugs Comitee? Im in!

##### Share on other sites
Guest Anonymous Poster
I'd just eyeball it... who cares if you get 2.0 or 2.1 gallons?

##### Share on other sites
Uh I had this problem in an exam at college.

Breadth first search does it. Dijkstra is definitely overkill since there is no associated weight in the transitions (unless you wanted to spend the least amount of water or something) and the problem is not linear so minmax is out. Genetic algorithm? for a (roughly) 12-state FSM? git out! Neural networks? Okay, maybe in a few years of random training you'll happen to walk into the solution by chance.

Doing the graph will give you ALL possible solutions, just find all possible paths to the states where the 4-gallon jug has 2 gallons in it.

PS: two jugs... heh heh

##### Share on other sites
Quote:
 I'd just eyeball it... who cares if you get 2.0 or 2.1 gallons?

ha ha ha that's the old "Die Hard" problem. they have like 2 minutes to solve it b4 a bomb goes off. if it's even an ounce over... bomb goes off too so it has to be exact.

after insulting each other with white boy and nigga jokes for 1:40, they all of a sudden solve it in like 20 seconds.

for something like this though trial-and-error (fill this one, empty this one, pour from one to the other) works best, lest ur coding an actual algorithm.

##### Share on other sites
gorogoro    122
Just put it in Prolog and it would find the solution...

##### Share on other sites
Asbestos    169
Quote:
 Original post by gorogoroJust put it in Prolog and it would find the solution...

Yes, but that's just because Prolog uses breadth-first search anyway (unless you flip the order of the parentheses, and then you're doing depth-first search, and you might end up not finding the solution. Which goes to show that you ought to know what you're doing in Prolog).

##### Share on other sites
clb    2147
Wow, now this is amazing. We have neural networks, genetic searches and minimax decision trees solving a problem where Euclid's algorithm works - and as an added bonus - it tells you whether there even is a solution for the given numbers.