w-25-graph-bfs.yml · YAML

# Graph BFS: frontier expansion on a grid (chapter 8.1)
# Single-panel chapter widget. Animates multi-source BFS on the canonical
# 2x3 grid with one rotten cell at (0, 0) and five fresh cells. Trace
# generated by instrumenting the verified Python reference;
# deterministic re-runs match byte-for-byte.

id: w-25-graph-bfs
title: "Graph BFS, frontier expansion (multi-source on a grid)"
type: single-panel
level: 1
modes: [preset, randomize, edit]

caps:
  rows: { min: 2, max: 12 }
  cols: { min: 2, max: 12 }
  cell_values: { allowed: [0, 1, 2] }   # 0 = empty, 1 = fresh, 2 = source
  trace_length: { max: 1000 }

commands:
  - name: enqueue
    payload: { cell: 'string', depth: 'integer', frontier_size: 'integer' }
    description: "Push a cell onto the FIFO queue at the given depth (minute)."
  - name: dequeue
    payload: { cell: 'string', minute: 'integer', frontier_size: 'integer' }
    description: "Pop the front of the queue. Update the displayed minute."
  - name: highlight
    payload: { cell: 'string' }
    description: "Mark the popped cell as the active expansion focus."
  - name: unhighlight
    payload: { cell: 'string' }
    description: "Remove the active marker once neighbor scan completes."
  - name: mark_and_enqueue
    payload: { cell: 'string', depth: 'integer', fresh_remaining: 'integer', frontier_size: 'integer' }
    description: "Set visited on a freshly discovered neighbor and enqueue it; decrement fresh count."
  - name: answer
    payload: { minutes: 'integer', fresh_remaining: 'integer' }
    description: "Final answer; the display freezes on the result."

static_fallback:
  generator: jsdom
  output: site/static/widgets/w-25-graph-bfs-fallback.svg
  keyframes_used: [0, 4, 13, 17, 25]
  # Phase boundaries: initial / minute 1 expansions / minute 2 expansions /
  # minute 3 expansion / final answer.

