2008 Winter Scripting Games

Solution to Advanced Perl Event 7: Play Ball!

Perl solution to Event 7 in the 2008 Winter Scripting Games.

Solutions are also available for VBScript and Windows PowerShell.

Play Ball!

Some people have wondered if this event was included in the Scripting Games simply because one of the Scripting Guys (a long-time baseball coach) needed to schedule a round-robin baseball tournament and didn’t know how to go about doing that. To be honest, the answer to that is no; as it turns out he already knew how to schedule a round-robin baseball tournament. However, don’t be surprised if the 2009 Games include an event in which you are asked to write a script that can – to everyone’s satisfaction – pick one winner out of the four teams that can (and often-times do ) tie for first-place in a round-robin tournament. That’s a script he really could use.

But we don’t care about that right now; all we care about is scheduling a round-robin tournament. How can you write a script that will schedule a round-robin tournament? Why, like this, of course :

@arrGames = ();
@arrSchedule = ();

@arrTeams = ("A", "B", "C", "D", "E", "F");

$size = @arrTeams;

for ($i = 0; $i < $size - 1; $i++) 
    {
        for ($j = $i; $j < $size - 1; $j++)
        {
          $strGame = $arrTeams[$i] . " vs. " .  $arrTeams[$j + 1];
          push(@arrGames, $strGame);
          }
    }

$intGamesLeft = @arrGames;
$intGamesToPlay = @arrGames;

while ($intGamesLeft > 0) {

    $low = 0;
    $high = $intGamesToPlay;
    $gameNumber = int(rand($high) + $low);

    if (@arrGames[$gameNumber] ne "Done") {
         push(@arrSchedule, @arrGames[$gameNumber]);
         @arrGames[$gameNumber] = "Done";
         $intGamesLeft --;
    }
}

for $game (@arrSchedule) 
    {print "$game \n";}

So how does this script work? Well, to begin with, we created a pair of arrays: @arrGames (which will hold a list of all the games that need to be played), and @arrSchedule (which will hold the final, official schedule):

@arrGames = ();
@arrSchedule = ();

We then use this line of code to add our teams (Teams A, B, C, D, E, and F) to another variable, this one named @arrTeams:

@arrTeams = ("A", "B", "C", "D", "E", "F");

In order to make this script generic (that is, to make it work with a tournament with any number of teams, not just with a six-team tournament) we use this line of code to determine the number of items in the array @arrTeams:

$size = @arrTeams;

Now it’s time to schedule some baseball games. To begin with, we set up a for loop that starts at 0 and continues running as long as the counter variable $i is less than the value of $size (the number of teams in the tournament) minus 1:

for ($i = 0; $i < $size - 1; $i++)

Good question: why does the loop start at 0 and run through the number of teams in the tournament minus 1? Well, remember, we’re dealing with an array here, and the first item in an array is always given the index number 0; that’s why we start at 0. And why ‘the number of teams in the tournament minus 1?’ Well, we’re going to determine all the games for Team A first; because each team plays each other team once, that means Team A will play the following games:

We’ll then schedule the games for Team B:

Notice that we didn’t schedule Team B to play Team A. Why not? Because we already scheduled this game when we determined the games from Team A, and teams are supposed to play each team only once. If you follow that logic, we don’t have to schedule any games for the last team in the array, Team F: by the time we get to Team F, we’ll have already scheduled all the games for that team.

To make a long story short, we’re going to start our first loop off with Team A. We’re then going to immediately launch into a second for loop:

for ($j = $i; $j < $size - 1; $j++)

What we’re doing in this loop is taking the current team (Team A, item 0 in the array) and then scheduling it to play each of the “higher” teams in the tournament (that is, each teams with higher index numbers in the array). To do that, we use this block of code:

$strGame = $arrTeams[$i] . " vs. " .  $arrTeams[$j + 1];
push(@arrGames, $strGame);

In line 1, we’re constructing a string value consisting of the name of the current team (A), the string value vs. and the name of the next team in the array (team j + 1, or Team B). In other words:

A vs. B

In line 2, we then use the push function to add this value to the array @arrGames.

We then increment the value of j by 1, loop around, and schedule Team A to play the next team in the array:

A vs. C

When we finish with Team A, we return to the original loop and repeat the entire process with Team B.

After we’ve finished with the outer loop, all the games that need to be played will be stored in the array $arrGames. However, those games are not in the desired order; for example, the first five items in the array are these:

A vs. B
A vs. C
A vs. D
A vs. E
A vs. F

If we left things as-is Team A would play the first 5 games in the tournament, something that we did not want to happen. Therefore, what we need to do is take the items in the array @arrGames and “shuffle” them.

Of course, we can’t really “shuffle” an array (not as far as we know, anyway). Therefore, what we’re going to do is the following. To begin with, we use this line of code to assign the number of items in the array @arrGames to a variable named $intGamesLeft (we also assign the same value to the variable $intGamesToPlay):

$intGamesLeft = @arrGames;

We then set up a do loop that continues to run as long as $intGamesLeft is greater than 0. Inside that loop, we use the following block of code to generate a random number between 0 (representing the first item in the array) and the value of $intGamesToPlay (representing the total number of items in the array):

$low = 0;
$high = $intGamesToPlay;
$gameNumber = int(rand($high) + $low);

If we have 15 items in the array (which we do), this is going to generate a random number between 0 and 14. In Perl, the highest number in a random number range will always be one less than the specified value. In this case, that means we’ll be choosing a number between 0 and 14, inclusively. Believe it or not, that’s what we want: with 15 items in the array, that means that the last item in the array has an index number of 14.

So what do we do with that random number? Well, the first thing we do is check to see if the array item with that index number has a value of Done:

if (@arrGames[$gameNumber] ne "Done")

If the array item does equal Done that means we’ve already scheduled that game; consequently, we go back to the top of the loop and generate a new random number. If the array item doesn’t equal Done then we execute the following block of code:

push(@arrSchedule, @arrGames[$gameNumber]);
@arrGames[$gameNumber] = "Done";
$intGamesLeft --;

In the first line, we take the value of the array item (e.g., C vs. E) and add that value (game) to the array @arrSchedule. In line 2, we set the value of the array item in the original array (that is, @arrGames) to Done. (Why do we do that? Because that way we know that this game has already been scheduled.) In line 3 we decrement the counter variable $intGamesLeft, then go back to the top of the loop and try again.

Sooner or later, we’ll have randomly selected all the games in @arrGames and added them to the array @arrSchedule; at that point, $intGamesLeft will be equal to 0, and we’ll exit our do loop. After that all we have to do is use this block of code to echo back each item in the array @arrSchedule:

for $game (@arrSchedule) 
    {print "$game \n";}

That’s going to give us output similar to this:

D vs. E
C vs. D
B vs. F
A vs. F
E vs. F
B vs. C
C vs. F
A vs. D
B vs. D
C vs. E
A vs. B
D vs. F
B vs. E
A vs. E
A vs. C

Remember, because the schedule is randomly generated your output is unlikely to match our output. The important thing is that you end up with 15 games, that each team in the tournament is scheduled to play 5 games, and that the order of games was randomly determined.

Top of page