Day 7/2025 - Laser Splitters

Day seven of AoC 2025 (available at https://adventofcode.com/2025/day/7) brings us more than halfway through this year's 12-day event. We're working with lasers and splitters in some kind of teleporter mechanism.

A laser enters from a starting position marked S, travels downward through the grid, and encounters splitters along the way. When a beam hits a splitter, it creates a schism — splitting into two paths, left and right.

Parsing the Input

The input is a simple character grid:

type Cell = "S" | "." | "\\";
type Matrix = Cell[][];

const processInput = (day: number): Matrix => {
    const lines = readInputLines(day);
    return lines.map(line => line.split("") as Cell[]);
};

The grid has empty spaces (.), the start position (S), and splitters. Conveniently, every even row is empty, so we never have adjacent splitters — and we never go out of bounds.

Part One: Counting Activated Splitters

For part one, track where beams go and count how many splitters get activated. The twist: when two beams arrive at the same splitter, it only counts once.

const partOne = (input: Matrix, debug: boolean) => {
    const firstRow = input[0];
    const startCol = firstRow.indexOf("S");
    
    let beamLocations = [startCol];
    let activatedSplitters = 0;
    
    for (let row = 1; row < input.length; row++) {
        const currentRow = input[row];
        const temps: number[] = [];
        
        for (const col of beamLocations) {
            if (currentRow[col] === "\\") {
                activatedSplitters++;
                temps.push(col - 1); // Split left
                temps.push(col + 1); // Split right
            } else {
                temps.push(col); // Continue straight
            }
        }
        
        // Remove duplicates — two beams at same position merge
        beamLocations = [...new Set(temps)];
    }
    
    return activatedSplitters;
};

The Set trick handles the merging elegantly. If two beams land on the same column, they become one beam going forward.

Part Two: Quantum Paths

Part two changes everything. Now we need to count all possible paths a particle could take if it randomly chose left or right at each splitter. This is no longer about tracking positions — it's about counting combinations.

The recursive approach is natural:

type Point = { row: number; col: number };

const countMoves = (input: Matrix, beamLocation: Point): number => {
    const { row, col } = beamLocation;
    
    // Reached the bottom — one valid path
    if (row === input.length - 1) {
        return 1;
    }
    
    const nextRow = input[row + 1];
    const isSplitter = nextRow[col] === "\\";
    
    if (isSplitter) {
        const leftMoves = countMoves(input, { row: row + 1, col: col - 1 });
        const rightMoves = countMoves(input, { row: row + 1, col: col + 1 });
        return leftMoves + rightMoves;
    } else {
        return countMoves(input, { row: row + 1, col: col });
    }
};

Clean, elegant, obviously correct. And completely unusable.

The Performance Problem

Running this on the real input, I added some logging to see progress. After letting it run for a while, it had made over 3 billion recursive calls and wasn't close to finishing. The recursion tree explodes exponentially.

But here's the key insight: it doesn't matter how a beam got to position (row, col). The number of paths from that point forward is always the same. We're recalculating the same subproblems billions of times.

Memoization to the Rescue

const countMoves = (input: Matrix, beamLocation: Point, cache: Record<string, number>): number => {
    const { row, col } = beamLocation;
    const key = `${row},${col}`;
    
    if (cache[key] !== undefined) {
        return cache[key];
    }
    
    if (row === input.length - 1) {
        cache[key] = 1;
        return 1;
    }
    
    const nextRow = input[row + 1];
    const isSplitter = nextRow[col] === "\\";
    
    let result: number;
    if (isSplitter) {
        const leftMoves = countMoves(input, { row: row + 1, col: col - 1 }, cache);
        const rightMoves = countMoves(input, { row: row + 1, col: col + 1 }, cache);
        result = leftMoves + rightMoves;
    } else {
        result = countMoves(input, { row: row + 1, col: col }, cache);
    }
    
    cache[key] = result;
    return result;
};

The cache stores results for each (row, col) position. Once we've calculated how many paths lead from a position to the bottom, we never recalculate it.

The result? A 14-digit number (trillions of paths) computed in milliseconds instead of millennia.

Why Memoization Works Here

This is a classic dynamic programming scenario. The problem has optimal substructure (the answer depends on answers to smaller subproblems) and overlapping subproblems (we solve the same subproblems repeatedly).

Without caching, we traverse the same positions over and over through different paths. With caching, each position is computed exactly once, and subsequent visits just look up the cached value.

The difference: O(2^n) becomes O(n×m) where n and m are the grid dimensions.

Takeaways

1. Recursion is elegant but dangerous: The recursive solution is beautiful and obviously correct. It's also completely impractical without optimization.

2. Memoization transforms exponential to polynomial: Adding a cache turned an impossible computation into a trivial one. Same algorithm, vastly different performance.

3. Position is all that matters: The key insight is that the path history doesn't affect the future. Only the current position determines the number of remaining paths.

4. Use strings for cache keys: JavaScript doesn't have structural equality for objects. Converting {row, col} to "row,col" gives us a usable hash key.

5. Monitor your recursion: Adding logging to track progress revealed that the naive solution was making billions of calls. When recursion seems slow, instrument it to understand why.

The full solution is available in the repository.