loading...
Cover image for Advent of Code 2019 Solution Megathread - Day 20: Donut Maze

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

jbristow profile image Jon Bristow ・1 min read

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

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.

Discussion

pic
Editor guide
Collapse
jbristow profile image
Jon Bristow Author

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 })
        }
    }
}
Collapse
jbristow profile image
Jon Bristow Author

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. :-\

Collapse
neilgall profile image
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.

Collapse
neilgall profile image
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?