Jon Bristow

Posted on

# Advent of Code 2019 Solution Megathread - Day 20: Donut Maze

Do you know what's better than one kind of interpreter? Two kinds of interpreter!

### Day 20 - The Problem

We safely finished testing our tractor beam and have landed on Pluto to do some exploring.

Part 1 needs us to find the best path through a maze with warp tiles. Man, those Plutonians (Plutoids?) were good at using minimal space!

Part 2 reveals that the warp tiles actually move us up and down through recursive space, and we need to find the shortest path into a recursively generated maze.

### Ongoing Meta

If you were part of Ryan Palo's leaderboard last year, you're still a member of that!

I'll edit in any leaderboards that people want to post, along with any description for the kinds of people you want to have on it. (My leaderboard is being used as my office's leaderboard.) And if I get something wrong, please call me out or message me and I’ll fix it ASAP.

There's no limit to the number of leaderboards you can join, so there's no problem belonging to a "Beginner" and a language specific one if you want.

Jon Bristow • Edited

Dirty simple kotlin solution for part 1...

``````import arrow.core.None
import arrow.core.Option
import arrow.core.extensions.list.functorFilter.filter
import arrow.core.some
import arrow.core.toOption
import java.nio.file.Files
import java.nio.file.Paths

object Day20 {
private const val FILENAME = "src/main/resources/day20.txt"

fun part1(input: List<String>) {
val width = input.map {
it.split(regex = """[^.#]+""".toRegex()).filterNot(String::isEmpty).map(String::length)
}.filter { it.size > 1 }.flatten().toSet().first()

val bottomRight = Point(
input.map { it.drop(2).dropLast(2).length }.max()!!,
input.drop(2).dropLast(2).size
)
val raw = input.drop(2).dropLast(2).map { it.drop(2) }.pointSet()
val rawMap = raw.map { p ->
p to allDirections().map(p::inDirection).filter { it in raw }
}.toMap()
val horizontalLeftWarps =
input.drop(2)
.map { it.take(2).trim() }.withIndex()
.filter { it.value.isNotEmpty() && it.value.none { c -> c in " .#" } }
.map { it.value to Point(0, it.index) } +
input.drop(2).dropLast(2)
.map { it.drop(bottomRight.x - width).take(2).trim() }.withIndex()
.filter { it.value.isNotEmpty() && it.value.none { c -> c in " .#" } }
.map { it.value to Point(bottomRight.x - width, it.index) }

val horizontalRightWarps =
input.drop(2).dropLast(2)
.map { it.take(width + 4).takeLast(2).trim() }.withIndex()
.filter { it.value.isNotEmpty() && it.value.none { c -> c in " .#" } }
.map { it.value to Point(width - 1, it.index) } +
input.drop(2).dropLast(2)
.map { it.takeLast(2).trim() }.withIndex()
.filter { it.value.isNotEmpty() && it.value.none { c -> c in " .#" } }
.map { it.value to Point(bottomRight.x - 1, it.index) }

val verticalTopWarps =
input[0].drop(2).withIndex()
.filter { it.value != ' ' }
.map { IndexedValue(index = it.index, value = "\${it.value}\${input[1].drop(2)[it.index]}") }
.map { it.value to Point(it.index, 0) } +
input[input.lastIndex - 3 - width].drop(2).withIndex()
.filter { it.value !in " .#" }
.map {
IndexedValue(
index = it.index,
value = "\${it.value}\${input[input.lastIndex - width - 2].drop(2)[it.index]}"
)
}
.map { it.value to Point(it.index, bottomRight.y - width) }

val verticalBottomWarps =
input[width + 2].drop(2).withIndex()
.filter { it.value !in " #." }
.map { IndexedValue(index = it.index, value = "\${it.value}\${input[width + 3].drop(2)[it.index]}") }
.map { it.value to Point(it.index, width - 1) } +
input[input.lastIndex - 1].drop(2).withIndex()
.filter { it.value !in " #." }
.map {
IndexedValue(
index = it.index,
value = "\${it.value}\${input[input.lastIndex].drop(2)[it.index]}"
)
}.map { it.value to Point(it.index, bottomRight.y - 1) }

val (endpoints, allWarpsRaw) =
(verticalTopWarps + verticalBottomWarps + horizontalLeftWarps + horizontalRightWarps)
.partition { it.first in listOf("AA", "ZZ") }
val allWarps = allWarpsRaw.filter { ' ' !in it.first }.groupBy { it.first }
.mapValues { it.value.map { v -> v.second } }

val warpedMap = rawMap + allWarps.flatMap { (k, v) ->
val a = v[0]
val b = v[1]
listOf(
a to ((rawMap[a] ?: error("Couldn't find \$a in rawMap")) + b),
b to ((rawMap[b] ?: error("Couldn't find \$b in rawMap")) + a)
)
}
val shortest = djikstra(warpedMap, endpoints[0].second, endpoints[1].second)
println("dist")
println(shortest)

}
}

