// Binærsøk: halvér søkerommet — Manimo lesson scene.
// Chapter 11 of itgk (Rekursjon, sortering og søk). Why sorted lists are
// worth their weight: linear search walks cell by cell (11 checks to find 42),
// binary search kills half the search space per check (4 checks). Fifteen
// live cells, a walking pointer with a ticking counter, a pulsing midpoint,
// and whole halves of the row dying in one stroke. The payoff: a million
// sorted numbers ≈ twenty checks.
//
// Beats (placeholder timings — rewire-scene.js overwrites them after audio):
// 0–10 Manimo hook
// 10–26 Lineært — pointer walks, counter climbs to 11 (GENUINE MOTION)
// 26–45 Binært — four phases, halves die in one stroke (GENUINE MOTION)
// 45–58 Kontrast — 11 vs 4, and the log₂ scaling payoff
// 58–66 Takeaway
//
// Colour discipline:
// chalk-100 cell values
// chalk-300 dimmed/visited cells, hints
// amber-400 found cell, mid pulse, primary accent
// amber-300 counter, payoff
// rose-400 discarded half (flash before dying)
// teal-400 verdict «høyre/venstre» direction hints
//
// Milestones inside the motion beats are fractions of the sprite's actual
// duration so audio rewires keep the choreography aligned.
const SCENE_DURATION = 68;
const NARRATION = [
/* 0–10 */ 'Du leter etter ett tall blant femten sorterte. Hvor mange forsøk trenger du? Femten? Eller holder det med fire?',
/* 10–26 */ 'Den enkle måten starter til venstre og sjekker én og én: er det deg? Er det deg? Førtito står langt ute i lista, så telleren rekker å bli elleve før vi finner den.',
/* 26–45 */ 'Binærsøk bruker at lista er sortert, og starter i midten. Tjueseks er for lite — da kan hele venstre halvdel kastes i ett jafs. Ny midte: førtisju er for stort, bort med toppen. Så trettiåtte — for lite. Og der står førtito. Fire forsøk.',
/* 45–58 */ 'Elleve forsøk mot fire. Og forspranget vokser: dobler du lista, trenger binærsøket bare ett forsøk til. En million sorterte tall? Omtrent tjue forsøk. Det er derfor det lønner seg å holde lister sortert.',
/* 58–66 */ 'Halvér søkerommet, igjen og igjen. Det er hele trikset — og grunnen til at sortering er gull verdt.',
];
const NARRATION_AUDIO = 'audio/binaersok-halvering/scene.mp3';
// ─── Data ──────────────────────────────────────────────────────────────────
const VALUES = [2, 5, 8, 11, 14, 17, 23, 26, 31, 38, 42, 47, 53, 59, 61];
const TARGET = 42; // index 10
const LINEAR_CHECKS = 11; // pointer walks indices 0..10
// Binary phases: search window [lo, hi], probe mid, verdict.
const PHASES = [
{ lo: 0, hi: 14, mid: 7, cmp: '26 < 42', dir: 'høyre', killLo: 0, killHi: 7 },
{ lo: 8, hi: 14, mid: 11, cmp: '47 > 42', dir: 'venstre', killLo: 11, killHi: 14 },
{ lo: 8, hi: 10, mid: 9, cmp: '38 < 42', dir: 'høyre', killLo: 8, killHi: 9 },
{ lo: 10, hi: 10, mid: 10, cmp: '42 = 42', dir: 'funnet', killLo: -1, killHi: -1 },
];
// ─── Layout ────────────────────────────────────────────────────────────────
function layoutGeom(portrait) {
if (portrait) {
return {
x0: 32, rowY: 560, cell: 40, pitch: 44, valueFont: 13,
badgeX: 32, badgeY: 460, counterX: 470, counterY: 460,
checkX: 32, checkY: 680, hintY: 740,
svgW: 720, svgH: 1280,
};
}
return {
x0: 104, rowY: 330, cell: 64, pitch: 72, valueFont: 20,
badgeX: 104, badgeY: 232, counterX: 940, counterY: 232,
checkX: 104, checkY: 470, hintY: 540,
svgW: 1280, svgH: 720,
};
}
function easeInOutCubic(t) {
return t < 0.5 ? 4 * t * t * t : 1 - Math.pow(-2 * t + 2, 3) / 2;
}
// ─── Pieces (DOM) ──────────────────────────────────────────────────────────
// state: 'normal' | 'visited' (linear walk) | 'dead' (binary discard)
// | 'mid' (probing) | 'found'
function Cell({ G, i, state }) {
const border =
state === 'found' ? 'var(--amber-400)' :
state === 'mid' ? 'var(--amber-400)' :
'rgba(232,220,193,0.25)';
const opacity = state === 'dead' ? 0.13 : state === 'visited' ? 0.38 : 1;
return (
{VALUES[i]}
);
}
function Pointer({ G, x, show }) {
if (!show) return null;
return (
);
}
function Badge({ x, y, label, value, accent = 'var(--amber-300)', big = false, show = true }) {
if (!show) return null;
return (
{label}
{value}
);
}
// Bracket under the still-alive window [lo, hi].
function WindowBracket({ G, lo, hi, show }) {
if (!show) return null;
const x1 = G.x0 + lo * G.pitch;
const w = (hi - lo) * G.pitch + G.cell;
return (
);
}
function CheckLine({ G, text, dir, show }) {
if (!show) return null;
const dirColor = dir === 'funnet' ? 'var(--amber-300)' : 'var(--teal-400)';
return (
{text}
→
{dir === 'funnet' ? 'funnet ✓' : `let ${dir}`}
);
}
// ─── Scene ─────────────────────────────────────────────────────────────────
function Scene() {
return (
);
}
// ─── Beat 2: Lineært søk (GENUINE MOTION) ──────────────────────────────────
function LineartBeat() {
const { localTime, duration } = useSprite();
const portrait = usePortrait();
const G = layoutGeom(portrait);
const T = Math.max(duration - 1, 1);
// Walk starts after the row has settled, ends with a hold on the find.
const walkStart = 0.22 * T;
const walkEnd = 0.86 * T;
const prog = clamp((localTime - walkStart) / (walkEnd - walkStart), 0, 1);
const exact = prog * (LINEAR_CHECKS - 1);
const idx = Math.min(Math.floor(exact), LINEAR_CHECKS - 1);
const started = localTime >= walkStart;
const foundNow = started && idx === LINEAR_CHECKS - 1 && prog >= 1;
// Pointer glides between cells.
const px = G.x0 + (started ? exact : 0) * G.pitch + G.cell / 2 - 9;
return (
<>
{VALUES.map((v, i) => (
|
))}
{foundNow && (
Elleve forsøk — og i verste fall måtte vi innom alle femten.
)}
);
}
// ─── Beat 3: Binærsøk (GENUINE MOTION) ─────────────────────────────────────
function BinartBeat() {
const { localTime, duration } = useSprite();
const portrait = usePortrait();
const G = layoutGeom(portrait);
const T = Math.max(duration - 1, 1);
const at = (f) => f * T;
// Four phases; each probes at probeAt and kills its half at killAt.
const SCHED = [
{ probeAt: at(0.10), killAt: at(0.24) },
{ probeAt: at(0.32), killAt: at(0.46) },
{ probeAt: at(0.54), killAt: at(0.66) },
{ probeAt: at(0.74), killAt: null },
];
const phaseIdx = SCHED.reduce((acc, s, k) => (localTime >= s.probeAt ? k : acc), -1);
const phase = phaseIdx >= 0 ? PHASES[phaseIdx] : null;
// A cell is dead once its phase's kill moment has passed.
const deadAt = (i) => {
for (let k = 0; k < PHASES.length; k++) {
const p = PHASES[k], s = SCHED[k];
if (s.killAt != null && i >= p.killLo && i <= p.killHi && localTime >= s.killAt) return true;
}
return false;
};
const found = phaseIdx === 3;
return (
<>
= 0}/>
{VALUES.map((v, i) => {
let state = 'normal';
if (deadAt(i)) state = 'dead';
else if (found && i === 10) state = 'found';
else if (phase && i === phase.mid) state = 'mid';
return ;
})}
{phase && phase.mid != null && !found && (
)}
= 0}/>
{phase && (
)}
{phaseIdx >= 1 && !found && (
Én sjekk — en hel halvdel borte.
)}
);
}
// ─── Beat 4: Kontrast ──────────────────────────────────────────────────────
function KontrastBeat() {
const portrait = usePortrait();
return (
lineært
11
forsøk
binært
4
forsøk
Dobbelt så lang liste → bare ett forsøk til.
1 000 000 tall → ~20 forsøk
);
}
// ─── Beat 5: Takeaway ──────────────────────────────────────────────────────
function Takeaway() {
const portrait = usePortrait();
return (
binærsøk
Halvér søkerommet — igjen og igjen.
15 → 7 → 3 → 1
);
}
// Expose narration to external tooling (TTS generation, subtitle export)
window.sceneNarration = NARRATION;
// ─── Mount ─────────────────────────────────────────────────────────────────
function App() {
return (
);
}
ReactDOM.createRoot(document.getElementById('root')).render();
|