w-28-union-find.yml · YAML

# Union-Find with path compression and union by rank: chapter widget.
# Single-panel widget for chapter 8.8. Trace transcribed verbatim from
# step buffer (deterministic; verified against the §2.2
# Python reference). Authoritative spec at runtime.

id: w-28-union-find
title: "Union-Find: parent forest with path compression and union by rank"
type: single-panel
level: 1
modes: [preset, edit]

caps:
  n: { min: 4, max: 12 }
  edges_length: { min: 4, max: 12 }
  total_steps: { max: 40 }

commands:
  - name: edge_in
    payload: { edge: 'integer[2]', edge_index: 'integer' }
    description: "Highlight the next edge from the input stream; pause before processing."
  - name: find_done
    payload: { target: 'integer', root: 'integer' }
    description: "Walk node target up parent pointers to its root; flash the path; report root."
  - name: compress
    payload: { node: 'integer', old_parent: 'integer', new_parent: 'integer' }
    description: "Path compression: rewire node's parent pointer directly to the new root."
  - name: union
    payload: { new_root: 'integer', attached: 'integer', rank_bumped: 'boolean' }
    description: "Attach the lower-rank root under the higher-rank root; bump rank if tied."
  - name: cycle_detected
    payload: { x: 'integer', y: 'integer', root: 'integer' }
    description: "Both endpoints share a root; flash the rejecting edge in vermilion."
  - name: answer
    payload: { redundant: 'integer[2]' }
    description: "Render the final answer in the answer chip."

static_fallback:
  generator: jsdom
  output: site/static/widgets/w-28-union-find-fallback.svg
  keyframes_used: [0, 8, 12, 18, 21]
  # Forced keyframes : init, two parallel depth-1 trees,
  # depth-2 merged tree, post-compression flat tree, cycle detected.

