Discussion on: Advent of Code 2019 Solution Megathread - Day 6: Universal Orbit Map

[Jon Bristow]

Without embarrassment, I show this code to you. Part 1 takes a few minutes to complete. I will respond with an optimized version later.

import java.nio.file.Files
import java.nio.file.Paths
import java.util.*

object Day06 {

    const val FILENAME = "src/main/resources/day06.txt"

    fun parseOrbit(s: String): Pair<String, String> {
        return """(.*)\)(.*)""".toRegex().matchEntire(s)?.let {
            it.groupValues[1] to it.groupValues[2]
        } ?: throw Error("Bad orbit: $s")
    }

    fun part1(): Int {

        return Files.readAllLines(Paths.get(FILENAME))
            .map(::parseOrbit).fold(mutableMapOf<String, MutableSet<String>>()) { m, (a, b) ->
                val nset = (m[a] ?: mutableSetOf())
                nset.add(b)
                m[a] = nset
                m
            }.countChildren()
    }

    fun part2(): Int {
        val paths = Files.readAllLines(Paths.get(FILENAME))
            .map(::parseOrbit).fold(mutableMapOf<String, Set<String>>()) { m, (a, b) ->
                m[a] = (m[a] ?: emptySet()) + b
                m
            }

        val youParents = paths.filterValues { "YOU" in it }.keys.map { it to 0 }

        return paths.findDistanceToSan(queue = LinkedList(youParents), seen = setOf("YOU"))
    }

    private tailrec fun MutableMap<String, Set<String>>.findDistanceToSan(
        queue: Deque<Pair<String, Int>>,
        seen: Set<String>
    ): Int {
        val (node, dist) = queue.pop()
        return when (node) {
            "SAN" -> dist - 1
            in seen -> findDistanceToSan(queue, seen)
            else -> {
                queue.addAll(filterValues { node in it }.keys.map { it to (dist + 1) })
                queue.addAll(filterKeys { node == it }.flatMap { (k, v) -> v.map { it to (dist + 1) } })
                findDistanceToSan(LinkedList(queue.filterNot { (n, d) -> n in seen }), seen + node)
            }
        }
    }


}

private fun MutableMap<String, MutableSet<String>>.countChildren() =
    toList().indices.fold(toMap()) { m, _ ->
        m.mapValues { (k, v) ->
            v.addAll(v.flatMap { this[it] ?: mutableSetOf() })
            v
        }
    }.toList().sumBy { (k, v) -> v.size }

fun main() {
    println(Day06.part1())
    println(Day06.part2())
}

Part 2 was my old friend "Djikstra's Algorithm". It wasn't enough data to warrant breaking out A*Search, but if previous years are any indication we will probably need it at some point.

[Jon Bristow]

Ahhh... much better. This runs in msecs.

import java.nio.file.Files
import java.nio.file.Paths
import java.util.*

object Day06 {

    private const val FILENAME = "src/main/resources/day06.txt"

    private fun parseOrbit(s: String): Pair<String, String> {
        return """(.*)\)(.*)""".toRegex().matchEntire(s)?.let {
            it.groupValues[1] to it.groupValues[2]
        } ?: throw Error("Bad orbit: $s")
    }


    private fun List<String>.countPaths() =
        map(::parseOrbit).fold(mapOf<String, Set<String>>()) { m, (a, b) ->
            val nset = (m[a] ?: emptySet()) + b
            m + (a to nset)
        }.let { orbits ->
            orbits.countChildren(orbits["COM"].orEmpty().map { it to 1 }, 0)
        }

    private tailrec fun Map<String, Set<String>>.countChildren(
        paths: List<Pair<String, Int>>,
        size: Int
    ): Int {

        val nextPaths = paths.flatMap {
            this[it.first].orEmpty().map { c -> c to it.second + 1 }
        }
        return when {
            nextPaths.isEmpty() -> size + paths.sumBy(Pair<String, Int>::second)
            else -> countChildren(nextPaths, size + paths.sumBy(Pair<String, Int>::second))
        }

    }

    private fun List<String>.shortestDistanceToSanta(): Int {
        val paths = map(::parseOrbit).fold(mutableMapOf<String, Set<String>>()) { m, (a, b) ->
            m[a] = (m[a] ?: emptySet()) + b
            m
        }

        val youParents = paths.filterValues { "YOU" in it }.keys.map { it to 0 }

        return paths.findDistanceToSan(queue = LinkedList(youParents), seen = setOf("YOU"))

    }

    private tailrec fun MutableMap<String, Set<String>>.findDistanceToSan(
        queue: Deque<Pair<String, Int>>,
        seen: Set<String>
    ): Int {
        val (node, dist) = queue.pop()
        return when (node) {
            "SAN" -> dist - 1
            in seen -> findDistanceToSan(queue, seen)
            else -> {
                queue.addAll(filterValues { node in it }.keys.map { it to (dist + 1) })
                queue.addAll(filterKeys { node == it }.flatMap { (_, v) -> v.map { it to (dist + 1) } })
                findDistanceToSan(LinkedList(queue.filterNot { (n, _) -> n in seen }), seen + node)
            }
        }
    }

    fun part1() = Files.readAllLines(Paths.get(FILENAME)).countPaths()

    fun part2(): Int = Files.readAllLines(Paths.get(FILENAME)).shortestDistanceToSanta()

}


fun main() {
    println(Day06.part1())
    println(Day06.part2())
}