# How Voting Systems Work 6, Exercise 1: does dropping a losing candidate change the winner?
# Assumed, invented profile: 13 voters rank four candidates. For each method, remove each
# non-winning candidate in turn and report whether the winner changes (an independence test).
from collections import Counter

def plurality(ballots):
    tally = Counter(b[0] for b in ballots)
    return max(sorted(tally), key=tally.get)

def borda(ballots):
    k = len(ballots[0])
    points = {c: 0 for c in sorted(ballots[0])}
    for b in ballots:
        for place, c in enumerate(b):
            points[c] += k - 1 - place
    return max(points, key=points.get)

def irv(ballots):
    alive = set(ballots[0])
    while True:
        tally = Counter({c: 0 for c in alive})
        for b in ballots:
            tally[next(c for c in b if c in alive)] += 1
        top = max(sorted(tally), key=tally.get)
        if tally[top] * 2 > len(ballots) or len(alive) == 1:
            return top
        alive.remove(min(sorted(tally), key=tally.get))

groups = [
    (4, ("Ana", "Dee", "Bo", "Cy")),
    (3, ("Bo", "Cy", "Dee", "Ana")),
    (3, ("Cy", "Bo", "Dee", "Ana")),
    (2, ("Dee", "Ana", "Cy", "Bo")),
    (1, ("Ana", "Bo", "Cy", "Dee")),
]
ballots = [r for n, r in groups for _ in range(n)]
for label, rule in (("plurality", plurality), ("Borda", borda), ("instant-runoff", irv)):
    w = rule(ballots)
    changes = []
    for drop in sorted(ballots[0]):
        if drop == w:
            continue
        reduced = [tuple(c for c in b if c != drop) for b in ballots]
        if rule(reduced) != w:
            changes.append(f"{drop} -> {rule(reduced)}")
    print(f"{label:<15} winner {w}; winner changes when dropping:", changes or "nobody")

# Output when run:
# plurality       winner Ana; winner changes when dropping: ['Bo -> Cy', 'Cy -> Bo']
# Borda           winner Bo; winner changes when dropping: ['Cy -> Dee', 'Dee -> Ana']
# instant-runoff  winner Ana; winner changes when dropping: nobody