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: MEDIUM
Tags: Data structures
Skill types: Data structures

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
		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]}
	for voter in voters:
		candidate_votes[voter[0]] += 1
	total_votes = sum(candidate_votes.values())
	for x in list(candidate_votes.keys()):
		if candidate_votes[x] > total_votes / 2:
			return x
	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)