water jug problem in recursive

i just learn about recursive and i was amazed with the logic, so i just want to learn. some questions came up: water jug problem at die hard 3 movie, this puzzle i posted, permutation, etc, but i still failed to solve them.

sorry i don't understand what do you mean with the goal of the task, i think it's just a common puzzle game, there are some more difficult variants but i think i can start learning from this first.

also please check my questions history, i am not new member, i've been working as programmer since 1999 and never touch school stuff anymore :)

It's quite a nice algorithm to develop, however a google search revealed a LOT of matches - you should look a little harder ;)

Here's a nice little page which because it has a few applets to play with, will probably explain it clearer than I can using text and code on here

http://www.cut-the-knot.org/ctk/Water.shtml

thx for the link, FentonEng. Actually i have read the link you gave, also in wikipedia about search algorithm, i understand about the logic but it's difficult for me to implement it with the recursive function.

Normally recursion side-steps some logic in return for lots of nested functions calls. However in this instance I believe it would be far easier to have a loop do all of the logical processing and have you put in a control statement to check for your target capacity. You are essentially going to have to "step" through the algorithm, recursion is only going to hinder you in this case.

Have you got any base code you have started to work on yet?

>>>> sorry i don't understand what do you mean with the goal of the task
I mean that you didn't mention that the water should be equally divided into the jugs (according to the link Fenton showed). I am still unsure why 2 2 3 is a solution then? Shouldn't it 2 litres in the last jug as well?

>>>> i think it's just a common puzzle game
I know a variant of the puzzle where you have to gauge a given amount into one of the jugs, e. g. 2 litres in your sample, though I don't know whether the solutions were similar.

I do think you (wuyinzhi) should play with the triangular co-ordinates applet with the trace function "on", to see exactly what is happening in geometric terms.

If I understand your question correctly you are interested in how the algorithm is developed, over trying to generate a particular solution. The problem does have a specific end criteria, so if you *did* want 2, 2, 3 as a valid solution, then the algorithm could grant you it. I am going to side with itsmeandnobodyelse (possible spelling error in there sorry!) and ask you for a slightly rephrased and more focused question

A = 0, B = 0, C = 0
A = 7, B = 0, C = 0
A = 3, B = 4, C = 0
A = 3, B = 1, C = 3
A = 6, B = 1, C = 0
A = 6, B = 0, C = 1
A = 2, B = 4, C = 1
A = 2, B = 2, C = 3

morning all,

yes i think ozo's comment made it clear. what i want to develop is the algorithm and display the steps of how the jugs are transfer each other till finally display 2,2,3.

my analysis so far:

- there are 6 possible moves:
 A fill B
 A fill C
 B fill A
 B fill C
 C fill A
 C fill B

the problem of my code is it returns out of stack because there are some states (ex. 7,0,0) repeat infinitely, should i save every states in table/array?



 

Private Sub Form_Load()
    puzzle 7, 0, 0
End Sub
 
Private Sub puzzle(ByVal t7 As Integer, ByVal t4 As Integer, ByVal t3 As Integer)
Dim i As Integer
 
    If t7 = 2 And t4 = 2 And t3 = 3 Then
        MsgBox "complete."
    Else
    
                i = fill(t7, t4, 4)
                puzzle abc(t7 + t4 - 4), i, t3
                i = fill(t7, t3, 3)
                puzzle abc(t7 + t3 - 3), t4, i
                i = fill(t4, t3, 3)
                puzzle t7, abc(t4 + t3 - 3), i
                i = fill(t4, t7, 7)
                puzzle i, abc(t4 + t7 - 7), t3
                i = fill(t3, t4, 4)
                puzzle t7, i, abc(t3 + t4 - 4)
                i = fill(t3, t7, 7)
                puzzle i, t4, abc(t3 + t7 - 7)
        
    End If
    
End Sub
 
Private Function abc(ByVal n As Integer) As Integer
    If n < 0 Then
        abc = 0
    Else
        abc = n
    End If
End Function
 
Private Function fill(ByVal source As Integer, ByVal dest As Integer, ByVal capacity As Integer) As Integer
 
    fill = dest + source
    If fill > capacity Then fill = capacity
 
End Function
                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:

What I did was to not save states that had been generated before.
I also included the moves
fill A
fill B
fill C
empty A
empty B
empty C
but it turned out that the shortest path did not use any of them except for fill A

It is a different method than what I did, but there are many methods that work.
Recursion may be more natural for a depth first search, but I did a breadth first search so I can stop when I find the shortest path,
and only used recursion to print the path.

Your fill function is still broken. I keep thinking that a tree would solve the general case more efficiently, but you are limited with respects to that in VB

hi FentonEng n other experts, can you provide some code/clue how to solve the problem maybe in another language? actually i just curious how it can be done with recursion effectively.  I read all of your comments but still can't get it.

I would break the problem down into "moves" ie transfers (from one to another), fills (fill one jar to the top) and empties (empty a jar) . Generate a "tree" data structure based on combinations and permutations of the said "moves" then apply an algorithmic approach to clip away the tree using constraints and "bad" moves.

What is left will be a family of solutions, which I could then simply traverse in turn to find the shortest one.

I would stay away from recursion until you can get the basic steps and a plan together. I really don't see any need for it, except perhaps for the "tree" facility.

Once I was satisfied I had the "tree" approach covered, I would look at ways of "removing" the tree and performing a direct determined calculation for each step.

There is probably a standard approach for this type of problem, but that is how I would approach the problem from first principles.

FWIW: By "tree" I *mean* a hierarchial data structure, the tree does not have a pre-determined number of roots, branches, nodes, children or any imposed limits whatsoever beyond that of a standard heirarchial structure.

dear FentonEng, i see your method is similar with ozo's, using fill and empty procedure/function. Something i don't understand is why we should fill and empty? since i guess this problem is about transfer x to y?

not necessary in this particular problem, but other problems in this genre may include them.

The fill/empty were just "possible" moves as your original question didn't specify any particular rules over handling the jugs itself.

*Just* having transfers makes the problem simplify a fair bit, but you haven't made a transfer function yet! You *literally* have a fill function and not a transfer function. That was a subtle error and point of your source code I was hoping you had seen.

Firstly, correct your transfer function, then you may be able to see if the rest of your program is close to a solution.

You seem to understand the recursion process itself, so your next task would be a case of converting an algorithm into an iterative process, then recursing through the steps.

ok FentonEng, i'll try your suggestion, thanks. Sorry for this long thread as i am doing this for fun and learning purpose, so my responses maybe not so fast.