// Rekursjonstre: arbeid på hvert nivå — Manimo lesson scene.
// Chapter 0 of algdat (Verktøykassa). Visualises the standard
// divide-and-conquer recurrence T(n) = 2T(n/2) + n by unrolling it into
// a four-level tree for n = 8. The root carries cost n; each level
// doubles the node count and halves the per-node cost, so every row
// sums to n — and there are log₂(n)+1 levels. The payoff is n·log n.
//
// Beats (placeholder timings — rewire-scene.js overwrites them after audio):
// 0– 9.5 Manimo hook
// 9.5–20 Rekursjonsligningen — T(n) = 2T(n/2) + n laid out as boxes
// 20–38.5 Treet vokser — four levels expand, row totals light up (GENUINE MOTION)
// 38.5–50.5 Summering — the four row totals stack into n·log n (GENUINE MOTION)
// 50.5–60 Takeaway (T(n) = O(n log n))
//
// Colour discipline:
// chalk-100 high-contrast text / cost numbers
// chalk-200 body text
// chalk-300 dimmed labels / dim tree state
// amber-300 payoff numbers, active row totals, formula pills
// amber-400 primary tree edges, active node border
// teal-400 leaf row (base case, work = 1)
// violet-400 splitting line accent + recursion arrows
//
// Milestones inside each motion beat are fractions of the sprite's
// actual duration so audio rewires keep the choreography aligned.
const SCENE_DURATION = 64;
const NARRATION = [
/* 0– 9.5 */ 'Hvor mye arbeid gjør en algoritme som deler problemet i to og løser hver halvdel? Vi bretter rekursjonen ut som et tre og leser av kjøretida.',
/* 9.5–20 */ 'Si at vi løser et problem av størrelse n med n arbeid på toppen, og så kaller oss selv to ganger på halv størrelse. Da er T av n lik to ganger T av n delt på to, pluss n.',
/* 20–38.5 */ 'Vi bretter ut rekursjonen. Roten gjør n arbeid. Den har to barn med n delt på to. Hvert barn deler igjen, så vi får fire med n delt på fire, og åtte løv med ett arbeid. Legg merke til summen i hver rad — den er alltid n.',
/* 38.5–50.5 */ 'Treet stopper når delproblemene er på ett — det skjer etter log av n nivåer. Hvert nivå koster n. Tell sammen, og kjøretida lander på n ganger log n.',
/* 50.5–60 */ 'Det er motoren bak del og hersk. Når roten gjør lineært arbeid og delproblemene halveres, lander kjøretida på orden n log n.',
];
const NARRATION_AUDIO = 'audio/rekursjonstre-arbeidsrader/scene.mp3';
// ─── Tree shape: n = 8, four levels (0..3) ─────────────────────────────────
// At level k there are 2^k nodes, each with cost n / 2^k.
const TREE_LEVELS = 4; // levels 0..3
const N_LABEL = 'n'; // symbolic display value at the root
const COST_AT_LEVEL = ['n', 'n/2', 'n/4', '1']; // text shown inside each node
// Per-level row total badge text (always "= n" except the leaf row uses
// "8 · 1 = n" so the equality is obvious to a careful reader).
const ROW_SUM_TEXT = [
'rad 0: n = n',
'rad 1: n/2 + n/2 = n',
'rad 2: 4 · n/4 = n',
'rad 3: 8 · 1 = n',
];
function easeInOutCubic(t) {
return t < 0.5 ? 4 * t * t * t : 1 - Math.pow(-2 * t + 2, 3) / 2;
}
// ─── Geometry — landscape + portrait ──────────────────────────────────────
// `sumLayout: 'right'` puts row-total badges to the right of each row
// (landscape). `'below'` stacks them under the tree (portrait — narrow
// canvas).
function treeGeom(portrait) {
if (portrait) {
// 8 cells at pitch 70 + cell 50 ⇒ 8*70 = 560, last-cell extra = 50.
// leftX = (720 - 560)/2 = 80. Tree spans roughly x∈[80, 700].
return {
svgW: 720, svgH: 1280,
cellW: 50, cellH: 44, cellPitch: 70,
rowH: 130, topY: 230,
leftX: 80,
labelFont: 16, sumFont: 13,
sumLayout: 'below',
sumStartY: 680, // row-totals stack starts below tree
sumRowH: 56, sumPanelW: 560,
sumX: 80,
bottomCaptionY: 980,
payoffY: 1030, // payoff pill (used in beat 4)
showLevelLabels: false, // labels would clip on this narrow canvas
levelLabelX: 0, levelLabelFont: 11,
};
}
// Landscape — tree on the LEFT, sums + payoff column on the RIGHT.
return {
svgW: 1280, svgH: 720,
cellW: 64, cellH: 46, cellPitch: 72,
rowH: 130, topY: 130,
leftX: 196, // 8*72+64 ⇒ tree ends ≈ x=764
labelFont: 18, sumFont: 14,
sumLayout: 'right',
sumX: 800, sumStartY: 130,
sumRowH: 130, sumPanelW: 380,
bottomCaptionY: 660,
payoffY: 470,
showLevelLabels: true,
levelLabelX: 180, levelLabelFont: 11,
};
}
// Slot range covered by node `idx` at level `k` (idx 0..2^k-1).
// At level k there are 2^k nodes; each node spans (8 / 2^k) leaf slots.
function nodeSpanAt(k, idx) {
const span = 8 >> k;
return { from: idx * span, to: idx * span + span - 1 };
}
// Centre x of node (k, idx) using the leaf grid.
function nodeCenterX(G, k, idx) {
const { from, to } = nodeSpanAt(k, idx);
const xFrom = G.leftX + from * G.cellPitch + G.cellW / 2;
const xTo = G.leftX + to * G.cellPitch + G.cellW / 2;
return (xFrom + xTo) / 2;
}
function nodeTopLeft(G, k, idx) {
const cx = nodeCenterX(G, k, idx);
const y = G.topY + k * G.rowH;
return { x: cx - G.cellW / 2, y };
}
// ─── Single tree node (rounded box + cost label) ──────────────────────────
function TreeNode({ G, k, idx, state = 'idle', opacity = 1 }) {
const { x, y } = nodeTopLeft(G, k, idx);
const isLeafRow = k === TREE_LEVELS - 1;
const border =
state === 'highlight' ? 'var(--amber-300)' :
state === 'leaf' ? 'var(--teal-400)' :
state === 'active' ? 'var(--amber-400)' :
state === 'dim' ? 'rgba(232,220,193,0.20)' :
'rgba(232,220,193,0.32)';
const bg =
state === 'highlight' ? 'rgba(244,184,96,0.18)' :
state === 'leaf' ? 'rgba(0,0,0,0.40)' :
state === 'active' ? 'rgba(244,184,96,0.10)' :
'rgba(0,0,0,0.45)';
const textColor =
state === 'leaf' ? 'var(--teal-400)' :
state === 'highlight' ? 'var(--amber-300)' :
state === 'dim' ? 'var(--chalk-300)' :
'var(--chalk-100)';
const label = isLeafRow ? '1' : COST_AT_LEVEL[k];
return (
{label}
);
}
// Edge from parent (k, pIdx) bottom → child (k+1, cIdx) top, drawn via
// stroke-dashoffset over `drawT` ∈ [0,1].
function TreeEdge({ G, k, pIdx, cIdx, drawT, color = 'var(--amber-400)', opacity = 0.8 }) {
const px = nodeCenterX(G, k, pIdx);
const py = G.topY + k * G.rowH + G.cellH;
const cx = nodeCenterX(G, k + 1, cIdx);
const cy = G.topY + (k + 1) * G.rowH;
const len = Math.hypot(cx - px, cy - py);
const t = clamp(drawT, 0, 1);
return (
);
}
function LevelLabel({ G, k, text, opacity = 1 }) {
const y = G.topY + k * G.rowH + G.cellH / 2 + 4;
return (
{text}
);
}
// ─── Scene ─────────────────────────────────────────────────────────────────
function Scene() {
return (
);
}
// ─── Beat 2: Rekursjonsligningen ──────────────────────────────────────────
// Lay out T(n) = 2 · T(n/2) + n as three boxed terms connected by mono
// operators. Boxes appear in sequence: T(n) on the left, then the split
// into 2·T(n/2) + n on the right. A caption underneath ties the parts
// to "arbeid på toppen / to halve problemer".
function Rekursjonsligningen() {
const portrait = usePortrait();
const layout = portrait
? {
boxFont: 24, opFont: 28, gap: 14,
wideW: 180, narrowW: 150, h: 78,
topY: 460, captionY: 760,
captionFont: 22,
}
: {
boxFont: 28, opFont: 32, gap: 22,
wideW: 230, narrowW: 200, h: 100,
topY: 280, captionY: 470,
captionFont: 24,
};
// Render the equation as a single centered row of divs.
const row = (
T(n)
=
2 · T(n/2)
+
n
);
return (
<>
{row}
{/* Caption — ties the parts to their meaning */}
n arbeid her oppe —
to halve problemer der nede.
);
}
// ─── Beat 3: Treet vokser (GENUINE MOTION) ────────────────────────────────
// Four-level recursion tree expands one level at a time. Each new level
// brings: (a) parent→child edges drawing in via dashoffset, (b) the new
// row of nodes fading in, (c) a row-sum badge to the right of the row
// asserting that the row totals to n.
function TreetVokser() {
const portrait = usePortrait();
const G = treeGeom(portrait);
const { localTime, duration } = useSprite();
const T = Math.max(duration - 1, 1);
const at = (f) => f * T;
// Schedule. The root sits alone for a beat; then three drop-waves bring
// levels 1, 2, 3 — and four row-sum badges fade in in order.
const LEVEL_AT = [at(0.05), at(0.20), at(0.38), at(0.56)]; // level k starts appearing
const LEVEL_DUR = 0.95;
const ROW_SUM_AT = [at(0.13), at(0.30), at(0.49), at(0.67)];
function levelVis(k) {
return clamp((localTime - LEVEL_AT[k]) / LEVEL_DUR, 0, 1);
}
function rowSumVis(k) {
return clamp((localTime - ROW_SUM_AT[k]) / 0.5, 0, 1);
}
// Position of row-total badge k. In landscape it sits on the right at the
// same y as the matching tree row. In portrait it stacks under the tree.
function rowBadgePos(k) {
if (G.sumLayout === 'right') {
const y = G.sumStartY + k * G.sumRowH + G.cellH / 2 - 22;
return { x: G.sumX, y, w: G.sumPanelW };
}
return { x: G.sumX, y: G.sumStartY + k * G.sumRowH, w: G.sumPanelW };
}
return (
);
}
// ─── Beat 4: Summering (GENUINE MOTION) ───────────────────────────────────
// Same tree, dimmed. Each row-total badge highlights in turn (amber glow
// pulse) and a connector line trails down through them to the payoff pill
// that lands at the bottom. No animation of the badge positions — keeps
// the geometry stable and avoids overlap with the dim tree.
function Summering() {
const portrait = usePortrait();
const G = treeGeom(portrait);
const { localTime, duration } = useSprite();
const T = Math.max(duration - 1, 1);
const at = (f) => f * T;
// Choreography (fractions of T):
// 0.05 → 4 badges light up in turn, ~0.6s each
// 0.40 → "log₂ n nivåer" connector badge slides in below
// 0.55 → payoff pill "n · log₂ n" lands
const HL_AT = [at(0.05), at(0.13), at(0.21), at(0.29)];
const HL_DUR = 0.55;
const LOG_AT = at(0.30);
const PAYOFF_AT = at(0.42);
function rowHL(k) {
return clamp((localTime - HL_AT[k]) / HL_DUR, 0, 1);
}
// Reuse the same badge geometry as beat 3 so the eye picks up the
// continuity without any motion needed.
function rowBadgePos(k) {
if (G.sumLayout === 'right') {
const y = G.sumStartY + k * G.sumRowH + G.cellH / 2 - 22;
return { x: G.sumX, y, w: G.sumPanelW };
}
return { x: G.sumX, y: G.sumStartY + k * G.sumRowH, w: G.sumPanelW };
}
// Position of the log₂ n callout + the payoff pill. Landscape: a single
// right-column stack below the row-totals. Portrait: below the badge stack.
const last = rowBadgePos(3);
const logPos = portrait
? { left: 80, top: last.y + 64, width: G.sumPanelW }
: { left: G.sumX, top: last.y + 50, width: G.sumPanelW };
const payoffPos = portrait
? { left: 0, right: 0, top: last.y + 130, textAlign: 'center' }
: { left: G.sumX, top: last.y + 96, width: G.sumPanelW, textAlign: 'center' };
return (
<>
{/* "antall rader = log₂ n" connector badge — DOM layer for crisp
typography (sub tag). */}
antall rader = log2 n
{/* Payoff pill — n · log₂ n */}
n · log2 n
);
}
// ─── Beat 5: Takeaway ──────────────────────────────────────────────────────
function Takeaway() {
const portrait = usePortrait();
return (
kjøretid
T(n) = O(n log n)
Rekursjonstreet er motoren bak splitt og hersk.
);
}
// Expose narration to external tooling (TTS generation, subtitle export)
window.sceneNarration = NARRATION;
// ─── Mount ─────────────────────────────────────────────────────────────────
function App() {
return (
);
}
ReactDOM.createRoot(document.getElementById('root')).render();