DEV Community

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

Collapse
 
yuriykulikov profile image
Yuriy Kulikov

Interesting and challenging problem today. I went for a parent-to-children map for the first part and a tree for the second. Runs within a couple of milliseconds.

Part 1:

    private fun parseMap(input: String): Map<String, List<String>> = input.lines()
            .map { line -> line.substringBefore(")") to line.substringAfter(")") }
            .groupBy(
                    { (name, _) -> name },
                    { (_, orbitedBy) -> orbitedBy }
            )

    private fun calculateAllOrbits(map: Map<String, List<String>>): Int {
        fun List<String>.recursiveSearch(level: Int): Int {
            return map { name ->
                map.getOrDefault(name, emptyList()).recursiveSearch(level + 1)
            }.sum() + level + size
        }

        return map.getValue("COM").recursiveSearch(-1) + 1
    }

Part 2:

private fun parseTree(input: String): Map<String, String> {
        return input.lines()
                .map { line -> line.substringAfter(")") to line.substringBefore(")") }
                .toMap()
    }

    private fun stepsToSanta(tree: Map<String, String>): Int {
        fun String.toRoot(): List<String> {
            return tree[this]?.toRoot()?.plus(this) ?: listOf(this)
        }

        val you = "YOU".toRoot()
        val san = "SAN".toRoot()
        val common = you.intersect(san)
        val path = you.plus(san.reversed()).minus(common)
        return path.size - 2
    }