Day 20 - Donut Maze - Code
You notice a strange pattern on the surface of Pluto and land nearby to get a closer look. Upon closer inspection, you realize you've come across one of the famous space-warping mazes of the long-lost Pluto civilization!
Because there isn't much space on Pluto, the civilization that used to live here thrived by inventing a method for folding spacetime. Although the technology is no longer understood, mazes like this one provide a small glimpse into the daily life of an ancient Pluto citizen.
This maze is shaped like a donut. Portals along the inner and outer edge of the donut can instantly teleport you from one side to the other. For example:
A
A
#######.#########
#######.........#
#######.#######.#
#######.#######.#
#######.#######.#
##### B ###.#
BC...## C ###.#
##.## ###.#
##...DE F ###.#
##### G ###.#
#########.#####.#
DE..#######...###.#
#.#########.###.#
FG..#########.....#
###########.#####
Z
Z
This map of the maze shows solid walls (#) and open passages (.). Every maze on Pluto has a start (the open tile next to AA) and an end (the open tile next to ZZ). Mazes on Pluto also have portals; this maze has three pairs of portals: BC, DE, and FG. When on an open tile next to one of these labels, a single step can take you to the other tile with the same label. (You can only walk on . tiles; labels and empty space are not traversable.)
One path through the maze doesn't require any portals. Starting at AA, you could go down 1, right 8, down 12, left 4, and down 1 to reach ZZ, a total of 26 steps.
However, there is a shorter path: You could walk from AA to the inner BC portal (4 steps), warp to the outer BC portal (1 step), walk to the inner DE (6 steps), warp to the outer DE (1 step), walk to the outer FG (4 steps), warp to the inner FG (1 step), and finally walk to ZZ (6 steps). In total, this is only 23 steps.
Here is a larger example:
A
A
#################.#############
#.#...#...................#.#.#
#.#.#.###.###.###.#########.#.#
#.#.#.......#...#.....#.#.#...#
#.#########.###.#####.#.#.###.#
#.............#.#.....#.......#
###.###########.###.#####.#.#.#
#.....# A C #.#.#.#
####### S P #####.#
#.#...# #......VT
#.#.#.# #.#####
#...#.# YN....#.#
#.###.# #####.#
DI....#.# #.....#
#####.# #.###.#
ZZ......# QG....#..AS
###.### #######
JO..#.#.# #.....#
#.#.#.# ###.#.#
#...#..DI BU....#..LF
#####.# #.#####
YN......# VT..#....QG
#.###.# #.###.#
#.#...# #.....#
###.### J L J #.#.###
#.....# O F P #.#...#
#.###.#####.#.#####.#####.###.#
#...#.#.#...#.....#.....#.#...#
#.#####.###.###.#.#.#########.#
#...#.#.....#...#.#.#.#.....#.#
#.###.#####.###.###.#.#.#######
#.#.........#...#.............#
#########.###.###.#############
B J C
U P P
Here, AA has no direct path to ZZ, but it does connect to AS and CP. By passing through AS, QG, BU, and JO, you can reach ZZ in 58 steps.
In your maze, how many steps does it take to get from the open tile marked AA to the open tile marked ZZ?
Your puzzle answer was 608.
Straightforward Dijkstra's algorithm. Only thing unique is the input conversion, which we'll get to at the end. Here's the gist of the code:
Note: Ignore all references about isInner. That's a concept for problem 20b.
export interface IMaze {
name: string;
grid: string[][];
entrance: IPoint;
exit: IPoint;
portals: Map<string, [IPoint, IPoint] | [IPoint]>;
portalLocations: Map<string, {key: string; isInner: boolean}>; // key is IPoint in toString()
}
export const entranceKey = 'AA';
export const exitKey = 'ZZ';
const toGraph = ({entrance, exit, grid, portals, portalLocations}: IMaze) => {
const graph = new WGraph<string, number>();
const queue = new PriorityQueue<{at: IPoint; lastPortal: string; steps: number}>(p => -1 * p.steps);
const visited = new Map<string, number>(); // IPoint -> distance from entrance
const isValid = makeIsValid(grid, entrance);
queue.enqueue({at: entrance, steps: 0, lastPortal: entranceKey});
visited.set(toKey(entrance), 0);
while (!queue.isEmpty()) {
const { at, steps, lastPortal } = queue.dequeue()!;
if (equals(at, exit))
break; // done
// we don't check visited here because we may want to revisit a visited node if the steps are shorter
// neighbors are reachable dots (.), some of which may be portals
const neighbors = getNeighbors(at).filter(isValid);
for (const neighbor of neighbors) {
const neighborStr = toKey(neighbor);
const newSteps = steps + 1;
if (!visited.has(neighborStr) || visited.get(neighborStr)! > newSteps) {
const neighborAtPortal = portalLocations.get(neighborStr);
if (neighborAtPortal != null) {
const neighborPortalName = neighborAtPortal.key;
if (neighborPortalName === lastPortal)
continue;
const portalTo = first(portals.get(neighborPortalName)!.filter(p => !equals(p, neighbor)));
queue.enqueue({
at: portalTo ?? neighbor, // possible if portal === 'ZZ'
lastPortal: neighborPortalName,
steps: newSteps + 1
});
graph.addDirectedEdge(lastPortal, neighborPortalName, newSteps);
visited.set(toKey(portalTo), newSteps);
}
else {
queue.enqueue({
at: neighbor,
lastPortal: lastPortal,
steps: newSteps
});
}
visited.set(neighborStr, newSteps);
}
}
}
return graph;
};
export const run = () => {
const sims = getSimulations();
for (const s of sims) {
console.log(timer.start(`20 - ${s.name}`));
const graph = toGraph(s);
console.log(graph.toString(n => n?.toString() ?? ''));
console.log(timer.stop());
}
};The auxiliary method to convert the graph into an IMaze is as follows (ignore the isInner stuff):
// when it lands on a dot (.), it checks if the two squares in direction X are both letters.
// If letters, then we know the dot (.) is a portal.
const toMaze = ({name, grid}: {name: string; grid: string[][]}): IMaze => {
const isInner = makeIsInner(grid);
const getKey = (i: number, j: number) => {
if (/^[A-Z]$/.test(grid[i - 1]?.[j]) && grid[i - 2]?.[j] === '.')
return {
key: grid[i - 1][j] + grid[i][j],
forPoint: { col: j, row: i - 2 },
isInner: isInner(i - 2, j, true)
};
if (/^[A-Z]$/.test(grid[i + 1]?.[j]) && grid[i + 2]?.[j] === '.')
return {
key: grid[i][j] + grid[i + 1][j],
forPoint: { col: j, row: i + 2 },
isInner: isInner(i + 2, j, true)
};
if (/^[A-Z]$/.test(grid[i]?.[j - 1]) && grid[i]?.[j - 2] === '.')
return {
key: grid[i][j - 1] + grid[i][j],
forPoint: { col: j - 2, row: i },
isInner: isInner(i, j - 2, false)
};
if (/^[A-Z]$/.test(grid[i]?.[j + 1]) && grid[i]?.[j + 2] === '.')
return {
key: grid[i][j] + grid[i][j + 1],
forPoint: { col: j + 2, row: i },
isInner: isInner(i, j + 2, false)
};
return { key: null, forPoint: null, isInner: false };
};
const portals = new Map<string, [IPoint, IPoint] | [IPoint]>();
const portalLocations = new Map<string, {key: string; isInner: boolean}>();
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[i].length; j++) {
if (!/^[A-Z]$/.test(grid[i]?.[j]))
continue;
const { key, forPoint, isInner } = getKey(i, j);
if (key == null || forPoint == null)
continue;
portalLocations.set(toKey(forPoint), {key, isInner});
if (portals.has(key))
portals.get(key)!.push(forPoint);
else
portals.set(key, [forPoint]);
}
}
return {
name,
grid,
portals,
portalLocations,
entrance: first(portals.get(entranceKey)!),
exit: first(portals.get(exitKey)!)
};
};