1import { RenderError } from '../runtime/errors'2import type { SideExpression, SquareGroup, SquaringDocument, SquaringNetworkSource, SquaringRectangleSource, SquaringWire } from './squaring'34export interface SquaringSquare {5 index: number6 x: number7 y: number8 side: number9 top: number10 bottom: number11 label: string12}1314export interface SquaringNode {15 id: string16 index: number17 y: number18 x0: number19 x1: number20 voltage: number21}2223export interface SquaringBlock {24 x: number25 y: number26 width: number27 height: number28 squares: number29}3031export interface BatteryCandidate {32 positive: string33 negative: string34 order: number35 width: number36 height: number37 simple: boolean38 perfect: boolean39 error: string | null40}4142export interface SquaringModel {43 form: 'rectangle' | 'network'44 width: number45 height: number46 squares: SquaringSquare[]47 nodes: SquaringNode[]48 positive: number49 negative: number50 order: number51 complete: boolean52 problem: string | null53 perfect: boolean54 repeatedSides: number[]55 simple: boolean56 blocks: SquaringBlock[]57 search: BatteryCandidate[] | null58 searchIndex: number59}6061const SEARCH_BUDGET = 250_00062const MAXIMUM_ORDER = 2_00063const MAXIMUM_BATTERY_SEARCH = 606465function sourceError(line: number, message: string): never {66 throw new RenderError(422, 'invalid_source', `Line ${line}: ${message}`)67}6869// ---------------------------------------------------------------------------70// Exact rational arithmetic keeps Kirchhoff and Stone solutions integral.7172type Fraction = { n: bigint; d: bigint }7374function gcd(a: bigint, b: bigint): bigint {75 let x = a < 0n ? -a : a76 let y = b < 0n ? -b : b77 while (y !== 0n) [x, y] = [y, x % y]78 return x79}8081function fraction(n: bigint, d = 1n): Fraction {82 if (d === 0n) throw new Error('Division by zero.')83 const sign = d < 0n ? -1n : 1n84 const divisor = gcd(n, d) || 1n85 return { n: (sign * n) / divisor, d: (sign * d) / divisor }86}8788const ZERO = fraction(0n)89const add = (a: Fraction, b: Fraction): Fraction => fraction(a.n * b.d + b.n * a.d, a.d * b.d)90const sub = (a: Fraction, b: Fraction): Fraction => fraction(a.n * b.d - b.n * a.d, a.d * b.d)91const mul = (a: Fraction, b: Fraction): Fraction => fraction(a.n * b.n, a.d * b.d)92const div = (a: Fraction, b: Fraction): Fraction => fraction(a.n * b.d, a.d * b.n)93const isZero = (a: Fraction): boolean => a.n === 0n9495/** Row-reduce an augmented matrix in place; returns pivot columns. */96function reduce(matrix: Fraction[][], columns: number): number[] {97 const pivots: number[] = []98 let row = 099 for (let column = 0; column < columns && row < matrix.length; column += 1) {100 let pivotRow = row101 while (pivotRow < matrix.length && isZero(matrix[pivotRow]?.[column] ?? ZERO)) pivotRow += 1102 if (pivotRow === matrix.length) continue103 ;[matrix[row], matrix[pivotRow]] = [matrix[pivotRow] as Fraction[], matrix[row] as Fraction[]]104 const pivotValues = matrix[row] as Fraction[]105 const pivotValue = pivotValues[column] as Fraction106 for (let index = 0; index < pivotValues.length; index += 1) pivotValues[index] = div(pivotValues[index] as Fraction, pivotValue)107 for (let other = 0; other < matrix.length; other += 1) {108 if (other === row) continue109 const values = matrix[other] as Fraction[]110 const factor = values[column] as Fraction111 if (isZero(factor)) continue112 for (let index = 0; index < values.length; index += 1) values[index] = sub(values[index] as Fraction, mul(factor, pivotValues[index] as Fraction))113 }114 pivots.push(column)115 row += 1116 }117 return pivots118}119120function integerScale(values: Fraction[]): bigint[] {121 let scale = 1n122 for (const value of values) scale = (scale * value.d) / gcd(scale, value.d)123 const integral = values.map(value => (value.n * scale) / value.d)124 let reduction = 0n125 for (const value of integral) reduction = gcd(reduction, value)126 return reduction === 0n ? integral : integral.map(value => value / reduction)127}128129function toSafeNumber(value: bigint, line: number): number {130 if (value > BigInt(Number.MAX_SAFE_INTEGER) || value < -BigInt(Number.MAX_SAFE_INTEGER)) {131 sourceError(line, 'The solution produces side lengths that are too large to draw.')132 }133 return Number(value)134}135136// ---------------------------------------------------------------------------137// Skyline placement shared by Bouwkamp order and network arrangement.138139interface Segment {140 x0: number141 x1: number142 depth: number143 node: number144}145146function mergeSkyline(segments: Segment[]): Segment[] {147 const merged: Segment[] = []148 for (const segment of segments) {149 const previous = merged.at(-1)150 if (previous !== undefined && previous.depth === segment.depth && previous.node === segment.node && previous.x1 === segment.x0) {151 previous.x1 = segment.x1152 } else {153 merged.push({ ...segment })154 }155 }156 return merged157}158159function lowestSegment(skyline: Segment[]): number {160 let best = 0161 for (let index = 1; index < skyline.length; index += 1) {162 if ((skyline[index]?.depth ?? Infinity) < (skyline[best]?.depth ?? Infinity)) best = index163 }164 return best165}166167interface Placed {168 x: number169 y: number170 side: number171 label: string172}173174interface Placement {175 width: number176 height: number177 squares: Placed[]178 problem: string | null179}180181// Bouwkamp placement: every square goes to the leftmost point of the highest182// unfilled segment, in source order. A "?" square is as wide as that segment.183// Placement stops at the first square that does not fit and reports why.184function placeBouwkamp(rectangle: SquaringRectangleSource): Placement {185 const { line } = rectangle186 const sides = rectangle.groups.flatMap(group => group.sides)187 if (sides.length > MAXIMUM_ORDER) sourceError(line, `At most ${MAXIMUM_ORDER} squares are supported.`)188 let width = rectangle.width189 if (width === null) {190 const first = rectangle.groups[0]191 if (first === undefined || first.sides.some(side => side.auto)) sourceError(line, 'With an unknown width, the first group must list the top row of squares with numbers, for example "(18 15)".')192 width = first.sides.reduce((sum, side) => sum + side.constant, 0)193 }194 const height = rectangle.height ?? Infinity195 let skyline: Segment[] = [{ x0: 0, x1: width, depth: 0, node: 0 }]196 const squares: Placed[] = []197 let problem: string | null = null198 for (const [index, expression] of sides.entries()) {199 const at = lowestSegment(skyline)200 const segment = skyline[at]201 if (segment === undefined || segment.depth >= height) {202 problem = `square ${index + 1} (${expression.text}) has nowhere to go; the rectangle is already full`203 break204 }205 const room = segment.x1 - segment.x0206 const side = expression.auto ? Math.min(room, height - segment.depth) : expression.constant207 if (side > room || segment.depth + side > height) {208 problem = `square ${index + 1} (side ${side}) does not fit at column ${segment.x0}, row ${segment.depth}; only ${room} × ${height === Infinity ? '∞' : height - segment.depth} is free there`209 break210 }211 squares.push({ x: segment.x0, y: segment.depth, side, label: String(side) })212 const replacement: Segment[] = [{ x0: segment.x0, x1: segment.x0 + side, depth: segment.depth + side, node: 0 }]213 if (segment.x0 + side < segment.x1) replacement.push({ x0: segment.x0 + side, x1: segment.x1, depth: segment.depth, node: 0 })214 skyline = mergeSkyline([...skyline.slice(0, at), ...replacement, ...skyline.slice(at + 1)])215 }216 const deepest = Math.max(...skyline.map(segment => segment.depth))217 const finalHeight = height === Infinity ? deepest : height218 if (problem === null && skyline.some(segment => segment.depth !== finalHeight)) {219 const gap = skyline[lowestSegment(skyline)]220 problem = `the squares do not fill the rectangle; the first gap is at column ${gap?.x0 ?? 0}, row ${gap?.depth ?? 0}`221 }222 return { width, height: finalHeight, squares, problem }223}224225// ---------------------------------------------------------------------------226// Stone sketches: sides are linear expressions and each group names the227// squares it hangs under. The geometry gives a linear system whose one-228// dimensional solution is the squaring.229230type Form = Map<string, Fraction>231232const CONSTANT = '$1'233const WIDTH = '$W'234const HEIGHT = '$H'235236function formOf(expression: SideExpression): Form {237 const form: Form = new Map()238 if (expression.constant !== 0) form.set(CONSTANT, fraction(BigInt(expression.constant)))239 for (const [symbol, coefficient] of Object.entries(expression.terms)) form.set(symbol, fraction(BigInt(coefficient)))240 return form241}242243function addForms(a: Form, b: Form, sign = 1n): Form {244 const result: Form = new Map(a)245 for (const [key, value] of b) {246 const next = add(result.get(key) ?? ZERO, mul(value, fraction(sign)))247 if (isZero(next)) result.delete(key)248 else result.set(key, next)249 }250 return result251}252253function solveSketch(rectangle: SquaringRectangleSource): Placement {254 const { groups, line } = rectangle255 const sides = groups.flatMap(group => group.sides)256 if (sides.length > MAXIMUM_ORDER) sourceError(line, `At most ${MAXIMUM_ORDER} squares are supported.`)257 const groupOf = groups.flatMap((group, index) => group.sides.map(() => index))258 const sideForms = sides.map(formOf)259 const xForms: Form[] = []260 const yForms: Form[] = []261 const equations: Form[] = []262 const usedAsBase = new Map<number, number>()263264 const resolve = (ref: string, group: SquareGroup, limit: number): number => {265 let matches: number[]266 if (ref.startsWith('#')) {267 const index = Number(ref.slice(1)) - 1268 matches = index >= 0 && index < sides.length ? [index] : []269 } else if (/^\d+$/.test(ref)) {270 matches = sides.flatMap((side, index) => Object.keys(side.terms).length === 0 && side.constant === Number(ref) ? [index] : [])271 } else {272 matches = sides.flatMap((side, index) => side.constant === 0 && Object.keys(side.terms).length === 1 && side.terms[ref] === 1 ? [index] : [])273 }274 if (matches.length === 0) sourceError(group.line, `"under ${ref}" does not name any square listed so far.`)275 if (matches.length > 1) sourceError(group.line, `"under ${ref}" is ambiguous; use #n to pick the n-th square.`)276 const index = matches[0] ?? 0277 if (index >= limit) sourceError(group.line, `"under ${ref}" refers to a square that is listed later; list the squares above first.`)278 return index279 }280281 let cursor = 0282 groups.forEach((group, groupIndex) => {283 const first = cursor284 let x: Form285 let y: Form286 if (groupIndex === 0) {287 x = new Map()288 y = new Map()289 } else {290 const refs = (group.under ?? []).map(ref => resolve(ref, group, first))291 for (const [position, ref] of refs.entries()) {292 const previousUse = usedAsBase.get(ref)293 if (previousUse !== undefined) sourceError(group.line, `Square ${sides[ref]?.text ?? ref} already has a group under it (line ${previousUse}).`)294 usedAsBase.set(ref, group.line)295 if (position > 0) {296 const left = refs[position - 1] ?? ref297 // Consecutive base squares share a bottom edge and touch side by side.298 equations.push(addForms(addForms(yForms[left] ?? new Map(), sideForms[left] ?? new Map()), addForms(yForms[ref] ?? new Map(), sideForms[ref] ?? new Map()), -1n))299 equations.push(addForms(addForms(xForms[left] ?? new Map(), sideForms[left] ?? new Map()), xForms[ref] ?? new Map(), -1n))300 }301 }302 const base = refs[0] ?? 0303 x = xForms[base] ?? new Map()304 y = addForms(yForms[base] ?? new Map(), sideForms[base] ?? new Map())305 // The group is exactly as wide as the run of base squares.306 let runWidth: Form = new Map()307 for (const ref of refs) runWidth = addForms(runWidth, sideForms[ref] ?? new Map())308 let groupWidth: Form = new Map()309 for (const side of group.sides) groupWidth = addForms(groupWidth, formOf(side))310 equations.push(addForms(groupWidth, runWidth, -1n))311 }312 for (const side of group.sides) {313 xForms.push(x)314 yForms.push(y)315 x = addForms(x, formOf(side))316 cursor += 1317 }318 })319320 // The top row spans the width; every square without anything under it rests on the bottom edge.321 const widthForm: Form = rectangle.width === null ? new Map([[WIDTH, fraction(1n)]]) : new Map([[CONSTANT, fraction(BigInt(rectangle.width))]])322 const heightForm: Form = rectangle.height === null ? new Map([[HEIGHT, fraction(1n)]]) : new Map([[CONSTANT, fraction(BigInt(rectangle.height))]])323 let topRow: Form = new Map()324 for (const side of groups[0]?.sides ?? []) topRow = addForms(topRow, formOf(side))325 equations.push(addForms(topRow, widthForm, -1n))326 sides.forEach((_, index) => {327 if (usedAsBase.has(index)) return328 equations.push(addForms(addForms(yForms[index] ?? new Map(), sideForms[index] ?? new Map()), heightForm, -1n))329 })330331 const unknowns = [...new Set([...equations.flatMap(form => [...form.keys()]), ...sideForms.flatMap(form => [...form.keys()])])].filter(key => key !== CONSTANT).sort()332 const column = new Map(unknowns.map((name, index) => [name, index]))333 const homogeneous = equations.every(form => !form.has(CONSTANT))334 const matrix = equations.map(form => {335 const row = unknowns.map(() => ZERO)336 for (const [key, value] of form) {337 const index = column.get(key)338 if (index !== undefined) row[index] = value339 }340 row.push(mul(form.get(CONSTANT) ?? ZERO, fraction(-1n)))341 return row342 })343 const pivots = reduce(matrix, unknowns.length)344 const free = unknowns.filter((_, index) => !pivots.includes(index))345 const inconsistent = matrix.some(row => row.slice(0, unknowns.length).every(isZero) && !isZero(row[unknowns.length] ?? ZERO))346 if (inconsistent) sourceError(line, 'The sketch cannot close: its equations contradict each other. Check the "under" clauses and any given numbers.')347348 const values = new Map<string, Fraction>()349 if (homogeneous) {350 if (free.length !== 1) {351 sourceError(line, free.length === 0352 ? 'The sketch only closes when every side is zero. Check the "under" clauses.'353 : `The sketch has ${free.length} free lengths (${free.join(', ')}); give a number for ${free.length - 1} of them or add a group that ties them together.`)354 }355 const freeName = free[0] ?? ''356 values.set(freeName, fraction(1n))357 pivots.forEach((columnIndex, rowIndex) => {358 const row = matrix[rowIndex] as Fraction[]359 const freeIndex = column.get(freeName) ?? 0360 values.set(unknowns[columnIndex] ?? '', mul(row[freeIndex] ?? ZERO, fraction(-1n)))361 })362 } else {363 if (free.length > 0) sourceError(line, `The sketch has ${free.length} free ${free.length === 1 ? 'length' : 'lengths'} (${free.join(', ')}); give a number for ${free.length === 1 ? 'it' : 'all but one'} or add a group that ties them together.`)364 pivots.forEach((columnIndex, rowIndex) => {365 values.set(unknowns[columnIndex] ?? '', (matrix[rowIndex] as Fraction[])[unknowns.length] ?? ZERO)366 })367 }368369 const evaluate = (form: Form): Fraction => {370 let total = form.get(CONSTANT) ?? ZERO371 for (const [key, value] of form) {372 if (key === CONSTANT) continue373 total = add(total, mul(value, values.get(key) ?? ZERO))374 }375 return total376 }377378 let width = evaluate(widthForm)379 let height = evaluate(heightForm)380 let sideValues = sideForms.map(evaluate)381 let xValues = xForms.map(evaluate)382 let yValues = yForms.map(evaluate)383 if (homogeneous) {384 // Scale the one-dimensional solution to the smallest positive integers.385 const scaled = integerScale([width, height, ...sideValues, ...xValues, ...yValues])386 const sign = (scaled[0] ?? 0n) < 0n ? -1n : 1n387 const [w = 0n, h = 0n, ...rest] = scaled.map(value => value * sign)388 width = fraction(w)389 height = fraction(h)390 sideValues = rest.slice(0, sides.length).map(value => fraction(value))391 xValues = rest.slice(sides.length, sides.length * 2).map(value => fraction(value))392 yValues = rest.slice(sides.length * 2).map(value => fraction(value))393 } else {394 const fractional = [width, height, ...sideValues].find(value => value.d !== 1n)395 if (fractional !== undefined) sourceError(line, `The given numbers force a side of ${fractional.n}/${fractional.d}; adjust them so every side is a whole number.`)396 }397 const bad = sideValues.findIndex(value => value.n <= 0n)398 if (bad >= 0) sourceError(line, `The sketch closes only if square ${bad + 1} (${sides[bad]?.text ?? ''}) has side ${sideValues[bad]?.n ?? 0n}; check the "under" clauses.`)399400 const squares: Placed[] = sides.map((side, index) => ({401 x: toSafeNumber(xValues[index]?.n ?? 0n, line),402 y: toSafeNumber(yValues[index]?.n ?? 0n, line),403 side: toSafeNumber(sideValues[index]?.n ?? 0n, line),404 label: Object.keys(side.terms).length === 0 ? String(sideValues[index]?.n ?? 0n) : `${side.text}=${sideValues[index]?.n ?? 0n}`,405 }))406 const widthNumber = toSafeNumber(width.n, line)407 const heightNumber = toSafeNumber(height.n, line)408 return { width: widthNumber, height: heightNumber, squares, problem: tilingProblem(squares, widthNumber, heightNumber) }409}410411function tilingProblem(squares: Placed[], width: number, height: number): string | null {412 for (const [index, square] of squares.entries()) {413 if (square.x < 0 || square.y < 0 || square.x + square.side > width || square.y + square.side > height) {414 return `square ${index + 1} (${square.label}) sticks out of the ${width} × ${height} rectangle`415 }416 for (const [otherIndex, other] of squares.entries()) {417 if (otherIndex <= index) continue418 if (square.x < other.x + other.side && other.x < square.x + square.side && square.y < other.y + other.side && other.y < square.y + square.side) {419 return `squares ${index + 1} (${square.label}) and ${otherIndex + 1} (${other.label}) overlap`420 }421 }422 }423 const area = squares.reduce((sum, square) => sum + square.side * square.side, 0)424 if (area !== width * height) return `the squares cover ${area} of the ${width * height} area; the sketch leaves a gap`425 return null426}427428// ---------------------------------------------------------------------------429// Smith diagram from geometry: every maximal horizontal segment is a node.430431function nodesFromGeometry(squares: Placed[], width: number, height: number): { nodes: SquaringNode[]; topOf: number[]; bottomOf: number[] } {432 const intervals = new Map<number, Array<[number, number]>>()433 const addInterval = (y: number, x0: number, x1: number): void => {434 const list = intervals.get(y) ?? []435 list.push([x0, x1])436 intervals.set(y, list)437 }438 addInterval(0, 0, width)439 addInterval(height, 0, width)440 for (const square of squares) {441 addInterval(square.y, square.x, square.x + square.side)442 addInterval(square.y + square.side, square.x, square.x + square.side)443 }444 const nodes: SquaringNode[] = []445 for (const y of [...intervals.keys()].sort((a, b) => a - b)) {446 const list = (intervals.get(y) ?? []).sort((a, b) => a[0] - b[0])447 let current: [number, number] | null = null448 const flush = (): void => {449 if (current === null) return450 nodes.push({ id: '', index: nodes.length, y, x0: current[0], x1: current[1], voltage: height - y })451 current = null452 }453 for (const [x0, x1] of list) {454 if (current !== null && x0 <= current[1]) current[1] = Math.max(current[1], x1)455 else {456 flush()457 current = [x0, x1]458 }459 }460 flush()461 }462 nodes.forEach((node, index) => {463 node.id = index === 0 ? 'top' : index === nodes.length - 1 ? 'bottom' : `n${index}`464 })465 const find = (y: number, x: number): number => {466 const node = nodes.find(candidate => candidate.y === y && candidate.x0 <= x && x < candidate.x1)467 if (node === undefined) throw new RenderError(422, 'invalid_source', `No horizontal segment contains column ${x} at row ${y}.`)468 return node.index469 }470 return {471 nodes,472 topOf: squares.map(square => find(square.y, square.x)),473 bottomOf: squares.map(square => find(square.y + square.side, square.x)),474 }475}476477// ---------------------------------------------------------------------------478// Networks: solve Kirchhoff and Ohm exactly, then arrange the squares.479480interface SolvedNetwork {481 voltages: number[]482 currents: number[]483}484485interface Battery {486 positive: string487 negative: string488}489490function solveNetwork(nodes: string[], wires: SquaringWire[], battery: Battery, line: number): SolvedNetwork {491 const indexOf = new Map(nodes.map((id, index) => [id, index]))492 const positiveIndex = indexOf.get(battery.positive) ?? 0493 const negativeIndex = indexOf.get(battery.negative) ?? 0494 const interior = nodes.map((_, index) => index).filter(index => index !== positiveIndex && index !== negativeIndex)495 const column = new Map(interior.map((node, position) => [node, position]))496 const size = interior.length497498 const matrix: Fraction[][] = interior.map(() => [...interior.map(() => ZERO), ZERO])499 for (const wire of wires) {500 const a = indexOf.get(wire.from) ?? 0501 const b = indexOf.get(wire.to) ?? 0502 for (const [self, other] of [[a, b], [b, a]] as const) {503 const row = column.get(self)504 if (row === undefined) continue505 const rowValues = matrix[row] as Fraction[]506 rowValues[row] = add(rowValues[row] ?? ZERO, fraction(1n))507 const otherColumn = column.get(other)508 if (otherColumn !== undefined) rowValues[otherColumn] = sub(rowValues[otherColumn] ?? ZERO, fraction(1n))509 else if (other === positiveIndex) rowValues[size] = add(rowValues[size] ?? ZERO, fraction(1n))510 }511 }512 const pivots = reduce(matrix, size)513 if (pivots.length !== size) sourceError(line, 'The network is not connected: every node must have a wire path to both battery nodes.')514515 const solution: Fraction[] = nodes.map(() => ZERO)516 solution[positiveIndex] = fraction(1n)517 interior.forEach((node, position) => {518 solution[node] = (matrix[position] as Fraction[])[size] ?? ZERO519 })520 const integral = integerScale(solution)521 const currentValues = wires.map(wire => (integral[indexOf.get(wire.from) ?? 0] ?? 0n) - (integral[indexOf.get(wire.to) ?? 0] ?? 0n))522 if (currentValues.every(value => value === 0n)) sourceError(line, 'No current flows through the network.')523 return { voltages: integral.map(value => toSafeNumber(value, line)), currents: currentValues.map(value => toSafeNumber(value, line)) }524}525526interface OrientedWire {527 index: number528 from: number529 to: number530 side: number531}532533function distinctPermutations<T>(items: T[], key: (item: T) => string): T[][] {534 const sorted = [...items].sort((a, b) => key(a).localeCompare(key(b)))535 const results: T[][] = []536 const used = sorted.map(() => false)537 const current: T[] = []538 const walk = (): void => {539 if (current.length === sorted.length) {540 results.push([...current])541 return542 }543 let previous: string | null = null544 sorted.forEach((item, index) => {545 if (used[index]) return546 const itemKey = key(item)547 if (itemKey === previous) return548 previous = itemKey549 used[index] = true550 current.push(item)551 walk()552 current.pop()553 used[index] = false554 })555 }556 walk()557 return results558}559560interface Arranged {561 width: number562 height: number563 squares: SquaringSquare[]564 nodes: SquaringNode[]565 positive: number566 negative: number567}568569// Rebuild the dissection from the circuit: fill the rectangle top-down, and at570// every horizontal segment try each left-to-right order of the squares that571// hang from it. Polyhedral networks admit one arrangement up to mirroring.572function arrangeNetwork(nodes: string[], wires: SquaringWire[], battery: Battery, solved: SolvedNetwork, line: number): Arranged {573 const indexOf = new Map(nodes.map((id, index) => [id, index]))574 const positiveIndex = indexOf.get(battery.positive) ?? 0575 const negativeIndex = indexOf.get(battery.negative) ?? 0576 const oriented: OrientedWire[] = wires.map((wire, index) => {577 const a = indexOf.get(wire.from) ?? 0578 const b = indexOf.get(wire.to) ?? 0579 const current = solved.currents[index] ?? 0580 if (current === 0) {581 sourceError(wire.line, `Wire ${wire.from} - ${wire.to} carries no current because both nodes settle at the same voltage, so it cannot become a square. Choose a different battery.`)582 }583 return current > 0 ? { index, from: a, to: b, side: current } : { index, from: b, to: a, side: -current }584 })585 const outgoing = nodes.map<OrientedWire[]>(() => [])586 const inflow = nodes.map(() => 0)587 for (const wire of oriented) {588 outgoing[wire.from]?.push(wire)589 inflow[wire.to] = (inflow[wire.to] ?? 0) + wire.side590 }591 const width = outgoing[positiveIndex]?.reduce((sum, wire) => sum + wire.side, 0) ?? 0592 const height = solved.voltages[positiveIndex] ?? 0593 const placement = new Map<number, { x: number; y: number }>()594 let budget = SEARCH_BUDGET595596 const search = (skyline: Segment[]): boolean => {597 budget -= 1598 if (budget < 0) sourceError(line, 'The network has too many possible arrangements to explore. Choose a battery on the outer face of a polyhedral network.')599 const at = lowestSegment(skyline)600 const segment = skyline[at]601 if (segment === undefined) return false602 if (segment.depth >= height) return true603 const node = segment.node604 if (node === negativeIndex) return false605 let start = at606 while (start > 0 && skyline[start - 1]?.depth === segment.depth && skyline[start - 1]?.node === node) start -= 1607 let end = at608 while (end + 1 < skyline.length && skyline[end + 1]?.depth === segment.depth && skyline[end + 1]?.node === node) end += 1609 const x0 = skyline[start]?.x0 ?? 0610 const x1 = skyline[end]?.x1 ?? 0611 const hanging = outgoing[node] ?? []612 const outflow = hanging.reduce((sum, wire) => sum + wire.side, 0)613 if (x1 - x0 !== outflow) return false614 for (const order of distinctPermutations(hanging, wire => `${wire.side}:${wire.to}`)) {615 const replacement: Segment[] = []616 let x = x0617 for (const wire of order) {618 placement.set(wire.index, { x, y: segment.depth })619 replacement.push({ x0: x, x1: x + wire.side, depth: segment.depth + wire.side, node: wire.to })620 x += wire.side621 }622 if (search(mergeSkyline([...skyline.slice(0, start), ...replacement, ...skyline.slice(end + 1)]))) return true623 for (const wire of order) placement.delete(wire.index)624 }625 return false626 }627628 if (!search([{ x0: 0, x1: width, depth: 0, node: positiveIndex }])) {629 sourceError(line, `The network cannot be arranged into a squared rectangle with the battery between ${battery.positive} and ${battery.negative}. Check that the wires form a planar network and try another battery.`)630 }631632 const squares: SquaringSquare[] = oriented.map(wire => {633 const at = placement.get(wire.index) ?? { x: 0, y: 0 }634 return { index: wire.index, x: at.x, y: at.y, side: wire.side, top: wire.from, bottom: wire.to, label: String(wire.side) }635 })636 const x0 = nodes.map(() => Infinity)637 for (const square of squares) x0[square.bottom] = Math.min(x0[square.bottom] ?? Infinity, square.x)638 x0[positiveIndex] = 0639 const modelNodes: SquaringNode[] = nodes.map((id, index) => {640 const voltage = solved.voltages[index] ?? 0641 const left = x0[index] === Infinity ? 0 : (x0[index] ?? 0)642 const span = index === positiveIndex ? width : inflow[index] ?? 0643 return { id, index, y: height - voltage, x0: left, x1: left + span, voltage }644 })645 return { width, height, squares, nodes: modelNodes, positive: positiveIndex, negative: negativeIndex }646}647648// ---------------------------------------------------------------------------649// Analysis: perfect (no repeated side) and simple (no compound block).650651function findBlocks(squares: SquaringSquare[], width: number, height: number): SquaringBlock[] {652 const xs = [...new Set(squares.flatMap(square => [square.x, square.x + square.side]))].sort((a, b) => a - b)653 const ys = [...new Set(squares.flatMap(square => [square.y, square.y + square.side]))].sort((a, b) => a - b)654 const blocks: SquaringBlock[] = []655 for (let left = 0; left < xs.length; left += 1) {656 const x0 = xs[left] ?? 0657 for (let right = left + 1; right < xs.length; right += 1) {658 const x1 = xs[right] ?? 0659 const overlapping = squares.filter(square => square.x < x1 && square.x + square.side > x0)660 const straddlers = overlapping.filter(square => square.x < x0 || square.x + square.side > x1)661 const inside = overlapping.filter(square => square.x >= x0 && square.x + square.side <= x1)662 const clean = ys.filter(y => !overlapping.some(square => square.y < y && square.y + square.side > y))663 for (const y0 of clean) {664 let limit = height665 for (const square of straddlers) {666 if (square.y + square.side > y0) limit = Math.min(limit, square.y)667 }668 for (const y1 of clean) {669 if (y1 <= y0) continue670 if (y1 > limit) break671 if (x0 === 0 && x1 === width && y0 === 0 && y1 === height) continue672 const count = inside.filter(square => square.y >= y0 && square.y + square.side <= y1).length673 if (count >= 2) blocks.push({ x: x0, y: y0, width: x1 - x0, height: y1 - y0, squares: count })674 }675 }676 }677 }678 const contains = (outer: SquaringBlock, inner: SquaringBlock): boolean =>679 outer !== inner && outer.x <= inner.x && outer.y <= inner.y && outer.x + outer.width >= inner.x + inner.width && outer.y + outer.height >= inner.y + inner.height680 return blocks.filter(block => !blocks.some(other => contains(other, block)))681}682683interface AnalysisInput {684 form: 'rectangle' | 'network'685 width: number686 height: number687 squares: SquaringSquare[]688 nodes: SquaringNode[]689 positive: number690 negative: number691 problem: string | null692 search?: BatteryCandidate[] | null693 searchIndex?: number694}695696function analyse(input: AnalysisInput): SquaringModel {697 const complete = input.problem === null698 const counts = new Map<number, number>()699 for (const square of input.squares) counts.set(square.side, (counts.get(square.side) ?? 0) + 1)700 const repeatedSides = [...counts.entries()].filter(([, count]) => count > 1).map(([side]) => side).sort((a, b) => a - b)701 const blocks = complete ? findBlocks(input.squares, input.width, input.height) : []702 return {703 form: input.form,704 width: input.width,705 height: input.height,706 squares: input.squares,707 nodes: input.nodes,708 positive: input.positive,709 negative: input.negative,710 order: input.squares.length,711 complete,712 problem: input.problem,713 perfect: repeatedSides.length === 0,714 repeatedSides,715 simple: complete && blocks.length === 0,716 blocks,717 search: input.search ?? null,718 searchIndex: input.searchIndex ?? -1,719 }720}721722function fromPlacement(placement: Placement): SquaringModel {723 const { width, height, problem } = placement724 if (problem !== null) {725 const squares = placement.squares.map((square, index) => ({ index, ...square, top: -1, bottom: -1 }))726 return analyse({ form: 'rectangle', width, height, squares, nodes: [], positive: -1, negative: -1, problem })727 }728 const { nodes, topOf, bottomOf } = nodesFromGeometry(placement.squares, width, height)729 const squares = placement.squares.map((square, index) => ({ index, ...square, top: topOf[index] ?? 0, bottom: bottomOf[index] ?? 0 }))730 return analyse({ form: 'rectangle', width, height, squares, nodes, positive: 0, negative: nodes.length - 1, problem: null })731}732733function solveBattery(network: SquaringNetworkSource, wires: SquaringWire[], battery: Battery): SquaringModel {734 const solved = solveNetwork(network.nodes, wires, battery, network.line)735 const arranged = arrangeNetwork(network.nodes, wires, battery, solved, network.line)736 return analyse({ form: 'network', ...arranged, problem: null })737}738739function rank(model: SquaringModel): number {740 return (model.simple ? 2 : 0) + (model.perfect ? 1 : 0)741}742743function searchBatteries(network: SquaringNetworkSource): SquaringModel {744 if (network.wires.length > MAXIMUM_BATTERY_SEARCH) sourceError(network.line, `"battery any" tries every wire, so the network can have at most ${MAXIMUM_BATTERY_SEARCH} wires.`)745 const candidates: BatteryCandidate[] = []746 let best: SquaringModel | null = null747 let bestIndex = -1748 network.wires.forEach((wire, index) => {749 const rest = network.wires.filter((_, other) => other !== index)750 const battery = { positive: wire.from, negative: wire.to }751 try {752 const model = solveBattery(network, rest, battery)753 candidates.push({ ...battery, order: model.order, width: model.width, height: model.height, simple: model.simple, perfect: model.perfect, error: null })754 const better = best === null755 || rank(model) > rank(best)756 || (rank(model) === rank(best) && model.width * model.height < best.width * best.height)757 if (better) {758 best = model759 bestIndex = candidates.length - 1760 }761 } catch (error) {762 const message = error instanceof Error ? error.message.replace(/^Line \d+: /, '') : String(error)763 candidates.push({ ...battery, order: rest.length, width: 0, height: 0, simple: false, perfect: false, error: message })764 }765 })766 if (best === null) {767 sourceError(network.line, `No wire works as the battery. ${candidates[0]?.error ?? ''}`.trim())768 }769 const chosen: SquaringModel = best770 return { ...chosen, search: candidates, searchIndex: bestIndex }771}772773export function buildSquaring(document: SquaringDocument): SquaringModel {774 if (document.rectangle !== null) {775 const rectangle = document.rectangle776 return fromPlacement(rectangle.symbolic ? solveSketch(rectangle) : placeBouwkamp(rectangle))777 }778 if (document.network === null) throw new RenderError(422, 'invalid_source', 'The squaring source is empty.')779 const network = document.network780 if (network.wires.length > MAXIMUM_ORDER) sourceError(network.line, `At most ${MAXIMUM_ORDER} wires are supported.`)781 if (network.searchBattery) return searchBatteries(network)782 return solveBattery(network, network.wires, { positive: network.positive ?? '', negative: network.negative ?? '' })783}