Leetcode #67

leetcode_00067.ts

// artisanal, handcrafted code written by a human, not by a statistical model ;)
// solution to leetcode #67
// this approach is very flexible and can be adapted to solve any leetcode problem

"use strict"; // this not needed in typescript but im leaving it in

const EMPTY = " " as const;
const START = "<" as const;

type Cell = typeof EMPTY | typeof START | string;
type Direction = "L" | "R";

class Tape {
    private symbols: Map<number, Cell>;
    private position: number;

    constructor(startState: string | undefined = undefined) {
        this.symbols = new Map();
        this.position = 0;
        this.symbols.set(-1, START);

        if (startState !== undefined) {
            for (let c of startState) {
                this.write(c);
                this.move("R");
            }
            this.position = 0;
        }
    }

    move(direction: Direction) {
        switch (direction) {
            case "L":
                if (this.position === -1)
                    throw "attempt to move tape leftwards from beginning";
                this.position -= 1;
                break;
            case "R":
                this.position += 1;
                break;
            default:
                break;
        }
    }

    read(): Cell {
        return this.symbols.get(this.position) ?? EMPTY;
    }

    write(cell: Cell) {
        if (this.position === -1 && cell !== START)
            throw "attempt to write to beginning of tape";

        if (this.position !== -1 && cell === START)
            throw "attempt to write start cell elsewhere";

        if (cell === EMPTY) {
            this.symbols.delete(this.position);
            return;
        }

        this.symbols.set(this.position, cell);
    }

    contents() {
        const sz = Math.max(...this.symbols.keys()) + 1;
        return Array.from({ length: sz }, (_, i) => this.symbols.get(i) ?? EMPTY).join("");
    }

    print() {
        const cursor = " ".repeat(1 + this.position) + "^";
        console.log(`${START}${this.contents()}\n${cursor}`);
    }

}

/** a null return means the state is final */
type State = (cell: Cell) => { state: State, cell: Cell, direction: Direction } | null;

function lambda(source: Map<string, Map<Cell, { cell: Cell, state: string, direction: Direction }> | null>, start: string): State {
    if (!source.has(start)) {
        throw "every turing machine must have a start state";
    }

    const stateMap: Map<string, State> = new Map();
    const errorState = (stateName: string) => (cell: Cell) => { throw `error state: no transition at state ${stateName} from ${cell}`; };

    for (let [stateName, mappings] of source.entries()) {
        if (mappings == null) {
            stateMap.set(stateName, (_) => null);
        } else {
            stateMap.set(stateName, (cell) => {
                const target = mappings.get(cell);

                // if the binding doesn't exist in the mapping it should return the errorState
                if (target === undefined) {
                    return errorState(stateName)(cell);
                }

                return {
                    cell: target.cell,
                    direction: target.direction,
                    state: stateMap.get(target.state) ?? errorState(stateName)
                };
            });
        }
    }

    return stateMap.get(start)!;
}

function run(start: string, initialState: State) {
    let tape = new Tape(start);
    let currentState: State = initialState;
    console.log("START:");
    tape.print();

    while (true) {
        let result = currentState(tape.read());
        if (result === null) {
            break;
        }

        let { state, direction, cell } = result;
        tape.write(cell);
        tape.move(direction);
        currentState = state;
    }
    console.log("END:");
    tape.print();
    return tape.contents();
}

function splat(o: Object) {
    return new Map(Object.entries(o));
}

function mt(o: { [from: string]: Map<string, Transition> | null }, start: string) {
    return lambda(splat(o), start);
}

function s(o: { [cellFrom: string]: Transition }): Map<string, Transition> {
    return splat(o);
}

type Transition = { cell: Cell, direction: Direction, state: string };

function t(cell: Cell, direction: Direction, state: string): Transition {
    return { cell, direction, state };
}

declare interface String {
    splitOnce(delim: string): [string, string] | null;
}

String.prototype.splitOnce = function (delim: string) {
    var i = this.indexOf(delim);
    if (i === -1) return null;
    return [this.slice(0, i), this.slice(i + delim.length)];
}

type AstNode = TransitionAstNode | FinalTransitionAstNode;
type TransitionAstNode = {
    type: "transition",

    from: string,
    to: string,
    cellFrom: Cell,
    cellTo: Cell,
    direction: Direction
};
type FinalTransitionAstNode = {
    type: "finalTransition",

    from: string
}
type TuringMachineSpec = AstNode[]

