Striking the scaffold ties

A scaffold comes down one tie at a time, and a tie may only be struck while another still holds its lift or its standard.

The problem

Ties bolt a scaffold back to a flat facade. Each sits at a whole-number position [lift, standard]: the lift is the horizontal level, the standard the vertical pole. No two ties share a position.

A tie may be struck (unbolted and carried away) only if, at that moment, some tie still in place sits on the same lift or on the same standard. Ties come off one at a time, the crew picks the order, and a struck tie braces nothing.

Input. ties — a list of pairs [lift, standard], all distinct.

Output. The maximum number of ties that can be struck.

Example.

ties = [[0, 0], [0, 2], [1, 2], [2, 0], [2, 1], [3, 1]]  ->  5

Every tie is chained to the rest: [0, 0] and [0, 2] share lift 0, [0, 2] and [1, 2] share standard 2, on down to [3, 1]. One chain, so five come off.

A second example, where the ties fall into two chains:

ties = [[0, 0], [0, 1], [1, 0], [2, 4], [3, 4], [3, 5]]  ->  4

The first three sit in the top corner, the last three in the far bay, sharing no lift and no standard across the gap. Each chain gives up two and keeps one. With [[0, 1], [1, 0]] there is no chain at all, and the answer is 0.

Constraints.

• 1 <= len(ties) <= 10^4
• 0 <= lift, standard <= 10^4
• no two ties sit at the same position

Hints

Approach

Brute force

Search over orders: strike any tie allowed to go, recurse, keep the best total. Up to n! orderings, and even memoised over which ties remain it is 2^n states, so twenty-five ties is out of reach.

The insight

Ties chained together by shared lifts and standards can always be reduced to exactly one survivor, so the answer is the tie count minus the number of chains.

You can never strike the last tie of a chain, because nothing else sits on its lift or its standard. And you can always get down to one: walk the chain outward from any tie and strike in reverse order, so each tie still has the neighbour it was reached from. Counting chains is a union-find job, and the trick is what to merge: not ties, but the lift and standard each tie touches.

Algorithm

1. Give every lift value and every standard value its own label, tagged so the two kinds cannot collide.
2. For each tie, union its lift label with its standard label.
3. Count the distinct roots among the labels that appeared.
4. Return the tie count minus that.

Complexity

Time O(n α(n)) — one union per tie, over a structure carrying both path halving and union by size, which together buy the inverse-Ackermann bound. Space O(n), two labels per tie at most.

Solution

"""Striking the scaffold ties — union-find over lift labels and standard labels."""


def find(parent, label):
    while parent[label] != label:
        parent[label] = parent[parent[label]]   # path halving keeps the trees flat
        label = parent[label]
    return label


def union(parent, size, a, b):
    ra, rb = find(parent, a), find(parent, b)
    if ra == rb:
        return
    # invariant: the smaller tree always hangs off the larger, so no tree ever
    # gets deeper than log n before path halving flattens it again. Union by
    # size and path halving together are what make a find near constant.
    if size[ra] > size[rb]:
        ra, rb = rb, ra
    parent[ra] = rb
    size[rb] += size[ra]


def solve(ties):
    parent = {}
    size = {}
    for lift, standard in ties:
        # A lift label must never collide with a standard label: ("L", 3) is not
        # ("S", 3). Merging the two a tie touches makes any pair of ties that
        # share a coordinate land in the same group, transitively.
        a = ("L", lift)
        b = ("S", standard)
        parent.setdefault(a, a)
        parent.setdefault(b, b)
        size.setdefault(a, 1)
        size.setdefault(b, 1)
        union(parent, size, a, b)

    groups = len({find(parent, label) for label in list(parent)})
    # invariant: each group can be emptied down to exactly one tie, no further
    return len(ties) - groups

TESTS = [
    (([[0, 0], [0, 2], [1, 2], [2, 0], [2, 1], [3, 1]],), 5),
    (([[0, 0], [0, 1], [1, 0], [2, 4], [3, 4], [3, 5]],), 4),
    (([[0, 1], [1, 0]],), 0),
    (([[5, 5]],), 0),
    (([[0, 0], [1, 1], [2, 2], [0, 2]],), 2),
    (([[0, 0], [0, 1], [0, 2], [0, 3]],), 3),
]

Pitfalls

• Letting lift 3 and standard 3 share a label. On [[0, 1], [1, 0]] the collision merges all four labels into one group, so the answer comes back 1 when neither tie can move.
• Counting groups over every coordinate in range, not the ones that appear. An empty lift is no chain; folding in all 10^4 lifts pushes the group count above the tie count and the answer goes negative.
• Grouping ties by lift alone. On the second example both chains split, into lift 0 [[0, 0], [0, 1]], lift 1 [[1, 0]], lift 2 [[2, 4]] and lift 3 [[3, 4], [3, 5]]. Four groups, not two, so the answer comes back 6 - 4 = 2 rather than 4.

Variants

• The trunk line survey — the same component count over one namespace, not two.
• Union-find — the structure itself, and why the near-constant cost holds.