The cask ledger

A winery's cellar ledger records what the cellarman tasted, one line per pair of casks. Nobody wrote down which blend is in which cask — only whether two casks match.

The problem

Each cask carries a short code. The ledger is a list of claims, and a claim is a triple [left, relation, right]. The relation is "same", meaning the two casks hold the same blend, or "differs", meaning they hold different blends.

The cellar can hold any number of distinct blends; nothing caps it. A claim may name the same cask twice, and a cask may appear in any number of claims. The lines are in no particular order: a later line is not a correction of an earlier one, it is another statement that has to hold as well.

Decide whether some assignment of blends to casks makes every line true at once.

Input. claims — a list of [left, relation, right] lists. left and right are cask code strings; relation is exactly "same" or "differs".

Output. True if an assignment exists, otherwise False.

Example.

claims = [["c1", "same", "c2"],
          ["c2", "differs", "c3"]]   ->  True

Pour blend A into c1 and c2, and blend B into c3.

A second example, where two lines rule out the third:

claims = [["c1", "same", "c2"],
          ["c2", "same", "c3"],
          ["c3", "differs", "c1"]]   ->  False

The first two lines put all three casks on one blend, so the third cannot hold.

A third example, which breaks the guess that "differs" chains the way "same" does:

claims = [["p4", "differs", "q7"],
          ["q7", "differs", "r2"],
          ["r2", "differs", "p4"]]   ->  True

Three blends, one per cask, and every line holds.

Constraints.

• 0 <= len(claims) <= 10^4
• cask codes are 1 to 8 lowercase letters and digits
• relation is "same" or "differs"
• an empty ledger claims nothing and is satisfiable

Hints

Approach

Brute force

Give each cask a blend number and check every line. With k casks and up to k blends there are k^k assignments — 10 casks is already 10 billion, and the ledger allows far more.

The insight

Sameness is transitive and difference is not, so the ledger holds exactly when no "differs" line names two casks that the "same" lines have already forced into one group.

The "same" lines alone decide the groups, and merging is order independent, so the grouping does not depend on how the ledger was written. Two distinct groups can always take two distinct blends, because blends are unlimited, so a "differs" line across groups is never a problem however many there are. Only a "differs" line inside one group is impossible. Union-find fits because the "same" lines only ever merge; nothing splits.

Algorithm

1. Keep a union-find keyed by cask code, each code its own group when first seen.
2. First pass: for every "same" line, merge the two codes.
3. Register the codes on "differs" lines too, so a cask that never appears in a "same" line still has a group.
4. Second pass: if a "differs" line's two codes share a root, return False.
5. Survive the second pass and return True.

Complexity

Time O(m α(k)), effectively O(m) for m claims — two passes, near-constant work per line. Space O(k) for k distinct cask codes.

Solution

"""The cask ledger — merge every 'same' claim, then test the 'differs' claims."""


def find(parent, code):
    parent.setdefault(code, code)          # a code is its own group when first seen
    root = code
    while parent[root] != root:
        root = parent[root]
    while parent[code] != root:            # second pass flattens the path
        parent[code], code = root, parent[code]
    return root


def solve(claims):
    parent = {}
    size = {}

    for left, relation, right in claims:
        if relation != "same":
            find(parent, left)             # register both codes even when unmerged
            find(parent, right)
            continue
        ra, rb = find(parent, left), find(parent, right)
        if ra == rb:
            continue
        if size.get(ra, 1) < size.get(rb, 1):
            ra, rb = rb, ra
        parent[rb] = ra
        size[ra] = size.get(ra, 1) + size.get(rb, 1)

    # Invariant: after the first pass a group holds exactly the casks the ledger
    # forces to share a blend, so distinct groups can always take distinct blends.
    for left, relation, right in claims:
        if relation == "differs" and find(parent, left) == find(parent, right):
            return False
    return True

TESTS = [
    (([["c1", "same", "c2"],
       ["c2", "differs", "c3"]],), True),
    (([["c1", "same", "c2"],
       ["c2", "same", "c3"],
       ["c3", "differs", "c1"]],), False),
    (([["p4", "differs", "q7"],
       ["q7", "differs", "r2"],
       ["r2", "differs", "p4"]],), True),   # difference does not chain
    (([["k9", "differs", "k9"]],), False),  # a cask matches itself
    (([["a1", "same", "a1"]],), True),
    (([["x1", "differs", "y1"],
       ["x1", "same", "y1"]],), False),     # order in the ledger must not matter
    (([],), True),                          # an empty ledger claims nothing
]

Pitfalls

• Settling each line as you read it. The ledger [["x1", "differs", "y1"], ["x1", "same", "y1"]] passes the first line, then merges, and reports True. It is unsatisfiable; the two passes are the fix.
• Treating "differs" as transitive. Assuming that a chain of differences forces an alternation is what two blends would do, not unlimited blends: the three-cask ring above returns False instead of True.
• Skipping a line whose two codes are equal. ["k9", "differs", "k9"] is unsatisfiable — a cask holds what it holds — and skipping it reports True.

Variants

• Two cabinets — the same consistency question with only two groups available, where difference does chain.
• Union-find — the merge-and-query structure the first pass is built on.