logigate/app/lib/logic/puzzles.ts

234 lines
11 KiB
TypeScript
Raw Permalink Normal View History

// Puzzles: a circuit someone built, turned into a task for others. Only the
// behaviour is published (a list of input settings and the outputs they must
// give), never the circuit. Every week there is also a generated puzzle.
// Shared by the browser and the server, which checks scores itself.
import { nandCounts, stats, TRANSISTORS_PER_NAND, type TestStep } from './analyze'
import { compile } from './compile'
import { chipPins, type DefLookup } from './geometry'
import { Simulator } from './sim'
import type { ComponentDef, PuzzleSpec } from './types'
export const PUZZLE_LIMITS = { inputs: 12, outputs: 16, steps: 4096, label: 24, name: 60, goal: 400 }
/** Gate evaluations allowed per step and per whole check, so a check always ends quickly. */
const STEP_BUDGET = 200_000
const TOTAL_BUDGET = 20_000_000
/** Small fast seeded random numbers (mulberry32). */
export function rng(seed: number) {
let a = seed >>> 0
return () => {
a = (a + 0x6d2b79f5) >>> 0
let t = a
t = Math.imul(t ^ (t >>> 15), t | 1)
t ^= t + Math.imul(t ^ (t >>> 7), t | 61)
return ((t ^ (t >>> 14)) >>> 0) / 4294967296
}
}
const hash = (s: string) => [...s].reduce((h, c) => (Math.imul(h, 31) + c.charCodeAt(0)) | 0, 7)
/**
* The steps that describe a circuit: every input combination when it has no
* memory, otherwise a fixed run of random input changes from power-on.
* Throws with a readable reason when the circuit can't be a puzzle.
*/
export function describeCircuit(get: DefLookup, defId: string): { inputs: string[]; outputs: string[]; steps: TestStep[]; sequential: boolean } {
const def = get(defId)
if (!def) throw new Error('Circuit not found')
const pins = chipPins(def)
if (!pins.inputs.length) throw new Error('Add at least one input')
if (!pins.outputs.length) throw new Error('Add at least one output')
if (pins.inputs.length > PUZZLE_LIMITS.inputs) throw new Error(`At most ${PUZZLE_LIMITS.inputs} inputs`)
if (pins.outputs.length > PUZZLE_LIMITS.outputs) throw new Error(`At most ${PUZZLE_LIMITS.outputs} outputs`)
const labels = [...pins.inputs, ...pins.outputs].map(p => p.label)
if (new Set(labels.map(l => l.toLowerCase())).size !== labels.length) throw new Error('Give every input and output its own name')
if (labels.some(l => l.length > PUZZLE_LIMITS.label)) throw new Error(`Pin names can have at most ${PUZZLE_LIMITS.label} characters`)
const nl = compile(get, defId)
if (nl.clocks.length) throw new Error('Use an input instead of a clock, so the steps can drive it')
const sequential = stats(nl).sequential
const sim = new Simulator(nl)
sim.run(STEP_BUDGET)
const n = pins.inputs.length
const patterns: number[][] = []
if (!sequential && n <= 10) {
for (let i = 0; i < 1 << n; i++) patterns.push(pins.inputs.map((_, k) => (i >> (n - 1 - k)) & 1))
} else {
// Change one input at a time, so latches and edges get exercised.
const r = rng(hash(def.name) ^ n)
const cur = pins.inputs.map(() => 0)
patterns.push([...cur])
for (let i = 0; i < Math.min(PUZZLE_LIMITS.steps - 1, 32 * n + 32); i++) {
cur[Math.floor(r() * n)]! ^= 1
patterns.push([...cur])
}
}
const steps: TestStep[] = []
for (const ins of patterns) {
pins.inputs.forEach((p, k) => sim.setSource(p.key, ins[k] === 1))
if (!sim.run(STEP_BUDGET)) throw new Error('The circuit keeps oscillating, so it has no clear answer')
steps.push({
set: Object.fromEntries(pins.inputs.map((p, k) => [p.label, ins[k]!])),
expect: Object.fromEntries(pins.outputs.map(p => [p.label, sim.output(p.key)])),
})
}
return { inputs: pins.inputs.map(p => p.label), outputs: pins.outputs.map(p => p.label), steps, sequential }
}
/** A puzzle from one of your circuits. */
export function makePuzzle(components: ComponentDef[], defId: string, name: string, goal: string): Omit<PuzzleSpec, 'id'> {
const get = (id: string) => components.find(d => d.id === id)
const d = describeCircuit(get, defId)
return {
name: name.trim().slice(0, PUZZLE_LIMITS.name) || 'Puzzle',
goal: goal.trim().slice(0, PUZZLE_LIMITS.goal) || (d.sequential ? 'Match the outputs step by step, from power-on.' : 'Match the truth table.'),
inputs: d.inputs,
outputs: d.outputs,
steps: d.steps,
author: (nandCounts(components).get(defId) ?? 0) * TRANSISTORS_PER_NAND,
}
}
/** Checks puzzle data from outside. Returns a clean copy, or throws. */
export function cleanPuzzle(raw: unknown, id: string): PuzzleSpec {
const p = raw as Partial<PuzzleSpec>
const fail = (why: string): never => {
throw new Error(`Not a valid puzzle: ${why}`)
}
if (!p || typeof p !== 'object') fail('no data')
const labels = (v: unknown, max: number) => {
if (!Array.isArray(v) || !v.length || v.length > max) fail('pins')
const list = (v as unknown[]).map(l => (typeof l === 'string' ? l.trim() : ''))
if (list.some(l => !l || l.length > PUZZLE_LIMITS.label)) fail('pin names')
return list
}
const inputs = labels(p.inputs, PUZZLE_LIMITS.inputs)
const outputs = labels(p.outputs, PUZZLE_LIMITS.outputs)
if (new Set([...inputs, ...outputs].map(l => l.toLowerCase())).size !== inputs.length + outputs.length) fail('pin names repeat')
if (!Array.isArray(p.steps) || !p.steps.length || p.steps.length > PUZZLE_LIMITS.steps) fail('steps')
const bit = (v: unknown) => (v === 0 || v === 1 ? v : fail('values must be 0 or 1'))
const steps = p.steps!.map(s => ({
set: Object.fromEntries(inputs.filter(l => s?.set && l in s.set).map(l => [l, bit(s.set[l])])),
expect: Object.fromEntries(outputs.filter(l => s?.expect && l in s.expect).map(l => [l, bit(s.expect[l])])),
}))
return {
id,
name: typeof p.name === 'string' && p.name.trim() ? p.name.trim().slice(0, PUZZLE_LIMITS.name) : 'Puzzle',
goal: typeof p.goal === 'string' ? p.goal.trim().slice(0, PUZZLE_LIMITS.goal) : '',
inputs,
outputs,
steps,
...(typeof p.author === 'number' && Number.isInteger(p.author) && p.author >= 0 ? { author: p.author } : {}),
}
}
export interface PuzzleScore {
pass: boolean
message: string
transistors: number
/** Longest gate path; null with feedback loops. */
delay: number | null
}
/** Runs a solution against a puzzle within a fixed amount of work. */
export function scoreSolution(components: ComponentDef[], defId: string, spec: PuzzleSpec): PuzzleScore {
const get = (id: string) => components.find(d => d.id === id)
const def = get(defId)
const transistors = (nandCounts(components).get(defId) ?? 0) * TRANSISTORS_PER_NAND
const out = (pass: boolean, message: string, delay: number | null = null): PuzzleScore => ({ pass, message, transistors, delay })
if (!def) return out(false, 'Circuit not found')
const pins = chipPins(def)
const find = (list: { key: string; label: string }[], label: string) => list.find(p => p.label.toLowerCase() === label.toLowerCase())
for (const l of spec.inputs) if (!find(pins.inputs, l)) return out(false, `Missing input pin "${l}"`)
for (const l of spec.outputs) if (!find(pins.outputs, l)) return out(false, `Missing output pin "${l}"`)
const nl = compile(get, defId)
if (nl.errors.length) return out(false, nl.errors[0]!)
const delay = stats(nl).delay
const sim = new Simulator(nl)
let left = TOTAL_BUDGET
const settle = () => {
let ok = false
for (let k = 0; k < STEP_BUDGET && left > 0; k += 20_000) {
left -= 20_000
if ((ok = sim.run(20_000))) break
}
return ok
}
settle()
for (let i = 0; i < spec.steps.length; i++) {
const step = spec.steps[i]!
for (const [l, v] of Object.entries(step.set)) sim.setSource(find(pins.inputs, l)!.key, v === 1)
if (!settle()) return out(false, left <= 0 ? 'The circuit takes too long to settle' : 'The circuit oscillates and never settles', delay)
for (const [l, want] of Object.entries(step.expect)) {
const got = sim.output(find(pins.outputs, l)!.key)
if (got !== want) {
const ins = Object.entries(step.set).map(([k, v]) => `${k}=${v}`).join(' ')
return out(false, `${spec.steps.length > 1 << spec.inputs.length ? `Step ${i + 1}: with` : 'With'} ${ins}: ${l} is ${got}, expected ${want}`, delay)
}
}
}
return out(true, `All ${spec.steps.length} checks pass`, delay)
}
// ── Puzzle of the week ──────────────────────────────────────────────
/** ISO week of a date, like "2026-43". */
export function weekKey(date = new Date()): string {
const d = new Date(Date.UTC(date.getUTCFullYear(), date.getUTCMonth(), date.getUTCDate()))
const day = d.getUTCDay() || 7
d.setUTCDate(d.getUTCDate() + 4 - day)
const year = d.getUTCFullYear()
const week = Math.ceil(((d.getTime() - Date.UTC(year, 0, 1)) / 86_400_000 + 1) / 7)
return `${year}-${String(week).padStart(2, '0')}`
}
export const weeklyId = (key: string) => `week:${key}`
export const isWeekKey = (key: string) => /^\d{4}-\d{2}$/.test(key)
/**
* The generated puzzle of a week: a random logic function of three or four
* inputs with one or two outputs. Each output depends on every input, so
* there is no shortcut through a single wire.
*/
export function weeklyPuzzle(key: string): PuzzleSpec {
const r = rng(hash(`logigate-week-${key}`))
const n = r() < 0.5 ? 3 : 4
const m = n === 3 ? 2 : r() < 0.5 ? 1 : 2
const inputs = ['A', 'B', 'C', 'D'].slice(0, n)
const outputs = m === 1 ? ['Q'] : ['X', 'Y']
const rows = 1 << n
const dependsOnAll = (t: number[]) => inputs.every((_, k) => t.some((v, i) => v !== t[i ^ (1 << (n - 1 - k))]))
const tables: number[][] = []
while (tables.length < m) {
const t = Array.from({ length: rows }, () => (r() < 0.5 ? 1 : 0))
if (dependsOnAll(t) && !tables.some(o => o.join() === t.join())) tables.push(t)
}
const steps: TestStep[] = []
for (let i = 0; i < rows; i++) {
steps.push({
set: Object.fromEntries(inputs.map((l, k) => [l, (i >> (n - 1 - k)) & 1])),
expect: Object.fromEntries(outputs.map((l, k) => [l, tables[k]![i]!])),
})
}
return {
id: weeklyId(key),
name: `Puzzle of week ${key.slice(5)}`,
goal: `Build the circuit from the table with as few transistors as you can. Everyone gets the same puzzle this week (${key}).`,
inputs,
outputs,
steps,
}
}
/** True when the steps are exactly one per input combination, so they read as a truth table. */
export function isTable(spec: PuzzleSpec): boolean {
return spec.steps.length === 1 << spec.inputs.length && spec.steps.every(s => Object.keys(s.set).length === spec.inputs.length)
}
/** Path segment of a puzzle in the API and links: "pz:abc" → "abc", "week:2026-43" → "week-2026-43". */
export function apiId(specId: string): string {
return specId.startsWith('pz:') ? specId.slice(3) : specId.replace(':', '-')
}