Your task is to implement a function that calculates an election winner from a list of voter selections using an [Instant Runoff Voting](http://en.wikipedia.org/wiki/Instant-runoff_voting) algorithm. If you haven't heard of IRV, here's a basic overview (slightly altered for this kata):

- Each voter selects several candidates in order of preference.
- The votes are tallied from the each voter's first choice.
- If the first-place candidate has more than half the total votes, they win.
- Otherwise, find the candidate who got the least votes and remove them from each person's voting list.
- In case of a tie for least, remove all of the tying candidates.
- In case of a complete tie between every candidate, return nil(Ruby)/None(Python)/undefined(JS).
- Start over.
- Continue until somebody has more than half the votes; they are the winner.

Your function will be given a list of voter ballots; each ballot will be a list of candidates (symbols) in descending order of preference. You should return the symbol corresponding to the winning candidate. See the default test for an example!

Difficulty: interview

Starter code:

def runoff(voters):
	

Solutions:
from collections import Counter

def runoff(voters):
    while voters[0]:
        poll = Counter(ballot[0] for ballot in voters)
        winner, maxscore = max(poll.items(), key = lambda x: x[1])
        minscore = min(poll.values())
        if maxscore * 2 > len(voters):
            return winner
        voters = [[c for c in voter if poll[c] > minscore] for voter in voters]

from collections import Counter

def runoff(voters):
    numVoters = len(voters)
    while voters[0]:
        c = Counter( voters[i][0] for i in range(numVoters) )
        
        maxVote = max(c.values())
        if maxVote > numVoters/2:
            return [elt for elt in c if c[elt] == maxVote][0]
        
        for k in set(c.keys()) ^ set(voters[0]): c[k] = 0   # add those who addn't receive any "first choice vote"
        minVote = min(c.values())
        voters = [[ p for p in v if not p in [elt for elt in c if c[elt] == minVote] ] for v in voters]
        
    return None

def runoff(voters):
    if voters == []:
        return None
    elif len(voters[0]) == 1:
        return voters[0][0]
    voters_dict = {elem: [x[0] for x in voters].count(elem) for elem in voters[0]}
    expelled = sorted([voters_dict.get(x) for x in voters_dict])[0]
    return runoff([i for i in [[x for x in choices if
                                voters_dict.get(x) != expelled] for choices in voters] if i != []])

def runoff(voters):
    if len(voters[0]) < 1:
        return None
    votes = count_votes(voters)
    possible_winner = get_winner(votes)
    if votes[possible_winner] > (len(voters) / 2):
        return possible_winner
    else:
        losers = get_losers(votes)
        new_voters = [[candidate for candidate in voter if candidate not in losers] for voter in voters]
        return runoff(new_voters)

def count_votes(voters):
    votes = {candidate: 0 for candidate in voters[0]}
    for voter in voters:
        votes[voter[0]] += 1
    return votes

def get_winner(votes):
    return max(votes, key=lambda x: votes[x])

def get_losers(votes):
    min_vote = min(votes.values())
    return [candidate for candidate in votes if votes[candidate] == min_vote]

from collections import Counter

def runoff(voters):
    cands = [cand for cand in voters[0] if cand]
    first_col = [row[0] for row in voters]
    counter = Counter(first_col)

    for candidate in counter:
        if counter[candidate] > len(voters)/2:
            return candidate and candidate or None

    excluded = [x for x in counter if counter[x] == min(counter.values())]
    excluded.extend(set(cands) - set(first_col))

    for arr in voters:
        for i,x in enumerate(arr):
            if x in excluded:
                arr[i] = None
    
   
    out = []
    for arr in voters:
        names, banned = [],[]
        for val in arr:
            if val:
                names.append(val)
            else:
                banned.append(val)
        
        out.append(names + banned)
    
    return runoff(out)


def runoff(votes):
    voters, candidates = len(votes), votes[0]
    while votes:
        round = [vote[0] for vote in votes]
        polls = sorted((round.count(candidate), candidate) for candidate in candidates)
        min_poll, (max_poll, winner) = polls[0][0], polls[-1]
        if max_poll / voters > 0.5:
            return winner
        if len(polls) > 1 and max_poll == min_poll:
            return None
        loosers = [candidate for poll, candidate in polls if poll == min_poll]
        for voter in votes:
            for candidate in loosers:
                voter.remove(candidate)


from collections import Counter

def runoff(voters):
    while sum(voters, []):
        poll = Counter(ballot[0] for ballot in voters)
        
        scores = sorted(poll.values())
        if scores[-1] * 2 > len(voters):
            return next((c for c in poll if poll[c] == scores[-1]))
        elif scores[-1] == scores[0]:
            return
        voters = [[c for c in voter if poll[c]  > scores[ 0]] for voter in voters]


def runoff(li):
    while all(li) and not all(len(k) == 1 for k in li):
        d = {l: 0 for k in li for l in k}
        for i in range(len(li)):
            d[li[i][0]] += 1
        m = min(d.values())
        li = [[j for j in i if d[j] != m] for i in li]
    return li[0][0] if li[0] else None

from collections import Counter

def runoff(voters):
    half_voters = len(voters)/2
    tally = {}
    for votes in voters:
        vote = votes[0]
        if vote in tally:
            tally[vote] += 1
        else:
            tally[vote] = 1
            
    high_counts = Counter(tally).most_common()
        
    if high_counts[0][1] > half_voters:
        return high_counts[0][0]
        
    
    lowest = []
    
    lowest_count = -1
    
    for i in range(len(high_counts)):
        current = high_counts[(-1 - i)]
        if current[1] == lowest_count or lowest_count == -1:
            lowest_count = current[1]
            lowest.append(current[0])
        else: break
    
    if len(lowest) == len(high_counts):
        return None
    
    voters = [[vote for vote in votes if (vote in tally) and (vote not in lowest)] for votes in voters]
    
    return runoff(voters)

def runoff(voters):

    candidate_votes = {candidate:0 for candidate in voters[0]}
    #tally votes
    for voter in voters:
        candidate_votes[voter[0]] += 1
    
    #decide winner or runoff
    total_votes = sum(candidate_votes.values())
    #clear winner
    for x in list(candidate_votes.keys()):
        if candidate_votes[x] > total_votes/2:
            return x
    #runoff
    least = min(candidate_votes.values())
    losers = [x for x in list(candidate_votes.keys()) if candidate_votes[x] == least]
    if len(losers) == len(list(candidate_votes.keys())):
        return None
    
    for voter in voters:
        for loser in losers:
            voter.remove(loser)
    return runoff(voters)