aoc24-20.mts

import { Advent, f, fm, chr, ord, GridDirectionsWithoutDiagonals, mapGrid } from "advent";
import { Set, Map, List } from "immutable";
import PriorityQueue from "ts-priority-queue";
// import { init } from "z3-solver";
// const { Context } = await init();
// const { Solver, Int, And } = Context("main");

// const x = Int.const("x");
// const solver = new Solver();
// solver.add(And(x.ge(0), x.le(10)));
// console.log(await solver.check());

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

compute(1, async (input) => {
	const data = input.parse(f.cGrid());
	const queue = new PriorityQueue.default<{ r: number, c: number, used: number, dist: number }>({ comparator: (a, b) => a.dist - b.dist });
	let visited = Set<number>();
	let dist = Map<number, number>();
	const idx = (u: number, r: number, c: number) => u * 100000000 + r * 10000 + c;
	for (let i = 0; i < data.length; i++) {
		for (let j = 0; j < data[i].length; j++) {
			if (data[i][j] === "E") {
				queue.queue({ r: i, c: j, used: 0, dist: 0 });
				dist.set(idx(0, i, j), 0);
			}
		}
	}

	while (queue.length > 0) {
		const { r, c, used, dist: d } = queue.dequeue();
		// console.log(r, c, used, d);
		const i = idx(used, r, c);
		if (visited.has(i)) {
			continue;
		}
		visited = visited.add(i);
		dist = dist.set(i, d);
		for (let dr = -2; dr <= 2; dr++) {
			for (let dc = -2; dc <= 2; dc++) {
				const size = Math.abs(dr) + Math.abs(dc);
				if (size === 0 || size > 2) {
					continue;
				}
				const nr = r + dr;
				const nc = c + dc;
				if (nr < 0 || nr >= data.length || nc < 0 || nc >= data[nr].length) {
					continue;
				}
				if (data[nr][nc] === "#") {
					continue;
				}
				const nu = used + (size - 1);
				const ni = idx(nu, nr, nc);
				if (nu > 1 || visited.has(ni)) {
					continue;
				}
				const nd = d + size;
				queue.queue({ r: nr, c: nc, used: nu, dist: nd });
			}
		}
	}

	let ok = mapGrid(data, () => false);
	let okVisited = Set<number>();
	let okQueue = List<{ r: number, c: number }>();

	for (let i = 0; i < data.length; i++) {
		for (let j = 0; j < data[i].length; j++) {
			if (data[i][j] === "S") {
				okQueue = okQueue.push({ r: i, c: j });
			}
		}
	}

	while (okQueue.size > 0) {
		const { r, c } = okQueue.first()!;
		okQueue = okQueue.shift();
		ok[r][c] = true;
		const d = dist.get(idx(0, r, c))!;
		for (const [dr, dc] of GridDirectionsWithoutDiagonals) {
			const nr = r + dr;
			const nc = c + dc;
			if (nr < 0 || nr >= data.length || nc < 0 || nc >= data[nr].length) {
				continue;
			}
			const nd = dist.get(idx(0, nr, nc));
			if (nd !== undefined && nd === d - 1) {
				okQueue = okQueue.push({ r: nr, c: nc });
			}
		}
	}


	let base = Infinity;

	for (let i = 0; i < data.length; i++) {
		for (let j = 0; j < data[i].length; j++) {
			if (data[i][j] === "S") {
				base = dist.get(idx(0, i, j))!;
			}
		}
	}

	let ans = 0;

	for (let i = 0; i < data.length; i++) {
		for (let j = 0; j < data[i].length; j++) {
			for (let dr = -20; dr <= 20; dr++) {
				for (let dc = -20; dc <= 20; dc++) {
					const d = Math.abs(dr) + Math.abs(dc);
					if (d > 20) {
						continue;
					}
					if (i + dr < 0 || i + dr >= data.length || j + dc < 0 || j + dc >= data[i + dr].length) {
						continue;
					}
					const d1 = dist.get(idx(0, i, j))!;
					const d2 = dist.get(idx(0, i + dr, j + dc))!;
					if (d1 - d2 >= 100 + d && ok[i][j] && ok[i + dr][j + dc]) {
						ans++;
					}
				}
			}
		}
	}

	return ans;
});

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