Sign in to follow this  
davidrachel

do you know this water jug problem

Recommended Posts

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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Quote:
Original post by stevenmarky
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).


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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Quote:
Original post by Steadtler
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.

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

Share this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Quote:
Original post by CyberSlag5k
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.


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 this post


Link to post
Share on other sites
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 this post


Link to post
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 this post


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

Share this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
You'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 this post


Link to post
Share on other sites
Quote:
Original post by Timkin
Quote:
Original post by Sneftel
You'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 this post


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

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by gorogoro
Just 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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this