https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2024 day 22> (spoilers) :thread:
# advent-of-code
a
d
What I'm doing right now is, for every secret number, compute the map of 4 deltas to price. That gives you a candidate set of delta sequences. Then find the one that maximizes price using those same maps. This works on the test input but has failed not the real input. I have to come back to debugging later.
r
Part 1 was fairly straightforward - just using generateSequence. I got the wrong answer originally because I misunderstood the 3 numbers as 3 separate new secrets.
d
Kotlin makes this easy to do using generate sequence, windowed, zipWithNext, zip, etc
👍 4
m
glory to kotlins sequence/iterable functions 🙏
Day 22 Michael.cpp
🙌 2
r
Part 2, building on the sequence generated in part 1, use zipWithNext + windowed + groupingBy to calculate the total price for each sequence of deltas. I originally missed the rule that each buyer only wants to buy one hiding spot, fixed that by adding a distinctBy to the inner sequences.
d
Thank you, that is my bug
👍 1
I'm like this is obviously logically correct lol
m
I really wish there was some sort of 'associateBy' with an 
onConflict: (T, T) -> T
function
and I also wish Maps had a merge function on their own instead of calling nested merges on their keys. Feels very stdlib
d
So in Guava they have buildOrThrow() on ImmutableMap.Builder for this reason
You probably don't want to silently lose data
m
Iirc, C# actually just throws an exception if you try to remap a key I'm fine with how Java/Kotlin does it, because 
map[x] = y
is functionally the same as 
array[x] = y
but I just think association could use a 'what if you want to recalculate the value`. I understand that, this is what 'groupingBy' does -> do not actually use a list, but define what you want. I just feel like groupingBy was introduced at Kotlin's start lifecycle and never got retouched with the same love as the normal Sequence/Iteratable functions do
d
I think 
reveresed
will produce the first one wins behavior. Will try it when I'm back in a computer
👍 1
m
yeah, but then you would lose the advantages of using a sequence, because then you would need to collect them and then reverse iterator order them.
d
Hmm good point
At first I thought you said C++ and I was like what are you talking about 😂
m
I had a professional Java -> C# -> Kotlin growth and C# REALLLLLY annoyed me with their lack of data structures and how they used them. Linq was great though
d
Alright so forEach-as-collect
I've done about half C++ and half Java but now I'm a Kotlin stan
That worked. It bothers me that 
forEach
and 
collect
have different names
b
holy smokes, took me 1.5 hours to think of what to try, but once i did it took about 5 min to solve
looks like most people thought of it an hour and a half before i did laugh cry face palm
i need to learn how to use grouping better, i never think of it
m
My part 2
k
I was doing 
shl 10
instead of 
shl 11
for the multiplied by 2048 and this ended up taking over 30 minutes to debug 🤦‍♂️ I tried to be smart with part 2 and failed woefully, so my final solution ends up taking about 4 seconds to compute. I'm curious if there's a smart way to speed this up
m
After some cleanup it doesn't look too terrible
j
Solved part 2, but was a stupid brute force, not really proud of the code, but hey it got me the stars: https://github.com/bulldog98/advent-of-code/blob/main/advent2024/src/main/kotlin/year2024/Day22.kt I have to watch again, how Sebastian did his parallelization of code.
m
@Jonathan Kolberg I think you want to switch to 
Dispatchers.Default
, otherwise your 
async
is not doing much.
👍 2
j
@Marcin Wisniowski thanks for the tip, I noticed it but I'm using coroutines for the first real time, so yeah.
j
Today finally was the day when I gave up and brute forced it. 12 cores for twenty-something minutes went brrrrr. I'll make it proper solution later, I already think I know how.
Copy code
fun <T, R> List<T>.mapParallel(op: (T) -> R) = runBlocking { map { async(Dispatchers.Default) { op(it) } }.awaitAll() }
for the rescue 🙂
d
Takes a few seconds
I’d be surprised if you find a faster algorithm but I’ve been surprised before
e
a
I did a much more explicit union-all-"first"-keys and then brute force maxOf each key. also used a 
data class Changes(a, b, c, d)
but I think it would be better to just build a Unified map on the first pass itself 🤔 with the values being added to a list, or just the sum directly 💡 will do that now
h
Today was certainly much easier than yesterday! (I finally finished yesterday about 30 minutes after todays puzzles were released) I too had the issue where things worked for the example, but not the input... because I was maximising the price when getting the sequences from each buyer, rather than just the first instance of the sequence. It also sounds like I must also go and learn about all the fancy generate sequence, windows, zip stuff... as I am guessing I did a lot of "manual" work here... such as:
Copy code
fun getSequences(priceList: List<List<Int>>): List<Map<List<Int>, Int>> {
        val sequences = mutableListOf<MutableMap<List<Int>, Int>>()
        priceList.forEachIndexed { i, list ->
            sequences.add(mutableMapOf())
            list.forEachIndexed { j, price ->
                if (j >= 4) {
                    val sequence = listOf(
                        list[j-3]-list[j-4],
                        list[j-2]-list[j-3],
                        list[j-1]-list[j-2],
                        list[j]-list[j-1])
                    if (!sequences[i].containsKey(sequence)) sequences[i][sequence] = price
                }
            }
        }
        return sequences
    }
