Re^4: Challenge: N Jugs Problem

I initially had an infinite loop as well. It turned out that my program was investigating the following path:

X → S (pour X into supply)
S → X (fill X from supply)
X → S (pour X into supply)
S → X (fill X from supply)
X → S (pour X into supply)
S → X (fill X from supply)
...

The necessary step to proceed would have increased the necessary supply, but the program was busy investigating options that didn't increase the necessary supply. I ended up using a "seen" hash to avoid states I had already explored.

Even using a brute force approach, the program should find the solution instantly (at least for the values previously discussed in this thread) unless there is no answer. My program checks for that condition as follows:

   $target % Math::Numbers->new($sz_X, $sz_Y)->gcd() == 0
      or die("No solution\n");
[download]

Comment on Re^4: Challenge: N Jugs Problem Download Code

Replies are listed 'Best First'.
Re^5: Challenge: N Jugs Problem by kyle (Abbot) on Apr 15, 2009 at 15:57 UTC
Yes, I have a "seen" hash already. A couple of them. Har. Anyway, I showed that mine works with an easier problem: target jug size 3, other jugs sized 4 and 1. The least water solution is six steps: `000. [ 0/T 0/4 0/1 ] starting state 001. [ 0/T 0/4 1/1 ] fill jug 1 002. [ 1/T 0/4 0/1 ] pour jug 1 into target 003. [ 1/T 0/4 1/1 ] fill jug 1 004. [ 2/T 0/4 0/1 ] pour jug 1 into target 005. [ 2/T 0/4 1/1 ] fill jug 1 006. [ 3/T 0/4 0/1 ] pour jug 1 into target USED 3 units in 6 steps` [download] Fewest steps solution: `000. [ 0/T 0/4 0/1 ] starting state 001. [ 0/T 4/4 0/1 ] fill jug 0 002. [ 0/T 3/4 1/1 ] pour jug 0 into jug 1 003. [ 3/T 0/4 1/1 ] pour jug 0 into target USED 4 units in 3 steps` [download] I've put my code in Re: Challenge: N Jugs Problem	[reply] [d/l] [select]
Re^6: Challenge: N Jugs Problem by ikegami (Patriarch) on Apr 15, 2009 at 16:09 UTC
For comparison: `$ time perl min_supply.pl 1 4 3 Required supply: 3 6 steps: S->X X->Z S->X X->Z S->X X->Z real 0m0.011s user 0m0.016s sys 0m0.000s $ time perl min_steps.pl 1 4 3 3 steps: S->Y Y->Z Z->X real 0m0.011s user 0m0.008s sys 0m0.004s $ time perl -e1 real 0m0.002s user 0m0.000s sys 0m0.000s` [download] Note that I got a different solution that yours for min steps, but it's has the same number of steps. Update: I seemed to have imagined that you said yours was slow. Ignore this post.	[reply] [d/l]