AdventOfCode-ts-2023/11/11_1.ts

import { Vector2 } from "../3/3_common.ts";
import { LoadInput, Inspect } from "../common.ts";

async function main() {
    const tests = [
        '...#......',
        '.......#..',
        '#.........',
        '..........',
        '......#...',
        '.#........',
        '.........#',
        '..........',
        '.......#..',
        '#...#.....'
    ];

    const test_reddit_1 = [
        "...#......#....",
        "...............",
        "#..........#...",
        "...............",
        "...............",
        "...............",
        "......#.....#..",
        ".#.............",
        "#..............",
        "...............",
        "...............",
        "...............",
        "......#.#......",
        "............#..",
        "....#..........",
    ];

    const test_reddit_2 = [
        "......#........",
        ".........#.....",
        "...............",
        "...............",
        "..........#...#",
        "...............",
        "...............",
        "#...#..........",
        "..#............",
        "...............",
        ".........#.....",
        ".........#.....",
        "...........#...",
        "...............",
        ".#...........#.",
    ];

    const input = await LoadInput(11);

    const sm = new StarMap(input);
    
    console.log("Empty Columns found:");
    Inspect(sm.emptyColumns);
    console.log("Empty Rows found:");
    Inspect(sm.emptyRows);
    console.log("Galaxies found:");
    console.log(sm.galaxyList);
    
    console.log(`The sum of the shortest paths between galaxies is: ${sm.solvePart1()}`);
}

class StarMap {
    private originalMap: string[];
    private mapDimensions: {width: number, height: number};
    public galaxyList: Array<Vector2> = [];
    public emptyColumns: number[] = [];
    public emptyRows: number[] = [];

    constructor(rawMap: string[]) {
        this.originalMap = rawMap;
        this.mapDimensions = {
            width: this.originalMap[0].length,
            height: this.originalMap.length
        };
        this.parse();
        // Sort the galaxy list by Y values
        this.galaxyList.sort((a, b) => a.Y - b.Y)
    }

    private parse() {
        // Find the empty rows and columns
        for (let col = 0; col < this.mapDimensions.width; col++) {
            // Count of the number of empty cells in the column
            let emptyCellsInColumn = 0;
            for (let row = 0; row < this.mapDimensions.height; row++) {
                // If current cell is a galaxy, add it to the list and move to the next row
                if (this.isGalaxy(this.originalMap[row][col])) {
                    this.galaxyList.push({
                        X: col,
                        Y: row
                    });
                    continue;
                }
                // Check if the current row is empty
                // Only needs done during the first column
                if (col == 0 && this.isEmpty(this.originalMap[row])) {
                    this.emptyRows.push(row);
                }

                // Otherwise, add an empty char to the pivotted column
                emptyCellsInColumn++;
            }
            // Check if the column was empty
            if (emptyCellsInColumn == this.mapDimensions.height) {
                this.emptyColumns.push(col);
            }
        }
    }

    private isEmpty(sector: string) {
        return /^[.]+$/.test(sector);
    }

    private isGalaxy(symbol: string) {
        return symbol == "#";
    }

    public getExpandedDistance(galaxyIdx1: number, galaxyIdx2: number, debug = false): number {
        // Get the two galaxies being compared
        const galaxy1 = this.galaxyList[galaxyIdx1];
        const galaxy2 = this.galaxyList[galaxyIdx2];

        // DEBUG
        if (debug) {
            console.log("DEBUG:");
            console.log("Comparing ", galaxy1, "to ", galaxy2);
        }

        // Check for any empty rows or columns between the two
        let yOffset = 0;
        let xOffset = 0;
        this.emptyColumns.forEach((col) => {
            if (between(col, galaxy1.X, galaxy2.X)) {
                yOffset += 1;
                if (debug) {
                    console.log(`Adding 2 for the empty column at ${col}`);
                }
            }
        });
        this.emptyRows.forEach((row) => {
            if (between(row, galaxy1.Y, galaxy2.Y)) {
                xOffset += 1;
                if (debug) {
                    console.log(`Adding 2 for the empty row at ${row}`);
                }
            }
        });

        if (debug) {
            console.log(`DEBUG: xOffset - ${xOffset}`);
            console.log(`DEBUG: yOffset - ${yOffset}`);
        }

        // Find the immediate deltas between the two galaxies
        const delta: Vector2 = {
            X: galaxy1.X - galaxy2.X,
            Y: galaxy1.Y - galaxy2.Y
        };

        if (debug) {
            console.log("DEBUG: delta values - ", delta);
        }

        return Math.abs(delta.X) + xOffset + Math.abs(delta.Y) + yOffset;
    }

    public solvePart1(debug = false):number {
        let totalPairs = 0;
        let totalShortestPaths = 0;
        for (let idx1 = 0; idx1 < this.galaxyList.length - 1; idx1++) {
            for (let idx2 = idx1 + 1; idx2 < this.galaxyList.length; idx2++) {
                totalPairs++;
                const manhatDist = this.getExpandedDistance(idx1, idx2, debug)
                if (debug) {
                    console.log(`Manhattan Distance between node ${idx1 + 1} and ${idx2 + 1} is: `, manhatDist);
                }
                totalShortestPaths += manhatDist;
            }

            if (debug) {
                console.log("---------------------");
            }
        }

        return totalShortestPaths;
    }
}

/**
 * Get the slope of a line going through two {@link Vector2}'s
 *
 * If the two are on the same x-axis, then the slope will be 0.
 *
 * If the two are on the same y-axis, then the slope will be `Infinity`.
 * 
 * @param {Vector2} node1 
 * @param {Vector2} node2 
 * @returns {number} A float or `Infinity`
 */
function getSlope(node1: Vector2, node2: Vector2): number {
    const delta = {
        X: node2.X - node1.X,
        Y: node2.Y - node1.Y
    };

    if (delta.X == 0) { return Infinity; }

    return delta.Y/delta.X;
}

function getDistance(node1: Vector2, node2: Vector2): number {
    const delta: Vector2 = {
        X: node2.X - node1.X,
        Y: node2.Y - node1.Y
    };

    return Math.sqrt(Math.pow(delta.X, 2) + Math.pow(delta.Y, 2));
}

function getManhattanDistance(node1: Vector2, node2: Vector2): number {
    const delta: Vector2 = {
        X: node1.X - node2.X,
        Y: node1.Y - node2.Y
    };

    const manhatDist = Math.abs(delta.X) + Math.abs(delta.Y);

    return manhatDist;
}

function between(toCheck: number, boundary1: number, boundary2: number): boolean {
    return (toCheck > boundary1 && toCheck < boundary2)
        || (toCheck > boundary2 && toCheck < boundary1);
}

main();