David
Nicol <gratuitoushyphenizations@tipjar.com> now no longer wonders
what grading papers at the end of the semester must be like.
Solitaire 500 results
"Trust in the Lord, and our internal representation"
--
Dave Shield, Liverpool U. CS dept.
On May first, 1999, an otherwise air-conditioned room deep within the University of Missouri - Kansas City's Computing Services department was transformed for a brief eight hours into the mission control center for what may very well have been the first ever programming contest of its kind, the Solitaire 500, described in TPJ #13.
As you might recall, all programs entered in the Solitaire 500 run simultaneously on the same computer. They must make a network connection to a server running on a different computer and solve an identical series of five hundred problems presented by the server. The first to complete the series of problems wins.
Nineteen entries reached the contest's e-mail inbox before the morning
of May first and of these seventeen were able to complete the trial run
of fifty puzzles.
Number Name
1 Theo Van Dinter
2 Joseph A. Diverdi
3 Steven W. McDougall
4 Eero Pajarre
5 Mark Kvale
6 Dave Shield
7 Andreas Gross
8 James P. Williams
9 David Brandt
10 Stephen M Moraco
11 John Whitmore
12 Edward M. Perry
13 Jack Applin
14 Robert Au
15 Ira Joseph Woodhead
16 Erle Schuyler
17 Yanick Champoux
18 Jeff Norden
19 Peter J Jones
Erle Schuyler's entry #16 froze in an internal loop.
If only Yanick Chanpoux could keep English and French separate
in his mind he might have won. See if you can spot the spelling inconsistency
in his Connect subroutine that prevented entry 18 from qualifying.
The word in question is always spelled correctly! Chanpoux did not catch
his simple mistake since he tested his program with a blank password, perhaps
someone will correct his program and test it. In fact this is being arranged
right now; we should know before this article is submitted for summer TPJ
publication.
##############################################
#
# Connect
# Connect Mercury to the Wheels server.
#
sub Connect($$)
{
# Get all the registration infos.
my( $pilot, $licence_plate ) = @_;
my $formula = $ENV{'SWP_SERVERPORT'} || 5200;
my $raceway = $ENV{'SWP_SERVERNAME'} || 'localhost';
print "Trying to connect to $raceway $formula",
" as $pilot:$license_plate\n";
my $iaddr = inet_aton($raceway)
|| die "Cannot find raceway named $raceway";
my $paddr = sockaddr_in($formula,$iaddr);
my $proto = getprotobyname('tcp');
socket(SOCK, PF_INET, SOCK_STREAM, $proto) || die "socket:
$!";
Connect(SOCK, $paddr) || die "connect: $!";
SOCK->autoflush(1);
( my $ServerLine = <SOCK> ) or die "read error: $!";
print "official:$ServerLine\n";
print "mercury:$pilot:$license_plate\n";
print SOCK "$pilot:$license_plate\n";
$ServerLine = <SOCK> || die "read error: $!";
print "official:$ServerLine\n";
die "Protocol error or bad name:password"
unless $ServerLine =~ /^OK/;
};
The other seventeen entries successfully completed the five hundred decks of cards over the next eleven hours:
> grep 'OK FI' competition_log
925611991 entry4 aai OK FI NI SH ED time 1527 round 6653
move 81951
925612196 entry3 aac OK FI NI SH ED time 1732 round 9345
move 108969
925612235 entry8 aaf OK FI NI SH ED time 1771 round 8376
move 72820
925612518 entry11 aab OK FI NI SH ED time 2054 round
8721 move 84869
925612702 entry6 aal OK FI NI SH ED time 2238 round 8105
move 96577
925612904 entry7 aaj OK FI NI SH ED time 2440 round 8861
move 101499
925612999 entry14 aak OK FI NI SH ED time 2535 round
10268 move 141576
925614674 entry19 aac OK FI NI SH ED time 4210 round
27908 move 312841
925614893 entry5 aap OK FI NI SH ED time 4429 round 7208
move 84750
925615025 entry12 aai OK FI NI SH ED time 4561 round
6725 move 79026
925615396 entry18 aaa OK FI NI SH ED time 4931 round
5566 move 64495
925615434 entry1 aah OK FI NI SH ED time 4970 round 5948
move 77961
925633669 entry15 aal OK FI NI SH ED time 23205 round
10871 move 91375
925634034 entry10 aab OK FI NI SH ED time 23570 round
9353 move 114787
925635423 entry2 aan OK FI NI SH ED time 24959 round
8932 move 78288
925641828 entry9 aan OK FI NI SH ED time 31364 round
6727 move 93842
925650130 entry13 aar OK FI NI SH ED time 39666 round
41316 move 317819
Eero Pajarre's entry #4, which averaged only 9.7 rounds per deck in the qualifying trial, reoptimized for speed in the main contest and won with an average time per deck of slightly more than three seconds. Developing with precompiled binaries of ActiveState perl and GNU Emacs under Microsoft Windows 95, Pajarre optimized pickup order for most discards available next round and compiled a table of eight and twelve card situations. Then with the help of use Benchmark he realized that switching to string representations would save much time.
His canonic function converts decks represented as strings of card rank letters into patterns for the pre-solved table:
sub canonic($){
my($d)=@_;
my($res)="";
my($ind)="";
my($c,$i);
for($i=0;$i<length($d);$i++){
$c=substr($d,$i,1);
if (0>index($ind,$c)){
$ind .= $c;
}
$res .= chr(ord('0')+index($ind,$c));
}
return $res;
}
This is the final ps listing before Pajarre finished. At this point
he had used the least CPU of all entries with good loop avoidance that
weren't blocking for input!
Sat May 1 21:25:00 CDT 1999
USER PID %CPU %MEM SIZE RSS TTY STAT START TIME COMMAND
entry1 17264 6.6 1.8 2416 1804 p3 R 20:54 2:03 perl entry.pl
entry2 17253 0.6 2.0 2560 1936 pd S 20:54 0:12 perl entry.pl
entry3 17235 4.5 1.9 2464 1852 q1 R 20:53 1:26 perl entry.pl
entry4 17237 4.4 2.0 2600 1984 pf R 20:53 1:24 perl entry.pl
entry5 17247 6.4 2.4 2916 2320 pe R 20:53 2:02 perl entry.pl
entry6 17245 4.8 1.9 2500 1884 q0 R 20:53 1:32 perl entry.pl
entry7 17241 5.5 2.3 2824 2216 q3 R 20:53 1:45 perl entry.pl
entry8 17239 4.7 1.9 2480 1860 q2 R 20:53 1:30 perl entry.pl
entry9 17255 4.1 2.1 2632 2024 q4 R 20:54 1:16 perl entry.pl
entry10 17266 0.6 2.4 2968 2360 p4 S 20:54 0:12 perl
entry.pl
entry11 17262 5.1 1.9 2424 1820 p5 R 20:54 1:35 perl
entry.pl
entry12 17251 6.5 1.9 2488 1872 pa S 20:53 2:02 perl
entry.pl
entry13 17259 0.1 1.9 2508 1892 p7 S 20:54 0:03 perl
entry.pl
entry14 17257 5.3 2.0 2556 1944 pb R 20:54 1:40 perl
entry.pl
entry15 17261 0.3 2.0 2528 1920 p6 R 20:54 0:06 perl
entry.pl
entry18 17249 7.0 3.2 3684 3072 p9 R 20:53 2:13 perl
entry.pl
entry19 17243 4.3 1.8 2404 1792 pc R 20:53 1:23 perl
entry.pl
Steven W. McDougal's entry #3, a completely commentless six page
program that nevertheless reads like a chess match, came in second. By
using arrays and array references for his internal representations, McDougal's
program was able to generate workable solutions faster than the next four
finishers could generate shorter solutions. His Partition function
uses bitmasks to determine if the lengths of arrays are divisible by four:
sub Partition
{
my($stacks, $block4) = @_;
my $s1 = scalar @{$Tab[$stacks->[1]]};
my $s2 = scalar @{$Tab[$stacks->[2]]};
my $s3 = scalar @{$Tab[$stacks->[3]]};
$block4 & 3 or return @$stacks;
($block4 + $s1 ) & 3 or return @$stacks[1, 0, 2,
3];
($block4 + $s2 ) & 3 or return @$stacks[2, 0, 1,
3];
($block4 + $s1 + $s2 ) & 3 or return @$stacks[1,
2, 0, 3];
($block4 + $s3) & 3 or return @$stacks[3, 0, 1, 2];
($block4 + $s1 + $s3) & 3 or return @$stacks[1, 3,
0, 2];
($block4 + $s2 + $s3) & 3 or return @$stacks[2, 3,
0, 1];
($block4 + $s1 + $s2 + $s3) & 3 or return @$stacks[1,
2, 3, 0];
()
}
Jim Williams's Expert.pm, #8, the only entry to have more than
one file of program code, also the only entry to have full pod,
came in third. After he settled on an algorithm to use, Williams made extensive
use of Benchmark and
Devel::DProf to guide his choice of
constructions, inlining several pieces of code that had been separate subroutines.
High points of his entry's extensive comments include benchmarking results
and explanations of the optimizations. His
%permutations hash, a
hash of pointers to arrays of pointers to the arrays that hold the layed
cards (a HoLoL, to try to quote perldsc(1)), allowed him to quickly construct
the decks that result from the various pickup instructions so as to choose
one that would provide at least one discard the following round. Using
"early pickups" to prevent missed discards, Williams's entry has the second
lowest total number of moves in the contest, after Norden.
Dave Shield's entry #6 made extensive use of regular expressions
Mark Kvale's entry #5 was the only entry to include an external
database. Kvale's Simulate routine provides the same functionality
as Williams's array-reference based @{$Permutations{$piles}} with
this verbose slice:
# create the deck after pickup
@order = split //, $perm;
@deck = (@{$pile[$order[0]]}, @{$pile[$order[1]]},
@{$pile[$order[2]]}, @{$pile[$order[3]]});
Jeff Norden's "RACE CAR" #18, using a full 2-rounds-deep heuristic as well as a hash of eight-card situations, achieved the best round count of the contest. However Norden did not achieve that result without spending more CPU time than any other entry:
foreach $order (@Pickups) {
@deck=map( @{$_}, @stack[@{$pickup_list{$order}}]
);
play_and_score();
};
Theo Van Dinter's Entry #1 was the last of the entries that offered
more than one move command within a single instruction to complete the
puzzles.
After it finished, delays were disabled by removing the Delay file from
the server's directory. Dynamic alteration of the server program's behavior
was done using file-system semaphores, which perl's abundant file tests
make trivial:
# Wait for the "green flag" to appear
while (! -e 'GreenFlag'){
Log $name,"Waiting for green flag"
unless time % 25;
sleep 1;
};
my $BTIME=time;
Log "GreenFlag seen";
$$Table{'BeginTime'} = time;
while( $line = <$Sock> ){
Log $name,$line;
# move-containing instructions are allowed once per second
if ($line =~ m/\b[321][210]\b/){
if(-e 'Delays'){while ($TimeOfLastMove == time){
# wait a twentieth of a second
select(undef,undef,undef,0.05);
};};
$TimeOfLastMove = time;
};
Unlike C, perl's if requires brackets even when there is only
one statement in the conditional block.
Ira Joseph Woodhead (#15): $ENV{'USER'} is a more portable construction
than `whoami`
Stephen M. Moraco (#10):
BEGIN {$Exporter::Verbose = 1; } is a good Package
debugging technique.
Joseph A. DiVerdi (#2) correctly noted that Wheels is based on
the game of solitaire known as "Perpetual motion." His entry achieved the
second-best move count, however it sent instructions frequently and spent
much time blocked for server response.
David
Nicol <gratuitoushyphenizations@tipjar.com> now no longer wonders
what grading papers at the end of the semester must be like.