busy-beaver-compiler.ts

const stateLabels = ["A", "B", "C", "D", "E", "F", "G"] as const;
type StateLabel = typeof stateLabels[number];

type Direction = "left" | "right";

interface Edge {
    write: 0 | 1;
    move: Direction;
    next: StateLabel;
}

interface State {
    0: Edge;
    1: Edge;
}

const parseEdge = (stateEdge: string): Edge => {
    const [write, move, next] = stateEdge.split('');

    return {
        write: write === "0" ? 0 : 1,
        move: move === "L" ? "left" : "right",
        next: next as StateLabel,
    };
}

const compile = (input: string): ((tapeSize: number) => void) => {
    const tokens = input.split(" ");

    const states: Partial<Record<StateLabel, State>> = {};

    for (let stateNumber = 0; stateNumber < tokens.length / 2; stateNumber++) {
        const label = stateLabels[stateNumber];

        states[label] = {
            0: parseEdge(tokens[stateNumber * 2]),
            1: parseEdge(tokens[stateNumber * 2 + 1]),
        }
    }

    const code = `
        (tapeSize) => {
            const tape = new Int8Array(tapeSize);
            let tapeHead = Math.floor(tapeSize / 2);
            let state = "A";
            let steps = 0;

            while (true) {
                if (tapeHead < 0) {
                    console.error("Tape head pointing below 0");
                    console.log({ steps });
                    return;
                }

                switch (state) {
                    ${
                    Object.entries(states).map(([label, edges]) => `
                    case "${label}":
                        if (tape[tapeHead] === 0) {
                            tape[tapeHead] = ${edges[0].write};
                            tapeHead += ${edges[0].move === "left" ? -1 : 1};
                            state = "${edges[0].next}";
                        } else {
                            tape[tapeHead] = ${edges[1].write};
                            tapeHead += ${edges[1].move === "left" ? -1 : 1};
                            state = "${edges[1].next}";
                        }
                        break;
                    `).join('')
                    }
                    case "H":
                        console.log("Halt!");
                        console.log({ steps });
                        return;
                }

                steps++;
            }
        }
    `;

    return eval(code);
}

const time = (func: () => void): void => {
    const start = new Date().getTime();
    func();
    const end = new Date().getTime();

    console.log(`Run time: ${end - start}`);
}

const bb42 = compile("1RB 1LB 1LA 0LC 1RH 1LD 1RD 0RA");
const bb52 = compile("1RB 1LC 1RC 1RB 1RD 0LE 1LA 1LD 1RH 0LA");

time(() => bb52(1000000));

https://en.wikipedia.org/wiki/Busy_beaver