The Moot's Long Count
The moot of bitwick chooses its reeve by the long count. The sealed ballots are stacked on the table in the moot house, and the clerk who used to work the tally has gone to the coast. The notice asks for one thing only: the name.
Input. ballots is a list of ballots. A ballot is a list of candidate names (strings of lowercase letters a-z), written most preferred first and least preferred last. A ballot may list any number of names, including none, and never lists the same name twice. The candidates are exactly the names that appear on at least one ballot.
The count. Every candidate begins standing. Counting proceeds in rounds.
In a round, each ballot gives its vote to the first name on it that is still standing. A ballot with no standing name on it gives no vote and is not part of that round's total. Let t be the number of ballots that gave a vote this round.
- If some standing candidate has more than t / 2 votes, that candidate is the winner and the count ends. - Otherwise exactly one standing candidate is struck and a new round begins. The one struck is chosen by the tests below, each used only to break a tie left by the test before it: 1. fewest votes in this round (a standing candidate with no votes has zero); 2. fewest votes in the first round (that first tally is fixed once, at the start, and never recomputed); 3. named on the fewest ballots, counting each ballot that lists the candidate anywhere, whatever the position, once; 4. the name latest in alphabetical order.
Return. The winner's name, as a string. If no name appears on any ballot, return the empty string. Whenever at least one name appears on at least one ballot, the count always reaches a winner.
examples
- case 1
ballots = [["a"], ["a"], ["b","c"], ["b","c"], ["c"], []]"a" — Round 1 counts 5 ballots (the blank one never counts): a 2, b 2, c 1, no majority, so c is struck. Round 2: the lone "c" ballot is now spent, so only 4 ballots count, a 2 and b 2, and every tie-break through mentions is level, so b (later alphabetically) is struck. Round 3: only 2 ballots still count, both for a, and 2 of 2 is a majority. - case 2
ballots = [["a","b"], ["b"], ["c"], ["c"]]"c" — Round 1: a 1, b 1, c 2 of 4, no majority; a and b tie on this round and on the first round, but a is named on 1 ballot and b on 2, so a is struck. Round 2: b 2, c 2 of 4, no majority; the first-round tally was b 1 and c 2, so b is struck. Round 3: only 2 ballots still count, both for c. - case 3
ballots = [[], []]"" — no name appears on any ballot.
- reward
- 540 XP
- signature
longCount
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- the clerk's worked tally
- struck by mentions, then by the first tally
- an empty ballot box
- every ballot left blank
- a single voter
- outright majority in the first round
- a name nobody ranks first
- the blank ballot does not count
- five candidates, every tie-break in turn