function parseAst(src: string): TuringMachineSpec {
    const lines = src.split("\n").map(s => s.trim()).filter(s => s);
    const rules = lines.map(l => {
        let [tok, rest] = l.splitOnce("->")!;
        let from = tok.trim();
        if (rest.trim() === "*") {
            return { type: "finalTransition", from } as FinalTransitionAstNode;
        }
        [tok, rest] = rest.trim().splitOnce(":")!;
        let to = tok.trim();
        rest = rest.trim();
        let triplet = rest.substring(1, rest.length - 1);
        let [cellFrom, cellTo, direction] = triplet.split(",").map(s => s.trim());
        let map = (c: string) => c === "_" ? EMPTY : c === "<" ? START : c;
        cellFrom = map(cellFrom);
        cellTo = map(cellTo);
        return { type: "transition", from, to, cellFrom, cellTo, direction: direction as Direction } as TransitionAstNode;
    });
    return rules;
}

function compile(ast: TuringMachineSpec, start: string) {
    console.log(`inputs=[${start}] outputs=[${findOutputs(ast)}]`)
    const grouped = Object.fromEntries(Object.entries(Object.groupBy(
        ast,
        ({ from }) => from
    )).map(
        ([state, rules]) => {
            if (rules!.find(x => x.type === "finalTransition")) {
                // this is a final state
                return [state, null];
            }

            const pivoted = Object.fromEntries(Object.entries(Object.groupBy(rules as TransitionAstNode[], ({ cellFrom }) => cellFrom)).map(
                ([cellFrom, rules]) => {
                    return [cellFrom, rules!.map(rule => t(rule.cellTo as string, rule.direction as Direction, rule.to)).at(0)!];
                }
            ));

            return [state, s(pivoted)];
        }
    ));
    return mt(grouped, start);
}

function findOutputs(m: TuringMachineSpec) {
    return m.filter(spec => spec.type == "finalTransition").map(spec => spec.from);
}

function parseAndCompile(src: string, start: string = 'S0') {
    const ast = parseAst(src);
    return compile(ast, start);
}

type CompositionAst = StartCompositionAst | ConnectionCompositionAst | EndCompositionAst;
type CompositionReferenceAst = { scope: string, state: string }
type StartCompositionAst = { type: "start", to: CompositionReferenceAst }
type ConnectionCompositionAst = { type: "connection", from: CompositionReferenceAst, to: CompositionReferenceAst }
type EndCompositionAst = { type: "end", to: CompositionReferenceAst }

function compose(source: string, references: { [key: string]: TuringMachineSpec }): { start: string, ast: TuringMachineSpec } {
    const lines = source.split('\n').map(x => x.trim()).filter(x => x);
    const parsed: CompositionAst[] = lines.map(l => {
        const [lhs, rhs] = l.splitOnce("->")!.map(x => x.trim());
        if (lhs === "*") {
            const [scope, state] = rhs.splitOnce(".")!;
            return {
                type: "start",
                to: { scope, state }
            }
        } else if (rhs === "*") {
            const [scope, state] = lhs.splitOnce(".")!;
            return {
                type: "end",
                to: { scope, state }
            }
        } else {
            const [lscope, lstate] = lhs.splitOnce(".")!;
            const [rscope, rstate] = rhs.splitOnce(".")!;
            return {
                type: "connection",
                from: { scope: lscope, state: lstate },
                to: { scope: rscope, state: rstate }
            }
        }
    });

    // separate machines into different namespaces
    let pfx = 0;
    const ctx = Object.fromEntries(Object.entries(references).map(([key, machine]) => [key, {
        machine: machine.map(m => {
            if (m.type === "transition")
                return { ...m, from: `${pfx}${m.from}`, to: `${pfx}${m.to}` } as TransitionAstNode;
            if (m.type == "finalTransition")
                return { ...m, from: `${pfx}${m.from}` } as FinalTransitionAstNode;
            throw "idk";
        }) as TuringMachineSpec, pfx: pfx++
    }]));

    // join all rules, merging nodes
    const equivalences = new Map(parsed.filter(p => p.type === "connection").map(p => [`${ctx[p.from.scope].pfx}${p.from.state}`, `${ctx[p.to.scope].pfx}${p.to.state}`]));
    // iteratively merge equivalences until there's no more equivalences to be merged
    // ie if rules A => B and B => C exist, end should be A => C and B => C
    // do it in an ugly way
    {
        let merged = true;
        while (merged) {
            merged = false;
            let entries = [...equivalences.entries()];
            for (let i = 0; i < entries.length; i++) {
                let [iFrom, iTo] = entries[i];
                // try to apply the mapping to other rules
                for (let j = 0; j < entries.length; j++) {
                    if (i == j) continue;
                    let [jFrom, jTo] = entries[j];
                    if (iTo !== jFrom) continue;
                    merged = true;
                    equivalences.set(iFrom, jTo);
                }
            }
        }
    }

    let everything = Object.values(ctx).map(c => c.machine).flat().map(m => {
        if (m.type === "transition")
            return { ...m, from: equivalences.get(m.from) ?? m.from, to: equivalences.get(m.to) ?? m.to } as TransitionAstNode;
        if (m.type === "finalTransition")
            return { ...m, from: equivalences.get(m.from) ?? m.from } as FinalTransitionAstNode;
        throw "idk";
    });

    // erase any end rule that's not in the source
    everything = everything.filter(r => r.type !== "finalTransition" || parsed.find(p => p.type === "end" && r.from === `${ctx[p.to.scope].pfx}${p.to.state}`));

    // find a start node
    const startRule = parsed.find(m => m.type === "start")!.to;
    let start = `${ctx[startRule.scope].pfx}${startRule.state}`;
    start = equivalences.get(start) ?? start;

    return { start, ast: everything };
}

