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

Dev.to List of Leaderboards

• 120635-5c140b9a - provided by Linda Thompson

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

If you want me to add your leaderboard code to this page, reply to one of these posts and/or send me a DM containing your code and any theming or notes you’d like me to add. (You can find your private leaderboard code on your "Private Leaderboard" page.)

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.

Comments

[Jon Bristow]

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.extensions.sequence.monadFilter.filterMap
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"
    val fileData get() = Files.readAllLines(Paths.get(FILENAME))

    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 -> {
            val updates =
                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]

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| {
                        r.add(&pos);
                        routes.push(r)
                    });
                }
            }
        }
        routes
    }

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

[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?

[Joana Borges Late]

Solving part 2 in 45ms - JavaScript

"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 deadEnds = [ ]

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

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


function main() {

    processInput()

    findPortalsAndDeadEnds() 

    blockDeadEnds()

    findPortalTrips()

    findLandTrips()

 // show()  
    console.log("the answer is", findBestDistance())
}

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

function processInput() {

    const input = Deno.readTextFileSync("input.txt")

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

    for (const line of lines) { 

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

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

function findPortalsAndDeadEnds() {

    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
}

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

function blockDeadEnds() {

    while (deadEnds.length > 0) {

        const point = deadEnds.shift()

        blockDeadEnd(point.row, point.col) 
    }
}

function blockDeadEnd(row, col) {

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

    map[row][col] = "#"

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

function blockIfDeadEnd(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()