Custom orders and comparator pitfalls

Custom orders are sort rules that you supply yourself, as a key or as a comparator. You need one whenever a problem’s order is neither numeric nor alphabetical. A key turns each item into a value that the built-in order already sorts correctly; a comparator looks at two items and says which goes first. Comparator pitfalls are the ways such a rule breaks a sort without any error, such as returning a boolean, never admitting a tie, or using <= where a strict order is needed. This lesson solves a problem whose order exists only as a comparison of two items, the largest number that a list of numbers spells side by side, then names each language’s comparator pitfalls.

The problem: the largest banner number

1. [5, 56, 9, 504, 50] gives "956550504": 9 leads, then 56, 5, 50 and 504.
2. [8, 89, 898] gives "898988". All three start with 8, and the shortest one goes last.
3. [0, 0, 0] gives "0", not "000".

The brute force: every order, and two shortcuts that fail

Try every order, join the numbers and keep the largest banner. Every banner of a team has the same length, so comparing banners as text compares them as numbers. The brute force is plainly correct, which makes it the referee for faster code, but a team of n jerseys has n! orders:

# The largest banner number by brute force: try every order of the jersey numbers and keep the largest result.
# Then two shortcuts that look right, checked against it on random teams.
import math
import random
from itertools import permutations


def as_number(text):
    """A banner of only zeros reads as 0, not 000."""
    return text.lstrip("0") or "0"


def largest_by_brute_force(jerseys):
    """Every order of the jerseys, n! of them; returns the largest banner and how many orders were tried."""
    tried = 0
    best = ""
    for order in permutations(jerseys):
        tried += 1
        banner = "".join(str(j) for j in order)
        # All banners have the same length, so comparing them as text compares them as numbers.
        if banner > best:
            best = banner
    return as_number(best), tried


def largest_value_first(jerseys):
    return as_number("".join(str(j) for j in sorted(jerseys, reverse=True)))


def largest_text_first(jerseys):
    return as_number("".join(sorted((str(j) for j in jerseys), reverse=True)))


for team in ([5, 56, 9, 504, 50], [0, 0, 0], [8, 89, 898]):
    banner, tried = largest_by_brute_force(team)
    print(f"{team} -> {banner} ({tried} orders tried)")

rng = random.Random(7)
teams = []
for _ in range(2_000):
    size = rng.randint(2, 5)
    # Numbers built from a few digits, so that shared prefixes such as 8, 89 and 898 are common.
    teams.append([int("".join(rng.choice("0589") for _ in range(rng.randint(1, 3)))) for _ in range(size)])

for name, shortcut in (("largest value first", largest_value_first), ("largest text first", largest_text_first)):
    wrong = [t for t in teams if shortcut(t) != largest_by_brute_force(t)[0]]
    first = min(wrong, key=len)
    print(f"{name}: wrong on {len(wrong):,} of {len(teams):,} teams, e.g. {first} gives {shortcut(first)}, "
          f"not {largest_by_brute_force(first)[0]}")

for n in (10, 15, 20):
    print(f"{n} jerseys: {math.factorial(n):,} orders")
digits = math.floor(math.lgamma(100_001) / math.log(10)) + 1
print(f"100,000 jerseys: the number of orders alone has {digits:,} digits")

[5, 56, 9, 504, 50] -> 956550504 (120 orders tried)
[0, 0, 0] -> 0 (6 orders tried)
[8, 89, 898] -> 898988 (6 orders tried)
largest value first: wrong on 1,185 of 2,000 teams, e.g. [80, 598] gives 59880, not 80598
largest text first: wrong on 554 of 2,000 teams, e.g. [590, 59] gives 59059, not 59590
10 jerseys: 3,628,800 orders
15 jerseys: 1,307,674,368,000 orders
20 jerseys: 2,432,902,008,176,640,000 orders
100,000 jerseys: the number of orders alone has 456,574 digits

Ten jerseys already make 3,628,800 orders, and for 100,000 jerseys the number of orders has 456,574 digits. Two quick rules look as if they could replace the search, and the run checks both on 2,000 random teams. Largest value first was wrong on 1,185 of them, for example on [80, 598], where the leading 8 should beat 598. Largest text first was wrong on 554, for example on [590, 59], where the shorter 59 should lead. Neither rule looks at what decides a banner: the digits that come first once two numbers are joined.

The key idea: let both joins decide

Take two jerseys, a and b, as text. On the banner one of them comes first, and nothing else on the banner depends on that choice, so compare the two joins: if a + b is the larger number, a goes first. For 5 and 504 the joins are 5504 and 5045, so 5 leads; for 59 and 590 they are 59590 and 59059, so 59 leads. Sort the team with that comparison, join it, and the banner is the largest one. Finally, turn a banner that starts with 0 into "0". Only the number 0 starts with that digit and the comparison puts it last, so a leading zero means that every jersey is 0.

Two facts make this safe: the comparison must be a consistent order, or no sort can be trusted with it, and the order it produces must beat every other order, not just look right locally. Both take a few lines to prove, and interviewers often ask for the second. The cost is one sort, about n log₂ n comparisons: roughly 1.7 million for 100,000 jerseys, each joining two texts of at most 10 digits.

