#!/usr/bin/python
from copy import deepcopy
# functions
def read_data_file( filename,data ):
print "Reading file named %s." % filename
fo = open(filename, 'r')
num_ballots = int(next(fo).split()[0])
for line in fo:
array = line.split()
data.append([int(array[0]), int(array[1]), int(array[2]), int(array[3]), int(array[4])])
fo.close
return num_ballots
def in_ballots( L,ballots ):
found = -1
counter = -1
for list in ballots:
counter += 1
if found == -1:
if list[0] == L[0]:
if list[1] == L[1]:
if list[2] == L[2]:
if list[3] == L[3]:
if list[4] == L[4]:
found = counter
return found # returns -1 if not found, index in ballots if found
def combine_raw_data( raw,new ):
for list in raw:
index_of_list_in_new = in_ballots(list,new)
if index_of_list_in_new == -1: #list not currently in new, so add it!
new.append([list[0], list[1], list[2], list[3], list[4], 1])
else: #found in list, so increment the appropriate counter
new[index_of_list_in_new][5] += 1
return
def methodA ( L ):
first_votes = [0, 0, 0, 0, 0]
for list in L:
index = 0
while list[index] > 1:
index += 1
first_votes[index] += list[5]
winner = 0
for i in range(1,5):
if first_votes[i] > first_votes[winner]:
winner = i
#THIS IMPLICITLY IGNORES TIES, GIVING THE WIN TO THE FIRST WINNER IN THE LIST!
return [winner,first_votes]
def methodB ( L,FV,winnerA ):
#First we find the second-highest first place vote getter:
if winnerA == 0:
number2 = 1
else:
number2 = 0
for i in range(1,5):
#print FV[winnerA],FV[number2],FV[i]
if i != winnerA:
if FV[i] > FV[number2]:
number2 = i
#print winnerA, number2
#Now we see which of winner and number2 wins for each ballot type:
score = [0, 0] #spot 0 for winner, spot 1 for number2
for list in L:
if list[winnerA] < list[number2]: #winnerA has a better (lower) rank
score[0] += list[5]
else: #number2 has a better (lower) rank
score[1] += list[5]
#Finally, we set the winner:
if score[1] > score[0]:
winner = number2
else:
winner = winnerA
#print score
#print winner
#THIS IMPLICITLY IGNORES TIES, GIVING THE WIN TO THE WINNER OF METHOD A!
return winner
def find_lowest_first_votes ( FV ):
done = 0
i=-1
while done==0 and i<5:
i += 1
if FV[i] > -1:
worst=i #starting point for worst
done = 1
for i in range(0,5):
if FV[i] < FV[worst] and FV[i] > -1:
worst = i
return worst
def methodC ( L_orig,FV_orig ):
FV = deepcopy(FV_orig)
L = deepcopy(L_orig)
elim = [0, 0, 0, 0, 0] #keeps track of which candidates have been eliminated (0=no,1=yes)
for j in range(1,5):
#find the current lowest first-place vote getter
worst = find_lowest_first_votes(FV)
elim[worst] = 1
#print FV
#print "worst : ", worst+1
#print elim
for list in L: #cycle through all ballots
if list[worst] == 1: #lowest first-place vote is #1 for this set of ballots
for k in range(0,5): #decrement all ranks, creating a new #1, #2, etc.
list[k] += -1
#now find the new lowest (best) ranked candidate for these ballots that has not yet been eliminated
done = 0
rk = 1
while done == 0:
for m in range(0,5): #go through ballot to find which one is rk, call it new1 (for now)
if list[m] == rk:
new1 = m
if elim[new1] == 1: #this one has been eliminated, so increment rk and keep going
rk += 1
else: #got a valid next-best candidate for this set of ballots, so done=1
done = 1
#print "HERE", list, new1
FV[worst] -= list[5] #remove list[5] votes from #first-place votes for worst
FV[new1] += list[5]
if FV[worst] > 0: #somehow failed to find all ballots with worst as #1
print "Something went wrong in Method C!!"
else:
FV[worst] = -1 #signal to find_lowest_first_votes that this index is out of contention
#print FV
#Now we just find the winner
for i in range(0,5):
if FV[i] > 0:
winner = i
return winner
def methodD ( L ):
total_score = [0,0,0,0,0]
scores = [5,4,3,2,1]
#print L
#add up score for each candidate
for list in L:
for i in range(0,5):
total_score[i] += scores[list[i]-1]*list[5]
#print total_score
#now just find the max
winner = 0
for i in range(1,5):
if total_score[i] > total_score[winner]:
winner = i
#SAME CAVEAT ABOUT TIES AS ABOVE!
return winner
def methodE ( L ):
wins = [0, 0, 0, 0, 0]
for i in range(0,4): #i,j cycle through all pairs of candidates
for j in range(i+1,5):
score = [0,0] #one-on-one score between candidates i,j
for list in L:
if list[i] < list[j]: #candidate i is preferred
score[0] += list[5]
else: #candidate j is preferred
score[1] += list[5]
if score[1] > score[0]:
wins[j] += 1
else: #win goes to candidate i in case of a tie
wins[i] += 1
#print wins
#Now we just find the winner!
#SAME CAVEAT ABOUT TIES AS ABOVE!
winner = 0
for i in range(1,5):
if wins[i] > wins[winner]:
winner = i
return winner
# First, we grab the data from the file in a raw form (duplicates allowed)
raw_data = []
num_ballots = read_data_file("input",raw_data) #calls function to read file "input", returns # voters
print "Successfully read in %d ballots." % num_ballots #number of voters - sanity check
#tests for in_ballots:
#print in_ballots([1,2,3,4,5], raw_data) #should get 37
#print in_ballots([1,1,1,1,1], raw_data) #should get -1
#print in_ballots([1,2,3,4,5], []) #should get -1
# Now we combine duplicates into the main data structure, ballots
ballots = []
combine_raw_data(raw_data,ballots)
print "Here's the table of data in the form [[votes for #1, ..., votes for #5, #ballots like this], [next ballot], ...] :"
print ballots
#tests for combine_raw_data
#print raw_data
#print ballots
#tests for find_lowest_first_votes
#print find_lowest_first_votes([18, 9, 6, 10, 12]) #should be 2
#print find_lowest_first_votes([-1, 0, -1, 5, 2]) #should be 1
#print find_lowest_first_votes([-1, -1, 7, -1, -1]) #should be 2
#Method A!
print "\nComputing Method A winner..."
[winner,first_votes] = methodA(ballots)
print "Winner of Method A : %d (ordered 1-5) : ", winner+1, "\n"
winnerA = winner
#print first_votes
#Method B!
print "Computing Method B winner..."
winner = methodB(ballots,first_votes,winnerA)
print "Winner of Method B : %d (ordered 1-5) : ", winner+1, "\n"
#Method C!
print "Computing Method C winner..."
winner = methodC(ballots,first_votes)
print "Winner of Method C : %d (ordered 1-5) : ", winner+1, "\n"
#Method D!
print "Computing Method D winner..."
winner = methodD(ballots)
print "Winner of Method D : %d (ordered 1-5) : ", winner+1, "\n"
#Method E!
print "Computing Method E winner..."
winner = methodE(ballots)
print "Winner of Method E : %d (ordered 1-5) : ", winner+1, "\n"