2008 Winter Scripting Games
Jan Dubois' Solution to Advanced Perl Event 7: Play Ball!
About the Author Jan Dubois is the tech lead for all Perl technologies at ActiveState. He is a member of the core Perl5-Porters group that maintains the Perl language implementation. Jan wrote the Win32::OLE Automation support for Perl while he was still working in the financial industry. He has a Masters degree in Physics from the University of Hamburg, Germany. Jan now lives in Vancouver in Beautiful British Columbia, home of the 2010 Winter Olympics. |
Play Ball!
In Event 7 of the 2008 Winter Scripting Games we get to play ball, and that means baseball around here. I would have expected hockey (which means ice hockey in this part of the world). But it looks like winter is almost over and things turned into the 2008 Summer Scripting Challenge when no one was looking.
The challenge
We have to write a script that schedules all the games for a round-robin baseball tournament.
How we are going to solve it
We create all possible pairings, randomize the order and print them out:
use 5.010;
use strict;
use warnings;
use List::Util qw(shuffle);
my @pairs;
my @teams = ('A'..'F');
while (my $team = shift @teams) {
push @pairs, map "$team vs. $_", @teams;
}
say for shuffle(@pairs);
We have teams “A” to “F”. Team “A” must play against every team from “B” to “F”, team “B” then needs to play against every team from “C” to “F” and so on until team “E” plays team “F”.
If we have N teams, it means we schedule N-1 games for the first team, an additional N-2 games for the second, and so on. The sum of the numbers from 1 to N-1 is (N-1)*N/2. In our case we have 6 teams, so we expect a total of 15 games (5*6/2). Incidentally this is the number of games the contest rules told us to expect, so we seem to be on the right track.
The algorithm generated the pairings as an ordered list, with all games of team A first, followed by all games of team B (except the one against team A) next and so on. Therefore we need to randomize the order to prevent any one team from getting too exhausted by playing all its games in a row. The List::Util module provides a fast implementation of the Fisher-Yates shuffle algorithm that is exactly what we needed.
So let’s run the script to see if it actually works:
D:\tmp\ScriptingGames>perl ae7a.pl B vs. D A vs. E A vs. F A vs. D C vs. D E vs. F C vs. E B vs. F C vs. F B vs. C D vs. E A vs. B D vs. F A vs. C B vs. E
It appears our work is done here. Presuming we didn’t already know about the shuffle() function in List::Util, we probably would have checked the Perl FAQ list:
C:>perldoc –q shuffle
The –q option tells perldoc to search all the headlines in all the perlfaq manual pages. It then displays all entries that contain the word or phrase we are looking for. We could have searched for “random” instead and would still have found the information we needed. The entry for “How do I shuffle an array randomly?” mentions the shuffle() function in List::Util, but also provides the algorithm for the Fisher-Yates shuffle directly.
use 5.010;
use strict;
use warnings;
my @pairs;
my @teams = ('A'..'F');
while (my $team = shift @teams) {
push @pairs, map "$team vs. $_", @teams;
}
for (my $i = @pairs; $i > 1; ) {
my $j = int rand($i--);
@pairs[$i,$j] = @pairs[$j,$i];
}
say for @pairs;
I’ve really only included this alternate version for 2 reasons: One, this commentary is still very short, and two, I wanted to explain the following expression: “@pairs[$i,$j] = @pairs[$j,$i]”.
In most languages you need a temporary variable if you want to swap two values:
{ my $t = $a; $a = $b; $b = $t; }
In Perl you can use list assignment to get rid of the $t temporary variable and make it much easier to read:
($a,$b) = ($b,$a);
The list on the right-hand side is constructed first and then assigned to the variables in the list on the left-hand side. $a and $b swap values without any (explicit) temporaries.
The expression @pairs[$i,$j] is an array slice; it is the same as ($pairs[$i],$pairs[$j]):
@pairs[$i,$j] = @pairs[$j,$i];
Therefore the statement above is exchanging the array elements $pairs[i] and $pairs[$j]. I find that using the assignment of array slices gives the whole expression some nice symmetry and conciseness. I’ve only ever needed to swap array elements in the implementation of sorting/shuffling algorithms, so I don’t really get to use this idiom very often. And I’ve never used it to rotate more than 2 elements, like this:
@array[$i,$j,$k] = @array[$j,$k,$i];
Let me know at jand@activestate.com if you come across a problem where this would be handy!
