aoc-2023/day_20/solve_2.ts

const input = await Deno.readTextFile("test3.txt");

const SourceKindTable = {
    "%": "flipflop",
    "&": "conjunction",
};
function getSourceKind(prefix: string): "flipflop" | "conjunction" {
    if (prefix in SourceKindTable) {
        return SourceKindTable[prefix as keyof typeof SourceKindTable] as "flipflop" | "conjunction";
    }
    throw new Error(`unknown source kind ${prefix}`);
}

function parseInput(input: string) {
    const lines = input.split("\n").map(x => x.trim()).filter(x => x.length > 0 && x[0] !== "#");
    return lines.map(line => {
        const [source, targetsLine] = line.split("->").map(x => x.trim())
        const targets = targetsLine.split(",").map(x => x.trim());
        if (source === "broadcaster") {
            return {
                sourceKind: source,
                sourceName: "broadcaster",
                targets
            }
        }
        const sourceKind = getSourceKind(source[0]);
        const sourceName = source.slice(1);

        return {
            sourceKind: sourceKind,
            sourceName: sourceName,
            targets
        }
    });
}

const s = parseInput(input);
console.log(s);

type Signal = boolean;
type ModuleMap = Record<string, Module>;

type PropagateResult = {
    signal: Signal,
};

interface Module {
    sourceName: string,
    targets: string[],
    propagate(sourceName: string, signal: Signal): null | PropagateResult;
}

class FlipFlop implements Module {
    public state = false;
    constructor(
        public sourceName: string,
        public targets: string[],
    ) {
    }

    propagate(_sourceName: string, signal: Signal) {
        if (!signal) {
            this.state = !this.state;
            return {
                signal: this.state
            };
        }
        return null;
    }
}

class Conjunction implements Module {
    public state: Map<string, Signal>;
    constructor(
        public sourceName: string,
        public targets: string[],
        public inputs: string[],
    ) {
        this.state = new Map<string, Signal>();
        for (const input of inputs) {
            this.state.set(input, false);
        }
    }

    propagate(sourceName: string, signal: Signal) {
        this.state.set(sourceName, signal);
        if ([...this.state.values()].every(x => x)) {
            return {
                signal: false,
            };
        }
        return {
            signal: true,
        };
    }
}

class Broadcaster implements Module {
    constructor(
        public sourceName: string,
        public targets: string[],
    ) {
    }
    propagate(_sourceName: string, signal: boolean): PropagateResult | null {
        return {
            signal
        };
    }
}

const state = {} as ModuleMap;
for (const line of s) {
    if (line.sourceKind === "broadcaster") {
        state[line.sourceName] = new Broadcaster(line.sourceName, line.targets);
    } else if (line.sourceKind === "flipflop") {
        state[line.sourceName] = new FlipFlop(line.sourceName, line.targets);
    }
    else if (line.sourceKind === "conjunction") {
        const sourceName = line.sourceName;
        const inputs = s.filter((x) => {
            return x.targets.includes(sourceName)
        }).map(x=> x.sourceName);
        state[line.sourceName] = new Conjunction(line.sourceName, line.targets, inputs);
    }
}

function drawMermaidChart(modules: Module[]) {
    let ret = "";
    ret += ("flowchart TD\n");
    ret += modules.map(module => {
        const kind = module instanceof Conjunction ? "c" : "f";
        return module.targets.map(target=> {
            return (`    ${module.sourceName}[${kind} ${module.sourceName}] --> ${target}`);
        }).join("\n");
    }).join("\n");
    return ret;
}

console.log(drawMermaidChart([...Object.values(state)]));


function cycle(state: ModuleMap) {
    const queue = [{
        from: "button",
        target: "broadcaster",
        signal: false,
    }];
    while (queue.length > 0) {
        const { target, signal, from } = queue.shift()!;
        const targetModule = state[target];
        if (targetModule === undefined) {
            // ignore
            continue;    
        }
        const result = targetModule.propagate(from, signal);
        if (result !== null) {
            const { signal } = result;
            if (!signal && targetModule.targets.includes("rx")){
                console.log("found rx");
                return true;
            }
            targetModule.targets.forEach(x => {
                console.log(`${target} -${signal ? "high" : "low"}-> ${x}`);
                queue.push({ from: target, target: x, signal });
            });
        }
    }
    return false;
}

let i = 0;
while (true) {
    console.log(i);
    const rx = cycle(state);
    i++;
    if (i % 10 === 0) {
        break;
    }
    if (rx) {
        break;
    }
}
console.log(i);