# How Voting Systems Work 3, Exercise 3: hunt for an instant-runoff monotonicity failure
# Random 21-voter, 3-candidate profiles (seeded). A failure: the winner W would LOSE if one
# group of voters who ranked W below first moved W up one place (nothing else changed).
import itertools
import random
from collections import Counter

def irv(ballots, verbose=False):
    """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

names = ("Ana", "Bo", "Cy")
perms = list(itertools.permutations(names))

random.seed(3)
found = None
for trial in range(1, 20001):
    cuts = sorted(random.sample(range(1, 22), 5))
    sizes = [b - a for a, b in zip([0] + cuts, cuts + [21])]
    ballots = [p for p, s in zip(perms, sizes) for _ in range(s)]
    w = irv(ballots)
    for p, s in zip(perms, sizes):
        i = p.index(w)
        if s == 0 or i == 0:
            continue
        lst = list(p)
        lst[i - 1], lst[i] = lst[i], lst[i - 1]       # move W up one place
        changed = [b for b in ballots if b != p] + [tuple(lst)] * s
        if irv(changed) != w:
            found = (trial, sizes, w, p, tuple(lst), irv(changed))
            break
    if found:
        break

if found:
    trial, sizes, w, old, new, other = found
    print(f"found on random profile number {trial}")
    for p, s in zip(perms, sizes):
        if s:
            print(f"  {s:2d} voters: {' > '.join(p)}")
    print("winner:", w)
    print(f"now the {sizes[perms.index(old)]} voters with {' > '.join(old)} switch to {' > '.join(new)}:")
    print("winner:", other)
else:
    print("none found in 20000 profiles")

# Output when run:
# found on random profile number 36
#    4 voters: Ana > Bo > Cy
#    2 voters: Ana > Cy > Bo
#    5 voters: Bo > Ana > Cy
#    3 voters: Bo > Cy > Ana
#    5 voters: Cy > Ana > Bo
#    2 voters: Cy > Bo > Ana
# winner: Bo
# now the 2 voters with Cy > Bo > Ana switch to Bo > Cy > Ana:
# winner: Ana