Rats! I figured someone would beat me to a solution. I
haven't looked closely at
hossman's. I came up with the
solution without looking at any references. Mine has
configurable parameters, produces some elementary stats,
and is shorter :P. It can be improved I'm sure, but I was
just happy to finish it. Specifically, instead of
rebuilding the entire hash, the changed key/values could be
updated. TIMTOWTDI!
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);
}
Sample Output
0 2 3 7 6 4 10 5 8 9 1 $empty: 0 move(1, 0);
2 0 3 7 6 4 10 5 8 9 1 $empty: 1 move(10, 1);
2 1 3 7 6 4 10 5 8 9 0 $empty: 10 move(6, 10);
2 1 3 7 6 4 0 5 8 9 10 $empty: 6 move(4, 6);
2 1 3 7 0 4 6 5 8 9 10 $empty: 4 move(5, 4);
2 1 3 7 4 0 6 5 8 9 10 $empty: 5 move(7, 5);
2 1 3 7 4 5 6 0 8 9 10 $empty: 7 move(3, 7);
2 1 3 0 4 5 6 7 8 9 10 $empty: 3 move(2, 3);
2 1 0 3 4 5 6 7 8 9 10 $empty: 2 move(0, 2);
0 1 2 3 4 5 6 7 8 9 10 $empty: 0
Trial: 1 Moves: 9
0 5 8 10 6 2 9 3 7 1 4 $empty: 0 move(1, 0);
5 0 8 10 6 2 9 3 7 1 4 $empty: 1 move(9, 1);
5 1 8 10 6 2 9 3 7 0 4 $empty: 9 move(6, 9);
5 1 8 10 6 2 0 3 7 9 4 $empty: 6 move(4, 6);
5 1 8 10 0 2 6 3 7 9 4 $empty: 4 move(10, 4);
5 1 8 10 4 2 6 3 7 9 0 $empty: 10 move(3, 10);
5 1 8 0 4 2 6 3 7 9 10 $empty: 3 move(7, 3);
5 1 8 3 4 2 6 0 7 9 10 $empty: 7 move(8, 7);
5 1 8 3 4 2 6 7 0 9 10 $empty: 8 move(2, 8);
5 1 0 3 4 2 6 7 8 9 10 $empty: 2 move(5, 2);
5 1 2 3 4 0 6 7 8 9 10 $empty: 5 move(0, 5);
0 1 2 3 4 5 6 7 8 9 10 $empty: 0
Trial: 2 Moves: 11
0 6 7 4 5 2 3 1 8 9 10 $empty: 0 move(1, 0);
6 0 7 4 5 2 3 1 8 9 10 $empty: 1 move(7, 1);
6 1 7 4 5 2 3 0 8 9 10 $empty: 7 move(2, 7);
6 1 0 4 5 2 3 7 8 9 10 $empty: 2 move(5, 2);
6 1 2 4 5 0 3 7 8 9 10 $empty: 5 move(4, 5);
6 1 2 4 0 5 3 7 8 9 10 $empty: 4 move(3, 4);
6 1 2 0 4 5 3 7 8 9 10 $empty: 3 move(6, 3);
6 1 2 3 4 5 0 7 8 9 10 $empty: 6 move(0, 6);
0 1 2 3 4 5 6 7 8 9 10 $empty: 0
Trial: 3 Moves: 8
Number of slots: 10
Trials: 3
Average Moves: 9.33333333333333
Minimum Moves: 8
Maximum Moves: 11
--Jim
Update: Hmmm . . . after much thought, this
approach uses the first out-of-sequence slot for the
initial move. Once the initial move is made, the rest is
optimal, but it raises a potential flaw--perhaps by
pre-testing each of the unordered initial moves, the
optimal solution for any given trial could be determined.
I'll do some more experimenting and post the results.