Scripting Games, Advanced Event 3, Instant Runoff Election

An interesting problem, although the resulting script (well, my resulting script!) isn’t that thrilling…

Basic recap: votes are cast for candidates in order of preference (1st choice, 2nd choice etc).  Count all the 1st choice votes for each candidate; if any of the candidates have greater than 50% of the total 1st choice votes they win.  Otherwise, ignore votes for the candidate in last place and recount, promoting other candidates accordingly.

Here’s my entry:

  1 $results=Get-Content 'c:\scripts\votes.txt'
  2 $candidates = 4
  3 $eliminated = @{}
  4 
  5 for ($i = $candidates - 1; $i -ge 0; $i -- ) {
  6 	$votes = @{}   # Accumulated count of votes for each candidate
  7 	$votecount = 0    # Tally total number of votes cast
  8 	foreach ($vote in $results) {
  9 		$votecount ++ 
 10 		foreach ($name in $vote.split(',')) {
 11 			if ( ! $eliminated[$name]) {
 12 				$votes[$name] ++ ; break
 13 			}
 14 		}
 15 	}
 16 	$names = $votes.psbase.keys|sort -Descending {$votes[$_]}
 17 
 18 	if ($votes[$names[0]] / $votecount -gt 0.5) { 
 19 		"The winner is $($names[0]) with {0:p1} of the vote" -f ($votes[$names[0]] / $votecount)
 20 		break
 21 	}
 22 	else {
 23 		$eliminated[$names[$i]]=$TRUE   # Eliminate loser and count again...
 24 	}
 25 }

The basic vote counting part of the script is between lines 6-24.  This is broken down into two main sections: a scan of the votes collecting counts; and a decision about a winner.  Lines 8-15 actually count the votes – take the first place from each ballot paper and if the candidate has not been eliminated add a first place vote to his count (in hash $votes, indexed by candidate name).  If the candidate has been eliminated check the next candidate and so on.

Once all counted, line 16 sorts the hash table by total votes and saves the result in $names (1st place candidate in $names[0])

Line 18 checks if the candidate with the highest result actually achieved more the 50% of the vote – if so the result is announced and the script ends.  If this isn’t the case the candidate with the lowest score is added to a hash of eliminated candidates at line 23.

The process is then repeated up to "$candidate" times at line 5.  The rather odd looking sequence $i=3..0 is to enable the last place candidate to be identified (in the first round of counting the last place candidate will be in $names[3] – see line 23).

Not very elegant I’m afraid.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s