66 lines
2.2 KiB
TypeScript
66 lines
2.2 KiB
TypeScript
|
import {Range, Seq, Set} from "immutable";
|
||
|
|
import fs from "fs";
|
||
|
|
|
||
|
|
type Position = [number, number];
|
||
|
|
type GalaxyPair = [Position, Position];
|
||
|
|
|
||
|
|
export class Observatory {
|
||
|
|
private grid: string[][] = [];
|
||
|
|
private expandedRows: number[] = [];
|
||
|
|
private expandedColumns: number[] = [];
|
||
|
|
|
||
|
|
constructor(input: string) {
|
||
|
|
this.grid = input.split('\n').map(line => line.split(''));
|
||
|
|
|
||
|
|
this.expandGrid();
|
||
|
|
}
|
||
|
|
|
||
|
|
private expandGrid() {
|
||
|
|
this.expandedColumns = Range(0, this.grid[0].length).filter(column => this.grid.every(row => row[column] === '.')).toArray();
|
||
|
|
this.expandedRows = Range(0, this.grid.length).filter(row => this.grid[row].every(column => column === '.')).toArray();
|
||
|
|
}
|
||
|
|
|
||
|
|
public get shortestPaths(): number {
|
||
|
|
const distances = this.pairs.map(pair => this.distanceBetween(pair[0], pair[1]));
|
||
|
|
return distances.reduce((sum, distance) => sum + distance, 0);
|
||
|
|
}
|
||
|
|
|
||
|
|
private get pairs(): GalaxyPair[] {
|
||
|
|
const galaxies = this.grid.reduce((galaxies, row, rowIndex) => {
|
||
|
|
row.forEach((galaxy, columnIndex) => {
|
||
|
|
if (galaxy === '#') {
|
||
|
|
galaxies.push([rowIndex, columnIndex]);
|
||
|
|
}
|
||
|
|
});
|
||
|
|
return galaxies;
|
||
|
|
}, [] as Position[]);
|
||
|
|
|
||
|
|
return galaxies.reduce((pairs, galaxy, index) => {
|
||
|
|
return pairs.withMutations(pairs => {
|
||
|
|
galaxies.slice(index + 1).forEach(otherGalaxy => {
|
||
|
|
pairs.add([galaxy, otherGalaxy]);
|
||
|
|
});
|
||
|
|
})
|
||
|
|
}, Set<GalaxyPair>()).toArray();
|
||
|
|
}
|
||
|
|
|
||
|
|
private range = (a: number, b: number): Seq.Indexed<number> => {
|
||
|
|
return Range(Math.min(a, b), Math.max(a, b) + 1);
|
||
|
|
}
|
||
|
|
public distanceBetween(galaxyOne: Position, galaxyTwo: Position): number {
|
||
|
|
const expansion = 999_999;
|
||
|
|
|
||
|
|
const xRange = this.range(galaxyOne[0], galaxyTwo[0]).filter(row => this.expandedRows.includes(row)).toArray().length;
|
||
|
|
const yRange = this.range(galaxyOne[1], galaxyTwo[1]).filter(column => this.expandedColumns.includes(column)).toArray().length;
|
||
|
|
|
||
|
|
const expansions = expansion * (xRange + yRange)
|
||
|
|
|
||
|
|
return Math.abs(galaxyOne[0] - galaxyTwo[0]) + Math.abs(galaxyOne[1] - galaxyTwo[1]) + expansions;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
export const runDayEleven = () => {
|
||
|
|
const input = fs.readFileSync('./inputs/day_eleven_input.txt', 'utf-8').trimEnd();
|
||
|
|
const observatory = new Observatory(input);
|
||
|
|
console.log(`The shortest path between every galaxy is ${observatory.shortestPaths}`);
|
||
|
|
}
|