AdventOfCode-ts-2023/11/11_common.ts

import { Vector2 } from "../3/3_common.ts";

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

    constructor(rawMap: string[], expansionRate = 1) {
        this.originalMap = rawMap;
        this.expansionRate = expansionRate > 1 ? expansionRate - 1 : expansionRate;
        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 += this.expansionRate;
                if (debug) {
                    console.log(`Adding ${this.expansionRate} for the empty column at ${col}`);
                }
            }
        });
        this.emptyRows.forEach((row) => {
            if (between(row, galaxy1.Y, galaxy2.Y)) {
                xOffset += this.expansionRate;
                if (debug) {
                    console.log(`Adding ${this.expansionRate} 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;
    }
}

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