which is easily solved using built-in Kotlin functionality?
j
I'd say it's abuse of stdlib at this point, but single-threaded it fits under 1s. What is not surprising: map operations are noticeable faster when keys are 
.toString()
-ed
Untitled.kt
👍 1
a
> just build a Unified map on the first pass ... sum directly 💡 ok, this way was MUCH faster. I didn't time the previous way, will commit & Ctrl+Z a bit Old Part Two time: 7.109126799s New Part Two time: 1.074562800s not quite 10x but in that range
m
@Jakub Gwóźdź what about 
.reduce{ acc, it -> acc shl 5 + it + 9 }
?
at least I think that would work 🤔
j
for code calculation?
p
urgh - Advent of Reading Comprehension again! I spent far too long debugging part 2 when I was using the example from part1 and expecting the part2 answer 🤦‍♂️
same 1
j
yeah I tried reduce, similar performance as toString 🙂
(I don't know why, intuition says Map<Long,...> should be faster than Map<String,...>, but experiments says nope
@Michael de Kaste even 
acc*100+it
works for that reduction
a
for me, I changed
Copy code
Changes(a, b, c, d) to chg.last().first
to
Copy code
"$a,$b,$c,$d" to chg.last().first
and it's gone up to 1.3 secs, from 1.0 secs. but I'm not benchmarking correctly. just using 
measureTime
j
30% of change can happen from various things outside your program
👍 1
I'm using measureTime as well, good enough for AoC 🙂
a
yup, I see that variation too now, goes from 1.0 to 1.2 with the data class as key
my part Two code with unified map on first pass. so only need to hold one buyer's sequence at a time in memory. and of course the keys of the unified map goes up to about 41k keys (around 1900-1950 keys from each buyer) but the values are Int's
Untitled.kt
p
interestingly I see destructuring the result of 
zipWithNext(Long::minus)
into 
"$a $b $c $d"
is the fastest (I'm using 
distinctBy
to take only the first instance seen in the sequence)
Copy code
BenchDay22.dataClass                  avgt    3  1.065 ± 0.129   s/op
BenchDay22.destructureToString        avgt    3  0.516 ± 0.473   s/op
BenchDay22.joinToString               avgt    3  0.867 ± 0.142   s/op
BenchDay22.list                       avgt    3  1.462 ± 0.142   s/op
BenchDay22.reduce                     avgt    3  0.705 ± 0.227   s/op
d
HashMap beats mutableMapOf (aka LinkedHashMap)
👍 1
This is a real heap hog, 
4354313
hash map entries
j
How is that possible, @Dan Fingal-Surma ? Five digits can make 100000 max entries in worst case…
d
I have 1 map per input line
sequence price map for that input
j
Ok, so c.a 1500 lines times 2000 entries worst case… 
3000000
max?
d
2256 * 1922
👍 2
a
ah yes, I too did a List<Map...> in my first run. so yeah, each run would have 1997 entries max (but usually 1900-1950 due to repeats). so I guess you have approx 2200 bots monkeys. (I had approx 1500 bots monkeys)
but the "union" of all keys (also for my first run) will have about 40k entries. so about 100 times smaller. so if you process for 'sums' or lists while generating the list-of-deltas and don't store it, you'll only need to have 1950 + 40k max entries at a time.
👍 1
d
Yeah that’s a good idea
j
yeah I have input 1571 lines, last hashMap is 40951 entries big. Which gives ~40% of all possibilities, probably way more as the digits like 89898 and 45454 give the same sequence 
1,-1,1,-1,1
. But it's big enough percentage to justify counting in 
IntArray(20*20*20*20*20) { 0 }
instead of a hashMap
d
Much faster with one map
👍 1
p
@Jakub Gwóźdź I've literally just done that ( but with an 
Array<Array<Array<IntArray>>>
)
Copy code
Warming up 2 puzzles for 10s each for year 2024 day 22...
	Acc warmed up with 74 iterations
	Default warmed up with 21 iterations
