use strict;
my @slots;
my $max = 10;
my $empty = 0;
my $sum_moves = 0;
my %rlookup;
my $trials = 3;
my $min_moves = $max*$max;
my $max_moves = 0;

# initialize @slots
$slots[$_] = $_ for (0..$max);
srand time;

for my $ct (1..$trials) {
   # randomize @slots
   for (1..$max) {
      my $rand = int(rand $max) + 1;
      ($slots[$_], $slots[$rand]) = ($slots[$rand], $slots[$_]);
   }

   %rlookup = ();
   build_hash();
   my $moves = 0;
   my $unordered = inorder();
   while ($unordered || $empty) {
      print join " ", @slots, " \$empty: $empty  ";
      if ($slots[0] != 0) {
         print "move($rlookup{$empty}, $empty);\n";
         $slots[$empty] = $rlookup{$slots[$empty]};
         $slots[$rlookup{$empty}] = 0;
         $empty = $rlookup{$empty};
      } else {
         print "move($unordered, $empty);\n";
         ($slots[$empty], $slots[$unordered]) = ($slots[$unordered], $slots[$empty]);
         $empty = $unordered;
      }
      $moves++;
      build_hash();
      $unordered = inorder();
   }
   print join " ", @slots, " \$empty: $empty\n";
   print "Trial: ", pack("A5", $ct), "  Moves: $moves\n\n";
   $min_moves = $moves if $moves < $min_moves;
   $max_moves = $moves if $moves > $max_moves;
   $sum_moves += $moves;
}

print "Number of slots: $max\n";
print "Trials: $trials\n";
print "Average Moves: ", $sum_moves / $trials, "\n";
print "Minimum Moves: ", $min_moves, "\n";
print "Maximum Moves: ", $max_moves, "\n";

sub inorder {
   my $i;
   for (1..$max) {
      $i = $_;
      last if $_ != $slots[$_];
   }
   return $i % $max;
}

sub build_hash {
  $rlookup{$slots[$_]} = $_ for (0..$max);
}