Two pedigree cards

Two clerks wrote out the same ewe's ancestry in two house styles. The flock book takes one entry, so the question is whether the cards agree.

The problem

A pedigree card names an animal, then its sire and dam, then their sires and dams, as far back as the records go. Every entry is a flock-book number and an unknown ancestor is blank. A number may appear twice on one card — line-breeding puts one ram in two places — so numbers do not identify a position.

The first clerk wrote a generation card: generation by generation, the animal, then its sire and dam, then all four grandparents, None for each blank. The second wrote an indented card: the animal, then its whole sire line written out, then its whole dam line, with a None written for every blank so the indentation can be recovered.

Decide whether the cards describe the same ancestry: the same numbers in the same places, blanks in the same places.

Input. rows — the generation card. trace — the indented card.

Output. True if the cards agree, False otherwise.

Example.

rows  = [6, 3, 8, None, 2]
trace = [6, 3, None, 2, None, None, 8, None, None]
  ->  True

Ewe 6 has sire 3 and dam 8. Ram 3's sire is unknown and its dam is 2, whose parents are unknown, and ewe 8's parents are unknown. Both cards say that.

A second example, where the cards carry the same numbers in the same order:

rows  = [6, 3, 8, 2]
trace = [6, 3, None, 2, None, None, 8, None, None]
  ->  False

The generation card now puts 2 in ram 3's sire slot and the indented card puts it in the dam slot. Both read 6, 3, 8, 2; the ancestry is not the same.

Constraints.

• 0 <= animals <= 2000 on each card
• 1 <= flock number <= 9999, and a number may repeat on a card
• an empty generation card is []; an empty indented card is [None]

Hints

Approach

Brute force

Rebuild both cards, list every line of descent from the animal back to an ancestor with no known parents, and check the collections agree. With up to 1000 lines per card and comparisons of up to 2000 entries that is millions of comparisons — and still wrong, because different pedigrees can produce the same collection of lines. Nothing that throws the shape away catches the second example.

The insight

Two pedigrees are equal exactly when their animals are equal and their sire lines and dam lines are equal, so compare them with one walk that steps down both at once and treats a blank against an entry as a decision.

The definition of the tree and the definition of equality have the same shape, so the comparison is that recursion with two positions instead of one. Both blank means agreement here; one blank against one filled means the cards disagree, and that single line is what separates shape from contents. Nothing is used beyond equality of the numbers, which is why repeats do no harm.

Algorithm

1. Rebuild the generation card with a queue: pull an animal, take the next two entries as its sire and dam, queue the ones that are not blank.
2. Rebuild the indented card with a forward-only cursor: None is no animal; otherwise take the number, read the sire line, then the dam line.
3. alike(a, b): if either side is blank, return whether both are.
4. Otherwise return the numbers equal and alike on the sires and on the dams.

Complexity

Time O(n) — each card is read once and the comparison stops at the first disagreement. Space O(n) for the two rebuilt cards, plus O(h) frames.

Solution

"""Two pedigree cards — rebuild both recordings, then walk them in lockstep."""

import sys
from collections import deque

sys.setrecursionlimit(20000)   # a card with one known parent per animal is n deep


class Animal:
    """One animal on the card, with its sire and dam where they are known."""

    def __init__(self, tag):
        self.tag = tag
        self.sire = None
        self.dam = None


def from_generations(rows):
    """Generation card: one generation at a time, None where an animal is unknown."""
    if not rows or rows[0] is None:
        return None
    subject = Animal(rows[0])
    queue, i = deque([subject]), 1
    while queue and i < len(rows):
        node = queue.popleft()
        if i < len(rows) and rows[i] is not None:
            node.sire = Animal(rows[i])
            queue.append(node.sire)
        i += 1
        if i < len(rows) and rows[i] is not None:
            node.dam = Animal(rows[i])
            queue.append(node.dam)
        i += 1
    return subject


def from_indent(trace):
    """Indented card: the whole sire line first, a None written for every unknown."""
    cursor = 0

    def read():
        # invariant: cursor is the first entry of the line still to be rebuilt.
        nonlocal cursor
        if cursor >= len(trace):
            return None
        tag = trace[cursor]
        cursor += 1
        if tag is None:
            return None
        node = Animal(tag)
        node.sire = read()
        node.dam = read()
        return node

    return read()


def alike(a, b):
    # invariant: a and b are the same position on the two cards.
    if a is None or b is None:
        return a is None and b is None   # an unknown on one side settles it
    return a.tag == b.tag and alike(a.sire, b.sire) and alike(a.dam, b.dam)


def solve(rows, trace):
    return alike(from_generations(rows), from_indent(trace))

TESTS = [
    (([6, 3, 8, None, 2], [6, 3, None, 2, None, None, 8, None, None]), True),
    (([6, 3, 8, 2], [6, 3, None, 2, None, None, 8, None, None]), False),
    (([7, 4], [7, 4, None, None, None]), True),
    (([7, 4], [7, None, 4, None, None]), False),
    (([9, 5, 6, 3, 4, 3],
      [9, 5, 3, None, None, 4, None, None, 6, 3, None, None, None]), True),
    (([5, None, None], [5, None, None]), True),
    (([], [None]), True),
    (([4], [None]), False),
]

Pitfalls

• Comparing the numbers in reading order. Both cards in the second example yield 6, 3, 8, 2 once the blanks are stripped. Equal readings are not equal pedigrees; the blanks are the information.
• Returning False as soon as one side is blank. Two blanks agree. Written as if a is None or b is None: return a is None and b is None, both cases are one line.
• Reading the indented card's dam line before its sire line. They share a cursor, so the dam call eats the sire's entries and a card compared with itself reports False.
• Treating an empty card as an error. A ewe with no recorded ancestry is [] against [None], and those two agree.

Variants

• The permit line — the same blanks-for- gaps convention, used to ship a whole structure as one line of text.
• Walking the house — two records that do pin a shape down between them, and why they need distinct values to do it.