panels:
  default:
    chapter: "8.8"
    label: "Union-Find on a 5-node redundant-connection input"
    canonical_input: |
      n = 5
      edges = [[1, 2], [3, 4], [2, 3], [1, 5], [4, 5]]
      expected_redundant = [4, 5]
    presets:
      - id: redundant_5node_with_compress
        label: "5-node cycle (default; surfaces both optimizations)"
        input:
          n: 5
          edges: [[1, 2], [3, 4], [2, 3], [1, 5], [4, 5]]
      - id: friend_groups
        label: "Friend-groups intuition (3 inserts, no cycle)"
        input:
          n: 5
          edges: [[1, 2], [2, 3], [4, 5]]
      - id: pathological_no_compression
        label: "Compression OFF, depth-n chain (motivates compression)"
        input:
          n: 8
          edges: [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8]]
          compression: false
      - id: kruskal_warmup
        label: "Same edges Kruskal sorts (cross-link to chapter 8.11)"
        input:
          n: 5
          edges: [[1, 2], [3, 4], [2, 3], [1, 5], [4, 5]]
    n_steps: 23
    keyframes:
      - step: 0
        kind: init
        state: { parent: [1, 2, 3, 4, 5], rank: [0, 0, 0, 0, 0] }
        narration: "parent = [1, 2, 3, 4, 5]; rank = [0, 0, 0, 0, 0]. Five singleton trees; no edges processed."
      - step: 1
        kind: edge_in
        payload: { edge: [1, 2], edge_index: 1 }
        state: { parent: [1, 2, 3, 4, 5], rank: [0, 0, 0, 0, 0] }
        narration: "Process edge 1 of 5: (1, 2)."
      - step: 2
        kind: find_done
        payload: { target: 1, root: 1 }
        state: { parent: [1, 2, 3, 4, 5], rank: [0, 0, 0, 0, 0] }
        narration: "find(1) = 1."
      - step: 3
        kind: find_done
        payload: { target: 2, root: 2 }
        state: { parent: [1, 2, 3, 4, 5], rank: [0, 0, 0, 0, 0] }
        narration: "find(2) = 2."
      - step: 4
        kind: union
        payload: { new_root: 1, attached: 2, rank_bumped: true }
        state: { parent: [1, 1, 3, 4, 5], rank: [1, 0, 0, 0, 0] }
        narration: "Roots tied at rank 0; attach 2 under 1, bump rank[1] to 1."
      - step: 5
        kind: edge_in
        payload: { edge: [3, 4], edge_index: 2 }
        state: { parent: [1, 1, 3, 4, 5], rank: [1, 0, 0, 0, 0] }
        narration: "Process edge 2 of 5: (3, 4)."
      - step: 6
        kind: find_done
        payload: { target: 3, root: 3 }
        state: { parent: [1, 1, 3, 4, 5], rank: [1, 0, 0, 0, 0] }
        narration: "find(3) = 3."
      - step: 7
        kind: find_done
        payload: { target: 4, root: 4 }
        state: { parent: [1, 1, 3, 4, 5], rank: [1, 0, 0, 0, 0] }
        narration: "find(4) = 4."
      - step: 8
        kind: union
        payload: { new_root: 3, attached: 4, rank_bumped: true }
        state: { parent: [1, 1, 3, 3, 5], rank: [1, 0, 1, 0, 0] }
        narration: "Roots tied at rank 0; attach 4 under 3, bump rank[3] to 1. Two parallel depth-1 trees now."
      - step: 9
        kind: edge_in
        payload: { edge: [2, 3], edge_index: 3 }
        state: { parent: [1, 1, 3, 3, 5], rank: [1, 0, 1, 0, 0] }
        narration: "Process edge 3 of 5: (2, 3)."
      - step: 10
        kind: find_done
        payload: { target: 2, root: 1 }
        state: { parent: [1, 1, 3, 3, 5], rank: [1, 0, 1, 0, 0] }
        narration: "find(2) walks 2 to 1; root = 1."
      - step: 11
        kind: find_done
        payload: { target: 3, root: 3 }
        state: { parent: [1, 1, 3, 3, 5], rank: [1, 0, 1, 0, 0] }
        narration: "find(3) = 3."
      - step: 12
        kind: union
        payload: { new_root: 1, attached: 3, rank_bumped: true }
        state: { parent: [1, 1, 1, 3, 5], rank: [2, 0, 1, 0, 0] }
        narration: "Equal-rank merge: attach root 3 under root 1; bump rank[1] to 2. Depth-2 tree built; this is the moment that primes path compression."
      - step: 13
        kind: edge_in
        payload: { edge: [1, 5], edge_index: 4 }
        state: { parent: [1, 1, 1, 3, 5], rank: [2, 0, 1, 0, 0] }
        narration: "Process edge 4 of 5: (1, 5)."
      - step: 14
        kind: find_done
        payload: { target: 1, root: 1 }
        state: { parent: [1, 1, 1, 3, 5], rank: [2, 0, 1, 0, 0] }
        narration: "find(1) = 1."
      - step: 15
        kind: find_done
        payload: { target: 5, root: 5 }
        state: { parent: [1, 1, 1, 3, 5], rank: [2, 0, 1, 0, 0] }
        narration: "find(5) = 5."
      - step: 16
        kind: union
        payload: { new_root: 1, attached: 5, rank_bumped: false }
        state: { parent: [1, 1, 1, 3, 1], rank: [2, 0, 1, 0, 0] }
        narration: "Lower rank merges under higher: attach 5 under 1; ranks unchanged."
      - step: 17
        kind: edge_in
        payload: { edge: [4, 5], edge_index: 5 }
        state: { parent: [1, 1, 1, 3, 1], rank: [2, 0, 1, 0, 0] }
        narration: "Process edge 5 of 5: (4, 5)."
      - step: 18
        kind: compress
        payload: { node: 4, old_parent: 3, new_parent: 1 }
        state: { parent: [1, 1, 1, 1, 1], rank: [2, 0, 1, 0, 0] }
        narration: "find(4) walks 4 to 3 to 1; on the way back the path compresses: parent[4] rewires from 3 directly to root 1."
      - step: 19
        kind: find_done
        payload: { target: 4, root: 1 }
        state: { parent: [1, 1, 1, 1, 1], rank: [2, 0, 1, 0, 0] }
        narration: "find(4) returns 1; the next find on any node in this tree is one hop."
      - step: 20
        kind: find_done
        payload: { target: 5, root: 1 }
        state: { parent: [1, 1, 1, 1, 1], rank: [2, 0, 1, 0, 0] }
        narration: "find(5) = 1."
      - step: 21
        kind: cycle_detected
        payload: { x: 4, y: 5, root: 1 }
        state: { parent: [1, 1, 1, 1, 1], rank: [2, 0, 1, 0, 0] }
        narration: "Both endpoints already share root 1; edge (4, 5) closes a cycle. This is the redundant edge."
      - step: 22
        kind: answer
        payload: { redundant: [4, 5] }
        state: { parent: [1, 1, 1, 1, 1], rank: [2, 0, 1, 0, 0] }
        narration: "Answer: redundant edge = [4, 5]."

selector_default: default

notes: |
  Trace transcribed verbatim step buffer; deterministic
  re-runs against the §2.2 Python reference yield byte-identical output
  . Three preset toggles surface the value of each
  optimization: redundant_5node_with_compress is the default; toggling
  compression off makes step 18's flatten disappear; toggling union_by
  off lets attach-second-into-first build a depth-n chain on the
  pathological_no_compression preset, visible motivation for rank.
  Color palette (Wong, per style-guide.md): root nodes bluish green
  #009E73; current find-path orange #E69F00; just-compressed edge
  reddish purple #CC79A7; cycle-detected edge vermilion #D55E00.