more useful options PerlMonks

### Re^3: Challenge: N Jugs Problem

by kyle (Abbot)
 on Apr 15, 2009 at 15:05 UTC ( #757695=note: print w/replies, xml ) Need Help??

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

I wrote my own solution (which I won't post, as several have now been posted) ...

I'd be interested to see that.

I did some more work on mine, and I got to where I thought it should find a minimum water solution, but it ran overnight without finishing.

Replies are listed 'Best First'.
Re^4: Challenge: N Jugs Problem
by ikegami (Pope) on Apr 15, 2009 at 15:32 UTC

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");

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

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

I've put my code in Re: Challenge: N Jugs Problem

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

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.

Re^4: Challenge: N Jugs Problem
by JavaFan (Canon) on Apr 19, 2009 at 19:18 UTC
I'd be interested to see that.
```#!/usr/bin/perl

use 5.010;

use strict;
use warnings;

my \$MINIMIZE_WATER = 1;

my \$X = 0;
my \$Y = 1;
my \$Z = 2;
my \$Water = 3;
my \$Move = 4;
my \$Previous = 5;
my \$MoveCount = 6;

my @trans = ('S -> X', 'S -> Y', 'X -> Y', 'X -> Z', 'Y -> X', 'Y -> Z
+',
'Z -> X', 'Z -> Y', 'X -> S', 'Y -> S');

my (\$Target, @LIMITS) = @ARGV;
\$LIMITS[\$Z] //= ~0;

package State;

sub new {
my \$class = shift;
bless [@_], \$class;
}

sub pour {
my \$self = shift;
my (\$from, \$to) = @_;

if (\$self->[\$from] + \$self->[\$to] <= \$LIMITS[\$to]) {
\$self->[\$to] += \$self->[\$from];
\$self->[\$from] = 0;
}
else {
\$self->[\$from] -= \$LIMITS[\$to] - \$self->[\$to];
\$self->[\$to] = \$LIMITS[\$to]
}
}

sub fill {
my \$self = shift;
my \$to = shift;
\$self->[\$Water] += \$LIMITS[\$to] - \$self->[\$to];
\$self->[\$to] = \$LIMITS[\$to];
}

sub empty {
my \$self = shift;
my \$from = shift;
\$self->[\$from] = 0;
}

sub trans {
my \$self = shift;
my \$trans = shift;

my \$New = State->new (@\$self);
\$New->[\$Move] = \$trans;
\$New->[\$Previous] = \$self;
\$New->[\$MoveCount] = \$self->[\$MoveCount] + 1;

given (\$trans) {
when ('S -> X') {\$New->fill(\$X)}
when ('S -> Y') {\$New->fill(\$Y)}
when ('X -> Y') {\$New->pour(\$X, \$Y)}
when ('X -> Z') {\$New->pour(\$X, \$Z)}
when ('Y -> X') {\$New->pour(\$Y, \$X)}
when ('Y -> Z') {\$New->pour(\$Y, \$Z)}
when ('Z -> X') {\$New->pour(\$Z, \$X)}
when ('Z -> Y') {\$New->pour(\$Z, \$Y)}
when ('X -> S') {\$New->empty(\$X)}
when ('Y -> S') {\$New->empty(\$Y)}
default {die \$trans}
}
\$New;
}

sub id {
my \$self = shift;
join ",", @\$self[\$X,\$Y,\$Z]
}

sub print {
my \$self = shift;
return unless \$self->[\$Move];
\$self->[\$Previous]->print;
printf "%2d. %s (X = %2d, Y = %2d, Z = %2d; Water = %2d)\n",
@\$self[\$MoveCount, \$Move, \$X, \$Y, \$Z, \$Water];
}

package main;

foreach my \$MINIMIZE_WATER (0, 1) {
my @QUEUE;
my %SEEN;

my \$start = State->new(0, 0, 0, 0, undef, undef, 0);
\$SEEN{\$start->id}++;

push @QUEUE, \$start;

LOOP:
while (1) {
my \$state = shift @QUEUE;
foreach my \$trans (@trans) {
my \$new = \$state->trans(\$trans);
next if \$SEEN{\$new->id}++;
if (\$new->[\$Z] == \$Target) {
\$new->print;
last LOOP;
}
push @QUEUE, \$new;
if (\$MINIMIZE_WATER) {
@QUEUE = sort {\$a->[\$Water] <=> \$b->[\$Water] ||
\$a->[\$MoveCount] <=> \$b->[\$MoveCount]}
+@QUEUE;
}
}
}
say "----";
}

__END__

Create A New User
Node Status?
node history
Node Type: note [id://757695]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (10)
As of 2017-07-25 17:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
I came, I saw, I ...

Results (376 votes). Check out past polls.