https://kotlinlang.org logo
Join SlackCommunities
Powered by
<Advent of Code 2024 day 25> (spoilers) :christmas...
# advent-of-code
a
j
Today was a breeze. And was a nice challenge.
Day25.kt
🎉 1
b
yea nice easy last day
m
day25.png
a
that was a nice ending. I should have had a 
List<List<T>>.transponse()
by now. would have made the 'create column heights' a simple 
heights.count { it == '#'}
m
Before the start of this year, I enabled all the Kotlin 2.1 features in my project. Today was the first day where I used the new non-local break/continue (in my initial solution). 😄
👍 1
j
I just wen't with brutal O(n^2)
Copy code
typealias Input = Pair<List<List<Int>>, List<List<Int>>>

fun part1(input: Input): Int = input.let { (keys, locks) ->
    locks.sumOf { lock ->
        keys.count { key -> key.zip(lock).all { (k, l) -> k >= l } }
    }
}

fun parse(text: String): Input = text.lines().chunked(8).let { chunks ->
    val keys = mutableListOf<List<Int>>()
    val locks = mutableListOf<List<Int>>()
    chunks.forEach { chunk ->
        val isKey = chunk[0] == "....."
        val isLock = chunk[0] == "#####"
        check(isKey xor isLock) { "Invalid chunk: $chunk" }
        val counts = (0..4).map { col ->
            chunk.filterNot { it.isBlank() }
                .count { row -> row[col] == if (isLock) '#' else '.' }
        }
        if (isLock) locks.add(counts) else keys.add(counts)
    }
    keys to locks
}
a
so did I. but this one requires a O(n^2) because any lock can fit with multiple keys so you have to check all locks with all keys. I mean some dynamic programming/early exit might help but you can't skip checking combos.
Untitled.cpp
j
but since my mind is still in yesterday's sum/carry mood, I think there is space for coding keys and locks into single integers and then performing a single addition or subtraction on them and see if there is no carry over.
a
in the example given, the key 
3,0,2,0,1
fits on two different locks and the lock 
1,2,0,5,3
works with two keys. so can't use an any or first because he wants all combos
yes black 1
if it was only "exact" fit and not "exact or less than", then I suppose one could make base-5 number and then 'OR' the locks and keys 🤔. also , with carry over, if the carry is on the LSB but there are gaps, then it won't reach the MSB, so can't check for max-base-5. it could be a bad-fit and still be less than the max. example: 
1 2 2 2 4
with 
1 2 2 0 4
then the LSB carries over but then 2 + 2 or 2 + 3 fits so would not be an error/overflow (but it should not be counted)
m
Merry christmas everyone :)
Day 25 Michael.cpp
k
It's a wrap!
Day25.kt.cpp
m
@Anirudh @Jakub Gwóźdź you can store all the locks in a nested 5 deep sortedmap that only requires a lookup in the form of: locks.tailMap(pin1).tailMap(pin2).tailMap(pin3).tailMap(pin4).tailMap(pin5).size for a O(n log n) solution I think
j
@Anirudh I went with base8 for fast bit comparisons:
Copy code
fun part1(input: Input): Int = input.let { (keys, locks) ->
    var count = 0
    for (key in keys) {
        for (lock in locks) {
            val valid = key <= lock &&
                    key and 7 <= lock and 7 &&
                    key and 63 <= lock and 63 &&
                    key and 511 <= lock and 511 &&
                    key and 4095 <= lock and 4095
            if (valid) count++
        }
    }
    count
}
but that can be tweaked even further
a
nice. but don't we consider that also O(n^2) ? although my 
for + for + all
is actually O(n^3) with early exit
Copy code
locksHeights.sumOf { lockH ->
    keysHeights.count { keyH ->
        lockH.zip(keyH).all { (lh, kh) -> lh + kh < rows - 1 }
    }
}
nested 5 deep sortedmap
@Michael de Kaste hehe I have no idea what that is 🙃
j
ok here's my 35us part1 approach:
Copy code
fun part1(input: Input): Int = input.let { (keys, locks) ->
    var count = 0
    val legit = 0b1110111011101110111
    for (key in keys)
        for (lock in locks)
            if ((lock - key) or legit == legit) count++
    count
}
parsing also takes 35us 🙂
Copy code
chunks.forEach { chunk ->
        val isKey = chunk[0] == "....."
        val isLock = chunk[0] == "#####"
        check(isKey xor isLock) { "Invalid chunk: $chunk" }
        val keyCode = (0..4).map { col ->
            chunk.filterNot { it.isBlank() }
                .count { row -> row[col] == if (isLock) '.' else '#' }
        }.fold(0) { acc, i -> acc * 16 + i }
        if (isLock) locks.add(keyCode) else keys.add(keyCode)
    }
