Festival jury ballots

Every juror at the short-film festival ranks all the finalists, first to last. The chair now has to turn a stack of ballots into a single ordering, and the rule she reads out is not "most first places wins".

The problem

Each finalist has a one-letter code. A ballot is a string listing all the finalists in that juror's order, best first, so every ballot is a permutation of the same codes.

The rule is a cascade. Compare two films by how many jurors put them first: more firsts ranks higher. On a tie, compare how many put them second, then third, and so on down the ballot. If two films are tied at every placement, the earlier code wins — the programme prints alphabetically when the jury cannot separate two entries.

Input. ballots — a list of strings, each a permutation of the same uppercase finalist codes.

Output. The final ranking as a single string, best first.

Example.

ballots = ["FKM", "MFK", "FMK"]   ->  "FMK"

F takes two firsts, M one, K none, so F leads. M and K each take one second place, but M has one first and K has none, so M is second and K last.

A second example, where the whole decision happens below first place:

ballots = ["QWZ", "QZW"]          ->  "QWZ"

Q wins outright with two firsts. W and Z each have zero firsts, one second and one third — identical at every placement — so the alphabet breaks the tie and W is printed above Z.

Constraints.

• 1 <= len(ballots) <= 1000
• every ballot has the same length m, 1 <= m <= 26
• codes are distinct uppercase letters; each appears exactly once per ballot

Hints

Approach

Brute force

Sort the finalists with a comparator that, for each pair, walks every ballot counting placements until the two films differ. One comparison costs O(n · m), and a sort makes about m log2 m of them: for 1000 ballots and 26 finalists, roughly 3 × 10⁶ interpreted steps recomputing counts that never change.

The insight

A film's entire standing is one vector — how many ballots put it first, how many second, and so on — and tuples already compare exactly the way the festival rule reads.

Tuples and lists compare left to right and stop at the first difference, which is the cascade for free. Count once in a single pass, negate each count so more votes sorts earlier, and append the code as the last component. Codes are distinct, so no two keys are equal: the ordering is total and no sort implementation can disagree about the result.

Algorithm

1. Read one ballot to learn the codes and the number of places m.
2. Give each code a list of m zeros.
3. For every ballot, add one to each code's count at its position.
4. Sort the codes by ([-count for count in tally[code]], code).
5. Join the sorted codes into a string.

Complexity

Time O(n·m + m² log m) — one pass over all n·m ballot entries, then a sort of m keys that are m long. Space O(m²) for the tally.

Solution

"""Festival jury ballots — a tuple key holding one sort level per placement."""


def solve(ballots):
    if not ballots:
        return ''
    places = len(ballots[0])
    tally = {code: [0] * places for code in ballots[0]}
    for ballot in ballots:
        for place, code in enumerate(ballot):
            tally[code][place] += 1

    # Key: placement counts negated so more votes sorts earlier, then the code
    # itself ascending. Codes are distinct, so no two keys are ever equal and
    # the ordering is total — the result does not depend on the sort's internals.
    def key(code):
        return ([-count for count in tally[code]], code)

    return ''.join(sorted(tally, key=key))

TESTS = [
    ((['FKM', 'MFK', 'FMK'],), 'FMK'),
    ((['QWZ', 'QZW'],), 'QWZ'),
    ((['DBCA'],), 'DBCA'),
    ((['AB', 'BA', 'AB', 'BA'],), 'AB'),
    ((['R'],), 'R'),
    ((['ZY', 'YZ'],), 'YZ'),
]

Pitfalls

• Ranking on first-place counts alone cannot separate W and Z in the second example, and whichever the sort happens to emit first is luck, not the rule.
• reverse=True on the whole sort flips the tie-break too, printing QZW. Negate the counts instead and leave the sort ascending, so the code component keeps running the right way.
• Building the tally only from codes seen at a given place leaves ragged lists that compare by length. Every code needs all m slots zero-filled.
• Recomputing the key inside a comparator is the brute force wearing a costume: the counts are fixed before the sort starts, so compute them once.

Variants

• Booth changeover run — the same key idea when a single number is enough.
• Order as a key — the lesson on tuple keys, stability, and when a comparator is genuinely unavoidable.