Merging the choir roster

Six terms of sign-up slips, and half the choir signed up more than once. Two slips belong to the same singer only when they share a way of reaching them.

The problem

A community choir keeps every slip it has collected. Each slip carries a singer's first name followed by one or more contact handles.

Two slips belong to the same singer if they list at least one handle in common. A handle never belongs to two singers, and every slip one singer ever filled in carries the same name — but two different singers may well share a first name, so the name settles nothing.

Fold the slips into one record per singer: the name, followed by every handle that singer has ever given, sorted and without repeats. The records may come back in any order.

Input. slips — a list of lists. slips[i][0] is a name and slips[i][1:] are that slip's handles.

Output. A list of records, each [name, handle, ...] with the handles sorted.

Example.

slips = [["Rosa", "rosa@lark.net", "rosa.b@post.co"],
         ["Rosa", "rosa.b@post.co", "rb@choir.org"],
         ["Ines", "ines@lark.net"],
         ["Rosa", "rosa2@post.co"]]

->  [["Ines", "ines@lark.net"],
     ["Rosa", "rb@choir.org", "rosa.b@post.co", "rosa@lark.net"],
     ["Rosa", "rosa2@post.co"]]

The first two slips share rosa.b@post.co. The fourth Rosa shares nothing with them, so she is a different singer and stays apart.

Example. Two slips can merge through a third:

slips = [["Tam", "tam@bell.io"],
         ["Tam", "tam@bell.io", "t.hall@bell.io"],
         ["Tam", "t.hall@bell.io", "tamsin@rehearsal.net"]]

->  [["Tam", "t.hall@bell.io", "tam@bell.io", "tamsin@rehearsal.net"]]

Slips 1 and 3 have no handle in common. They are still one singer, joined through slip 2.

Constraints.

• 1 <= len(slips) <= 1000
• 2 <= len(slips[i]) <= 10 — a name and at least one handle
• a handle is 1 to 30 characters, a name 1 to 20
• no handle ever appears on the slips of two different singers

Hints

Approach

Brute force

Compare every pair of slips, merge any that intersect, and repeat until a whole pass merges nothing. A chain that links one slip at a time needs a pass per link, so with k slips of h handles each it is O(k^3 h) in the worst case — around a billion handle comparisons at a thousand slips.

The insight

Make the handles the nodes rather than the slips: join every handle on a slip to the others, and a singer is one connected component of the handle graph.

"Same singer" is generated by "shares a handle", and the transitive closure of that relation is precisely connectivity in that graph. Once it is built, the chain case stops being special — a component does not care how many hops apart two of its handles are. The name can be read off any handle in the component, because every slip in one component carries the same name.

Algorithm

1. Take each slip's first handle as its anchor.
2. Register every handle on the slip, record the slip's name against it, and join it to the anchor.
3. Once all slips are read, bucket the handles by group root.
4. Sort each bucket and put the root's name in front of it.

Complexity

Time O(H a(H) + H log H), where H is the total number of handles written across all slips — near-constant per join, and the log factor is the sort inside each component. Space O(H) for the parent map, the names and the buckets.

Solution

"""Merging the choir roster — components of the graph whose nodes are handles."""


def find(parent, handle):
    """Root handle of this group, flattening the path walked on the way back."""
    root = handle
    while parent[root] != root:
        root = parent[root]
    while parent[handle] != root:
        parent[handle], handle = root, parent[handle]
    return root


def solve(slips):
    parent = {}
    singer = {}
    for slip in slips:
        name, handles = slip[0], slip[1:]
        anchor = handles[0]
        for handle in handles:
            if handle not in parent:
                parent[handle] = handle
            singer[handle] = name
            # Invariant: every handle written on one slip lands in one group, so
            # a singer is exactly one connected component of the handle graph.
            root_anchor, root_handle = find(parent, anchor), find(parent, handle)
            if root_anchor != root_handle:
                parent[root_anchor] = root_handle

    groups = {}
    for handle in parent:
        groups.setdefault(find(parent, handle), set()).add(handle)
    records = [[singer[root]] + sorted(handles) for root, handles in groups.items()]
    records.sort()
    return records

TESTS = [
    ((
        [["Rosa", "rosa@lark.net", "rosa.b@post.co"],
         ["Rosa", "rosa.b@post.co", "rb@choir.org"],
         ["Ines", "ines@lark.net"],
         ["Rosa", "rosa2@post.co"]],
    ), [["Ines", "ines@lark.net"],
        ["Rosa", "rb@choir.org", "rosa.b@post.co", "rosa@lark.net"],
        ["Rosa", "rosa2@post.co"]]),
    ((
        [["Tam", "tam@bell.io"],
         ["Tam", "tam@bell.io", "t.hall@bell.io"],
         ["Tam", "t.hall@bell.io", "tamsin@rehearsal.net"]],
    ), [["Tam", "t.hall@bell.io", "tam@bell.io", "tamsin@rehearsal.net"]]),
    (([["Ada", "a@x.net", "a@x.net"]],), [["Ada", "a@x.net"]]),   # handle written twice
    ((
        [["Rosa", "r1@x.net"], ["Rosa", "r2@x.net"]],
    ), [["Rosa", "r1@x.net"], ["Rosa", "r2@x.net"]]),             # same name, two singers
    (([["Bo", "bo@x.net"]],), [["Bo", "bo@x.net"]]),              # one slip, one handle
]

Pitfalls

• Grouping by name. Both Rosas collapse into one record with four handles. The name is a label carried along by the group, never a key for it.
• One pass of pairwise comparison. In the second example slips 1 and 3 share nothing directly, so a single sweep leaves them apart and reports two Tams.
• Skipping the dedupe. A handle written twice on one slip, or repeated across two slips of the same singer, appears twice in the record unless the bucket is a set.

Variants

• The tunnel to seal — the same structure on integers, asked for the edge that closes a loop.
• Union-find — the structure and what it costs.