Fairground scoreboard

The prize board at a fairground is a rail of wooden panels, each stamped with a number. Hung in a row the panels read as one long number, and the order you pick decides how big that number is.

The problem

Every panel carries one whole number, printed without leading zeros, and you may hang them in any order. The digits run together with no gaps: panel 7 next to panel 76 reads 776, and the same pair the other way round reads 767.

Hang every panel exactly once so the board reads as large as possible, and return the reading as a string — ten thousand panels spell tens of thousands of digits, which no integer type holds. An all-zero crate reads "0".

Input. panels — a list of non-negative integers, one per panel, at least one panel.

Output. A string: the largest number the panels can spell when hung in some order.

Example.

panels = [7, 76, 761]   ->  "776761"

7 hangs first because 7 then 76 reads 776, while 76 then 7 reads 767 — the smallest panel by value goes first.

A second example, where the panel with the largest value is not the panel that goes first:

panels = [3, 30, 34, 5, 9]   ->  "9534330"

3 beats 30 because 330 beats 303, even though 30 is the bigger number. An all-zero crate collapses:

panels = [0, 0]   ->  "0"

Constraints.

• 1 <= len(panels) <= 10^4
• 0 <= panels[i] <= 10^9
• The answer may run to 10^5 digits, so it comes back as a string.

Hints

Approach

Brute force

Hang the panels in every order and keep the largest reading: n! boards, each costing the total digit count to build. Ten panels is 3.6 million strings, twelve is 479 million.

The insight

Panel a belongs before panel b exactly when the text a + b is not smaller than the text b + a, and that pairwise rule is a genuine total order, so a single sort under it produces the whole board.

Two readings of the same pair have identical length, so comparing them as text is the same as comparing them as numbers. The rule is transitive because asking whether a + b beats b + a is the same as asking whether the endless repetition aaaa… beats bbbb…, and that is an ordering on strings. Transitivity is the precondition a sort needs; without it the comparator hands back different boards for different starting orders.

Algorithm

1. Turn every panel into its printed text.
2. Sort the texts so that a precedes b when a + b > b + a.
3. Join the sorted texts into one string.
4. If the first character is 0, every panel is zero: return "0".

Complexity

Time O(n log n · d), where d is the digit count of the widest panel — about n log n comparisons, each building two strings of at most 2d characters. Space O(n · d) for the text copies.

When panels hold at most d digits there is a counting route: pad each panel by repeating its own digits out to length d — the endless-repetition key above — and bucket by that value, for O(n + 10^d). It wins only while 10^d stays near n.

Solution

"""Fairground scoreboard — sort panels by the pairwise concatenation order."""

from functools import cmp_to_key


def board_order(a, b):
    """Negative when a belongs before b, i.e. when a + b reads larger."""
    if a + b > b + a:
        return -1
    if a + b < b + a:
        return 1
    return 0


def solve(panels):
    labels = [str(panel) for panel in panels]
    # invariant after the sort: swapping any two adjacent panels cannot
    # increase the reading, and the order is total, so no board is larger.
    labels.sort(key=cmp_to_key(board_order))
    reading = "".join(labels)
    # A leading zero can only happen when every panel is zero.
    return "0" if reading[0] == "0" else reading

TESTS = [
    (([7, 76, 761],), "776761"),
    (([3, 30, 34, 5, 9],), "9534330"),
    (([0, 0],), "0"),
    (([12],), "12"),
    (([5, 51],), "551"),
    (([10, 2],), "210"),
    (([0, 0, 0, 1],), "1000"),
]

Pitfalls

• Sorting by value, descending. [3, 30] becomes "303" instead of "330". The bigger number is not the better prefix.
• Sorting the texts lexicographically, descending. It agrees with the comparator often enough to look right: [5, 51] gives "515", because "51" > "5" as text, while the board should read "551".
• Joining without the all-zero check. [0, 0] produces "00", which is not a number anyone prints on a board.

Variants

• Mosaic diagonals — sorting again, but the hard part there is which bucket an element belongs to.
• Order as a key — why a key function beats a comparator whenever the order can be written as one.