This continues my series of solution posts for the 2008 Scripting Games with my solution for the Advanced Event 3 which was about counting votes in an instant run-off election. The idea was to take a CSV file with lines representing “ballots” such that each ballot should be a list of four candidates in order of preference. The election results are calculated by counting up the votes, and if no candidate receives a majority of the votes, the candidate with the least votes is eliminated from all ballots, and they are recounted. This continues until one candidate is the highest rated candidate on the majority of the ballots.
In PowerShell, the Scripting Guys’ examples are considered harmful.
This time, the Scripting Guys’ solution is not only inefficient, it actually promotes bad coding practices! They actually use a do{ ... } while() loop (as do I) but instead of testing for an exit case in it, they test for $x -ne 1. But $x is a variable they don’t ever set, so in other words, they took the simplest loop ever and made it hard to understand by obscuring what the exit case is. Worse than that, although they think they’re basically testing do{ ... }while($true), they never set $x, so if $x is set to 1 in your environment before you run their script, their script will run with no output. The rest of their solution is no less confusing, involving the use of a hashtable which they treat as if it were some sort of special dictionary, calling get_item and set_item instead of using indexing:
# So they do:
$candidate = $dictionary.Get_Item($strVote)
$candidate++
$dictionary.Set_Item($strVote, $candidate)
# When they could do:
$dictionary[$strVote]++
Honestly, even if you think of this as a VBScript converted to PowerShell, the solution is bad. It’s even determining the number of votes (which they could get at any time from $arrContents.Count) using a manually incremented counter … which they reset and recalculate on each recount (as though it might change).
The contributed solution was written by Don Jones for this event … and is basically what I expected the Scripting Guys solution to be: a good VB-script style solution. Except, the script they published for him on their website doesn’t actually do anything, because it never calls his “Tally” function… I’m probably being overly critical, so I should just stop now, show you my solution, and leave the comment form open so people can flame me in turn.
$votes = Get-Content c:\Scripts\Votes.txt
do {
$vote = $votes | % { $_ -split "," | select -first 1 } | Group-Object |
Select-Object Count, Name | Sort-Object Count -Desc
$votes = $votes | % { $_ -split "," -ne $vote[-1].Name –join "," }
} while( $vote[0].Count -le ($votes.Count/2) )
"The winner is {0} with {1:#0.0#%} of the vote" -f $vote[0].Name, ($vote[0].Count/$votes.Count)
Very simply: on the first line we read in the text file. Then we enter a loop where we calculate the number of votes for each candidate in this round, and then remove the lowest candidate from the ballots. When we exit, we print out the winner and the percentage of the total using string -f formatting.
I’ll give you a little more detail on the two lines inside the loop. The first line just takes the votes, and splits each line on the commas, and selects the first vote. These votes are grouped, sorted by count, and $votes is assigned the custom objects with just the candidate’s name and number of votes. The second line splits on the commas again, filters out items which match the candidate with the lowest vote count, and then joins them back together. Now, obviously that’s not the most efficient way of doing things, but it’s very simple. Of course, with the sample set of votes provided as part of the scenario, the voting goes all the way to the last round, so the string split and rejoin each time takes it’s toll. You could cut the runtime of the script to one fourth by simply moving that split out of the loop:
$votelines = Get-Content c:\Scripts\Votes.txt
## This is complicated by the fact that PowerShell likes to unroll arrays.
## We have to force the variable to be an array or arrays
[string[][]]$votes = new-object string[][] $votelines.Count,4
## And then we have to parse the votelines and manually insert them
## otherwise the split array would be cast to a string
$x=0; $votelines | % { $votes[$x++] = @($_ -split ",") }
do {
$vote = $votes | Group-Object {$_[0]} | Select-Object Count, Name | Sort-Object Count -Desc
for($i=0; $i -lt $votes.Count; ++$i) { $votes[$i] = $votes[$i] -ne $vote[-1].Name }
} while( $vote[0].Count -le ($votes.Count/2) )
"The winner is {0} with {1:#0.0#%} of the vote" -f $vote[0].Name,($vote[0].Count/$votes.Count)
Incidentally, I have to point out again how cool it is that you can do: $array = $array -ne "value" to remove items that match “value” from an array.