aoc23-17.mts

import { Advent, f, fm, chr, ord } from "advent";
import { Set, Map } from "immutable";
import { MinPriorityQueue } from "@datastructures-js/priority-queue";

const { compute, computeCheck } = await Advent({ day: 17 });

interface Location {
	i: number;
	j: number;
	direction: number; // right, down, left, up
	steps: number;
}

interface QueueEntry {
	loc: Location;
	distance: number;
}

function locationKey(loc: Location) {
	return `${loc.i},${loc.j},${loc.direction},${loc.steps}`;
}

compute(1, async (input) => {
	const data = input.parse(f.cGrid());
	const grid = data.map((x) => x.map((y) => parseInt(y)));

	let visited = Set<string>();
	// let queue: QueueEntry[] = [{ loc: { i: 0, j: 0, direction: 0, steps: 0 }, distance: 0 }];
	const pq = new MinPriorityQueue<QueueEntry>((x) => x.distance);
	pq.push({ loc: { i: 0, j: 0, direction: 0, steps: 0 }, distance: 0 });

	while (pq.size() > 0) {
		// queue.sort((a, b) => a.distance - b.distance);
		const { loc, distance } = pq.pop();
//		console.log(loc, distance);

		if (visited.has(locationKey(loc))) {
			continue;
		}

		if (loc.i === grid.length - 1 && loc.j === grid[loc.i].length - 1) {
			return distance;
		}

		visited = visited.add(locationKey(loc));

		const { i, j, direction, steps } = loc;

		if (i === 0 && j === 0) {
			// options are right and down
			for (const dir of [0, 1]) {
				const [i2, j2] = step(i, j, dir);
				if (inBounds(grid, i2, j2)) {
					pq.push({ loc: { i: i2, j: j2, direction: dir, steps: 1 }, distance: distance + grid[i2][j2] });
				}
			}
			continue;
		}

		if (steps < 10) {
			const [i2, j2] = step(i, j, direction);
			if (inBounds(grid, i2, j2)) {
				pq.push({ loc: { i: i2, j: j2, direction, steps: steps + 1 }, distance: distance + grid[i2][j2] });
			}
		}

		if (steps >= 4) {
			const leftdir = (direction + 3) % 4;
			const rightdir = (direction + 1) % 4;

			const [i2, j2] = step(i, j, leftdir);
			if (inBounds(grid, i2, j2)) {
				pq.push({ loc: { i: i2, j: j2, direction: leftdir, steps: 1 }, distance: distance + grid[i2][j2] });
			}

			const [i3, j3] = step(i, j, rightdir);
			if (inBounds(grid, i3, j3)) {
				pq.push({ loc: { i: i3, j: j3, direction: rightdir, steps: 1 }, distance: distance + grid[i3][j3] });
			}
		}
	}

	return -1;
});

function inBounds(grid: number[][], i: number, j: number) {
	return i >= 0 && i < grid.length && j >= 0 && j < grid[i].length;
}

function step(i: number, j: number, direction: number): [number, number] {
	return (
		direction == 0 ? [i, j + 1] :
		direction == 1 ? [i + 1, j] :
		direction == 2 ? [i, j - 1] :
		[i - 1, j]
	);
}

// computeCheck(1, async function* (input) {
// 	const data = input.parse(f.nl(f.int()));
// 	let ans = 0;
// 	yield ans;
// });