w-14-floyd-cycle.yml · YAML

# Floyd's tortoise and hare: cycle detection on a singly linked list
# Single-panel chapter widget for chapter 5.3.

id: w-14-floyd-cycle
title: "Floyd's tortoise and hare (cycle detection)"
type: single-panel
level: 1
modes: [preset, randomize, edit]

caps:
  array_length: { min: 1, max: 8 }
  values: { min: -99, max: 99 }
  pos: { min: -1, max: "array_length - 1" }
  # Tightened from the linear-pointer default cap of 16 because the cycle
  # geometry crowds past 8 nodes; / widget-decision-rule
  # `widget-decision-rule.md` §3.

commands:
  - name: setPointer
    payload: { which: 'slow | fast', index: 'integer' }
    description: "Move the named pointer to the given node index. Animates a hop."
  - name: advance
    payload: { slow_idx: 'integer', fast_idx: 'integer' }
    description: "One algorithm step: slow steps by 1, fast by 2 (Phase 1) or by 1 (Phase 2)."
  - name: meet
    payload: { idx: 'integer', phase: 'phase1 | phase2' }
    description: "Pointers coincide. Phase 1 meet: cycle confirmed. Phase 2 meet: cycle entry located."
  - name: resetSlow
    payload: { fast_idx: 'integer' }
    description: "Phase 1 has just ended. Slow jumps back to head; fast stays at the meeting point."
  - name: noCycle
    payload: {}
    description: "Fast or fast.next has reached null; the algorithm returns null."

static_fallback:
  generator: jsdom
  output: site/static/widgets/w-14-floyd-cycle-fallback.svg
  keyframes_used: [0, 3, 4, 6]
  # Override: the four fallback stills capture (init, Phase 1 meet, Phase 2
  # reset, Phase 2 meet)., these are the four moments
  # the reduced-motion reader must see.

panels:
  default:
    chapter: "5.3"
    label: "Floyd's tortoise and hare (LC 142)"
    canonical_input: |
      values = [1, 3, 2, 0, -4]
      pos = 2
      # Five distinct nodes; the tail at index 4 (value -4) loops back to
      # index 2 (value 2). Prefix length a = 2, cycle length L = 3,
      # entry-to-meeting distance b = 1. Expected entry: index 2.
    presets:
      - id: lc142_canonical
        label: "LC 142 example 1"
        input: { values: [1, 3, 2, 0, -4], pos: 2 }
      - id: head_is_entry
        label: "Cycle starts at head (a = 0)"
        input: { values: [1, 2], pos: 0 }
      - id: self_loop
        label: "Single-node self-cycle"
        input: { values: [1], pos: 0 }
      - id: acyclic
        label: "Acyclic list"
        input: { values: [1, 2, 3, 4, 5], pos: -1 }
    n_steps: 7
    # Trace generated by instrumenting the verified Python reference in
    # against the canonical input. Re-run yields a byte-
    # identical sequence.
    keyframes:
      - step: 0
        kind: init
        state: { phase: init, slow_idx: 0, fast_idx: 0, a: 2, L: 3 }
        narration: "Slow and fast both start at head (index 0, value 1). Phase 1 begins."
      - step: 1
        kind: advance
        payload: { slow_idx: 1, fast_idx: 2 }
        state: { phase: phase1-advance, slow_idx: 1, fast_idx: 2 }
        narration: "Slow advances 1 to index 1 (value 3). Fast advances 2 to index 2 (value 2, cycle entry)."
      - step: 2
        kind: advance
        payload: { slow_idx: 2, fast_idx: 4 }
        state: { phase: phase1-advance, slow_idx: 2, fast_idx: 4 }
        narration: "Slow steps to index 2 (value 2; now inside the cycle). Fast steps to index 4 (value -4)."
      - step: 3
        kind: meet
        payload: { idx: 3, phase: phase1 }
        state: { phase: phase1-meet, slow_idx: 3, fast_idx: 3 }
        narration: "Pointers meet at index 3 (value 0). Cycle confirmed. The meeting point sits b = 1 step past the entry."
      - step: 4
        kind: resetSlow
        payload: { fast_idx: 3 }
        state: { phase: phase2-reset, slow_idx: 0, fast_idx: 3 }
        narration: "Reset slow to head. Fast stays at the meeting point. Both will now advance at speed 1."
      - step: 5
        kind: advance
        payload: { slow_idx: 1, fast_idx: 4 }
        state: { phase: phase2-advance, slow_idx: 1, fast_idx: 4 }
        narration: "Slow steps to index 1; fast steps to index 4. Same speed; the gap is held constant modulo L."
      - step: 6
        kind: meet
        payload: { idx: 2, phase: phase2 }
        state: { phase: phase2-meet, slow_idx: 2, fast_idx: 2, result: 2 }
        narration: "Both pointers meet at the cycle entry: index 2 (value 2). Return this node."

notes: |
  Animates Floyd's two-phase algorithm on the LC 142 canonical input. The
  derivation a = k*L - b is the geometric reason resetting
  slow to head and walking both at speed 1 reaches the entry simultaneously.
  Wong palette assignments (per `style-guide.md` "Color-blind palettes"):
    - orange (#E69F00)         active pointer (slow, fast)
    - reddish-purple (#CC79A7) Phase 1 meeting point inside the cycle
    - bluish-green (#009E73)   cycle entry node when located in Phase 2
    - sky-blue (#56B4E9)       visited prefix nodes
  Status line is the `narration` field of each step; aria-live="polite".