Tower of Hanoi: Recursive Solver

// Tower of Hanoi animated solver.
// Classic recursive solution: to move N disks from src->dst via aux, first
// move N-1 from src->aux, then disk N from src->dst, then N-1 from aux->dst.
// Total moves T(N) = 2*T(N-1) + 1 = 2^N - 1. Mouse Y scrubs N from 3 to 9.
// Each move animates as lift -> translate -> drop in three phases.

const MIN_N = 3, MAX_N = 9;
let N = 7;
let pegs;           // [[disks bottom..top], [], []] of disk sizes
let plan;           // array of [from, to] precomputed moves
let step;           // index into plan
let phase;          // 0 lift, 1 translate, 2 drop, 3 settle
let phaseT;         // 0..1 progress in current phase
let curDisk;        // disk size currently moving (or 0 if idle)
let fromPeg, toPeg;
let elapsed;        // seconds since reset (for autoplay regardless of dt)
let lastN;

// Speed: total moves grows exponentially, so we scale per-move time so the
// full solve finishes in roughly the same wall-clock window for any N.
function moveDuration() {
  const total = (1 << N) - 1;
  // total time budget ~ 8s + extra for big N, divided by total moves, but
  // clamped so small N is still leisurely.
  const budget = 6 + 0.6 * N;
  return Math.max(0.06, Math.min(0.45, budget / total));
}

function plan_(n, from, via, to, out) {
  if (n === 0) return;
  plan_(n - 1, from, to, via, out);
  out.push([from, to]);
  plan_(n - 1, via, from, to, out);
}

function reset(newN) {
  N = newN;
  pegs = [[], [], []];
  for (let i = N; i >= 1; i--) pegs[0].push(i);
  plan = [];
  plan_(N, 0, 1, 2, plan);
  step = 0;
  phase = 0;
  phaseT = 0;
  curDisk = 0;
  fromPeg = 0;
  toPeg = 2;
  elapsed = 0;
  lastN = N;
}

function init() {
  reset(7);
}

function pegX(i, width) {
  // Three pegs at 1/6, 3/6, 5/6 of width.
  return width * (1 + 2 * i) / 6;
}

function diskW(size, width) {
  // Largest disk spans ~85% of a peg slot. Slot width is width/3.
  const slot = width / 3;
  const maxW = slot * 0.85;
  const minW = slot * 0.18;
  return minW + (maxW - minW) * (size - 1) / Math.max(1, MAX_N - 1);
}

function diskColor(size) {
  // Spectrum from cool (small) to warm (large).
  const h = (size - 1) / Math.max(1, MAX_N - 1);
  const hue = 220 - 220 * h;
  return "hsl(" + hue + ",70%,55%)";
}