A worked example

The sorted order of the first example, checked pair by pair:

Every pair of neighbours passes, and the banner, 956550504, is the one the brute force found.

Keys and comparators in five languages

Every language accepts custom orders, but each expects its own form:

• Python: sorted() and list.sort() take a key only; functools.cmp_to_key turns a comparator into a key, as long as its result is below zero, zero or above zero.
• JavaScript: Array.prototype.sort() takes a comparator whose result must be a number: below zero puts the first item first, above zero the second.
• Java: a Comparator returns a negative, zero or positive int; Comparator.comparing builds one from a key.
• C++: std::sort takes a predicate that is true only when its first argument goes strictly before the second.
• Go: slices.SortFunc takes a function that returns a negative, zero or positive int.

Comparator pitfalls follow from those contracts, and each of them can pass a small test:

• A boolean instead of a number: in JavaScript true counts as 1 and false as 0, so (a, b) => a > b never says “a first”.
• No answer of zero: a comparator that never reports a tie breaks its contract whenever two items are equal.
• <= where a strict order is needed: C++ requires comp(a, a) to be false.
• Subtracting to compare: b - a can overflow a Java int, as the Java toolkit lesson shows.

Exercise and self-check

Write the banner yourself first. The sample tests include a stress test against every order of 300 small teams.

largest_banner([5, 56, 9, 504, 50])   # "956550504"
largest_banner([8, 89, 898])          # "898988"
largest_banner([0, 0, 0])             # "0"

def largest_banner(jerseys):
    """The largest number, as a string, made by writing every jersey number side by side once."""
    # Replace this line with your code.
    return ""

import random
import sys
from itertools import permutations

from banner import largest_banner

LINE_LIMIT = 4_000_000


def trusted(jerseys):
    """Every order of a small team, the largest banner kept."""
    best = max("".join(map(str, order)) for order in permutations(jerseys))
    return best.lstrip("0") or "0"


class TooSlow(Exception):
    pass


def run_limited(jerseys):
    """Call largest_banner, stopped after LINE_LIMIT executed lines (a fair time limit)."""
    executed = 0

    def count_lines(frame, event, arg):
        nonlocal executed
        if event == "line":
            executed += 1
            if executed > LINE_LIMIT:
                raise TooSlow
        return count_lines

    sys.settrace(count_lines)
    try:
        return largest_banner(jerseys)
    except TooSlow:
        raise AssertionError(f"too slow: more than {LINE_LIMIT:,} lines ran; aim for one sort") from None
    finally:
        sys.settrace(None)


def test_examples():
    """the examples from the prompt"""
    assert largest_banner([5, 56, 9, 504, 50]) == "956550504"
    assert largest_banner([8, 89, 898]) == "898988"
    assert largest_banner([0, 0, 0]) == "0"


def test_single_jersey():
    """one jersey is the whole banner"""
    assert largest_banner([7]) == "7"
    assert largest_banner([1_000_000_000]) == "1000000000"
    assert largest_banner([0]) == "0"


def test_shared_prefixes():
    """12 and 121, 3 and 30: the shorter number is not always first"""
    assert largest_banner([121, 12]) == "12121"
    assert largest_banner([12, 121]) == "12121"
    assert largest_banner([30, 3, 34]) == "34330"
    assert largest_banner([10, 2]) == "210"


def test_zeros_with_other_numbers():
    """zeros go last, and only an all-zero banner collapses to 0"""
    assert largest_banner([0, 0, 1]) == "100"
    assert largest_banner([0, 10, 100]) == "101000"


def test_input_not_changed():
    """the list passed in keeps its order"""
    team = [3, 30, 34, 5, 9]
    largest_banner(team)
    assert team == [3, 30, 34, 5, 9]


def test_stress_against_every_order():
    """300 random teams of up to 6 jerseys, built from few digits so that prefixes repeat"""
    rng = random.Random(42)
    for _ in range(300):
        team = [int("".join(rng.choice("0189") for _ in range(rng.randint(1, 3)))) for _ in range(rng.randint(1, 6))]
        got, want = largest_banner(list(team)), trusted(team)
        assert got == want, f"jerseys={team}: got {got!r}, expected {want!r}"


def test_large_team_is_fast():
    """20,000 jerseys within a fixed number of executed lines"""
    rng = random.Random(7)
    team = [rng.randint(0, 10**9) for _ in range(20_000)]
    banner = run_limited(team)
    assert len(banner) == sum(len(str(j)) for j in team)
    assert sorted(banner) == sorted("".join(map(str, team)))

The banner order in five languages, with its proof Pro: opens with a Pro, Premium or Ultimate pass

Comparator pitfalls reproduced in four languages Pro: opens with a Pro, Premium or Ultimate pass

Keys or comparators: multi-key orders and measured costs Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• A custom order reaches a sort as a key, which maps each item to a value, or as a comparator of two items.
• The largest banner comes from one comparison: a goes first when a + b is the larger number.
• A comparator must agree with itself: test it on many ties before you trust it.