function printMachine(machine: TuringMachineSpec): string {
    const n = (s: Cell) => s === EMPTY ? "_" : s;

    return machine.map(r => {
        if (r.type === "finalTransition")
            return `${r.from} -> *`;
        if (r.type === "transition")
            return `${r.from} -> ${r.to} : (${n(r.cellFrom)}, ${n(r.cellTo)}, ${r.direction})`;
        throw "idk";
    }).join("\n");
}

run("1010", parseAndCompile(`
    S0 -> S0 : (0, 1, R)
    S0 -> S0 : (1, 0, R)
    S0 -> S1 : (_, _, L)
    S1 -> S1 : (1, 1, L)
    S1 -> S1 : (0, 0, L)
    S1 -> Sf : (<, <, R)
    Sf -> *
`));


/**
    TrySub1Lhs:
    start from idx=0
    scans to +
    moves left trying to subtract 1
    if hit beginning, over
    otherwise, subtract and move to idx=0
 */

const trySub1Lhs = parseAst(`
    S0 -> S0 : (0, 0, R)
    S0 -> S0 : (1, 1, R)
    S0 -> S1 : (+, +, L)
    S1 -> S1 : (0, 0, L)
    S1 -> sub_fail : (<, <, R)
    S1 -> S2 : (1, 0, R)
    S2 -> S2 : (0, 1, R)
    S2 -> S3 : (+, +, L)
    S3 -> S3 : (0, 0, L)
    S3 -> S3 : (1, 1, L)
    S3 -> sub_ok : (<, <, R)
    sub_ok -> *
    sub_fail -> *
`);
const c_trySub1Lhs = compile(trySub1Lhs, "S0");

console.log("subber 1")
run("1+", c_trySub1Lhs)
console.log("subber 100")
run("100+", c_trySub1Lhs)
console.log("subber 1100")
run("1100+", c_trySub1Lhs)

/*
    incRhs: moves to the right of the + and adds 1 to the number
*/

const incRhs = parseAst(`
    pre -> pre : (0, 0, R)
    pre -> pre : (1, 1, R)
    pre -> S0 : (+, +, R)

    S0 -> S0 : (0, 0, R)
    S0 -> S0 : (1, 1, R)
    S0 -> soma : (_, _, L)
    soma -> retorno : (0, 1, L)
    soma -> vai um : (1, 0, L)
    retorno -> retorno : (0, 0, L)
    retorno -> retorno : (1, 1, L)
    retorno -> post : (+, +, L)
    vai um -> vai um : (1, 0, L)
    vai um -> retorno : (0, 1, L)
    vai um -> estouro : (+, +, R)
    estouro -> avanca : (0, 1, R)
    avanca -> avanca : (0, 0, R)
    avanca -> retorno : (_, 0, L)

    post -> post : (0, 0, L)
    post -> post : (1, 1, L)
    post -> saida : (<, <, R)

    saida -> *
`)
const c_incRhs = compile(incRhs, "pre");

