https://kotlinlang.org logo
Join SlackCommunities
Powered by
<Advent of Code 2021 day 12> :thread:
# advent-of-code
a
m
j
Pretty happy today
d
@Michael Böiers - I can't follow the overloaded 
map
m
@David Whittaker Good point! Refactored it a little more 🙂
k
e
https://github.com/ephemient/aoc2021/blob/main/kt/src/commonMain/kotlin/com/github/ephemient/aoc2021/Day12.kt non-recursive, using 
Int
as a bitset again (including using the high bit for part 2)
m
build up graph from input and then just a recursive walk through it. I quite like making graphs from input because it makes the whole program very readable to me. Probably should make the visited list a mutable one to speed up https://github.com/mdekaste/AdventOfCode2021/blob/main/src/main/kotlin/year2021/day12/Day12.kt
m
p
Seeing all your solutions of all these days I finally feel like an OOP nerd 😁 https://github.com/PaulWoitaschek/Advent-of-Code-2021/blob/main/src/main/kotlin/aoc/day12/Day12.kt
m
@Paul Woitaschek nice! Brings back memories from the 2000s. Today I just say skip all that ceremony. Later today I’ll try to condense my solution further - the goal is 10 readable loc.😊
p
For these small one time solutions that works. However as part of a larger application I would not like to work with these "one function does anything using only primitive types" functions.
m
I prefer FP these days. Even (much) larger applications ultimately consist of relatively small parts doing the heavy lifting. If this challenge was part of a large application, I would make it a little more generic, but IMHO it doesn't deserve more than 20 loc.
m
Anyone can participate in AoC in whatever way they want. My preference goes out to a combination of readable code and speed. When I look at some of y'alls contribution I think: "Thats fucking sick! Nice job!". But that still wouldn't be how I would like to program it. Every time I need to make a calculation twice I cringe a little inside, knowing that I already calculated something before. Thats just my preference though, I still calculate things FP style; but take some OOP and mutable detours along the way.
🙌 1
m
To me the most impressive solutions represent a sweet spot between elegance, conciseness, performance and readability. In particular, it’s cool when a solution is both very short and very “not clever”.
💯 1
t
Recursion fun! Started very late because of F1 and am myself racing to get out of the house in a couple of minutes. 🙂 ‱ Code ‱ Blog
🙌 1
d
How does the functional solution prevent duplicate paths from being counted?
m
@David Whittaker which one - mine?
d
Any of them really. I can't seem to parse it out. I had to specifically look for duplicates.
m
In mine there can’t really be any duplicates, since the recursion starts with [“start”] and then walks into each available next cave exactly once.
Copy code
fun Set<Set<String>>.findExit(paths: List<String> = listOf("start"), twiceAllowed: Boolean): List<List<String>> {
    val here = paths.last().takeUnless { it == "end" } ?: return listOf(paths)
    val canVisitSmallTwice = twiceAllowed && paths.filter { it.all(Char::isLowerCase) }.let { it == it.distinct() }
    return mapNotNull { rule -> if (rule.contains(here)) rule.single { it != here } else null }
        .filter { if (canVisitSmallTwice) it != "start" else it.any(Char::isUpperCase) || !paths.contains(it) }
        .flatMap { findExit(paths.plus(it), twiceAllowed) }
}
(and btw: I think my solution is currently too terse. The lines are too long, obviously. 🙂)
Improved it a little bit 🙂
Copy code
fun Map<String, Set<String>>.explore(paths: List<String> = listOf("start"), twiceAllowed: Boolean): List<List<String>> {
    val here = paths.last().takeUnless { it == "end" } ?: return listOf(paths)
    val canVisitSmallTwice = twiceAllowed && paths.filter { it == it.lowercase() }.let { it == it.distinct() }
    return getValue(here)
        .filter { if (canVisitSmallTwice) it != "start" else it == it.uppercase() || !paths.contains(it) }
        .flatMap { explore(paths.plus(it), twiceAllowed) }
}
d
May update mine to use a Map<Cave, List<Cave>> rather than List<Edge>
p
d
Did a little cleanup but now happy as is
n
Being able to have named local closures in Kotlin is quite nice; in recursive problems it saves you re-passing the unchanging bits of state over and over
e
what do you mean by that? labeled lambdas, or nested functions? I don't see either in use, so maybe I'm not understanding your message.
n
ah damn I pasted the wrong thing lol
Copy code
typealias Graph = Map<String, List<String>>

fun getInputs(): Graph = (aocDataDir / "2021" / "day12.txt").useLines { lines ->
    mutableMapOf<String, MutableList<String>>().apply {
        lines.forEach { line ->
            val (node1, node2) = line.split("-")
            getOrPut(node1) { mutableListOf<String>() }.add(node2)
            getOrPut(node2) { mutableListOf<String>() }.add(node1)
        }
    }
}

fun Graph.countPaths(canVisitTwice: Boolean): Long {
    val smallCavesVisited = mutableMapOf<String, Int>()

    fun recurse(hasSecondVisit: Boolean, nodeName: String): Long {
        if (nodeName == "end") {
            return 1
        }

        val smallTimesVisited = smallCavesVisited.getOrDefault(nodeName, 0)

        if (smallTimesVisited == 2 || (smallTimesVisited == 1 && (nodeName == "start" || !hasSecondVisit))) {
            return 0
        }

        if (nodeName.toLowerCase() == nodeName) {
            smallCavesVisited.update(nodeName) { (it ?: 0) + 1 }
        }

        val stillHasSecondVisit = hasSecondVisit && smallTimesVisited == 0

        return getValue(nodeName).sumOf { recurse(stillHasSecondVisit, it) }.also {
            smallCavesVisited[nodeName]?.let { smallCavesVisited[nodeName] = it - 1 }
        }
    }

    return recurse(canVisitTwice, "start")
}
e
nested functions compile to function objects just like lambdas do. I wish they'd compile to hidden method with extra parameters (for captures) in the same class instead, which would require less allocation and indirection, but indeed it can be handy
3 Views
Open in Slack
PreviousNext
Powered by