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



Disqualifications
 
 

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
 



Winners
 

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.
 


Honorable Mentions:
 

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.
 
 
 

photoDavid Nicol <gratuitoushyphenizations@tipjar.com> now no longer wonders what grading papers at the end of the semester must be like.