Re^5: Challenge: N Jugs Problem


Welcome to the Monastery
	PerlMonks

Re^5: Challenge: N Jugs Problem

by kyle (Abbot)

on Apr 15, 2009 at 15:57 UTC ( [id://757710]=note: print w/replies, xml )

Need Help??

in reply to Re^4: Challenge: N Jugs Problem
in thread Challenge: N Jugs Problem

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

Comment on Re^5: Challenge: N Jugs Problem Select or Download Code

Replies are listed 'Best First'.

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]

In Section Seekers of Perl Wisdom