private fun List<String>.pointSet(yOffset: Int = 0, xOffset: Int = 0): Set<Point> {
return this.asSequence().withIndex().flatMap { (y, line) ->
line.withIndex().asSequence().filterMap { (x, c) ->
when (c) {
'.' -> Point(x + xOffset, y + yOffset).some()
else -> None
}
}
}.toSet()
}

fun main() {
Day20.part1(Day20.fileData)
}

tailrec fun djikstra(
map: Map<Point, List<Point>>,
start: Point,
end: Point,
q: Set<Point> = map.keys,
dist: Map<Point, Int> = mapOf(start to 0),
prev: Map<Point, Point> = emptyMap()
): Option<Int> = when {
q.isEmpty() -> None
else -> when (val u = q.filter { it in dist }.minBy { dist[it]!! }!!) {
end ->
dist[u].toOption()
else -> {
q.filter { it in (map[u] ?: emptyList()) }
.filter { v -> v !in dist || ((dist[u] ?: 0) + 1) < dist[v]!! }
djikstra(
map,
start,
end,
q - u,
dist + updates.map { it to dist[u]!! + 1 },
prev + updates.map { it to u })
}
}
}
``````

Jon Bristow

I'm not proud, part 2 is basically just part 1 with the ability to move up and down levels.

I let it run overnight to get my answer. :-\

Neil Gall • Edited

Ok time to do something different. I've done part 1 for this one in Rust! Scanning the maze for the labels was the tricky bit as I just did a row-by-row scan looking for capital letters. The route finding was easy - just count portal partners as neighbours and do a standard flood-fill or dijkstra type search.

``````
fn neighbours(&self, pos: &Pos) -> Vec<Pos> {
let mut ns = Vec::new();
for dir in Dir::iter() {
match self.go(&pos, dir) {
Some(p) => ns.push(p),
None => {}
}
}
match self.portals.get(pos) {
Some(p) => ns.push(*p),
None => {}
}
ns
}

fn find_routes(&self) -> Vec<Route> {
self.search(&self.start, &HashSet::new())
}

fn search(&self, pos: &Pos, visited: &HashSet<Pos>) -> Vec<Route> {
let mut routes: Vec<Route> = Vec::new();
if *pos == self.end {
routes.push(Route::new());
} else {
for n in self.neighbours(pos) {
if self[&n] == '.' && !visited.contains(&n) {
let mut v = visited.clone();
v.insert(n);
self.search(&n, &v).into_iter().for_each(|mut r| {
routes.push(r)
});
}
}
}
routes
}
``````

Full code here. I'll come back for part 2.

Joana Borges Late
``````"use strict"

// solving the puzzle takes (my computer) 0.045s

// this program treats the nearest walkable spot to a portal as the portal  //

const map = [ ]

var WIDTH = 0
var HEIGHT = 0

const PORTALS = { } // name-without-level: row, col, trips

const positionsWithPortal = { } // row~col: name-without-level

function main() {

processInput()

findPortalTrips()

findLandTrips()

// show()
}

///////////////////////////////////////////////////////////

function processInput() {

const lines = input.split("\n")

for (const line of lines) {

if (line != "") { map.push(line.split("")) }
}

WIDTH = map[0].length
HEIGHT = map.length
}

for (let row = 2; row < HEIGHT - 2; row++) { // skips margin

for (let col = 2; col < WIDTH - 2; col++) { // skips margin

if (map[row][col] != ".") { continue }

let count = 0

count += checkNeighbor(row, col, -1, 0)
count += checkNeighbor(row, col, +1, 0)
count += checkNeighbor(row, col, 0, -1)
count += checkNeighbor(row, col, 0, +1)

if (count > 2) { deadEnds.push(createPoint(row, col)) }
}
}
}

function checkNeighbor(baseRow, baseCol, deltaRow, deltaCol) {

const row = baseRow + deltaRow
const col = baseCol + deltaCol

const item =  map[row][col]

if (item == "#") { return 1 }
if (item == " ") { return 1 } // unreachable by "." neighbor
if (item == ".") { return 0 }

// got letter

let portal = ""

if (deltaRow == -1) {
portal = map[row-1][col] + item
}
else if (deltaCol == -1) {
portal = map[row][col-1] + item
}
else if (deltaRow == +1) {
portal = item + map[row+1][col]
}
else { // if (deltaCol == +1) {
portal = item + map[row][col+1]
}

const isExternal = (baseRow == 2  ||  baseRow == HEIGHT - 3  ||  baseCol == 2  ||  baseCol == WIDTH - 3)

portal += isExternal ? "e" : "i"

PORTALS[portal] = createPortal(baseRow, baseCol)

positionsWithPortal[baseRow + "~" + baseCol] = portal

return 0
}

