Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re: sort with fewest moves

by jlongino (Parson)
on Feb 12, 2002 at 08:33 UTC ( #144814=note: print w/replies, xml ) Need Help??


in reply to sort with fewest moves

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.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://144814]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (3)
As of 2022-01-29 00:59 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    In 2022, my preferred method to securely store passwords is:












    Results (74 votes). Check out past polls.

    Notices?