<Advent of Code 2025 day 11> (spoilers) :thread:

# advent-of-code

[Advent of Code 2023 day 11]

Advent of Code 2025 day 11 (spoilers) 🧵

[Marcin Wisniowski]

After the last two hard days, this one was a breather.

[Marcin Wisniowski]

image.png

[Michael de Kaste]

Simple memoization today

Untitled.kt

[Jakub Gwóźdź]

super happy to have a no-brainer today

fun outputs(data: String) = data.reader().readLines().associate {
    it.split(":")
        .let { (device, outputs) -> device to outputs.split(' ').map(String::trim).filterNot(String::isBlank) }
}

fun dfs(end: String, start: String, graph: Map<String, List<String>>): Long {
    val cache = mutableMapOf<String, Long>()
    fun search(id: String): Long = graph[id].orEmpty().sumOf { i ->
        if (i == start) 1 else cache.getOrPut(i) { search(i) }
    }
    return search(end)
}

fun part1(data: String): Any {
    val inputs = outputs(data)
    return dfs("you", "out", inputs)
}

fun part2(data: String): Any {
    val inputs = outputs(data)
    return dfs("svr", "fft", inputs) * dfs("fft", "dac", inputs) * dfs("dac", "out", inputs) +
            dfs("svr", "dac", inputs) * dfs("dac", "fft", inputs) * dfs("fft", "out", inputs)

}

[Dan Fingal-Surma]

Got it right away modulo Int -> Long https://github.com/dfings/advent-of-code/blob/main/src/2025/problem_11.main.kts

[Dan Fingal-Surma]

Actually those ifs are redundant

[ephemient]

I was expecting that we might get hit by cycles but I didn't add any cycle detection and it all worked out

Day11.kt

[Dan Fingal-Surma]

Ah multiplying partial path counts, interesting

[Norbert Kiesel]

These recursive solutions look really nice. My solution is iterative but that makes the code a bit longer.

[phldavies]

Refreshing after yesterday.
I missed the "in any order" and just did svr-fft-dac-out and still got the right answer it seems.

y25d11.kt

[Dan Fingal-Surma]

It’s one or the other 🙂

[Michael de Kaste]

if both existed, solution would be ∞

[ephemient]

if "path" as defined to not repeat vertices (as is the typical convention in graph theory), no it is not infinite. but it does slightly complicate the solution

[phldavies]

ah I have no paths from dac to fft

[Dan Fingal-Surma]

Yeah no cycles

[Michael Böiers]

Short and sweet again 🙂

fun main() {
    val links = generateSequence(::readLine).associate { line -> line.split(": ").let { it[0] to it[1].split(" ") } }

    val cache = mutableMapOf<Pair<String, Set<String>>, Long>()

    fun String.findOut(visit: Set<String> = setOf(), seen: Set<String> = setOf()): Long = cache.getOrPut(this to seen) {
        when {
            this == "out" -> if (seen == visit) 1 else 0
            else -> links.getValue(this).sumOf { it.findOut(visit, if (it in visit) seen + it else seen) }
        }
    }

    println("you".findOut())
    println("svr".findOut(setOf("fft", "dac")))
}

[Andriy]

I didn't immediately figure out how to optimize path tracking via memoization:

companion object Part2 {
    const val START = "svr"
    const val POINT1 = "dac"
    const val POINT2 = "fft"
    const val END = "out"
}

fun solvePart2(): Long {

    data class Path(val start: String, val notPass: Set<String>, val end: String)

    val memo = mutableMapOf<Path, Long>()

    fun track(state: Path): Long {
        if (state.start == state.end) return 1
        if (state.start in state.notPass) return 0

        val next = graph[state.start]!!
        return next.sumOf {
            val newState = Path(it, state.notPass, state.end)
            memo.getOrPut(newState) { track(newState) }
        }
    }

    val part1 =
        track(Path(start = START, notPass = setOf(POINT2, END), end = POINT1)) *
        track(Path(start = POINT1, notPass = setOf(START, END), end = POINT2)) *
        track(Path(start = POINT2, notPass = setOf(START, POINT1), end = END))

    val part2 =
        track(Path(start = START, notPass = setOf(POINT1, END), end = POINT2)) *
        track(Path(start = POINT2, notPass = setOf(START, END), end = POINT1)) *
        track(Path(start = POINT1, notPass = setOf(START, POINT2), end = END))

    return part1 + part2
}