The dispatch console

A dispatcher types a destination one key at a time, and the console has to redraw its three suggestions between keystrokes. Re-reading the whole log on every key is the thing to avoid.

The problem

A taxi office's console remembers every destination phrase its dispatchers have sent and how often. A phrase is lowercase letters and spaces.

A dispatcher types a phrase one character at a time. After each character the console lists up to three past phrases beginning with everything typed so far, most-sent first, ties broken alphabetically; fewer than three matches shows fewer, and none shows nothing.

The character # ends the phrase: the console files what was typed as sent once more — a phrase never sent before starts at one — shows nothing, and hands the next character a fresh line.

Input. history — past phrases; counts — how many times each was sent, in the same order; keystrokes — the characters typed, in order, # included.

Output. A list with one entry per keystroke: a tuple of up to three phrases, best first. # gives the empty tuple, and so does a prefix nothing matches.

Example.

history = ["harbour gate", "harbour road", "hill farm"], counts = [5, 3, 2]
keystrokes = "ha#"
->  [("harbour gate", "harbour road", "hill farm"),
     ("harbour gate", "harbour road"),
     ()]

After h all three phrases match and rank by tally; after a only the harbour pair survives; # files ha as a phrase sent once and clears the line.

A second example, where the phrase # files joins the ranking:

history = ["depot", "depot yard"], counts = [2, 2]
keystrokes = "de#de"
->  [("depot", "depot yard"), ("depot", "depot yard"), (),
     ("depot", "depot yard", "de"), ("depot", "depot yard", "de")]

depot and depot yard are tied at two, so the alphabet separates them. The newly filed de has been sent once and comes third.

Constraints.

• 0 <= len(history) <= 10^4, len(counts) == len(history)
• 1 <= len(phrase) <= 100, lowercase a-z and spaces
• 1 <= counts[i] <= 10^6
• 1 <= len(keystrokes) <= 10^4, and every # ends a phrase of at least one character

Hints

Approach

Brute force

After every keystroke, scan the history: test each phrase against the prefix, then sort the matches by tally and name. With 10⁴ phrases of 100 characters and 10⁴ keystrokes that is 10¹⁰ character comparisons, and the prefix test starts again from character one each time.

The insight

Hold a pointer into the prefix tree and keep a ready-made best three at every node: a keystroke is then one edge step, and filing a phrase can only disturb the nodes along that one phrase's path.

Three entries per node are enough, which is the part worth proving. Tallies only rise, and # raises exactly one phrase by one. Take any node above that phrase and any other phrase q that was outside its old best three: q was beaten by three phrases whose tallies did not fall, so q is still beaten by three and cannot enter the new best three. The new three therefore come from the old three plus the one phrase that moved — four candidates to rank, at constant cost. Nodes off the path see no change at all.

Algorithm

1. Build a trie over the phrases; each node keeps hot, up to three phrases from its subtree, ranked by tally descending then name ascending.
2. To file a phrase: raise its tally, then walk its path re-ranking hot plus this phrase at each node, keeping three. Seed the tree this way from the history.
3. Hold a pointer at the root and a buffer of what has been typed.
4. On a letter or space, step the pointer to that child and emit its hot; a missing child sends the pointer nowhere and the answer is empty.
5. On #, file the buffer as sent once more, clear it, return the pointer to the root, and emit nothing.

Complexity

Time O(S) to build, S the characters in the history, then O(1) per typed character — one dict lookup and a copy of at most three phrases — and O(L) per #, L the phrase length. Space O(S): one node per distinct prefix, holding three references each.

Solution

"""The dispatch console — a prefix tree whose every node carries its own top three."""

SHOWN = 3


class Node:
    """One node per distinct typed prefix, plus that prefix's ranked shortlist."""

    __slots__ = ("children", "hot")

    def __init__(self):
        self.children = {}
        self.hot = []            # up to SHOWN phrases, best first


def file_phrase(root, sent, phrase, times):
    """Raise one phrase's tally and refresh the shortlist along its own path."""
    sent[phrase] = sent.get(phrase, 0) + times
    node = root
    for ch in phrase:
        node = node.children.setdefault(ch, Node())
        # Tallies only ever rise and only this phrase moved, so a phrase outside
        # the old top three is still beaten by three others and cannot enter it.
        # The new top three lives in the old three plus this one phrase.
        candidates = set(node.hot)
        candidates.add(phrase)
        node.hot = sorted(candidates, key=lambda p: (-sent[p], p))[:SHOWN]


def solve(history, counts, keystrokes):
    root = Node()
    sent = {}
    for phrase, times in zip(history, counts):
        file_phrase(root, sent, phrase, times)

    shown = []
    node = root                  # invariant: node holds the prefix typed so far
    typed = []
    for ch in keystrokes:
        if ch == "#":
            file_phrase(root, sent, "".join(typed), 1)
            typed = []
            node = root
            shown.append(())
            continue
        typed.append(ch)
        # Once the typed prefix leaves the tree it stays gone until the next "#".
        node = None if node is None else node.children.get(ch)
        shown.append(() if node is None else tuple(node.hot))
    return shown

TESTS = [
    # "#" files "ha" as sent once and clears the line.
    (
        (["harbour gate", "harbour road", "hill farm"], [5, 3, 2], "ha#"),
        [
            ("harbour gate", "harbour road", "hill farm"),
            ("harbour gate", "harbour road"),
            (),
        ],
    ),
    # Equal tallies are ranked alphabetically, and the phrase just filed by "#"
    # joins the ranking below them.
    (
        (["depot", "depot yard"], [2, 2], "de#de"),
        [
            ("depot", "depot yard"),
            ("depot", "depot yard"),
            (),
            ("depot", "depot yard", "de"),
            ("depot", "depot yard", "de"),
        ],
    ),
    # A phrase outside the top three climbs into it when "#" files it:
    # "kiln walk" goes 5 -> 6 and displaces "kiln hill".
    (
        (
            ["kiln road", "kiln lane", "kiln walk", "kiln hill"],
            [9, 7, 5, 5],
            "kiln walk#k",
        ),
        [
            ("kiln road", "kiln lane", "kiln hill"),
            ("kiln road", "kiln lane", "kiln hill"),
            ("kiln road", "kiln lane", "kiln hill"),
            ("kiln road", "kiln lane", "kiln hill"),
            ("kiln road", "kiln lane", "kiln hill"),
            ("kiln walk",),
            ("kiln walk",),
            ("kiln walk",),
            ("kiln walk",),
            (),
            ("kiln road", "kiln lane", "kiln walk"),
        ],
    ),
    # A prefix that leaves the tree shows nothing, and keeps showing nothing.
    (
        (["north pier"], [1], "nz#n"),
        [("north pier",), (), (), ("north pier", "nz")],
    ),
    # An empty console: the first phrase can only come from a "#".
    (([], [], "a#a"), [(), (), ("a",)]),
]

Pitfalls

• Ranking only the old three after a #. Drop the filed phrase from the candidates and a phrase that has just climbed past them stays invisible: send kiln walk past kiln hill and the console keeps offering kiln hill.
• Restarting the walk from the root on a missing child. Once the typed prefix leaves the tree it is gone until the next #; a pointer that resets starts suggesting phrases that do not begin with what was typed.
• Filing a repeat as new. # on a phrase already in the tree must add one to its tally, not set it to one, or a popular destination drops out of its own suggestions the moment it is used again.

Variants

• Filling the grid — the same tree with a marker at the ends instead of a ranking at every node.
• The shade chart — one static tree, many walks, no ranking and no updates.