https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2024 day 23> :thread:
# advent-of-code
a
m
Just part 2 for now, I don't trust today being so 'easy'
Day 23 Michael.cpp
d
"The gang implements union find" (haven't otherwise started, we will see when I get time)
k
I know this could be much better, but I need to get some sleep, and do a proper tidying up later
Day23.kt
j
Today was nice, part 2 I first tried to construct the next bigger group via the smaller ones, but noticed that that does not scale. Now it's just a few while loops https://github.com/bulldog98/advent-of-code/blob/main/advent2024/src/main/kotlin/year2024/Day23.kt
j
my initial part2 takes over 5 seconds, so for sure it is bad approach, but hey, it works:
Copy code
typealias Input = Map<String, Set<String>>

fun part2(graph: Input): String {
    val result = mutableSetOf<Set<String>>()
    graph.keys.forEach { result += setOf(it) }
    while (result.size > 1) {
        val newResult = mutableSetOf<Set<String>>()
        val asList = result.toList()
        asList.forEach { s1 ->
            graph.filter { (v,es)-> v !in s1 && es.containsAll(s1) }
                .forEach { newResult += s1 + it.key }
        }
        result.clear()
        result += newResult
    }
    return result.first().sorted().joinToString(",")
}
I tried to do union-find, but feared it might lead to bad results in such graphs:
Copy code
aa-bb
cc-dd
aa-cc
aa-dd
my UF would first group 
aa
with 
bb
, then 
cc
with 
dd
, but not 
aa
-
cc
-
dd
e
Day23.kt once I chose the right representation, it became easy
m
Good enough
e
for me, the right representation was 
mapOf("aa" to setOf("bb", "cc"), "bb" to setOf("cc"), "cc" to setOf())
where the values are limited to those which are lexicographically greater than the key. that means my searching code doesn't have to handle any loops or duplicates
j
oh!
馃檶 1
yeah, great protip, @ephemient! it speeded up my part2 from 5s to 1/5 s 馃檪
b
that took me way longer than it should have
d
Nevermind this is find maximal clique
b
i read the rules wrong in p1, i thought the groups had to be exactly 3
馃憖 1
then i tried to get fancy with sets
d
I love NP complete problems
j
Ok, so my original solution after Ephemient's optimization with pre-sorting vertices got me to 65ms. Now I'm starting to play with Bron-Kerbosch, first unoptimized attempt - 8ms 馃檪
b
simple caching was pretty fast for me
oh wait, i might have broke it on cleanup
ah yea, my pre-cleanup takes 18ms, post cleanup 3m laugh cry face palm
this is my much uglier, but much faster solution
Untitled.kt
Untitled.kt
appologies, struggling with the slack interface at 1am
d
That was surprisingly easy
Start with triples, evolve repeatedly
evolve being
Copy code
fun Set<String>.fullyConnected() = map { connections.getValue(it) }.reduce(Set<String>::intersect)
Copy code
fun Set<Set<String>>.next(): Set<Set<String>> {
    val n = mutableSetOf<Set<String>>()
    for (s in this) {
        for (candidate in s.fullyConnected()) {
            n.add(s + candidate)
        }
    }
    return n
}
until there鈥檚 only 1 in next, I manually unrolled
Runs fast enough
Look at this silly (pre-cleanup) code
j
Copy code
class Box<T>(var value: T)

fun <V> bronKerbosch(r: List<V>, p: List<V>, x: List<V>, graph: Map<V, Set<V>>, result: Box<List<V>>) {
    if (p.isEmpty() && x.isEmpty()) {
        if (result.value.size < r.size) result.value = r
        return
    }
    val pivot = p.firstOrNull()?:x.first()
    val p1 = p.toMutableList()
    val x1 = x.toMutableList()
    (p - graph[pivot]!!).forEach { v ->
        val es = graph[v]!!
        bronKerbosch(r + v, p1.filter { it in es }, x1.filter { it in es }, graph, result)
        p1 -= v
        x1 += v
    }
}

fun part2(graph: Map<String, Set<String>>): Any {
    val result = Box(emptyList<String>())
    bronKerbosch(emptyList(), graph.keys.toList(), emptyList(), graph, result)
    return result.value.joinToString(",")
}
3ms, I need to take a break now
p
Copy code
Warming up 1 puzzles over 15s for year 2024 day 23...
Warmup finished after 15.000042584s with 12709 iterations
year 2024 day 23 part 1
	 Default took 594.475us 馃憫: 1062
year 2024 day 23 part 2
	 Default took 574.32us 馃憫: bz,cs,fx,ms,oz,po,sy,uh,uv,vw,xu,zj,zm
Day23.kt
d
Good enough, now I鈥檒l read about how to go faster 馃檪 https://github.com/dfings/advent-of-code/blob/main/src/2024/problem_23.main.kts
I saw Bron-Kerbosch immediately upon looking up maximal cliques, but looked annoying to implement based on sample code
Alright Jakub鈥檚 version doesn鈥檛 look so bad
Mine takes 2.2s
p
Can someone test my approach on their input? I'm concerned it works for me but it only takes 0.5ms so potentially misses some edge cases if others are needing Bron-Kerbosch
j
That wasn鈥檛 too difficult; nice one to do in Kotlin Notebooks again. I didn鈥檛 do anything to optimize for speed but it鈥檚 done in less than a second. Just keep creating bigger groups until there is one left. Only now I realise I start at group size 0 馃 But it works https://github.com/JBeet/MyAdventOfCode2024/blob/main/src/Day23.ipynb
h
@phldavies FYI, works fine on my input. If I am reading your code correctly, I think I have a very similar (if somewhat more verbose) solution for Part 2. That is to say, iterate down the path of neighbours, ensuring each one is connected to all the previous neighbours.
Copy code
fun part2(): String {

        // Function to recursively look along the chain of neighbours, finding sets of computers
        // that all have each other as neighbours
        fun findAllSets(neighbour: String, prevNeighbours: MutableList<String>): List<List<String>> {

            val foundSets = mutableSetOf<List<String>>()

            if (graph[neighbour]!!.containsAll(prevNeighbours)) {
                // this computer has all previous computers in the chain as neighbours, so add it to the set
                // and continue the search on unvisited neighbours
                prevNeighbours.add(neighbour)
                graph[neighbour]!!.forEach { nextNeighbour ->
                    if (!prevNeighbours.contains(nextNeighbour)) {
                        foundSets += findAllSets(nextNeighbour, prevNeighbours)
                    }
                }
                return foundSets.toList()
            } else {
                // This computer doesn't have all previous computers in the set as neighbours, so the set is complete.
                foundSets += prevNeighbours
                return foundSets.toList()
            }
        }

        val allSets = mutableListOf<List<String>>()

        // Iterate through all the computers and their neighbours looking for "Sets of connected computers"
        // Have since learned, these sets are called "cliques" in Graph theory.
        graph.forEach { (comp, neighbours) ->
            val prevNeighbours = mutableListOf(comp)
            neighbours.forEach { neighbour ->
                allSets += findAllSets(neighbour, prevNeighbours)
            }
        }
        // return the largest set as a comma separated list ie. the LAN Party password
        return allSets.maxBy { it.size }.sortedBy { it }.joinToString(",")
    }
m
Recursively remove connected computers until the remaining ones are all interconnected. Good enough for me...
Takes ~500ms
k
Cleaned up and pushed my solution now. It's fairly straightforward and I wonder if I might have just been lucky. Runtime is about 200碌s and 2.5ms warm for part 1 and 2 respectively
If someone can also help try this with their input and let me know if it works 馃檹
p
I don't cache/share the parsing when benchmarking (as the "parsing" may contain a sizeable amount of processing) or share anything between part1 and part2, but with minor refactors (i.e. creating your map afresh each time):
Copy code
Warming up 3 puzzles for 15s each for year 2024 day 23...
	BitSet warmed up with 23839 iterations
	Default warmed up with 15991 iterations
	Kingsley warmed up with 2606 iterations
year 2024 day 23 part 1
	 BitSet took 458.908us 馃憫: 1062
	 Default took 495.233us (1.08x): 1062
	 Kingsley took 1.456684ms (3.17x): 1062
year 2024 day 23 part 2
	 BitSet took 198.283us 馃憫: bz,cs,fx,ms,oz,po,sy,uh,uv,vw,xu,zj,zm
	 Default took 486.706us (2.45x): bz,cs,fx,ms,oz,po,sy,uh,uv,vw,xu,zj,zm
	 Kingsley took 4.306325ms (21.72x): bz,cs,fx,ms,oz,po,sy,uh,uv,vw,xu,zj,zm
k
Interesting. Thanks for checking @phldavies
p
this is with cacheing parsed input data structures (at least on my M3)
Copy code
year 2024 day 23 part 1
	 BitSet took 94.455us 馃憫: 1062
	 Default took 288.479us (3.05x): 1062
	 Kingsley took 1.134040ms (12.01x): 1062
year 2024 day 23 part 2
	 BitSet took 83.13us 馃憫: bz,cs,fx,ms,oz,po,sy,uh,uv,vw,xu,zj,zm
	 Default took 262.556us (3.16x): bz,cs,fx,ms,oz,po,sy,uh,uv,vw,xu,zj,zm
	 Kingsley took 3.512550ms (42.25x): bz,cs,fx,ms,oz,po,sy,uh,uv,vw,xu,zj,zm
鉂わ笍 1
k
Wonderful. Good to know that it's at least producing the correct result 馃槄 I might try to optimize further later, but I don't really mind the current runtime too much
m
Cleaned up my code and brought the runtime down from 500 to 6 ms by swapping two when clauses and replacing a 
<
by a 
<=
Enough for today!
p
woo! cracked 200us for part 1 and 2, including parsing time:
Copy code
year 2024 day 23 part 1
	 BitSet took 196.226us 馃憫: 1062
year 2024 day 23 part 2
	 BitSet took 185.713us 馃憫: bz,cs,fx,ms,oz,po,sy,uh,uv,vw,xu,zj,zm
Day23BitSet.kt
馃敟 2
b
@phldavies your original solution you asked about works on my input, but i can construct a simple input that it fails on
Copy code
aa-ab
aa-ba
ba-ca
ca-aa
p
ah - part2 it fails
b
right, not sure how realistic the edge case is, but since you're adding the first/lowest order element first in your check, if that element is not part of the largest group it will fail
d
I might convert mine to using 
Bitset
, same algorithm, see what speed up we get
p
p
Copy code
context(PuzzleInput) fun part2() = parse { network ->
        var best = emptyList<String>()
        val splits = ArrayDeque<Int>()
        val lan = ArrayDeque<String>()

        for ((first, nodes) in network) {
            if (nodes.size < best.lastIndex) continue
            val bestThreshold = (nodes.size / 2) + 1
            splits.add(0)
            while (splits.isNotEmpty()) {
                val split = splits.removeFirst()
                for (idx in split downTo 0) {
                    val next = nodes[idx]
                    if (lan.all { it in network[next].orEmpty() }) lan.addFirst(next)
                }
                lan.addFirst(first)
                for (idx in split + 1..nodes.lastIndex) {
                    val next = nodes[idx]
                    if (lan.all { next in network[it].orEmpty() }) {
                        lan.addLast(next)
                        splits.remove(idx)
                    } else splits.add(idx)
                }

                if (lan.size > best.size) best = lan.toList()
                if (lan.size > bestThreshold) splits.clear()
                lan.clear()
            }
        }
        best.joinToString(",")
    }
@bj0 fixed (I think) - still ~190us so I'm happy
b
Untitled
Untitled
nice, i didn't look too much at the bitset solution, but this change to your original is how i "fixed" it:
still very compact and only slightly slower
p
馃 interestingly it fails for
Copy code
aa-ab
aa-ac
aa-ba
aa-cb
ab-ac
ba-ca
cb-ca
cb-ba
ca-aa
part 2 gets "aa,ac,ba,ca,cb" when ba and ac aren't connected
b
ah, taking (first) and (second) out of the check was me trying to optimize it, leaving them in i think works
Copy code
add((buildSet {
                                add(first)
                                add(second)
                                for (next in connected - visited) {
                                    if (all { next in network[it].orEmpty() }) add(next)
                                }
                            }).also { visited += it })
p
yup,that fixes it:
Copy code
BrianFix took 1.258929ms (6.50x): bz,cs,fx,ms,oz,po,sy,uh,uv,vw,xu,zj,zm
d
BitSet reduces my time 10x from Set<String>, 2.2s to 200ms
p
using the more compact encoding instead of treating it as base36 takes me down to 140us for part2 馃檶
d
Screenshot 2024-12-23 at 1.21.13鈥疨M.png
I keep tweaking it
馃槃 1
advent of code intensifies 1
p
I know what you mean:
Copy code
Warming up 2 puzzles for 5s each for year 2024 day 23...
	BitSet warmed up with 37760 iterations
	Default warmed up with 6001 iterations
year 2024 day 23 part 1
	 BitSet took 73.336us 馃憫: 1062
	 Default took 483.22us (6.59x): 1062
year 2024 day 23 part 2
	 BitSet took 65.698us 馃憫: bz,cs,fx,ms,oz,po,sy,uh,uv,vw,xu,zj,zm
	 Default took 332.059us (5.05x): bz,cs,fx,ms,oz,po,sy,uh,uv,vw,xu,zj,zm
no cached parsing - 74us and 66us
d
Did you implement BK?
e
I didn't know about BK but looking it up now, I basically wrote the non-pivoting form
馃憤 1
10 Views
Open in Slack
PreviousNext
Powered by