Day 5/2021 - Hydrothermal Venture

Day five of AoC 2021 (available at https://adventofcode.com/2021/day/5) has us mapping hydrothermal vents on the ocean floor. These vents produce large opaque clouds — smoke on the water, if you will. We need to find where the vent lines overlap.

The input describes line segments: 0,9 -> 5,9 means a line from point (0,9) to point (5,9).

Parsing the Input

Regex makes this clean:

interface Point {
    x: number;
    y: number;
}

interface Vent {
    from: Point;
    to: Point;
}

const processInput = (day: number): Vent[] => {
    const lines = readInputLines(day);
    const regex = /^(\d+),(\d+) -> (\d+),(\d+)$/;
    
    return lines.map(line => {
        const match = line.match(regex);
        if (!match) throw new Error(`Invalid line: ${line}`);
        
        return {
            from: { x: parseInt(match[1], 10), y: parseInt(match[2], 10) },
            to: { x: parseInt(match[3], 10), y: parseInt(match[4], 10) }
        };
    });
};

Part One: Horizontal and Vertical Lines Only

First, filter to only horizontal (same Y) or vertical (same X) lines:

const gridLines = input.filter(vent => 
    vent.from.x === vent.to.x || vent.from.y === vent.to.y
);

Then build a grid and mark each point on each line:

const xMax = Math.max(...input.flatMap(v => [v.from.x, v.to.x]));
const yMax = Math.max(...input.flatMap(v => [v.from.y, v.to.y]));

const grid: number[][] = new Array(xMax + 1)
    .fill(0)
    .map(() => new Array(yMax + 1).fill(0));

for (const line of gridLines) {
    const fromX = Math.min(line.from.x, line.to.x);
    const toX = Math.max(line.from.x, line.to.x);
    const fromY = Math.min(line.from.y, line.to.y);
    const toY = Math.max(line.from.y, line.to.y);
    
    for (let row = fromX; row <= toX; row++) {
        for (let col = fromY; col <= toY; col++) {
            grid[row][col]++;
        }
    }
}

Note the nested loops: for horizontal/vertical lines, one of these loops is "degenerate" — it runs exactly once because fromX === toX or fromY === toY. So we're not actually doing O(n²) work per line.

Finally, count cells where two or more lines overlap:

const result = grid
    .map(row => row.filter(cell => cell >= 2).length)
    .reduce((a, b) => a + b, 0);

Part Two: Adding Diagonals

The puzzle guarantees all diagonal lines are exactly 45 degrees — the X and Y distances are always equal. This simplifies things enormously.

First, I checked whether my input had any non-grid, non-diagonal lines:

for (const line of diagonals) {
    const xDiff = Math.abs(line.from.x - line.to.x);
    const yDiff = Math.abs(line.from.y - line.to.y);
    if (xDiff !== yDiff) {
        console.log("Non-diagonal found!");
    }
}

Result: everything is either horizontal, vertical, or 45-degree diagonal. We don't have to solve the general case — just our specific input.

For diagonals, we need direction vectors:

const diagonals = input.filter(vent => 
    vent.from.x !== vent.to.x && vent.from.y !== vent.to.y
);

for (const line of diagonals) {
    const count = Math.abs(line.from.x - line.to.x);
    const xDir = line.from.x < line.to.x ? 1 : -1;
    const yDir = line.from.y < line.to.y ? 1 : -1;
    
    for (let i = 0; i <= count; i++) {
        const x = line.from.x + i * xDir;
        const y = line.from.y + i * yDir;
        grid[x][y]++;
    }
}

The xDir and yDir are either +1 or -1, indicating which way we step. A line from (8,0) to (0,8) has xDir = -1 and yDir = +1.

Why Not Use the Nested Loop for Diagonals?

The nested loop approach for horizontal/vertical lines would fill a square for diagonals. A line from (0,0) to (8,8) would incorrectly mark all 81 cells in that 9×9 region, when we only want the 9 diagonal cells.

Performance

The grid is about 1000×1000 = 1 million cells. That's ~4MB of memory and takes about 100-120ms to process. Not blazing fast, but acceptable.

An analytical solution exists: calculate line intersections mathematically without building a grid. But for a one-shot puzzle with a million cells, the naive approach works fine.

My overall goal for AoC is total runtime under a minute for all 25 days. Individual puzzles taking 100ms are well within budget.

Takeaways

1. Don't solve the general case: The puzzle guarantees 45-degree diagonals. I verified my input had no other angles, then wrote code specifically for that constraint.

2. Degenerate loops are fine: A loop from 5 to 5 runs once. Using the same nested-loop structure for horizontal and vertical lines is cleaner than special-casing.

3. Direction vectors simplify diagonal logic: Instead of sorting coordinates, compute xDir and yDir as +1 or -1, then step from the start point.

4. A million cells is manageable: Modern computers handle megabyte-scale data trivially. Don't prematurely optimize away from the obvious grid approach.

5. Verify assumptions with code: Instead of manually checking 500 lines for non-diagonal cases, write a quick check and run it.

The full solution is available in the repository.