year 2024 day 22 part 1
	 Array took 22.518514ms 👑: 16039090236
	 Default took 24.194791ms (1.07x): 16039090236
year 2024 day 22 part 2
	 Array took 134.197583ms 👑: 1808
	 Default took 455.922416ms (3.40x): 1808
j
There are only 19 possiblities for the price difference, so an 
IntArray(19*19*19*19*19) { 0 }
is enought
j
yes, but 20x is easier to debug than 19x 🙂
😀 1
p
using two arrays, one to accumulate the banana count and one to accumulate the last seen buyer for that sequence - the latter is used to filter for just the first per buyer before incrementing the banana count
j
honestly, I have this feeling that with
Copy code
private fun Long.nextSecret(): Long = step1().step2().step3()

private fun Long.step1() = shl(6) xor this and 0xFFFFFF
private fun Long.step2() = shr(5) xor this and 0xFFFFFF
private fun Long.step3() = shl(11) xor this and 0xFFFFFF
it might be enlightening to print all the numbers in sequence in binary 🙂
a
I was going to check the binary of the output for part 1 but then just decide to finish part 1 and see if that investigation is needed for part 2.
d
Copy code
fun encode(deltas: List<Int>) = ((deltas[0] + 10) shl 15) or ((deltas[1] + 10) shl 10) or ((deltas[2] + 10) shl 5) or ((deltas[3] + 10))
(playing around)
p
why not 
deltas.reduce { acc, delta -> acc shl 5 or (delta and 0x1F) }
?
m
this is why I stopped doing leetcode aswell, its micro-optimilization that takes away from the beauty of languages, but you could do this:
Copy code
part2 {
    val bananas = Array(19){ Array(19){ Array(19){ IntArray(19) } } }
    val visited = Array(19){ Array(19){ Array(19){ Array(19){ BitSet(secrets.size) } } } }
    var max = 0
    secrets.forEachIndexed { index, line ->
        line.map { it % 10 }.windowed(5){ (a,b,c,d,e) ->
            val ax = b - a + 9
            val bx = c - b + 9
            val cx = d - c + 9
            val dx = e - d + 9
            if(!visited[ax][bx][cx][dx].get(index)){
                bananas[ax][bx][cx][dx] += e
                visited[ax][bx][cx][dx].set(index)
                if(bananas[ax][bx][cx][dx] > max){
                    max = bananas[ax][bx][cx][dx]
                }
            }
        }
    }
    max
}
It speeds up my part2 to 213.419400ms Could be even faster with classic for loops
👍 1
p
Copy code
context(PuzzleInput) fun part2(): Int {
        val bananas = Array(19) { Array(19) { Array(19) { IntArray(19) } } }
        val seen = Array(19) { Array(19) { Array(19) { IntArray(19) { -1 } } } }
        var max = 0

        Parsers.Longs().forEachIndexed { buyer, secret ->
            generateSequence(secret) { it.evolve() }
                .map { it % 10 }.take(2001)
                .windowed(5) { (a, b, c, d, e) ->
                    val i = (e - d).mod(19)
                    val j = (d - c).mod(19)
                    val k = (c - b).mod(19)
                    val l = (b - a).mod(19)
                    if (seen[i][j][k][l] != buyer) {
                        seen[i][j][k][l] = buyer
                        bananas[i][j][k][l] += e.toInt()
                        max = maxOf(bananas[i][j][k][l], max)
                    }
                }
                .count()
        }

        return max
    }
