Hamiltonian path generator for ModelRift.com

hamiltonian-path.js

#!/usr/bin/env node
import fs from "node:fs";
import path from "node:path";
/*
 run this as: node generate.js --dim 8 --seed demo3
 then go to modelrift.com and copypasted the svg as text into chat message along with the prompt "please generate hamiltonian path from this svg"
*/

function parseArgs(argv) {
  const args = {
    dim: null,
    out: null,
    cell: 20,
    margin: 10,
    stroke: 4,
    seed: null,
    tries: 200,
  };
  for (let i = 0; i < argv.length; i += 1) {
    const a = argv[i];
    if (a === "--dim" || a === "-d") {
      args.dim = Number(argv[i + 1]);
      i += 1;
      continue;
    }
    if (a.startsWith("--dim=")) {
      args.dim = Number(a.split("=")[1]);
      continue;
    }
    if (a === "--out" || a === "-o") {
      args.out = argv[i + 1];
      i += 1;
      continue;
    }
    if (a.startsWith("--out=")) {
      args.out = a.split("=")[1];
      continue;
    }
    if (a === "--cell") {
      args.cell = Number(argv[i + 1]);
      i += 1;
      continue;
    }
    if (a.startsWith("--cell=")) {
      args.cell = Number(a.split("=")[1]);
      continue;
    }
    if (a === "--margin") {
      args.margin = Number(argv[i + 1]);
      i += 1;
      continue;
    }
    if (a.startsWith("--margin=")) {
      args.margin = Number(a.split("=")[1]);
      continue;
    }
    if (a === "--stroke") {
      args.stroke = Number(argv[i + 1]);
      i += 1;
      continue;
    }
    if (a.startsWith("--stroke=")) {
      args.stroke = Number(a.split("=")[1]);
      continue;
    }
    if (a === "--seed") {
      args.seed = String(argv[i + 1]);
      i += 1;
      continue;
    }
    if (a.startsWith("--seed=")) {
      args.seed = String(a.split("=")[1]);
      continue;
    }
    if (a === "--tries") {
      args.tries = Number(argv[i + 1]);
      i += 1;
      continue;
    }
    if (a.startsWith("--tries=")) {
      args.tries = Number(a.split("=")[1]);
      continue;
    }
    if (args.dim === null && !a.startsWith("-")) {
      args.dim = Number(a);
      continue;
    }
  }
  return args;
}

function assertValid(n, name) {
  if (!Number.isFinite(n) || n < 1 || !Number.isInteger(n)) {
    throw new Error(`${name} must be a positive integer`);
  }
}

function mulberry32(seed) {
  let t = seed >>> 0;
  return () => {
    t += 0x6d2b79f5;
    let r = t;
    r = Math.imul(r ^ (r >>> 15), r | 1);
    r ^= r + Math.imul(r ^ (r >>> 7), r | 61);
    return ((r ^ (r >>> 14)) >>> 0) / 4294967296;
  };
}

function seedToInt(seed) {
  if (seed === null || seed === undefined) return null;
  let h = 2166136261;
  for (let i = 0; i < seed.length; i += 1) {
    h ^= seed.charCodeAt(i);
    h = Math.imul(h, 16777619);
  }
  return h >>> 0;
}