e
https://github.com/ephemient/aoc2024/blob/main/kt/aoc2024-lib/src/commonMain/kotlin/com/github/ephemient/aoc2024/Day25.kt and that's a wrap. still got some cleanups and completing other languages to do, but that can wait for the morning
m
This is 8 times faster for me than a zip solution
Nested map.kt
although since depth of key/lock is fixed, one loop could just add itself to every height and then its a O(n) solution
p
a
My pretty straightforward solution. Here Key and Lock are defined as
Copy code
typealias Lock = List<Int>
typealias Key = List<Int>
I'm a bit wandered as this solution is fast on task data. I've expected long time matching and was ready doing tree-matching optimization 🫠
@Marcin Wisniowski could you show the usage?
p
I think the puzzle gave it away by also showing it in the number representation. If they would have left it at only the pin images, more people would have started doing shape matching.
☝️ 1
true 1
j
can't see how it's effective to come below O(n^2). Best I could do is to prepare five sorted lists for each pin, where I could do bisect later to quickly figure out which locks are ok for given key, but then I get 5 lists and need to intersect them all, so it's idk... O(n*logn*logn*logn*logn*logn)?
m
Thats what I have Jakub in my post above. And no, thats not O(n log n * log n). Thats O(n * (log 5)^5))
a
so it's idk... O(n*logn*logn*logn*logn*logn)?
that's nice but when N=5, logn*logn*logn*logn*logn = 10.7 so n * logn...5 times = ~53 but N^2 = 25 🙂
m
which is worst case O(n * 243)
j
it's not N=5. N is a number of locks, not pins
👍 1
m
no your sorted map depth comparing when preputting them is only 5
a
it's not N=5. N is a number of locks, not pins
ah, yes. my bad
j
and what is the complexity of preparing this sorted map?
m
same complexity as getting them
analyze my solution here: https://kotlinlang.slack.com/archives/C87V9MQFK/p1735108368033029?thread_ts=1735102805.528469&amp;cid=C87V9MQFK I loop through all locks and put them in first, then loop through all keys and retrieve a value putting them and getting them is O(n)
its not as fast overall as your bit solution but it is technically O(n) blob think smart
j
But building TreeMap is far from O(n), right? 🙂
m
the depth of the tree is dependent on amount of pins and depth of pins which is 5 width and 5 height, that is totally independent of amount of keys and locks
and such, that means it is a constant
iirc: if width and height are variables its 
O(n * width * height log height)
whereas the double loop solution is 
O(n² * width)
d
For many many locks, you could precompute an Array<Array<Array<Array<IntArray>>>> where each array is of size 5. For each lock, add 1 to every array index combination that is a valid key for that lock. 5-way nested for-loop.
then the count for a single key is O(1)
But I just brute forced
OK yeah that’s the same thing Michael said
h
Wow... so happy, this is my first real attempt at AoC... and I got it all done. Today was a little late due having Xmas day (Yay for New Zealand being UTC+13) with family and only got home about an hour ago. A nice easy one to finish... was wondering how bad Part 2 was going to be... what a pleasant surprise!
Also, the easter eggs are quite funny
In the same way that christmas cracker jokes are "funny" 😛
p
Copy code
@AoKSolution
object Day25 {
    context(PuzzleInput) fun part1() = parse {
        it.combinations(2).count { (a, b) -> a and b == 0 }
    }

