2008 Winter Scripting Games

Solution to Advanced Windows PowerShell Event 3: Instant (Runoff) Winner

Windows PowerShell solution to Event 3 in the 2008 Winter Scripting Games.

Solutions are also available for VBScript and Perl.

Instant (Runoff) Winner

This was an interesting event, at least for the Scripting Guys. As usual, we wrote the VBScript solution first, then turned to the Windows PowerShell version. In VBScript we used a Dictionary object to keep a running tally of the number of votes received by each candidate. That worked pretty well, well enough that it seemed like a reasonable thing to do in the PowerShell script. Consequently, one of the first things we did was add a hash table (roughly the equivalent of the Dictionary object) to our PowerShell solution, without having the slightest idea how – or even if – we could retrieve and modify individual values within that hash table. We just had faith that there had to be a way to do this.

And you know what? Sometimes faith is rewarded. It took a little poking around the .NET Framework SDK, but eventually we figured out how to get our script to interact with the hash table. And once we did that, the rest was easy:

$arrContents = Get-Content "C:\Scripts\Votes.txt"

$dictionary = @{}

:OuterLoop do
  {$y = 0
    $dblLowest = 1
    $strLowest = ""

    foreach ($strLine in $arrContents)
        {$arrLine = $strLine.Split(",")
            $y++
            $i = 0

            do
                {If ($arrLine[$i] -eq "VOID")
                        {$i++}
                    else
                        {$strVote = $arrLine[$i]
                            $blnCheck = $dictionary.Contains($strVote)

                            if ($blnCheck -eq $False)
                                {$dictionary.Add($strVote, 1)}
                            else
                                {$candidate = $dictionary.Get_Item($strVote)
                                 $candidate++
                                 $dictionary.Set_Item($strVote, $candidate)}
                            break
                         }
                 }
            until ($z -eq 1)
         }

      foreach ($strPerson in $dictionary.Keys)
        {$intVotes = $dictionary.Get_Item($strPerson)
            $dblTotal = $intVotes / $y

            if ($dblTotal -gt .5)
                { $final = "{0:P2}" -f $dblTotal
                 write-host "The winner is $strPerson with $final of the vote."
                 break OuterLoop}

            else
                {if ($dblTotal -lt $dblLowest)
                       {$dblLowest = $dblTotal
                        $strLowest = $strPerson}              
                }
         }

    $strContents = [string]::join("`n", $arrContents)
    $strContents = $strContents -replace($strLowest, "VOID")
    $arrContents = $strContents.Split("`n")
    $dictionary.Clear()
  }

while ($x -ne 1)

In most Scripting Games events the Scripting Guys simply test a script to see whether it works or not; that’s partly because we don’t have a lot of time to spend looking at code, but also because there’s often only one way (or at least one reasonable way) to approach the problem.

That’s definitely not the case with Event 3; we’ve spent more time than we should have looking at code to see how people chose to tackle this event. (Needless to say, we’ve seen some very creative – and…efficient – approaches.) But that’s another article for another day. For now, we need to talk about how we chose to tackle the event.

We decided to begin at the beginning, using the Get-Content cmdlet to read the text file C:\Scripts\Votes.txt, storing the contents of that file in an array named $arrContents. That’s going to give $arrContents 1200 items (each item representing one of the 1200 lines in the text file). Each of those array items looks a little something like this:

Ken Myer,Jonathan Haas,Pilar Ackerman,Syed Abbas

From there we use the following line of code to create an empty hash table, a container we’ll employ to keep track of the votes received by each candidate:

$dictionary = @{}

OK, so maybe this won’t be so bad after all.

Our next task is to set up a do loop designed to run forever (or at least as long as $x, a variable we never use, isn’t equal to 1). By the way, note that we gave this do loop the label :OuterLoop:

:OuterLoop do

By labeling the loop it makes it easier for us to break out of the otherwise-endless loop once we’ve declared a winner of the election.

The first thing we do inside the loop is assign values to 3 different variables:

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

We’re going to use the variable $y to keep track of the total number of votes cast; we need to know the total number of votes so we can determine the percentage of the vote that each candidate received. Meanwhile, we’ll use $dblLowest and $strLowest to keep track of which candidate received the fewest votes. Do we really need to know who got the fewest votes? Yes, we do; remember, the event instructions stipulate that, at the end of a round, if no candidate has received more than 50 percent of the votes then the candidate with the fewest votes is eliminated and we begin a new round of ballot counting.

So how exactly do we conduct a round of ballot counting? To begin with, we set up a foreach loop that runs through all the items in the array $arrContents (that is, all the votes that were cast in the election):

foreach ($strLine in $arrContents)

Inside this loop, we use the split method to split the first ballot into an array named $arrLine:

$arrLine = $strLine.Split(",")

Why do we do that? Well, as you might recall, in this kind of an instant runoff election a voter votes for all four candidates, in order of preference; that means we need to separate the voter’s first choice from his or her second choice, the second choice from the third choice, and the third choice from the fourth choice. One easy way to do that is to turn the ballot into an array, an array containing items similar to this:

Ken Myer
Jonathan Haas
Pilar Ackerman
Syed Abbas

Once that’s done we increment $y by 1 (because we’re counting the first vote) and set a counter variable named $i to 0:

$y++
$i = 0

Next we set up yet another do loop, this one also designed to run forever. (But don’t worry: we’ll figure out a way to break out of this loop, too.) Inside this second, unlabeled loop the first thing we do is check to see if the initial item in our mini-array (the first choice on this ballot) is equal to the string VOID (we’ll take about that momentarily):

if ($arrLine[$i] -eq "VOID"

Suppose this item is equal to VOID. In that case, we increment our counter variable $i by 1, then check the next item in the array. This continues until we find an array item that isn’t equal to VOID:

So what happens then? Well, for starters, we store the value of that array item (that is, the candidate the voter voted for) in a variable named $strVote:

$strVote = $arrLine[$i]

We then use the Contains method to see if our hash table already contains an entry for this candidate:

$blnCheck = $dictionary.Contains($strVote)

If the Contains method returns False ($False) that means that the candidate isn’t in the hash table; consequently, we use this line of code to add the candidate to the table and give him or her their first vote:

$dictionary.Add($strVote, 1)

If the Contains method returns True ($True) that means that the candidate is already in the array. Consequently, we use this block of code to retrieve the candidate’s current vote total, add one to it, and then update the hash table to reflect the fact that the candidate just received another vote:

{$candidate = $dictionary.Get_Item($strVote)
$candidate++
$dictionary.Set_Item($strVote, $candidate)}

At that point, whether we created a new hash table entry or updated an existing entry, we call the break command to break out of our interior loop. From there we go back to the top of our foreach loop and repeat this process with the next ballot (that is, the next line read in from the text file).

After all 1200 ballots have been counted we set up a brand-new foreach loop, this one designed to walk through all the keys in our hash table:

foreach ($strPerson in $dictionary.Keys)

For each hash table entry we use the Get_Item method to retrieve the number of votes each candidate received. (The hash table key is the candidate’s name, the hash table item is his or her vote total):

$intVotes = $dictionary.Get_Item($strPerson)

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

$dblTotal = $intVotes / $y

What happens if this value is greater than .5? Well, in that case this candidate received more than 50 percent of the vote, meaning he or she is the winner of the election. In turn, we use this block of code to echo back the final results and break out of our original do loop:

{ $final = "{0:P2}" -f $dblTotal
    write-host "The winner is $strPerson with $final of the vote."
    break OuterLoop}

And once we break out of our original do loop the script comes to an end.

But what happens if the candidate didn’t receive more than 50 percent of the vote? Well, in that case, we check to see if the candidate’s vote percentage is less than the value stored in the variable $dblLowest:

if ($dblTotal -lt $dblLowest)

If the candidate’s vote percentage is lower that means that, at the moment anyway, this candidate received the fewest votes in this round of balloting. That also means that we use these two lines of code to assign the candidate’s vote percentage to $dblLowest and the candidate’s name to the variable $strLowest:

$dblLowest = $dblTotal
$strLowest = $strPerson

And then we do the same thing for the remaining candidates listed in the hash table.

Now, what happens if none of the candidates received at least 50 percent of the vote? Well, according to the rules of the election, we need to discard all the votes given to the candidate who received the fewest votes and try again. That’s what this block of code is for:

$strContents = [string]::join("`n", $arrContents)
$strContents = $strContents -replace($strLowest, "VOID")
$arrContents = $strContents.Split("`n")
$dictionary.Clear()

In line 1 we’re using the join method to glom all the values in $arrContents into a single string variable named $strContents; for us, anyway, that makes it easier to re-create the array $arrContents (in part because we place a carriage return-linefeed [`n] between each ballot.) Once we’ve done that we can use the replace method to replace all votes for the last-place candidate with the string VOID:

$strContents = $strContents -replace($strLowest, "VOID")

What does that mean? Well, if Ken Myer received the fewest votes that means the first ballot will now look like this:

VOID,Jonathan Haas,Pilar Ackerman,Syed Abbas

That also means that, the next time we count the votes, Jonathan Haas will receive this voter’s vote. Why? Because the voter’s original first choice, Ken Myer, been eliminated. (Hence the string VOID.) In turn, that means that the vote goes to the number 2 choice, Jonathan Haas.

Which is just exactly how the election is supposed to work.

After we call the replace method we recreate our array using this line of code:

$arrContents = $strContents.Split("`n")

Finally, we call the clear method to erase all the entries in our hash table:

$dictionary.Clear()

And once that’s done we go back to the top of our original do loop (OuterLoop) and count the votes for a second time.

Sooner or later, the script will report back the election results:

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

Way to go, Pilar. Now, about these high taxes ….

Top of page