function shuffle(arr, rng) {
  for (let i = arr.length - 1; i > 0; i -= 1) {
    const j = Math.floor(rng() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
}

function randomHamiltonianPath(dim, rng, tries) {
  const total = dim * dim;
  const visited = Array.from({ length: dim }, () => Array(dim).fill(false));
  const deltas = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];

  const inBounds = (x, y) => x >= 0 && x < dim && y >= 0 && y < dim;
  const isBoundary = (x, y) => x === 0 || y === 0 || x === dim - 1 || y === dim - 1;

  const unvisitedNeighbors = (x, y) => {
    const out = [];
    for (const [dx, dy] of deltas) {
      const nx = x + dx;
      const ny = y + dy;
      if (inBounds(nx, ny) && !visited[ny][nx]) out.push([nx, ny]);
    }
    return out;
  };

  const degree = (x, y) => unvisitedNeighbors(x, y).length;

  function dfs(path, x, y) {
    if (path.length === total) return isBoundary(x, y);
    const nbrs = unvisitedNeighbors(x, y);
    if (nbrs.length === 0) return false;
    nbrs.sort((a, b) => degree(a[0], a[1]) - degree(b[0], b[1]));
    const groups = [];
    let current = [nbrs[0]];
    for (let i = 1; i < nbrs.length; i += 1) {
      const prev = nbrs[i - 1];
      const cur = nbrs[i];
      if (degree(prev[0], prev[1]) === degree(cur[0], cur[1])) {
        current.push(cur);
      } else {
        groups.push(current);
        current = [cur];
      }
    }
    groups.push(current);
    const ordered = [];
    for (const g of groups) {
      shuffle(g, rng);
      ordered.push(...g);
    }

    for (const [nx, ny] of ordered) {
      visited[ny][nx] = true;
      path.push([nx, ny]);
      if (dfs(path, nx, ny)) return true;
      path.pop();
      visited[ny][nx] = false;
    }
    return false;
  }

  for (let attempt = 0; attempt < tries; attempt += 1) {
    for (let y = 0; y < dim; y += 1) visited[y].fill(false);
    const side = Math.floor(rng() * 4);
    const t = Math.floor(rng() * dim);
    let sx = 0;
    let sy = 0;
    if (side === 0) {
      sx = t;
      sy = 0;
    } else if (side === 1) {
      sx = dim - 1;
      sy = t;
    } else if (side === 2) {
      sx = t;
      sy = dim - 1;
    } else {
      sx = 0;
      sy = t;
    }
    const path = [[sx, sy]];
    visited[sy][sx] = true;
    if (dfs(path, sx, sy)) return path;
  }

  return null;
}

function pointsToPath(points, cell, margin) {
  if (points.length === 0) return "";
  const [x0, y0] = points[0];
  let d = `M ${margin + x0 * cell} ${margin + y0 * cell}`;
  for (let i = 1; i < points.length; i += 1) {
    const [x, y] = points[i];
    d += ` L ${margin + x * cell} ${margin + y * cell}`;
  }
  return d;
}

function buildSvg(dim, cell, margin, stroke, seed, tries) {
  const seedInt = seedToInt(seed ?? String(Date.now()));
  const rng = mulberry32(seedInt ?? Math.floor(Math.random() * 2 ** 32));
  const points = randomHamiltonianPath(dim, rng, tries);
  if (!points) {
    throw new Error(`Failed to find Hamiltonian path after ${tries} tries; try a different seed or increase --tries.`);
  }
  const d = pointsToPath(points, cell, margin);
  const width = margin * 2 + (dim - 1) * cell;
  const height = margin * 2 + (dim - 1) * cell;

  return `<?xml version="1.0" encoding="UTF-8"?>\n` +
    `<svg xmlns="http://www.w3.org/2000/svg" width="${width}" height="${height}" viewBox="0 0 ${width} ${height}">\n` +
    `  <path d="${d}" fill="none" stroke="black" stroke-width="${stroke}" stroke-linecap="square" stroke-linejoin="miter"/>\n` +
    `</svg>\n`;
}

function main() {
  const args = parseArgs(process.argv.slice(2));
  if (args.dim === null) {
    console.error("Usage: node generate.mjs --dim <N> [--out file.svg] [--cell 20] [--margin 10] [--stroke 4] [--seed abc] [--tries 200]");
    process.exit(1);
  }
  assertValid(args.dim, "dim");
  assertValid(args.cell, "cell");
  assertValid(args.margin, "margin");
  assertValid(args.stroke, "stroke");
  assertValid(args.tries, "tries");

  const svg = buildSvg(args.dim, args.cell, args.margin, args.stroke, args.seed, args.tries);
  const outPath = args.out || path.resolve(process.cwd(), `hamiltonian-${args.dim}.svg`);
  fs.writeFileSync(outPath, svg, "utf8");
  console.log(`Wrote ${outPath}`);
}

main();