1/**2 * Memory-bounded breadth-first search over compact, settled solver states.3 *4 * `codec` owns the level-specific state representation. The search queue never5 * retains decoded snapshots or partial paths; it keeps one compact blob and a6 * parent link per visited state. The transition callback remains responsible7 * for authoritative engine semantics.8 */910function asActions(actions) {11 if (!Array.isArray(actions) || actions.length === 0)12 throw new TypeError('search actions must be a non-empty array');13 return actions.slice();14}1516function isRecord(value) {17 return value !== null && typeof value === 'object';18}1920function reconstructPath(nodes, index) {21 const path = [];22 let cursor = index;23 while (cursor >= 0) {24 const node = nodes[cursor];25 if (node.parent >= 0) path.push(node.action);26 cursor = node.parent;27 }28 path.reverse();29 return path;30}3132function resultFor(status, fields = {}) {33 return Object.freeze({ status, path: [], attempts: 0, expanded: 0, visited: 0, ...fields });34}3536// A numeric hash keeps the visited index small when a level has millions of37// states. Equality always compares the full codec bytes, so hash collisions38// cannot merge different futures.39function hashBytes(bytes) {40 let hash = 2166136261;41 for (const byte of bytes) hash = Math.imul(hash ^ byte, 16777619);42 return hash >>> 0;43}4445function sameBytes(left, right) {46 if (left.length !== right.length) return false;47 for (let index = 0; index < left.length; index += 1) if (left[index] !== right[index]) return false;48 return true;49}5051/**52 * Search a level's settled state graph in breadth-first order.53 *54 * @param {object} options55 * @param {object} options.initial Initial settled snapshot. A winning initial56 * state is returned immediately without passing through the frontier codec.57 * @param {{ encode: Function, decode: Function, key: Function }} options.codec58 * @param {Array<unknown>} options.actions Actions attempted in this order for59 * every frontier state.60 * @param {(snapshot: object, action: unknown) => {accepted?: boolean, state?: object, meta?: object}} options.transition61 * @param {number} [options.cap=100000] Maximum number of attempted actions.62 * @param {number} [options.maxVisited=Infinity] Maximum number of compact63 * frontier states retained, including the initial state.64 * @param {(context: {snapshot: object, action: unknown, result: object}) => boolean} [options.filter]65 * Optional post-transition filter. Rejected transitions and filtered66 * transitions both count toward `attempts`.67 * @param {(snapshot: object, result?: object) => boolean} [options.isWin]68 * Terminal predicate. Defaults to `snapshot.won === true`.69 * @param {(bytes: Uint8Array) => number} [options.hash]70 * Numeric bucket hash; full bytes are still compared for identity. This is71 * injectable so collision behavior can be tested deterministically.72 * @returns {{status: 'solved'|'exhausted'|'limit', path: unknown[], attempts: number,73 * expanded: number, visited: number, state?: object, meta?: object}}74 */75export function searchStates({76 initial,77 codec,78 actions,79 transition,80 cap = 100_000,81 maxVisited = Infinity,82 filter,83 isWin = snapshot => snapshot?.won === true,84 hash = hashBytes,85} = {}) {86 if (!isRecord(initial)) throw new TypeError('search initial snapshot is required');87 if (!codec || typeof codec.encode !== 'function' || typeof codec.decode !== 'function' || typeof codec.key !== 'function') {88 throw new TypeError('search codec must provide encode, decode, and key');89 }90 const moveSet = asActions(actions);91 if (typeof transition !== 'function') throw new TypeError('search transition must be a function');92 if (!Number.isSafeInteger(cap) || cap < 0) throw new RangeError('search cap must be a non-negative safe integer');93 if (maxVisited !== Infinity && (!Number.isSafeInteger(maxVisited) || maxVisited < 0)) throw new RangeError('search maxVisited must be a non-negative safe integer');94 const allowTransition = filter || (() => true);95 if (typeof allowTransition !== 'function' || typeof isWin !== 'function' || typeof hash !== 'function') throw new TypeError('search filter, isWin, and hash must be functions');9697 if (isWin(initial)) return resultFor('solved', { path: [], attempts: 0, expanded: 0, visited: 0, state: initial });98 if (maxVisited === 0) return resultFor('limit', { reason: 'visited' });99100 const initialBlob = codec.encode(initial);101 const nodes = [{ blob: initialBlob, parent: -1, action: undefined }];102 // Most buckets contain one node index. Allocate a collision array only for103 // hashes shared by different payloads, avoiding a second long string per104 // frontier state.105 const seen = new Map([[hash(initialBlob), 0]]);106 function remember(blob) {107 const bucketHash = hash(blob);108 const bucket = seen.get(bucketHash);109 if (bucket !== undefined) {110 const indexes = Array.isArray(bucket) ? bucket : [bucket];111 if (indexes.some(index => sameBytes(nodes[index].blob, blob))) return false;112 }113 if (nodes.length >= maxVisited) return null;114 const index = nodes.length;115 if (bucket === undefined) seen.set(bucketHash, index);116 else if (Array.isArray(bucket)) bucket.push(index);117 else seen.set(bucketHash, [bucket, index]);118 return true;119 }120 let head = 0;121 let attempts = 0;122 let expanded = 0;123124 while (head < nodes.length) {125 const nodeIndex = head++;126 const node = nodes[nodeIndex];127 const snapshot = codec.decode(node.blob);128 expanded += 1;129130 for (const action of moveSet) {131 if (attempts >= cap) return resultFor('limit', { reason: 'attempts', attempts, expanded, visited: nodes.length });132 attempts += 1;133 const result = transition(snapshot, action);134 if (!isRecord(result)) throw new TypeError('search transition must return an object');135 if (!result.accepted) continue;136 if (!isRecord(result.state)) throw new TypeError('accepted search transition must return a state');137 if (!allowTransition({ snapshot, action, result })) continue;138139 if (isWin(result.state, result)) {140 return resultFor('solved', {141 path: [...reconstructPath(nodes, nodeIndex), action],142 attempts,143 expanded,144 visited: nodes.length,145 state: result.state,146 ...(result.meta === undefined ? {} : { meta: result.meta }),147 });148 }149150 const blob = codec.encode(result.state);151 const remembered = remember(blob);152 if (remembered === null) return resultFor('limit', { reason: 'visited', attempts, expanded, visited: nodes.length });153 if (!remembered) continue;154 nodes.push({ blob, parent: nodeIndex, action });155 }156 }157158 return resultFor('exhausted', { attempts, expanded, visited: nodes.length });159}160161export const search = searchStates;162export default searchStates;