///////////////////////////////////////////////////////////

}
}

if (map[row][col] == "#") { return }

map[row][col] = "#"

}

if (map[row][col] != ".") { return }

let count = 0

if (map[row-1][col] == "#") { count += 1 }
if (map[row+1][col] == "#") { count += 1 }
if (map[row][col-1] == "#") { count += 1 }
if (map[row][col+1] == "#") { count += 1 }

if (count > 2) { deadEnds.push(createPoint(row, col)) }
}

///////////////////////////////////////////////////////////

function findPortalTrips() {

const portals = Object.keys(PORTALS)

for (const portal of portals) {

if (portal == "AAe") { continue }
if (portal == "ZZe") { continue }

const data = PORTALS[portal]

const a = portal.substr(0, 2)

const b = (portal[2] == "i") ? "e" : "i"

const destiny = a + b

const levelChange = (portal.endsWith("i")) ? +1 : -1

data.trips.push(createTrip(destiny, 1, levelChange))
}
}

///////////////////////////////////////////////////////////

function findLandTrips() {

const portals = Object.keys(PORTALS)

for (const portal of portals) {

const data = PORTALS[portal]

const trips = explore(data.row, data.col)

for (const trip of trips) { data.trips.push(trip) }
}
}

///////////////////////////////////////////////////////////

function explore(row, col) {

const myTrips = [ ]

let futurePoints = [ createPoint(row, col) ]

const walkTable = new Uint8Array(WIDTH * HEIGHT)

const index = row * WIDTH + col

walkTable[index] = 1

let distance = 0

while (true) {

const currentPoints = futurePoints

futurePoints = [ ]

for (const point of currentPoints) {

const row = point.row
const col = point.col

grabNeighbor(row-1, col)
grabNeighbor(row+1, col)
grabNeighbor(row, col-1)
grabNeighbor(row, col+1)
}

if (futurePoints.length == 0) { return myTrips }

distance += 1
}

function grabNeighbor(row, col) {

if (row < 0) { return }
if (col < 0) { return }

if (row >= HEIGHT) { return }
if (col >= WIDTH)  { return }

const index = row * WIDTH + col

if (walkTable[index] == 1) { return }

walkTable[index] = 1 // touched

const symbol = map[row][col]

if (symbol != ".") { return }

const point = createPoint(row, col)

futurePoints.push(point)

const coord = row + "~" + col

const portal = positionsWithPortal[coord]

if (portal == undefined) { return }

if (portal == "AAe") { return } // filtered!

myTrips.push(createTrip(portal, distance + 1, 0))
}
}

///////////////////////////////////////////////////////////

function findBestDistance() {

const reserved = { "AAe~0": true }

const currentNodes = [ createNode("AAe~0", 0) ]

while (currentNodes.length > 0) {

const closest = extractClosestNode(currentNodes)

if (closest.portal == "ZZe~0") { return closest.distance }

const core = closest.portal.substr(0, 3)

const level = parseInt(closest.portal.substr(4))

for (const trip of PORTALS[core].trips) {

const newLevel = level + trip.levelChange

if (newLevel < 0) { continue }

const newSpot = trip.destiny + "~" + newLevel

if (reserved[newSpot]) { continue }

reserved[newSpot] = true

const newDistance = closest.distance + trip.distance

const newNode = createNode(newSpot, newDistance)

currentNodes.push(newNode)
}
}

console.log("could not reach target")
Deno.exit()
}

function extractClosestNode(nodes) { // expects nodes is not empty

let bestNode = nodes[0]
let bestIndex = 0

let n = 0

while (true) {

n += 1

const candidate = nodes[n]

if (candidate == undefined) { break }

if (candidate.distance < bestNode.distance) { bestNode = candidate; bestIndex = n }
}

nodes.splice(bestIndex, 1)

return bestNode
}

///////////////////////////////////////////////////////////

function createPoint(row, col) {

return { "row": row, "col": col }
}

function createPortal(row, col) {

return { "row": row, "col": col, "trips": [ ] }
}

function createNode(portal, distance) { // portal-with-level

return { "portal": portal, "distance": distance }
}

function createTrip(destiny, distance, levelChange) {

return { "destiny": destiny, "distance": distance, "levelChange": levelChange }
}

function show() {

console.log("")

console.log("-".repeat(WIDTH + 2))

for (const line of map) { console.log("|" + line.join("") + "|") }

console.log("-".repeat(WIDTH + 2))

console.log("")
}

main()

``````

Neil Gall

Part 2 of this one has me quite confused. The level shifting seems straightforward but the example given has the possibility to loop ever deeper into the maze, which you have to detect and prevent. I've tried various ideas of checking past transits through the same portal in the same direction for equally spaced level deltas, etc., but I seem to be closing off valid routes and exiting the search without an answer. I think I'm missing some important detail of the representation of the portals that would make things much simpler. Any tips?