function tick({ ctx, dt, width, height, input }) {
  // Scrub N from mouse Y. Top of canvas = 9 disks, bottom = 3.
  if (input && input.mouseY != null && height > 0) {
    const f = 1 - Math.max(0, Math.min(1, input.mouseY / height));
    const target = MIN_N + Math.round(f * (MAX_N - MIN_N));
    if (target !== lastN) reset(target);
  }

  elapsed += dt;

  // Advance animation.
  const dur = moveDuration();
  if (step < plan.length) {
    if (curDisk === 0) {
      // Pick up next move.
      const mv = plan[step];
      fromPeg = mv[0];
      toPeg = mv[1];
      curDisk = pegs[fromPeg][pegs[fromPeg].length - 1] || 0;
      phase = 0;
      phaseT = 0;
    }
    phaseT += dt / (dur / 3);
    if (phaseT >= 1) {
      phaseT = 0;
      phase++;
      if (phase >= 3) {
        // Commit move.
        const d = pegs[fromPeg].pop();
        pegs[toPeg].push(d);
        step++;
        curDisk = 0;
        phase = 0;
      }
    }
  } else {
    // Hold finished state for a beat, then loop.
    if (elapsed > 1.2 + ((1 << N) - 1) * dur + 1.2) {
      reset(N);
    }
  }

  // Background.
  ctx.fillStyle = "#0b0d12";
  ctx.fillRect(0, 0, width, height);

  // Base and pegs.
  const baseY = height * 0.82;
  const pegH = height * 0.55;
  const pegTop = baseY - pegH;
  ctx.fillStyle = "#2a3040";
  ctx.fillRect(width * 0.06, baseY, width * 0.88, height * 0.03);
  ctx.strokeStyle = "#3a4256";
  ctx.lineWidth = Math.max(3, width * 0.008);
  for (let i = 0; i < 3; i++) {
    const x = pegX(i, width);
    ctx.beginPath();
    ctx.moveTo(x, baseY);
    ctx.lineTo(x, pegTop);
    ctx.stroke();
  }

  // Disk dimensions.
  const diskH = Math.max(8, Math.min(22, (baseY - pegTop) / (MAX_N + 1)));

  // Compute moving disk position if any.
  const liftHeight = baseY - pegTop + diskH * 2;
  const apex = pegTop - diskH * 1.2;
  let mover = null;
  if (curDisk > 0 && step < plan.length) {
    const stackIdxFrom = pegs[fromPeg].length - 1; // it's still on fromPeg
    const yRest = baseY - (stackIdxFrom + 1) * diskH;
    const xFrom = pegX(fromPeg, width);
    const xTo = pegX(toPeg, width);
    let mx = xFrom, my = yRest;
    if (phase === 0) {
      my = yRest + (apex - yRest) * easeInOut(phaseT);
      mx = xFrom;
    } else if (phase === 1) {
      my = apex;
      mx = xFrom + (xTo - xFrom) * easeInOut(phaseT);
    } else if (phase === 2) {
      const stackIdxTo = pegs[toPeg].length; // will land here
      const yLand = baseY - (stackIdxTo + 1) * diskH;
      my = apex + (yLand - apex) * easeInOut(phaseT);
      mx = xTo;
    }
    mover = { x: mx, y: my, size: curDisk };
  }

  // Draw resting disks.
  for (let p = 0; p < 3; p++) {
    const x = pegX(p, width);
    for (let i = 0; i < pegs[p].length; i++) {
      const size = pegs[p][i];
      // Skip the disk currently being moved (it's on top of fromPeg before commit).
      if (mover && p === fromPeg && i === pegs[p].length - 1) continue;
      const dy = baseY - (i + 1) * diskH;
      drawDisk(ctx, x, dy, diskW(size, width), diskH, size);
    }
  }
  if (mover) {
    drawDisk(ctx, mover.x, mover.y, diskW(mover.size, width), diskH, mover.size);
  }

  // HUD.
  const total = (1 << N) - 1;
  const done = step;
  const pad = 10;
  ctx.fillStyle = "rgba(0,0,0,0.55)";
  ctx.fillRect(pad, pad, 240, 70);
  ctx.fillStyle = "#e8e8f0";
  ctx.font = "13px system-ui, sans-serif";
  ctx.fillText("Tower of Hanoi  N=" + N, pad + 8, pad + 20);
  ctx.fillStyle = "#9aa3b2";
  ctx.font = "12px system-ui, sans-serif";
  ctx.fillText("moves: " + done + " / " + total, pad + 8, pad + 38);
  ctx.fillText("T(N) = 2^N - 1", pad + 8, pad + 54);
  ctx.fillStyle = "#6f7888";
  ctx.font = "11px system-ui, sans-serif";
  ctx.fillText("move cursor Y to scrub N (3..9)", pad + 8, pad + 68);

  // Progress bar.
  const barW = width - pad * 2;
  const barY = height - pad - 6;
  ctx.fillStyle = "rgba(255,255,255,0.08)";
  ctx.fillRect(pad, barY, barW, 4);
  ctx.fillStyle = "#7aa2ff";
  ctx.fillRect(pad, barY, barW * (done / total), 4);
}

function easeInOut(t) {
  if (t < 0) return 0;
  if (t > 1) return 1;
  return t * t * (3 - 2 * t);
}

function drawDisk(ctx, cx, topYIfRest, w, h, size) {
  // cx, topYIfRest = top-left-anchor where topYIfRest is the TOP of the disk's
  // rect when at rest. The mover uses (cx, my) where my is the top of the disk.
  const x = cx - w / 2;
  const y = topYIfRest;
  const r = Math.min(h / 2, 8);
  ctx.fillStyle = diskColor(size);
  roundRect(ctx, x, y, w, h, r);
  ctx.fill();
  ctx.strokeStyle = "rgba(0,0,0,0.35)";
  ctx.lineWidth = 1;
  ctx.stroke();
  // Size label.
  if (h >= 12) {
    ctx.fillStyle = "rgba(0,0,0,0.55)";
    ctx.font = (Math.floor(h * 0.7)) + "px system-ui, sans-serif";
    ctx.textAlign = "center";
    ctx.textBaseline = "middle";
    ctx.fillText(String(size), cx, y + h / 2 + 1);
    ctx.textAlign = "start";
    ctx.textBaseline = "alphabetic";
  }
}

function roundRect(ctx, x, y, w, h, r) {
  ctx.beginPath();
  ctx.moveTo(x + r, y);
  ctx.lineTo(x + w - r, y);
  ctx.quadraticCurveTo(x + w, y, x + w, y + r);
  ctx.lineTo(x + w, y + h - r);
  ctx.quadraticCurveTo(x + w, y + h, x + w - r, y + h);
  ctx.lineTo(x + r, y + h);
  ctx.quadraticCurveTo(x, y + h, x, y + h - r);
  ctx.lineTo(x, y + r);
  ctx.quadraticCurveTo(x, y, x + r, y);
  ctx.closePath();
}