Movie Club Instant Runoff Voting

irv.py

import csv
from collections import defaultdict
import copy
import random

def tabulate(voters, round=1):
	votes = defaultdict(int)

	for voter in voters:
		if len(voter) == 0: # abstention
			continue

		votes[voter[0]] += 1

	total_votes = sum(votes.values())
	winnerval = max(votes.values())
	eliminated = min(votes.values())

	candidates_remaining = len(votes.values())
	winners = [ candidate for candidate, total in votes.items() if total == winnerval ]
	losers = [ candidate for candidate, total in votes.items() if total == eliminated ]

	# TIE
	# This check must be computed first to make sure floating point
	# errors do not result in a 0.499999991 and 0.500000001 race being
	# inaccurately called.
	if winnerval == eliminated:
		return [ votes.keys(), winnerval ] 

	winning_proportion = float(winnerval) / float(total_votes)

	# WINNER, Majority Candidate
	if winning_proportion > 0.50:
		return [ winners, winnerval ]

	# Candidate elimination
	next_voters = copy.deepcopy(voters)
	for voter in next_voters:
		for loser in losers:
			try:
				voter.remove(loser)
			except ValueError:
				continue

	return tabulate(next_voters, round + 1)

winners, votes = tabulate([
	['Scarface', 'Her', 'The Wall'],
	['The Wall', 'Her', 'Scarface'],
	['Her', 'Scarface', 'The Wall'],
	['Her', 'Scarface', 'The Wall'],
	['Scarface', 'Don Quixote', 'The Wall'],
])

if len(winners) > 1:
	print("A TIE BETWEEN " + ", ".join(winners)) + " WITH {} VOTES EACH".format(votes)
	print("RANDOMLY CHOOSING A WINNER: " + random.choice(winners))
else:
	print winners
	print "CONGRATULATIONS " + winners[0] + " WITH {} VOTES".format(votes)