Kotlin

This was substantially easier than yesterday’s problem. Especially considering I still haven’t done Part 2 from yesterday.

Anyway, here is my Part 2 solution for today. Given how quickly Part 1 ran without a cache, I didn’t think Part 2 would be much different, until my computer fans spun up and stayed there for over a minute. So I added a cache and re-ran it and it ran in 31ms.

const val end = "out"
var map: Map<String, List<String>>? = null
val problemVertices = "dac" to "fft"
val cache: MutableMap<Pair<String, Pair<Boolean, Boolean>>, Long> = mutableMapOf()

fun main() {
    val input = getInput(11)
    map = parseInput1(input)
    val total = countPaths2("svr", false to false).first
    println(total)
}

fun countPaths2(vertex: String, problemVerticesEncountered: Pair<Boolean, Boolean>): Pair<Long, Pair<Boolean, Boolean>> {
    val otherVertices = map!![vertex]!!
    var total = 0L
    val nextProblemVerticesEncountered =
        (problemVerticesEncountered.first || vertex == problemVertices.first) to (problemVerticesEncountered.second || vertex == problemVertices.second)
    for (otherVertex in otherVertices) {
        val key = otherVertex to nextProblemVerticesEncountered
        if (cache.contains(key)) {
            total += cache[key]!!
        } else if (otherVertex == end) {
            if (nextProblemVerticesEncountered.first && nextProblemVerticesEncountered.second) {
                total++
            }
        } else {
            total += countPaths2(otherVertex, nextProblemVerticesEncountered).first
        }
    }
    cache[vertex to nextProblemVerticesEncountered] = total
    return total to nextProblemVerticesEncountered
}


fun parseInput1(input: String): Map<String, List<String>> = input.lines()
    .filter { it.isNotBlank() }
    .associate {
        val split = it.split(": ")
        split[0] to split[1].split(" ").toList()
    }