was my take, @Michael de Kaste
👍 1
m
something something great minds 😂
j
yeah I'm now around 400ms, I see some places for improvement, but need to do some other things 🙂
ok, introducing buyer table took me to 300ms, but made the whole solution less readable 🙂
d
The array approach is too ugly for me to continue with
If I wanted to write C++ I’d write C++
j
same 🙂
and if I wanted super speed I wouldn't be using sequences anyway
d
going to
Copy code
.map { (a, b, c, d) -> a.mod(19) * 6859 + b.mod(19) * 361 + c.mod(19) * 19 + d.mod(19) }
from
Copy code
.map { (a, b, c, d) -> "$a $b $c $d" }
saves 300-400ms
Ok 
IntArray(19 * 19 * 19 * 19) { 0 }
is clean enough and saves a further 250 ms
j
yeah my
Copy code
fun part2(input: Input): Any {
    val array = IntArray(19 * 19 * 19 * 19 * 19)
    val done = BooleanArray(19 * 19 * 19 * 19 * 19)
    input.forEach { seed ->
        done.fill(false)
        generateSequence(seed, Long::nextSecret)
            .map { it % 10 }
            .take(2001)
            .windowed(5)
            .forEach { last5 ->
                val code = last5.zipWithNext { a, b -> b - a }.fold(0L) { acc, l -> acc * 19 + l + 9 }.toInt()
                if (!done[code]) {
                    done[code] = true
                    array[code] += last5.last().toInt()
                }
            }
    }
    return array.max()
}
makes it in 300ms (+/- 10%)
m
Moved it all to arrays and computing everything in a single pass. Part 1 is still my old implementation. Part 2 is almost equally fast (but uses coroutines...) Not very idiomatic anymore, but pretty fast... part2Fast:
Copy code
Part 1 median:      7.035 ms  (709 benchmark iterations)
Part 2 median:      7.179 ms  (676 benchmark iterations)
d
whoops I was calculating prices twice due to re-using the sequence instead of converting to list
Around 600ms from 10s
Always make sure the code still gives the right answer before posting lol
😁 1
j
@Dan Fingal-Surma oh that’s nothing. A few days ago I posted a visualization I was so proud of just to find out later that because of multiple optimizations on the way it was no longer correct 😁
d
175ish ms, goodnight
👍 1
(I was missing a + on line 18 which somehow compiled and produced the wrong answer??)
oh it was dropping the final clause, treating it as a standalone expression
k
Tidied up a bit more and I think I'm done for this day. Got it down to:
Copy code
Cold
Part1: ~24ms. Part2: ~180ms

Warm
Part1: ~7ms. Part2: ~94ms
Also replaced 
list.slice(a..b)
with 
list.subList(a, b+1)
and saved a few extra milliseconds
e
@Jakub Gwóźdź
it might be enlightening to print all the numbers in sequence in binary 🙂
good luck with that 😉 https://en.wikipedia.org/wiki/Xorshift
today i learned 1
j
@ephemient oh wait so this is a real PRNG? 😮 TIL
plus one 1
p
Copy code
Warming up 2 puzzles for 10s each for year 2024 day 22...
	Array warmed up with 520 iterations
	Default warmed up with 22 iterations
year 2024 day 22 part 1
	 Array took 7.885264ms 👑: 16039090236
	 Default took 15.524028ms (1.97x): 16039090236
year 2024 day 22 part 2
	 Array took 11.130472ms 👑: 1808
	 Default took 449.944569ms (40.42x): 1808