panels:
  default:
    chapter: "8.1"
    label: "Graph BFS, multi-source frontier"
    canonical_input: |
      grid = [[2, 1, 1],
              [1, 1, 1]]
      rows = 2
      cols = 3
      initial_sources = [(0, 0)]
      initial_fresh = 5
    presets:
      - id: canonical
        label: "Canonical 2×3 (one source, five fresh)"
        input: { grid: [[2, 1, 1], [1, 1, 1]] }
      - id: lc_994_example_1
        label: "LC 994 Example 1 (3×3)"
        input: { grid: [[2, 1, 1], [1, 1, 0], [0, 1, 1]] }
      - id: unreachable
        label: "Unreachable cell (returns -1)"
        input: { grid: [[2, 1, 1], [0, 1, 1], [1, 0, 1]] }
    n_steps: 26
    keyframes:
      - step: 0
        kind: init
        state: { rows: 2, cols: 3, grid: [[2, 1, 1], [1, 1, 1]], queue: [], minute: 0, fresh: 5 }
        narration: "Scan grid. One source at (0, 0); five fresh cells."
      - step: 1
        kind: enqueue
        payload: { cell: "c-0-0", depth: 0, frontier_size: 1 }
        state: { queue: ["c-0-0"], minute: 0, fresh: 5 }
        narration: "Seed the queue with the source at (0, 0), depth 0."
      - step: 2
        kind: dequeue
        payload: { cell: "c-0-0", minute: 0, frontier_size: 0 }
        state: { queue: [], minute: 0, fresh: 5 }
        narration: "Dequeue (0, 0) at minute 0."
      - step: 3
        kind: highlight
        payload: { cell: "c-0-0" }
        state: { active: "c-0-0", minute: 0, fresh: 5 }
        narration: "Active expansion: (0, 0)."
      - step: 4
        kind: mark_and_enqueue
        payload: { cell: "c-1-0", depth: 1, fresh_remaining: 4, frontier_size: 1 }
        state: { queue: ["c-1-0"], minute: 0, fresh: 4 }
        narration: "Discover (1, 0). Mark visited, enqueue at minute 1; fresh = 4."
      - step: 5
        kind: mark_and_enqueue
        payload: { cell: "c-0-1", depth: 1, fresh_remaining: 3, frontier_size: 2 }
        state: { queue: ["c-1-0", "c-0-1"], minute: 0, fresh: 3 }
        narration: "Discover (0, 1). Mark visited, enqueue at minute 1; fresh = 3."
      - step: 6
        kind: unhighlight
        payload: { cell: "c-0-0" }
        state: { active: null, minute: 0, fresh: 3 }
        narration: "Done expanding (0, 0)."
      - step: 7
        kind: dequeue
        payload: { cell: "c-1-0", minute: 1, frontier_size: 1 }
        state: { queue: ["c-0-1"], minute: 1, fresh: 3 }
        narration: "Dequeue (1, 0) at minute 1."
      - step: 8
        kind: highlight
        payload: { cell: "c-1-0" }
        state: { active: "c-1-0", minute: 1, fresh: 3 }
        narration: "Active expansion: (1, 0)."
      - step: 9
        kind: mark_and_enqueue
        payload: { cell: "c-1-1", depth: 2, fresh_remaining: 2, frontier_size: 2 }
        state: { queue: ["c-0-1", "c-1-1"], minute: 1, fresh: 2 }
        narration: "Discover (1, 1). Mark visited, enqueue at minute 2; fresh = 2."
      - step: 10
        kind: unhighlight
        payload: { cell: "c-1-0" }
        state: { active: null, minute: 1, fresh: 2 }
        narration: "Done expanding (1, 0)."
      - step: 11
        kind: dequeue
        payload: { cell: "c-0-1", minute: 1, frontier_size: 1 }
        state: { queue: ["c-1-1"], minute: 1, fresh: 2 }
        narration: "Dequeue (0, 1) at minute 1."
      - step: 12
        kind: highlight
        payload: { cell: "c-0-1" }
        state: { active: "c-0-1", minute: 1, fresh: 2 }
        narration: "Active expansion: (0, 1)."
      - step: 13
        kind: mark_and_enqueue
        payload: { cell: "c-0-2", depth: 2, fresh_remaining: 1, frontier_size: 2 }
        state: { queue: ["c-1-1", "c-0-2"], minute: 1, fresh: 1 }
        narration: "Discover (0, 2). Mark visited, enqueue at minute 2; fresh = 1."
      - step: 14
        kind: unhighlight
        payload: { cell: "c-0-1" }
        state: { active: null, minute: 1, fresh: 1 }
        narration: "Done expanding (0, 1)."
      - step: 15
        kind: dequeue
        payload: { cell: "c-1-1", minute: 2, frontier_size: 1 }
        state: { queue: ["c-0-2"], minute: 2, fresh: 1 }
        narration: "Dequeue (1, 1) at minute 2."
      - step: 16
        kind: highlight
        payload: { cell: "c-1-1" }
        state: { active: "c-1-1", minute: 2, fresh: 1 }
        narration: "Active expansion: (1, 1)."
      - step: 17
        kind: mark_and_enqueue
        payload: { cell: "c-1-2", depth: 3, fresh_remaining: 0, frontier_size: 2 }
        state: { queue: ["c-0-2", "c-1-2"], minute: 2, fresh: 0 }
        narration: "Discover (1, 2). Mark visited, enqueue at minute 3; fresh = 0. Last fresh cell rotted."
      - step: 18
        kind: unhighlight
        payload: { cell: "c-1-1" }
        state: { active: null, minute: 2, fresh: 0 }
        narration: "Done expanding (1, 1)."
      - step: 19
        kind: dequeue
        payload: { cell: "c-0-2", minute: 2, frontier_size: 1 }
        state: { queue: ["c-1-2"], minute: 2, fresh: 0 }
        narration: "Dequeue (0, 2) at minute 2."
      - step: 20
        kind: highlight
        payload: { cell: "c-0-2" }
        state: { active: "c-0-2", minute: 2, fresh: 0 }
        narration: "Active expansion: (0, 2). All neighbors are already visited."
      - step: 21
        kind: unhighlight
        payload: { cell: "c-0-2" }
        state: { active: null, minute: 2, fresh: 0 }
        narration: "Done expanding (0, 2)."
      - step: 22
        kind: dequeue
        payload: { cell: "c-1-2", minute: 3, frontier_size: 0 }
        state: { queue: [], minute: 3, fresh: 0 }
        narration: "Dequeue (1, 2) at minute 3."
      - step: 23
        kind: highlight
        payload: { cell: "c-1-2" }
        state: { active: "c-1-2", minute: 3, fresh: 0 }
        narration: "Active expansion: (1, 2). All neighbors are already visited."
      - step: 24
        kind: unhighlight
        payload: { cell: "c-1-2" }
        state: { active: null, minute: 3, fresh: 0 }
        narration: "Done expanding (1, 2). Queue is empty."
      - step: 25
        kind: answer
        payload: { minutes: 3, fresh_remaining: 0 }
        state: { minute: 3, fresh: 0, result: 3 }
        narration: "Answer = 3 minutes; fresh = 0."

selector_default: default

notes: |
  Single-panel chapter widget for 8.1 graph BFS. The grid is the implicit
  graph; the queue is shown as a column on the right; each cell carries a
  visited bit (filled = visited) and, once popped, a discovery-time label
  in the bottom-right corner. Visual legend reuses the convention
  established in chapter 8.0 (filled cell = visited; arrow = directed edge).
  Trace transcribed (26 steps; deterministic given the
  fixed direction order down/up/right/left and row-major source scan).