Hints for Programming Assignment 2 (Ranked Voting Scheme)

Pseudo Code main() function:

read ballots from file
while ballots contain more than one candidate:
    compute ranks (# of 1st place votes for each candidate)
    determine candidates to drop (these are candidates tied for lowest first-place votes)
    for each candidate to drop:
        update ballots by eliminating candidate from each ballot
        update ballots by removing empty ballots 
Determine and print winners

---

I. Here is a sample input and ITERATIONS to determine Winner:

INITIAL BALLOTS:

ballots = [['Red', 'Green'], ['Blue'], ['Green', 'Red', 'Blue'], ['Blue', 'Green', 'Red'], ['Green']]

ITERATION 1:

ranks= [(1, 'Red'), (2, 'Blue'), (2, 'Green')]
candidatesToDrop = ['Red']
Updated ballots = [['Green'], ['Blue'], ['Green', 'Blue'], ['Blue', 'Green'], ['Green']]

ITERATION 2:

ranks= [(2, 'Blue'), (3, 'Green')]
candidatesToDrop= ['Blue']
Updated ballots = [['Green'], ['Green'], ['Green'], ['Green']]

STOP because we have only ONE candidate in the ballots; DECLARE Green as winner

---

II. Another sample input and ITERATIONS to determine Winner:

INITIAL BALLOTS:

ballots = [['red', 'blue'], ['blue', 'red']]

ITERATION 1:

ranks = [(1, 'blue'), (1, 'red')]
candidatesToDrop = ['blue', 'red']
Updated ballots = []

STOP because we have ZERO candidates in the ballots; DECLARE all candidates dropped as winners: blue and red.

---

Useful Functions to Write

# returns list of candidates in ballots
# candidates([['Red','Green'], ['Blue'], ['Green','Red','Blue'], ['Blue','Green','Red'], ['Green']])
# = ['Red','Green','Blue']
def candidates(ballots):
  pass

# returns number of first-place votes received by candidate in first-place votes
# voteCount("Red",["Red","Blue","Red","Green","Red"]) = 3
def voteCount(candidate,votes):
  pass

# remove candidate from each ballot in ballots and return updated ballots
# eliminate('Red',[['Red', 'Green'], ['Blue'], ['Green', 'Red', 'Blue'], ['Blue', 'Green', 'Red'], ['Green']]) 
# = [['Green'], ['Blue'], ['Green', 'Blue'], ['Blue', 'Green'], ['Green']]
def eliminate(candidate,ballots):
  pass

# remove empty ballots from ballots and return updated ballots
# remove_empty_ballot([['Red', 'Green'], [], ['Green', 'Red'], ['Green', 'Red'], ['Green']])
# = [['Red', 'Green'], ['Green', 'Red'], ['Green', 'Red'], ['Green']]
def remove_empty_ballot(ballots):
  pass

# compute ranks = list of pairs of number of first-place votes and candidate 
# sorted lowest to highest
# rank_first_preferences([['Red', 'Green'], ['Blue'], ['Green', 'Red', 'Blue'], ['Blue', 'Green', 'Red'], ['Green']])
# = [(1, 'Red'), (2, 'Blue'), (2, 'Green')]
def rank_first_preferences(ballots):
  pass

# find candidates to drop by finding lowest ranked candidates
# find_lowest([(1, 'Red'), (2, 'Blue'), (2, 'Green')])
# = ['Red']
def find_lowest(ranks):
  pass

# returns True if ballots contain 0 or 1 candidate; False otherwise
# single_or_no_candidate([['Red', 'Green'], ['Blue'], ['Green', 'Red', 'Blue'], ['Blue', 'Green', 'Red'], ['Green']])
# = False
# single_or_no_candidate([['Red'],['Red'],['Red']]) = True
# single_or_no_candidate([]) = True
def single_or_no_candidate(ballots):
  pass