AOC 2022 12

Day12.kt

import se.saidaspen.aoc.util.*

fun main() = Day12.run()

object Day12 : Day(2022, 12) {

    private val map = toMap(input)
    private fun costOf(b: Pair<Int, Int>, a: Pair<Int, Int>) =  (map[b]!!.code - 'a'.code) - (map[a]!!.code - 'a'.code)
    private val startPos = map.entries.first { it.value == 'S' }.key
    private val endPos = map.entries.first { it.value == 'E' }.key
    init {
        map[startPos] = 'a'
        map[endPos] = 'z'
    }

    override fun part1() =  search(startPos).second

    override fun part2(): Any {
        val candidateStarts = map.entries.filter { it.value == 'a' }.map { it.key }
        return candidateStarts.map { search(it) }.filter { it.first != null }.minOf { it.second }
    }

    private fun search(s: P<Int, Int>) = bfs(s, { it == endPos }, { t ->
        t.neighborsSimple().filter { map.containsKey(it) }
            .filter { costOf(it, t) <= 1 }
            .toMutableList()
    })
}


 // --------------- But these functions I already have in my util library :)
 
inline fun <State> bfs(start: State, isEnd: (State) -> Boolean, next: (State) -> Iterable<State>): Pair<State?, Int> {
    val seen = mutableSetOf(start)
    var queue = mutableListOf(start)
    var nextQueue = mutableListOf<State>()
    var dist = -1

    while (queue.isNotEmpty()) {
        dist++
        for (current in queue) {
            if (isEnd(current)) return current to dist
            for (i in next(current)) {
                if (seen.add(i))
                    nextQueue.add(i)
            }
        }
        val p = nextQueue
        nextQueue = queue
        queue = p
        nextQueue.clear()
    }
    return null to dist
}

fun Pair<Int, Int>.neighborsSimple() = listOf(
    this + P(-1, 0),
    this + P(0, -1),
    this + P(0, 1),
    this + P(1, 0))

fun toMap(input: String): MutableMap<P<Int, Int>, Char> {
    val lines = input.lines()
    val map = mutableMapOf<P<Int, Int>, Char>()
    for (line in lines.indices) {
        val lineChars = lines[line].toCharArray()
        for (col in lineChars.indices) {
            map[P(col, line)] = lineChars[col]
        }
    }
    return map
}