I think I'm done now - single threaded, no coroutines.
j
no fancy window(5) / zipWithNext neither, I presume? 🙂
p
Copy code
context(PuzzleInput) fun part2(): Int {
        val len = 0xFFFFF
        val bananas = IntArray(len)
        val seen = IntArray(len) { -1 }
        var max = 0

        for ((buyer, secret) in Parsers.Longs().withIndex()) {
            var s = secret
            var prevPrice = (s % 10).toInt()
            var delta = 0
            for (i in 0..<2000) {
                s = s.evolve()
                val price = (s % 10).toInt()
                delta = (delta shl 5 and 0xFFFFF) or (9 + price - prevPrice)
                prevPrice = price
                if (i >= 3 && seen[delta] < buyer) {
                    seen[delta] = buyer
                    val newBananas = bananas[delta] + price
                    bananas[delta] = newBananas
                    max = maxOf(newBananas, max)
                }
            }
        }

        return max
    }
nope - just abusing a nice large sparse array and some bit twiddling
👍 1
d
I was gonna say, looks like a hash function to me
p
Each delta is (made to be) in the range of 0..18, which means they all fit in 5 bits. Four would take up 20 bits. So I just store them all in a single Int. shl 5 keeping the lowest 20 bits keeps just the last for rolling deltas.
🧠 1
k
I did exactly the same thing with the 5 bits. Though I used just 1 array. And I was able to reduce the size from 0xfffff to about half of that since 0..18 doesn't necessarily use up all 5 bits
p
How did you go about ensuring you only count a single instance of each with only a single array?
k
Copy code
val map = IntArray(608850)
for (n in input) for ((k, v) in sequences(n)) map[k] += v
println(map.max())
p
Ah you track the state per sequence. I was attempting to avoid any sequences so I used two arrays total for the entire solution.
Tracked the last input index to avoid needing to clear the "seen" array between buyers
k
Yea. I tried that but it became slower. I guess using the extra seen array should avoid the issue I was having. Though it also felt dirty creating such a large array
p
"large" is relative. It's 2.5MB of ints.
k
True. My thinking was relative to how much of it actually gets filled. I think I only had about 18k or so unique keys (can't quite remember now)
p
I did try a more compact 19*18*18*18 array layout but shifting was faster. Figured I could spare a few more KB
k
Haha. I also did the same. But the memory saving here ended up costing more in runtime when finding the actual max. The flat array also looks nicer, so whatever
Ah. I could have just done the max inline
👍 1
p
I maintained the max value as I increased each key, to avoid needing a second scan. I only use the array to keep track of individual sums
➕ 2
k
Makes sense
d
Looking at my last screenshot above. Somehow if inline the addPrices function into the loop, I go from 175ms to 250ms. Any idea why? (live link: https://github.com/dfings/advent-of-code/blob/main/src/2024/problem_22.main.kts)
incrementally computing the max only saves me about 2-5ms
Hmm these numbers are not warmed
Still a 50ms penalty for inlining even with warming
currently hitting 110ms warmed
might be stack allocating the boolean array?
k
You could try removing the 
{ 0 }
and 
{ false }
when initializing the int and Boolean arrays
d
Right but that's the same in both cases?
k
The initializer does an extra fill operation that might be a bit heavy, especially for the Boolean array which also happens for every entry in the initial values
d
Maybe saves 3ms? Hard to say. You could expect such a redundant initialization to be optimized out
ok but adding 
.toIntArray()
after 
.toList()
on prices saves a good 15-20ms
now I’m sub 100
doing 
+ 9
instead of 
.mod(19)
also saves another 15-20ms
👍 1
ok and then another 20ms by removing the sequence
Copy code
val prices = IntArray(2001)
    var v = s
    for (i in 0..2000) {
        prices[i] = (v % 10).toInt()
        v = next(v)
    }
now the inlining penalty has gone away
Another 20 ms:
Copy code
(v xor s) % (1 shl 24)
to
Copy code
(v xor s) and 0xFFFFFF
in the 35-40 range now
👏 2
good time to stop
16 Views
Open in Slack
PreviousNext
Powered by