Click Here to Install Silverlight*
United StatesChange|All Microsoft Sites
Microsoft TechNet*
Search Microsoft.com for:
|TechCenters|Downloads|TechNet Program|Subscriptions|Security Bulletins|Archive
Search for

2008 Winter Scripting Games

Solution to Advanced Perl Event 3: Instant (Runoff) Winner

Event 3 Solution


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

Solutions are also available for VBScript and Windows PowerShell.

*

Event 3 – Instant (Runoff) Winner


Before the Scripting Games began we were a little concerned about Event 3, not because it was so hard to script, but because it was so hard to explain. We were afraid that people might find the instructions to be confusing, they might not get the point, and the Scripting Guys might end up with a full-fledged mutiny on our hands.

Note. Not to worry; turns out that’s what Event 1 in the Sudden Death Challenge was for.

Fortunately, though, almost everyone understood the concept, and almost everyone managed to successfully complete this event. (In fact, many people managed to solve this in very few lines of code. We definitely tip our hats to all of them.) In the end, the event went pretty well, which should make our jobs much easier next year. After all, for the 2009 Winter Scripting Games we can probably just say, “Write a script that does something” and everyone will figure out what we mean and write a script that successfully completes the event.

But that’s next year. As far as this year goes, here’s the solution that the Scripting Guys came up with. Not particularly Perl-like, but it works:

%dictionary = ();

open (VoteList, "C:\\Scripts\\Votes.txt");
@arrContents = <VoteList>;
close (VoteList);

do
    {
        $y = 0;
        $dblLowest = 1;
        $strLowest = "";

        for $strLine (@arrContents) 
            {
                @arrLine = split(',',$strLine);
                $y++;
                $i = 0;

                do
                    {
                        if (@arrLine[$i] eq "VOID")
                            {
                                $i++;
                            }
                        else
                            {
                                $strVote = @arrLine[$i]; 
                                $blnCheck = exists($dictionary{$strVote});
                                if ($blnCheck == 0)
                                    {
                                        $dictionary{$strVote} = 1;
                                        next;
                                    }
                                else
                                    {
                                        $candidate = $dictionary{$strVote};
                                        $dictionary{$strVote} = $candidate + 1;
                                        next;
                                    }                            
                            }
                    }
                until $z == 1;
            }

        foreach $strCandidate (keys %dictionary)
            {
                $intVotes = $dictionary{$strCandidate};
                $dblTotal = $intVotes / $y;
          
                if ($dblTotal > .5)                    
                    {    
                        $dblTotal = $dblTotal * 100;
                        printf "The winner is $strCandidate with %.2f%% of the vote.", $dblTotal;
                        exit;
                    }
                else
                    {
                        if ($dblTotal < $dblLowest)
                            {
                                $dblLowest = $dblTotal;
                                $strLowest = $strCandidate;
                            }
                    }
            }

        $intLength = @arrContents;

        for ($j = 0; $j < $intLength; $j++)
            {
                $strNewLine = @arrContents[$j];
                $strNewLine =~ s/$strLowest/VOID/;
                @arrContents[$j] = $strNewLine;
            }
        %dictionary = ();          
    }
until $w == 1;

So how do we determine the winner of an instant runoff election? Well, to begin with, we create an empty hash table named %dictionary; that’s what this line of code is for:

%dictionary = ();

After creating our hash table we then use the following block of code to open and read the file C:\Scripts\Votes.txt:

open (VoteList, "C:\\Scripts\\Votes.txt");
@arrContents = <VoteList>;
close (VoteList);

As you can see, to open the file we call the open function, passing two parameters: VoteList (a reference to the text file we’re about to open), and C:\\Scripts\\Votes.txt, the path to the file. (And no, you’re not seeing double: because the \ is a reserved character in Perl, we need to “escape” each \ by prefacing it with another \.) In line 2 we use standard Perl syntax to read the contents of Votes.txt, storing each line in the file as a separate item in an array named @arrContents. And then, in line 3, we use the close function to close the file.

A little unusual, perhaps, but it works just fine.

So what do we do now? Well, now we set up a do loop designed to run until the variable $w is equal to 1 (until $w == 1). The first thing we do inside that loop? We assign values to three different variables:

$y = 0;
$dblLowest = 1;
$strLowest = "";

We’ll use the variable $y to keep track of the total number of votes cast; we’ll use the other variables to keep track of the candidate who received the lowest percentage of votes ($strLowest), as well just exactly what that percentage is ($dblLowest).

And now it’s time to count some votes.

To do that, we start by setting up a for loop that will loop through all the items in the array @arrContents (in other words, all the ballots that were cast in the election):

for $strLine (@arrContents)

As you might recall, each ballot looks something like this, listing the four candidates in the election in order of precedence:

Ken Myer,Jonathan Haas,Pilar Ackerman,Syed Abbas

A big, long string value like this is a little cumbersome to work with; therefore, we immediately use the split function to convert this value to a mini-array named @arrLine:

@arrLine = split(',',$strLine);

By spitting on the comma that gives us an array consisting of the following elements:

Ken Myer
Jonathan Haas
Pilar Ackerman
Syed Abbas

Once we have our array we increment the value of $y by 1, indicating that a vote has been cast. After setting a counter variable named $i to 0, we then set up a do loop that loops through the candidates in this particular ballot.

Why do we need to do this? Well, remember how our instant runoff election works. The first time we count the votes we give the vote to the user’s first choice; with this ballot that means that Ken Myer will get one vote. However, suppose that, at the end of the first round, no candidate has received more than 50 percent of the votes. That means that we need to discard all the votes for the candidate receiving the lowest number of votes. Let’s assume Ken Myer is the odd man out. In that case, we need to modify this ballot so it looks like this:

VOID
Jonathan Haas
Pilar Ackerman
Syed Abbas

Why? Because Ken Myer is now out of the election. Therefore, we need to void any votes cast for him. So what happens in round 2, when we count the votes for a second time? Well, because this voter’s first choice is no longer in the running, we need to give the vote to his or her second choice: Jonathan Haas.

And that, to make a long story short, is why we need to be able to loop through all the candidates on a ballot.

To that end, we check to see if the first item in the array (item 0) is equal to VOID:

if (@arrLine[$i] eq "VOID")

If it is, then we increment $i by 1, go back to the top of the loop, and try again with the next item in the array (that is, the next candidate on the ballot).

Let’s suppose, however, that item 1 in the array is not equal to VOID. In that case, we grab the name of the candidate and store it in a variable named $strVote:

$strVote = @arrLine[$i];

From there, we then check to see if this candidate is already listed in our hash table:

$blnCheck = exists($dictionary{$strVote});

If $blnCheck is False (0) we use this block of code to add the candidate to the hash table, give that candidate a single vote, and then exit our interior do loop:

$dictionary{$strVote} = 1;
next;

If the candidate is already in the hash table we execute this block of code instead:

$candidate = $dictionary{$strVote};
$dictionary{$strVote} = $candidate + 1;
next;

In the first line we retrieve the hash table value (vote total) for the candidate in question; in line 2, we increment that value by 1. (In other words, we give the candidate another vote.) In line 3 we use the next function to, again, break out of our interior loop.

And then we go back to the start of the for loop and repeat this process with the next item in the array.

Eventually, we’ll have counted each and every ballot. Once that’s happened we next need to determine whether or not anyone has won our election. To do that, we start by setting up a foreach loop to loop through all the keys in our hash table:

foreach $strCandidate (keys %dictionary)

Inside that loop, we use this line of code to retrieve the total number of votes received by the candidate:

$intVotes = $dictionary{$strCandidate};

We then use this line of code to determine the total percentage of the vote received by that candidate:

$dblTotal = $intVotes / $y;

According to the rules of our election, if any candidate receives more than 50 percent of the vote he or she is immediately declared the winner. Therefore, our next step is to check and see if the candidate did receive more than 50 percent of the vote:

if ($dblTotal > .5)

If $dblTotal is greater than .5 we echo back the name of the candidate and his or her winning percentage, then call the exit function to terminate the script:

print "The winner is $strCandidate with $dblTotal of the vote.";
exit;

That was easy enough. But what if the candidate didn’t receive more than 50 percent of the vote?

In that case, we use this line of code to determine whether the candidate’s vote percentage is less than the current value of $dblLowest:

if ($dblTotal < $dblLowest)

If it’s not, then we don’t do anything. If it is, then we assign the candidate’s name to $strLowest and his or her vote percentage to $dblLowest:

$dblLowest = $dblTotal;
$strLowest = $strCandidate;

As you probably figured out, that’s how we keep track of the candidate who receives the lowest number of votes (and will thus be eliminated if we need to do another round of vote counting).

Of course, before we can do another round of vote counting we need to void the votes cast for the last-place candidate. To do that, we first use this line of code to retrieve the total number of items in the array @arrContents and store that value in the variable $intLength:

$intLength = @arrContents;

Once we know that value we can set up a for loop that loops through each item in the array:

for ($j = 0; $j < $intLength; $j++)

Inside that loop, we grab the value of the current array item and store it in a variable named $strNewLine; we then use this line of code to substitute the word VOID for the name of the last-place candidate:

$strNewLine =~ s/$strLowest/VOID/;

In other words, if Ken Myer is the last-place candidate then $strNewLine might look like this:

VOID,Jonathan Haas,Pilar Ackerman,Syed Abbas

We then use this line of code to assign this modified value back to the array:

@arrContents[$j] = $strNewLine;

And once we’ve thrown out the votes for the last-place candidate we use this line of code to remove all the items from our hash table:

%dictionary = ();

From there we go back to our original do loop, and count the votes a second time. That’s all we have to do.

What’s that? Who won the election? Good question; we have no idea. But that’s OK; let’s just run our Perl script and see four ourselves:

The winner is Pilar Ackerman with 50.17% of the vote.

Looks like Pilar Ackerman was the winner. Way to go, Pilar.


 

© 2008 Microsoft Corporation. All rights reserved. Contact Us |Terms of Use |Trademarks |Privacy Statement
Microsoft