2008 Winter Scripting Games
Solution to Advanced VBScript Event 3: Instant (Runoff) Winner
Windows PowerShell solution to Event 3 in the 2008 Winter Scripting Games.
Solutions are also available for Windows PowerShell and Perl.
Instant (Runoff) Winner
This was a tough event for the Scripting Guys. Why? Because we actually had to think about this one. We couldn’t just sit down and start typing; instead, we had to figure out how in the world we could eliminate the low-scoring candidate after the end of each round. Admittedly, that took awhile; thinking has never been the Scripting Guys’ forte. Once we came up with a method that would make it quick and easy to eliminate the low-scoring candidate, however, the rest of the script was surprisingly easy.
Here’s the solution we came up with:
Const ForReading = 1
Set objFSO = CreateObject("Scripting.FileSystemObject")
Set objFile = objFSO.OpenTextFile("C:\Scripts\Votes.txt")
strContents = objFile.ReadAll
objFile.Close
arrContents = Split(strContents, vbCrLf)
Set objDictionary = CreateObject("Scripting.Dictionary")
Do Until x = 1
dblLowest = 1
strLowest = ""
y = 0
For Each strLine in arrContents
arrLine = Split(strLine, ",")
y = y + 1
i = 0
Do While True
If arrLine(i) = "VOID" Then
i = i + 1
Else
strVote = arrLine(i)
If Not objDictionary.Exists(strVote) Then
objDictionary.Add strVote, 1
Else
objDictionary.Item(strVote) = objDictionary.Item(strVote) + 1
End If
Exit Do
End If
Loop
Next
For Each strKey in objDictionary.Keys
strCandidate = strKey
dblTotal = objDictionary.Item(strCandidate) / y
If dblTotal > .5 Then
Wscript.Echo "The winner is " & strKey & " with " & FormatPercent(dblTotal) & " of the vote."
x = 1
Else
If dblTotal < dblLowest Then
dblLowest = dblTotal
strLowest = strCandidate
End If
End If
Next
strContents = Join(arrContents, vbCrLf)
strContents = Replace(strContents, strLowest, "VOID")
arrContents = Split(strContents, vbCrlf)
objDictionary.RemoveAll
Loop
When we first conceived of this event we were concerned that the script required to solve the task would end up being pretty long and pretty complicated. As it turned out, the script isn’t very long at all. As for whether or not the script is pretty complicated, well, we admit that it looks complicated. But is this just a case of the bark being worse than the bite? Let’s find out.
We actually start out in pretty simple fashion: we define a constant named ForReading and set the value to 1; we’ll need this constant in order to read the text containing the election results. We next create an instance of the Scripting.FileSystemObject object, then use this line of code to open the file C:\Scripts\Votes.txt for reading:
Set objFile = objFSO.OpenTextFile("C:\Scripts\Votes.txt")
As soon as the file is open, we use the ReadAll method to read in the entire contents of the file, storing those contents in a variable named strContents. At that point we close the file. Why? Because from here on out all the work will be done using the “virtual” copy of the file stored in strContents.
Well, check that: we’ll also be doing work with a second copy of the file; to be a little more precise, we’re also going to work with an array named arrContents, an array we create by splitting strContents on the carriage return-linefeed character (vbCrLf):
arrContents = Split(strContents, vbCrLf)
Why do we do that? Because that gives us an array in which each item corresponds to a line in the text file; that is, where each item looks something like this:
Ken Myer,Jonathan Haas,Pilar Ackerman,Syed Abbas
And why do we do that? We’ll explain that in just a moment.
Finally, we create an instance of the Scripting.Dictionary object; we’ll use this object to help us keep track of the votes received by each candidate.
And now it’s time to start counting votes.
To begin with, we set up a Do Until loop that continues to loop until x is equal to 1. Because x is an undeclared variable, it currently has a value of 0; x will maintain that value until we’ve determined a winner of the election. At that point, we’ll set x to 1, and the script will exit the loop.
The first thing we do inside the loop is assign values to three variables:
dblLowest = 1 strLowest = "" y = 0
What are these variables for? Well, dblLowest will help us keep track of the candidate who receives the fewest votes in each round; that’s important, because – as you no doubt recall – at the end of each round the candidate who receives the fewest votes is eliminated. The variable strLowest serves a similar function: we’ll use that variable to store the name of the candidate who receives the fewest votes in a round. As for the variable y, that’s simply a counter variable that keeps track of the total number of votes cast; we’ll use that to determine the percentage of the total vote that each candidate receives. (Remember, you must get more than 50% of the vote to win.)
Our next chore is to set up a For Each loop that loops us through all the items in the array arrContents, which – happily enough – also loops us through all the ballots that were cast in the election:
For Each strLine in arrContents
Inside the For Each loop, the first thing we do is split the first item into a mini-array named arrLine:
arrLine = Split(strLine, ",")
So what does that do? The first time through the loop, that gives us an array equal to this:
Ken Myer Jonathan Haas Pilar Ackerman Syed Abbas
Is this useful? Of course it is; after all, item 1 represents the voter’s first choice in the election, item 2 represents the second choice, and so on. Needless to say, this is very useful.
After creating the mini-array we then execute these two lines of code:
y = y + 1 i = 0
As we noted earlier, y is a counter variable that tracks the total number of votes cast; because we’re now analyzing the first ballot we go ahead an increment y by 1. As for i, well, this is yet another counter variable, one that we’ll use to keep track of our location within the array arrLine.
Speaking of which, our next step is to set up a Do While loop designed to run as long as True is equal to True. Admittedly, this is some what risky when dealing with elections; when you’re dealing with politicians when is True ever really True? As a scripting convention, however, this enables us to loop through the ballot (that is, the items in the variable arrLine) until we find a valid vote.
And just what is a valid vote? Well, as you know, the first time we count the votes we count only the No. 1 choice for each voter. With a ballot like this, that means that Ken Myer gets 1 vote:
Ken Myer Jonathan Haas Pilar Ackerman Syed Abbas
Now, suppose we count all the votes and no candidate has received more than 50%. According to the rules of the election, that means the candidate who received the fewest votes is eliminated from the race. We decided an easy way to eliminate a candidate was to simply mark all votes for the candidate as VOID. For example, if Ken Myer received the fewest votes this particular ballot would be changed to look like this:
VOID Jonathan Haas Pilar Ackerman Syed Abbas
Notice that when we go to count a vote, the first thing we do is check to see if item i in the array is equal to VOID:
If arrLine(i) = "VOID" Then
Suppose it is. In that case, we don’t want to count this vote; it’s not a valid vote. Instead, we have to look at the user’s next choice (Jonathan Haas). Thus we increment i by 1, and try again. This continues until we find a valid vote.
So what happens when we do find a valid vote? Well, when that happens we execute this block of code:
strVote = arrLine(i)
If Not objDictionary.Exists(strVote) Then
objDictionary.Add strVote, 1
Else
objDictionary.Item(strVote) = objDictionary.Item(strVote) + 1
End If
Exit Do
What we’re doing here is storing the name of the candidate who’s about to get the vote in a variable named strVote. We then use this line of code to see if our Dictionary object contains a key with the same name as the candidate (e.g., a key named Ken Myer):
If Not objDictionary.Exists(strVote) Then
If no such key can be found (meaning that this is the first vote the candidate received) then we use the Add method to add the candidate to the Dictionary, using his or her name as the key, and setting the value (number of votes received) to 1:
objDictionary.Add strVote, 1
If the candidate is already in the Dictionary, meaning that he or she has already received at least one vote, then we simply increment the candidate’s vote total by 1:
objDictionary.Item(strVote) = objDictionary.Item(strVote) + 1
And then, because we’re done with the first ballot, we call the Exit Do statement. That pops us back into our For Each loop, at which point we repeat the process with the next ballot.
Whew. If you need to get a drink of water or something, go right ahead; we’ll wait.
Eventually (and remarkably soon when you consider everything that’s going on here) we’ll have counted all the ballots. That can mean only one thing: its time to see if any of our candidates received more than 50% of the votes cast.
So how do we determine that? Well, step 1 is to set up yet another loop, this one a For Each loop that loops through all the keys in our Dictionary:
For Each strKey in objDictionary.Keys
For each key (that is, for each candidate) we then execute the following two lines of code:
strCandidate = strKey dblTotal = objDictionary.Item(strCandidate) / y
In the first line, we simply assign the candidate name to a variable named strCandidate; this just helps us keep track of what we’re doing. We then take the vote total for the candidate (objDictionary.Item(strCandidate)) and divide that by the total number of votes cast (y); the resulting value is then stored in a variable named dblTotal. For example, if 100 votes were cast and our candidate received 43 of those votes, dblTotal would be equal to .43 (that is, 43 / 100).
Next we check to see if dblTotal is greater than .5; if it is that means that candidate has received more than 50% of the votes. In turn, that means that this particular candidate has won the election, and we use this line of code to report the winner (and his or her percentage of the vote):
Wscript.Echo "The winner is " & strKey & " with " & FormatPercent(dblTotal) & " of the vote."
Once we have a winner there’s no need to count any more ballots. Therefore, we set the value of x to 1:
x = 1
That causes us to exit our original Do loop, and brings the script to an end.
That’s great. But what if the candidate didn’t receive more than 50 percent of the votes? In that case, we execute this block of code:
If dblTotal < dblLowest Then
dblLowest = dblTotal
strLowest = strCandidate
End If
What we’re doing here is checking to see if the candidate’s total percentage of the vote is less than the value assigned to the variable dblLowest. (And because dblLowest starts out with a value of 1.0 the only way to not have a percentage lower than that would be to receive all the votes.) If dblTotal is lower than dblLowest, then we replace the value of dblLowest with dblTotal, and we assign the candidate’s name (strCandidate) to the variable strLowest. That lets us keep track of which candidate received the lowest total percentage of the vote.
And why do we need to keep track of that? That’s easy: we need to eliminate that candidate from the next round of ballot counting. That’s what this block of code does:
strContents = Join(arrContents, vbCrLf) strContents = Replace(strContents, strLowest, "VOID") arrContents = Split(strContents, vbCrlf) objDictionary.RemoveAll
In the first line, we take our array (arrContents) and use the Join function to turn this back into a string value. That brings us to line two:
strContents = Replace(strContents, strLowest, "VOID")
This is where we get rid of the candidate who got the fewest votes; in this line we use the Replace function to replace any instances of that candidate’s name (strLowest) with the string value VOID. If Ken Myer received the fewest votes, then any instances of Ken Myer will be replaced with the word VOID. After that we use the Split function to recreate the array arrContents, then use this line of code to remove all the items from the Dictionary:
objDictionary.RemoveAll
From there it’s back to the top of our original Do loop, where we begin the next round of ballot counting.
By the way, here are the results of the election:
The winner is Pilar Ackerman with 50.17% of the vote.
Congratulations, Pilar!