    val parse = Parser {
        input.split("\n\n").map {
            it.fold(0) { acc, c ->
                when (c) {
                    '#' -> acc shl 1 or 1
                    '.' -> acc shl 1
                    else -> acc
                }
            }
        }
    }
}
happy BitMas everyone advent of code intensifies
I realised I used 32bit ints despite there being 35 bits in the key/lock - but the locks' highest 3 bits are always set and will always pass on a "key"'s highest 3 bits (which are clear) so it's irrelevant
j
yes, it's actually 6 possibilities, so 30bits is ok
p
I know when I've done too much bit twiddling in AoC when my instinct was to reach for bits rather than the hinted-at IntArray(5) approach
j
Ooooooh I see now the 
O(n*6^5)
solution (ok in reality it's much less than 6^5, but it's upper bound) Thanks @Michael de Kaste @Dan Fingal-Surma
Copy code
// part1 but O(n*6^5)
fun part2(input: Input): Int {
    val locks = BitSet(6 * 6 * 6 * 6 * 6)
    input.forEach { chunk ->
        if (chunk[0] == "#####") locks.set(keyCode(chunk, '.', 6))
    }
    var count = 0
    input.forEach { chunk ->
        if (chunk[0] != "#####") {
            val (k0,k1,k2,k3,k4) = heights(chunk, '#')
            for (l0 in k0..6) {
                for (l1 in k1..6) {
                    for (l2 in k2..6) {
                        for (l3 in k3..6) {
                            for (l4 in k4..6) {
                                val keyCode = keyCode(listOf(l0, l1, l2, l3, l4), 6)
                                if( locks.get(keyCode)) count++
                            }
                        }
                    }
                }
            }
        }
    }
    return count
}

private fun heights(chunk: List<String>, c: Char) = (0..4).map { col -> chunk.count { row -> row[col] == c } }
private fun keyCode(heights: List<Int>, base: Int) = heights.fold(0) { acc, i -> acc * base + i - 1}
private fun keyCode(chunk: List<String>, c: Char, base: Int) = keyCode(heights(chunk, c), base)
although to be fair it is still slower than my O(n^2) 🙂
Copy code
// O(n^2)
fun part1(input: Input): Int {
    var count = 0
    val legit = 0b1110111011101110111
    val keys = mutableListOf<Int>()
    val locks = mutableListOf<Int>()
    input.forEach { chunk ->
        val isLock = chunk[0] == "#####"
        if (isLock) {
            val keyCode = keyCode(chunk, '.', 16)
            count += keys.count { (keyCode - it) or legit == legit }
            locks.add(keyCode)
        } else {
            val keyCode = keyCode(chunk, '#', 16)
//            for (lock in locks) if ((lock - keyCode) or legit == legit) count++
            count += locks.count { (it - keyCode) or legit == legit }
            keys.add(keyCode)
        }
    }
    return count
}
m
@Andriy https://github.com/Nohus/AdventofCode2024 My repo is here if you want to run it
d
I have an idea for how to make the precompute faster, but after Christmas
Did it anyway
3.160583ms brute force, 343.291us precomputed when warmed… though I’m not sure how much I can trust the numbers. Warming drops from 9.861834ms on run 1 to 343.291us on run 10
hmm, on first run it’s 1.349375ms vs 1.627458ms, then I run the script again and get 1.797708ms vs 344.917us
ok 100 runs warming each, 731.75us vs 446.084us
Maximize short circuiting during precompute, no list construction during look up, flat int array
Might try running with keys*100
With 1024x keys it's 1.5s vs 1.5ms
1024x locks and 1024x keys… does not complete in reasonable time vs 320ms
n^2 gonna n^2
👍 2
14 Views
Open in Slack
PreviousNext
Powered by