Re^2: Challenge: N Jugs Problem

I saw your node when I was about to post a solution that uses the technique you mentioned, so I'll post it here. It saves me from explaining it :)

Such as solution for the first problem:

# perl min_steps.pl x_size y_size z_target

use strict;
use warnings;

use List::Util    qw( min );
use Math::Numbers qw( );

use constant {
   X => 0, Y => 1, Z => 2,   # state and args
   STEPS => 3,               # state
   SZ_X => 3, SZ_Y => 4,     # args
};


sub bounded {
   my ($src_idx, $dst_idx) = @_;
   return sub {
       my $xfer = min($_[$src_idx], $_[$dst_idx+SZ_X]-$_[$dst_idx]);
       return 0 if $xfer == 0;
       $_[$src_idx] -= $xfer;
       $_[$dst_idx] += $xfer;
       return 1;
   };
}

my %ops = (
  #'S->S' => sub { 0 },
  #'S->Z' => sub { 0 },
  #'X->X' => sub { 0 },
  #'Y->Y' => sub { 0 },
  #'Z->Z' => sub { 0 },

   'X->S' => sub { return 0 if $_[X]==0; $_[X]=0; 1 },
   'Y->S' => sub { return 0 if $_[Y]==0; $_[Y]=0; 1 },
   'Z->S' => sub { return 0 if $_[Z]==0; $_[Z]=0; 1 },

   'S->X' => sub { return 0 if $_[X]==$_[SZ_X]; $_[X]=$_[SZ_X]; 1 },
   'S->Y' => sub { return 0 if $_[Y]==$_[SZ_Y]; $_[Y]=$_[SZ_Y]; 1 },

   'Y->X' => bounded(Y, X),
   'Z->X' => bounded(Z, X),

   'X->Y' => bounded(X, Y),
   'Z->Y' => bounded(Z, Y),

   'X->Z' => sub { return 0 if $_[X]==0; $_[Z]+=$_[X]; $_[X]=0; 1 },
   'Y->Z' => sub { return 0 if $_[Y]==0; $_[Z]+=$_[Y]; $_[Y]=0; 1 },
);

my @ops = keys %ops;



{
   my ($sz_X, $sz_Y, $target) = @ARGV ? @ARGV : (3, 5, 4);

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

   my @states = [ 0,0,0, () ];

   for (;;) {
      my $state = shift(@states);

      if ($state->[Z] == $target) {
         print(@$state - STEPS, " steps:\n");
         print("   $state->[$_]\n") for STEPS..$#$state;
         last;
      }

      for my $op (@ops) {
          my @new_state = @$state;
          next if !$ops{$op}->(
             $new_state[X], $new_state[Y], $new_state[Z],
             $sz_X, $sz_Y
          );
          push @new_state, $op;
          push @states, \@new_state;
      }
   }
}
[download]

7 steps:
   S->X
   X->Z
   S->X
   X->Z
   Z->Y
   S->X
   X->Z
[download]

And for the second problem

# perl min_supply.pl x_size y_size z_target

use strict;
use warnings;

use List::Util    qw( max min sum );
use Math::Numbers qw( );

use constant {
   X => 0, Y => 1, Z => 2,    # state and args
   S => 3, STEPS => 4,        # state
   SZ_X => 3, SZ_Y => 4,      # args
};


sub bounded {
   my ($src_idx, $dst_idx) = @_;
   return sub {
       my $xfer = min($_[$src_idx], $_[$dst_idx+SZ_X]-$_[$dst_idx]);
       return 0 if $xfer == 0;
       $_[$src_idx] -= $xfer;
       $_[$dst_idx] += $xfer;
       return 1;
   };
}

my %ops = (
  #'S->S' => sub { 0 },
  #'S->Z' => sub { 0 },
  #'X->X' => sub { 0 },
  #'Y->Y' => sub { 0 },
  #'Z->Z' => sub { 0 },

   'X->S' => sub { return 0 if $_[X]==0; $_[X]=0; 1 },
   'Y->S' => sub { return 0 if $_[Y]==0; $_[Y]=0; 1 },
   'Z->S' => sub { return 0 if $_[Z]==0; $_[Z]=0; 1 },

   'S->X' => sub { return 0 if $_[X]==$_[SZ_X]; $_[X]=$_[SZ_X]; 1 },
   'S->Y' => sub { return 0 if $_[Y]==$_[SZ_Y]; $_[Y]=$_[SZ_Y]; 1 },

   'Y->X' => bounded(Y, X),
   'Z->X' => bounded(Z, X),

   'X->Y' => bounded(X, Y),
   'Z->Y' => bounded(Z, Y),

   'X->Z' => sub { return 0 if $_[X]==0; $_[Z]+=$_[X]; $_[X]=0; 1 },
   'Y->Z' => sub { return 0 if $_[Y]==0; $_[Z]+=$_[Y]; $_[Y]=0; 1 },

);

my @ops = keys %ops;



{
   my ($sz_X, $sz_Y, $target) = @ARGV ? @ARGV : (3, 5, 4);

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

   my @states = [ [ 0,0,0, 0, () ] ];
   my $best = 0;
   my %seen;

   for (;;) {
      ++$best, next if !$states[$best] || !@{ $states[$best] };
      my $state = shift(@{ $states[$best] });

      if ($state->[Z] == $target) {
         print("Required supply: $state->[S]\n");
         print(@$state - STEPS, " steps:\n");
         print("   $state->[$_]\n") for STEPS..$#$state;
         last;
      }

      for my $op (@ops) {
          my @new_state = @$state;
          next if !$ops{$op}->(
             $new_state[X], $new_state[Y], $new_state[Z],
             $sz_X, $sz_Y
          );

          $new_state[S] = max(
             $new_state[S],
             sum($new_state[X], $new_state[Y], $new_state[Z]),
          );

          next if $seen{join(':',
             $new_state[X], $new_state[Y], $new_state[Z], $new_state[S
+]
          )}++;

          push @new_state, $op;
          push @{ $states[$new_state[S]] }, \@new_state;
      }
   }
}
[download]

Required supply: 6
7 steps:
   S->X
   X->Z
   S->X
   X->Z
   Z->Y
   Y->X
   X->Z
[download]

Being the brute-force approach, I wrote is as a baseline for verification and benchmarking.

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