# How Voting Systems Work 3, Exercise 2: instant-runoff with a step-by-step log
# 40 voters, five candidates, some ballots rank only a few candidates (assumed, invented numbers).
# Print every round, then say whether the winner holds a majority of ALL 40 ballots.
from collections import Counter

def irv(ballots, verbose=True):
    """Instant-runoff: drop the candidate with the fewest top choices, pass their ballots on,
    repeat until someone holds a majority of the ballots still in play.
    Assumption: a tie for last place is broken alphabetically (real rules differ)."""
    remaining = {c for b in ballots for c in b}
    round_no = 1
    while True:
        counts = Counter({c: 0 for c in remaining})
        for b in ballots:
            for c in b:                      # first candidate still standing on this ballot
                if c in remaining:
                    counts[c] += 1
                    break
        active = sum(counts.values())
        leader = sorted(counts, key=lambda c: (-counts[c], c))[0]
        if verbose:
            line = ", ".join(f"{c} {counts[c]}" for c in sorted(counts))
            print(f"round {round_no}: {line}  (in play {active}, exhausted {len(ballots) - active})")
        if counts[leader] > active / 2:
            if verbose:
                print(f"  {leader} has {counts[leader]} of {active}: winner")
            return leader
        fewest = min(counts.values())
        out = sorted(c for c in remaining if counts[c] == fewest)[0]
        if verbose:
            print(f"  eliminate {out}")
        remaining.discard(out)
        round_no += 1

ballots = (
    [("Ana", "Bo")] * 9
    + [("Bo", "Ana", "Cy")] * 6
    + [("Cy", "Dee", "Bo")] * 8
    + [("Dee", "Cy")] * 7
    + [("Eli",)] * 6
    + [("Eli", "Bo", "Ana")] * 4
)
winner = irv(ballots)
print("winner:", winner)

# Output when run:
# round 1: Ana 9, Bo 6, Cy 8, Dee 7, Eli 10  (in play 40, exhausted 0)
#   eliminate Bo
# round 2: Ana 15, Cy 8, Dee 7, Eli 10  (in play 40, exhausted 0)
#   eliminate Dee
# round 3: Ana 15, Cy 15, Eli 10  (in play 40, exhausted 0)
#   eliminate Eli
# round 4: Ana 19, Cy 15  (in play 34, exhausted 6)
#   Ana has 19 of 34: winner
# winner: Ana