One tray per formula

A compounding pharmacy weighs each order out on its own tray. Two slips that call for the same grams of the same ingredients can share one, however differently they were written.

The problem

Every order slip carries a formula code: a string of lowercase letters, one letter per gram of that ingredient. A slip reading talc asks for one gram each of t, a, l and c; a slip reading aab asks for two grams of a and one of b. Prescribers write the ingredients in whatever order comes to mind, so talc and clat are the same preparation.

Two slips are interchangeable when one code is a rearrangement of the other: the same letters, the same number of each. Interchangeable slips are weighed together on one tray. Everything else needs a tray of its own.

Bin the morning's slips into trays. A tray holding a single slip still counts. Two slips whose codes are identical are still two prescriptions, and both belong in that tray's group. Trays may come back in any order, and the slips within a tray in any order.

Input. slips — a list of strings, each a formula code of lowercase letters.

Output. A list of groups. Each group is the list of slips sharing one tray.

Example.

slips = ["talc", "clat", "kaolin", "nakoli", "talc"]
->  [["talc", "clat", "talc"], ["kaolin", "nakoli"]]

The first tray takes three slips — two of them written identically, which is two prescriptions and two rows in the group.

A second example, where the ingredients agree but the grams do not:

slips = ["aab", "abb", "bab", "b"]
->  [["aab"], ["abb", "bab"], ["b"]]

aab and abb both draw on a and b, and they are not interchangeable: one wants two grams of a, the other two of b.

Constraints.

• 0 <= len(slips) <= 10^4
• 0 <= len(slips[i]) <= 100, letters a–z only
• total characters across all slips <= 10^5

Hints

Approach

Brute force

Compare every slip with every slip already assigned to a tray. With 10⁴ slips that is up to 5 × 10⁷ comparisons, each one a letter-count of up to 100 characters — several billion character operations, and fiddly bookkeeping to merge a slip into an existing group.

The insight

Interchangeability is an equivalence relation, and each class has a name you can compute from one member alone — so a single dictionary keyed by that name does the grouping in one pass.

The name has to be canonical: equal for interchangeable slips, different for everything else. A gram count per letter is exactly that, since "same letters, same number of each" is the definition of interchangeable. Sorting the letters gives the same guarantee, because a sorted sequence is determined by the multiset and determines it back.

Algorithm

1. Start an empty dictionary from key to list of slips.
2. For each slip, build its key: 26 gram counts, or its sorted letters.
3. Append the slip — the original text, not the key — to that key's list.
4. Return the dictionary's values.

Complexity

Time O(N) in the total number of characters with counting keys, or O(N log k) if you sort each slip of length k. Space O(N) — every slip is stored once, plus one key per tray.

Solution

"""One tray per formula — group slips by a canonical form of their letters."""

from collections import defaultdict


def tray_key(slip):
    """Gram count per letter: equal for two slips exactly when they are interchangeable."""
    counts = [0] * 26
    for ch in slip:
        counts[ord(ch) - 97] += 1
    return tuple(counts)


def solve(slips):
    trays = defaultdict(list)
    for slip in slips:
        # invariant: trays[k] holds every slip seen so far whose letters canonicalise to k
        trays[tray_key(slip)].append(slip)
    return list(trays.values())

TESTS = [
    ((["talc", "clat", "kaolin", "nakoli", "talc"],), [["talc", "clat", "talc"], ["kaolin", "nakoli"]]),
    ((["aab", "abb", "bab", "b"],), [["aab"], ["abb", "bab"], ["b"]]),
    (([],), []),
    (([""],), [[""]]),
    ((["borax"],), [["borax"]]),
    ((["zz", "zz", "zz"],), [["zz", "zz", "zz"]]),
]

Pitfalls

• Keying on set(slip) merges aab with abb, since both have the letter set {a, b}. Grams are counts, not membership.
• Storing the key instead of the slip returns [["aab"], ["abb"]]-shaped keys and loses the text the technician has to read off the tray.
• De-duplicating identical codes drops the second talc and the tray comes up one prescription short.
• sorted(slip) returns a list, which cannot be a dictionary key. Join it into a string or wrap it in a tuple, or you get a TypeError.

Variants

• The marquee swap — the same letter counting for two strings only, answering yes or no instead of grouping.