151 lines
3.5 KiB
TypeScript
151 lines
3.5 KiB
TypeScript
import fs from "fs";
|
|
import {window} from "./utils";
|
|
|
|
type Grid = Tile[][];
|
|
type Cell = [number, number];
|
|
type Tile = 'S' | 'F' | 'J' | 'L' | '7' | '-' | '|' | '.';
|
|
type Loop = string[];
|
|
|
|
const isTile = (value: string): value is Tile => {
|
|
return ['S', 'F', 'J', 'L', '7', '-', '|', '.'].includes(value);
|
|
}
|
|
|
|
const toString = (cell: Cell): string => {
|
|
return JSON.stringify(cell);
|
|
}
|
|
|
|
const fromString = (cell: string): Cell => {
|
|
return JSON.parse(cell);
|
|
}
|
|
|
|
|
|
const getStart = (grid: Grid): Cell => {
|
|
const row = grid.findIndex(row => row.includes('S'));
|
|
const col = grid[row].findIndex(cell => cell === 'S');
|
|
return [row, col];
|
|
}
|
|
|
|
const getSurrounding = (grid: Grid, [row, col]: Cell): Cell[] => {
|
|
return ([
|
|
[row - 1, col],
|
|
[row + 1, col],
|
|
[row, col - 1],
|
|
[row, col + 1],
|
|
[row - 1, col - 1],
|
|
[row - 1, col + 1],
|
|
[row + 1, col - 1],
|
|
[row + 1, col + 1],
|
|
] as Cell[]).filter((cell) => isInGrid(grid, cell));
|
|
}
|
|
const getConnectingNeighbours = (grid: Grid, [row, col]: Cell): Cell[] => {
|
|
return getSurrounding(grid, [row, col]).filter((cell) =>
|
|
isValid(grid, cell) && neighbours(grid, cell).map(toString).includes(toString([row, col]))
|
|
);
|
|
}
|
|
|
|
const neighbours = (grid: Grid, [row, col]: Cell): Cell[] => {
|
|
const value = grid[row][col];
|
|
switch (value) {
|
|
case 'F':
|
|
return [
|
|
[row, col + 1],
|
|
[row + 1, col],
|
|
];
|
|
case 'J':
|
|
return [
|
|
[row - 1, col],
|
|
[row, col - 1]
|
|
];
|
|
case 'L':
|
|
return [
|
|
[row, col + 1],
|
|
[row - 1, col]
|
|
];
|
|
case '7':
|
|
return [
|
|
[row + 1, col],
|
|
[row, col - 1]
|
|
];
|
|
case '-':
|
|
return [
|
|
[row, col + 1],
|
|
[row, col - 1]
|
|
];
|
|
case '|':
|
|
return [
|
|
[row - 1, col],
|
|
[row + 1, col]
|
|
];
|
|
default:
|
|
return [];
|
|
}
|
|
}
|
|
|
|
function isInGrid(grid: Tile[][], [row, col]: Cell) {
|
|
return row >= 0 && row < grid.length && col >= 0 && col < grid[row].length;
|
|
}
|
|
|
|
const isValid = (grid: Grid, cell: Cell): boolean => {
|
|
return isInGrid(grid, cell) && grid[cell[0]][cell[1]] !== '.';
|
|
}
|
|
|
|
function parseGrid(input: string) {
|
|
return input.split('\n').map(line => line.split('').filter(isTile));
|
|
}
|
|
|
|
function getMainLoop(grid: Grid): Loop {
|
|
const start = getStart(grid);
|
|
const queue = [getConnectingNeighbours(grid, start)[0]];
|
|
const visited = [toString(start)];
|
|
|
|
while (queue.length > 0) {
|
|
const current = queue.shift()!;
|
|
const next = neighbours(grid, current);
|
|
|
|
next.forEach(cell => {
|
|
if (!visited.includes(toString(cell)) && isValid(grid, cell)) {
|
|
queue.push(cell);
|
|
visited.push(toString(cell));
|
|
}
|
|
});
|
|
}
|
|
return visited;
|
|
}
|
|
|
|
export const getFurthestDistance = (input: string): number => {
|
|
const grid = parseGrid(input);
|
|
const loop = getMainLoop(grid);
|
|
|
|
return loop.length / 2;
|
|
}
|
|
|
|
export const area = (grid: Grid, loop: Loop): number => {
|
|
// Use shoelace formula to calculate area of polygon
|
|
const polygon = loop.map(fromString).filter((cell) => {
|
|
const value = grid[cell[0]][cell[1]];
|
|
return ['F', 'J', 'L', '7', 'S'].includes(value);
|
|
});
|
|
|
|
const total = window([...polygon, polygon[0]], 2).reduce((total, [a, b]) => {
|
|
const [y1, x1] = a;
|
|
const [y2, x2] = b;
|
|
return total + (x1 * y2 - y1 * x2);
|
|
}, 0);
|
|
|
|
return Math.abs(total) / 2;
|
|
}
|
|
|
|
export const tilesContained = (input: string): number => {
|
|
const grid = parseGrid(input);
|
|
const loop = getMainLoop(grid);
|
|
|
|
const loopArea = area(grid, loop);
|
|
const boundaryPointsCount = loop.length;
|
|
return loopArea - (boundaryPointsCount / 2) + 1;
|
|
}
|
|
|
|
export const runDayTen = () => {
|
|
const input = fs.readFileSync('./inputs/day_ten_input.txt', 'utf8').trimEnd();
|
|
const result = tilesContained(input);
|
|
console.log(`Day Ten: ${result}`);
|
|
} |