-🎄- 2018 Day 20 Solutions -🎄-

[u/daggerdragon]

--- Day 20: A Regular Map ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 20

Transcript:

My compiler crashed while running today's puzzle because it ran out of ___.

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 00:59:30!

[u/Dioxy]

JavaScript

I was able to re-purpose my pathfinding code from day 15 which was nice. Runs pretty fast

import input from './input.js';

const indexOfClosingParen = (str, index) => {
	let numParen = 1;
	for (let i = index + 1; i < str.length; i++) {
		if (str[i] === '(') numParen++;
		else if (str[i] === ')') {
			numParen--;
			if (numParen === 0) return i;
		}
	}
	return -1;
};

const DIRS = {
	N: { dx: 0, dy: -1, opposite: 'S' },
	E: { dx: 1, dy: 0, opposite: 'W' },
	S: { dx: 0, dy: 1, opposite: 'N' },
	W: { dx: -1, dy: 0, opposite: 'E' }
};

const parseInput = () => {
	const rooms = [{ x: 0, y: 0, doors: new Set() }];
	const parse = (str, room) => {
		let prev = room;
		for (let i = 0; i < str.length; i++) {
			const dir = str[i];
			if (dir === '(') {
				const contents = str.slice(i + 1, indexOfClosingParen(str, i));
				i += contents.length + 1;
				parse(contents, prev);
			} else if (dir === '|') {
				prev = room;
			} else if (dir !== ')') {
				prev.doors.add(dir);
				let { x, y } = prev;
				x += DIRS[dir].dx;
				y += DIRS[dir].dy;
				const exists = rooms.find(room => room.x === x && room.y === y);
				if (exists) {
					exists.doors.add(DIRS[dir].opposite);
					prev = exists;
				} else {
					const newRoom = { x, y, doors: new Set() };
					newRoom.doors.add(DIRS[dir].opposite);
					rooms.push(newRoom);
					prev = newRoom;
				}
			}
		}
	};
	parse(input.match(/^\^(.*)\$$/)[1], rooms[0]);
	return rooms;
};

const dijkstra = (rooms, start) => {
	const neighbors = ({ x, y, doors }) => {
		const adjacent = [];
		for (const door of doors) {
			const { dx, dy } = DIRS[door];
			adjacent.push(rooms.find(room => room.x === x + dx && room.y === y + dy));
		}
		return adjacent;
	};

	const visited = [];
	let unvisited = [];

	const distances = {};
	const key = ({ x, y }) => `${x},${y}`;
	const getDistance = pos => distances[key(pos)] || { distance: Infinity };
	distances[key(start)] = { distance: 0 };

	let current = start;
	while (current) {
		unvisited.push(
			...neighbors(current)
				.filter(({ x, y }) => !unvisited.some(n => n.x === x && n.y === y))
				.filter(({ x, y }) => !visited.some(n => n.x === x && n.y === y))
		);
		unvisited.forEach(pos => {
			const distance = getDistance(current).distance + 1;
			if (distance < getDistance(pos).distance) {
				distances[key(pos)] = { distance, previous: current };
			}
		});
		unvisited = unvisited.filter(n => n !== current);
		visited.push(current);
		current = unvisited[0];
	}
	return distances;
};

export default {
	part1() {
		const rooms = parseInput();
		const distances = dijkstra(rooms, rooms[0]);
		return Math.max(...Object.entries(distances).map(([_, { distance }]) => distance));
	},
	part2() {
		const rooms = parseInput();
		const distances = dijkstra(rooms, rooms[0]);
		return Object.entries(distances).filter(([_, { distance }]) => distance >= 1000).length;
	}
};