console.log("incRhs 1")
run("+1", c_incRhs)
console.log("incRhs 100")
run("+101", c_incRhs)
console.log("incRhs 1100")
run("+1111", c_incRhs)

/*
    eraseLhs: replaces the number to the left of the + with empty space
*/
const eraseLhs = parseAst(`
    S0 -> S0 : (0, _, R)
    S0 -> S1 : (+, +, L)
    S1 -> S1 : (_, _, L)
    S1 -> Sf : (<, <, R)
    Sf -> *
`)
const c_eraseLhs = compile(eraseLhs, "S0");

console.log("eraseLhs 0")
run("0+", c_eraseLhs)
console.log("eraseLhs 00")
run("00+", c_eraseLhs)
console.log("eraseLhs 000")
run("000+", c_eraseLhs)

/* cutRhsPasteLhs: moves the right hand number to tape start and clears tape content after it */

const cutRhsPasteLhs = parseAst(`
    start -> start : (_, _, R)
    start -> start0 : (+, +, R)
    start0 -> start0 : (0, 0, R)
    start0 -> start0 : (1, 1, R)
    start0 -> back : (_, #, L)
    back -> back : (0, 0, L)
    back -> back : (1, 1, L)
    back -> back : (+, +, L)
    back -> back : (_, _, L)
    back -> S0 : (<, <, R)

    S0 -> S0 : (_, _, R)
    S0 -> S0 : (0, 0, R)
    S0 -> S0 : (1, 1, R)
    S0 -> S1 : (+, +, R)
    S1 -> S1 : (_, _, R)
    S1 -> Sone : (1, _, L)
    S1 -> Szero : (0, _, L)
    S1 -> Squit : (#, _, L)

    Squit -> Squit : (0, 0, L)
    Squit -> Squit : (1, 1, L)
    Squit -> Squit : (_, _, L)
    Squit -> Squit : (+, _, L)
    Squit -> quit : (<, <, R)
    quit -> *

    Sone -> Sone : (_, _, L)
    Sone -> Sone : (0, 0, L)
    Sone -> Sone : (1, 1, L)
    Sone -> Sone : (+, +, L)
    Sone -> Swone : (<, <, R)
    Swone -> Swone : (0, 0, R)
    Swone -> Swone : (1, 1, R)
    Swone -> back : (_, 1, R)
    Swone -> backPlus : (+, 1, R)

    Szero -> Szero : (_, _, L)
    Szero -> Szero : (0, 0, L)
    Szero -> Szero : (1, 1, L)
    Szero -> Szero : (+, +, L)
    Szero -> Swzero : (<, <, R)
    Swzero -> Swzero : (0, 0, R)
    Swzero -> Swzero : (1, 1, R)
    Swzero -> back : (_, 0, R)
    Swzero -> backPlus : (+, 0, R)

    backPlus -> back : (_, +, L)
`)
const c_cutRhsPasteLhs = compile(cutRhsPasteLhs, "start");

console.log("cutPaste ______+10111")
run("     +10111", c_cutRhsPasteLhs)
console.log("cutPaste _____+10111")
run("    +10111", c_cutRhsPasteLhs)
console.log("cutPaste _+10111")
run(" +10111", c_cutRhsPasteLhs)

// function composition? in my turing machines? unheard of

const { start: solutionStart, ast: solutionAst } = compose(`
    * -> trySub1Lhs.S0
    trySub1Lhs.sub_ok -> incRhs.pre
    incRhs.saida -> trySub1Lhs.S0
    trySub1Lhs.sub_fail -> eraseLhs.S0
    eraseLhs.Sf -> cutRhsPasteLhs.start
    cutRhsPasteLhs.quit -> *
`, { trySub1Lhs, incRhs, eraseLhs, cutRhsPasteLhs });
const solution = compile(solutionAst, solutionStart);
console.log("\nprint machine:");
console.log(printMachine(solutionAst));

console.log("solution 0+1", run("0+1", solution))
console.log("solution 1+1", run("1+1", solution))
console.log("solution 1+0", run("1+0", solution))
console.log("solution 10+1", run("10+1", solution))
console.log("solution 10+10", run("10+10", solution))
console.log("solution 10+101", run("10+101", solution))
console.log("solution 111+111", run("111+111", solution))