https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2024 day 11> (spoilers) :thread:
# advent-of-code
a
d
Easy once you see the trick. Primed for it since it’s how I solved yesterday.
👍 1
Recursion + memoization
👍 1
I simulated it for part 1, hence the heap error in the other thread 🤣
👍 3
m
Part 2
👍 2
Simulated as normal for part 1, and caching for part 2.
p
d
Oh counting down is better than counting up
p
I have smaller cache key and possibly less cache misses that way but the core is same recursion+memoization theme
👍 1
e
d
I think it’s the only strategy 🙃
m
I wasted some time thinking we are supposed to find some mathematical solution or notice a pattern in the iterations, but it was just a matter of memoization.
👍 2
o
Used memoisation
j
I am trying to reimplement my solution with Arrow-Kt's 
MemoizedDeepRecursiveFunction
but can't seem to get it to work as fast as my simple MutableMap cache 🤔
arrow 1
m
memoization + recursion
Day 11 Michael.cpp
b
the one time i don't reach for recursion first.... it bites me
n
I of course also used memorization but did not use recursion, but instead simple repeated blinking 75 times, each time computing a new map from stone value to count.
❤️ 1
🧠 1
same 2
p
@Norbert Kiesel thanks for sharing, this is actually a great idea
b
cleaned up
d
Ah interesting, iterating on 
Map<Long, Int>
is a totally different, valid approach. That’s actually how the #1 ranked person did it
I didn’t understand what they were doing until I read your comment @Norbert Kiesel. Mutable map but same principle.
l
After I interrupt my competitive programming grind for AoC, I think that I can just force my way with brute force and no more DP. That didn't age well today.
k
Figured I needed to memoize fairly quickly, but it somehow took me way too long to construct the actual code 🤦‍♂️
r
We didn't even get the expected value for the example input in Part 2 this time... It's as if Eric was saying: "Congratz, you solved Part 1, now go find out how horribly your solution scales!", and boy was he right 😂 Ultimately changed the implementation to recursion + memoization like mentioned before 👍
e
I was originally trying to do loop-detection but figuring out what to do with a tree of values was giving me headaches. but the 
Map<Long, Long>
for that purpose ended up being all I needed
👍 1
plus1 1
r
d
Alternate solution
🙌 1
👀 1
For my input, final Map<Long, Long> has 3753 entries, whereas memoizing cache has 122546 entries.
r
No matter how the stones change, their order is preserved, and they stay on their perfectly straight line.
This tripped me for a bit. I assume, even if we shuffle numbers on every blink - the result should be same.
d
Ordering matters not at all
💯 4
e
you don't have to simulate the parts of the problem that aren't relevant to the solution
j
Blinking suddenly seems very dangerous. That’s A LOT of stones.
l
I guess in the map solution the blink function is overloaded? Otherwise I can't imagine how it work
a
> Blinking suddenly seems very dangerous. Don't blink! It empowers the Weeping Angels! https://en.wikipedia.org/wiki/Blink_(Doctor_Who)
today's puzzle reminded me of the Jelly Fish or something fish that multiply very quickly. but in that one, the conversion can be done with Math/Formulae. this one doesn't. must be caching; I haven't figured any other patterns apart from the obvious (0 -> 1 -> 2024 -> 20 24 -> 2 0 2 4 -> 4048 0 4048 8096) then the 0 repeats and the others split twice and repeat. edit: it was Lantern Fish, 2021 Day 6 edit2: and it also needed a Map, not math formula but I think it only needs 8 entries in the map
m
Nice! A very simple puzzle today, Eric masterfully tries to trick the reader into thinking that the order of the stones has relevance. https://github.com/MikeEnRegalia/advent-of-code/blob/master/src/main/kotlin/aoc2024/day11.kt
j
saved a millisecond by this little trick:
Copy code
private fun Long.blink(times: Long) = when (this) {
    0L -> listOf(1L to times)
    in (10..99) -> listOf(this / 10 to times, this % 10 to times)
    in (1000..9999) -> listOf(this / 100 to times, this % 100 to times)
    in (100000..999999) -> listOf(this / 1000 to times, this % 1000 to times)
    in (10000000..99999999) -> listOf(this / 10000 to times, this % 10000 to times)
    in (1000000000..9999999999) -> listOf(this / 100000 to times, this % 100000 to times)
    in (100000000000..999999999999) -> listOf(this / 1000000 to times, this % 1000000 to times)
    else -> listOf(this * 2024 to times)
}
xd
💡 1
K 1
a
would it help if those Ranges were predefined as Long so that they aren't being cast at runtime ? like 
(10L..99L)
and 
(1000L..9999L)
etc.
j
No memoization, no recursion, just counting
Copy code
Part 1 took 185.833us, result is 239714
Part 2 took 8.262500ms, result is 284973560658514
Untitled.pas
@Anirudh I strongly believed they are resolved to longRange at compiled time. Now you made me wondering 🙂
a
@Jakub Gwóźdź tbh, I have no idea, so I would err on the side of caution. by explicitly making them Longs. I guess it should be obvious to the compiler that all comparisons in that function are being done with 
this: Long
and never `Int`'s but I don't know what compile-time optimisations exist
j
but you're probably right, it was an IntRange and without `L`s it calls 
value.toIntExactOrNull()
Copy code
@kotlin.jvm.JvmName("intRangeContains")
public operator fun ClosedRange<Int>.contains(value: Long): Boolean {
    return value.toIntExactOrNull().let { if (it != null) contains(it) else false }
}
🕵️‍♂️ 1
e
in
range literals get optimized by the compiler anyway
it doesn't actually construct the Range object, it just emits the comparison code
👍 3
a
ok, that's good. I was wondering if the comparison code emitted does casts 
toLong()
. Jakub has confirmed that switching those to `L`'s did not affect performance - so the comparisons are probably being done between `Long`'s and no runtime casting
j
moreover,
Copy code
var l = Random.nextLong()
    val t = l in 40..50
gets compiled to
Copy code
L0
    LINENUMBER 6 L0
    GETSTATIC kotlin/random/Random.Default : Lkotlin/random/Random$Default;
    INVOKEVIRTUAL kotlin/random/Random$Default.nextLong ()J
    LSTORE 0
   L1
    LINENUMBER 7 L1
    LDC 40
    LLOAD 0
    LCMP
    IFGT L2
    LLOAD 0
    LDC 51
    LCMP
...
I assume LCMP is a long compare. And 
40
and 
50
, being literals, are not casted in any way Bytecode is the same for 
40L..50L
🤩 1
K 1
a
this mini thread ⬆️ is what I love about the Kotlin-AoC community 🫶
l
For some reason, if I use 
when(subject)
, there is no warning. But when I use 
when{}
, the IDE will have this warning
😕 1
r
I wonder if IDE is in k2 mode.
l
yeah it is in K2, is that a known problem?
j
can't reproduce, no warning on my side. probably some indexing leftovers
l
And I also kind of wonder if it is provable that the number on the stone is restricted in Long. For example the code of @Jakub Gwóźdź gives wrong answer on my input and need another condition in the 
when
to get it right. Could there be a number that will eventually exceed Long?
j
oh! yeah 12 digits were enough for me, ymmv
a
@Luan Tran Long.Max is
Copy code
9,223,372,036,854,775,807
and Jakub's last range is:
Copy code
999,999,999,999
so yes, it's possible you need 4 more entries (7 more digits) as in, you probably don't exceed Long.MAX but need more entires in the 
when
l
For my input
Copy code
99,999,999,999,999
is enough. But I'm interested in what is the maximal digit reachable by the rule of the game.
a
interesting question. it's possible to backtrack that and assume 2024 division but there's always an "even numbered digit" that would make it split in the question (and hence become smaller). also, Mr. Wastl probably checked that already and made sure to avoid that situation in everyone's input
l
OK, there are two observations about the numbers on the stone for my input: 1. There seems to be at most 3811 distinct numbers on the stones 2. The maximal number is reached since the third blink Reddit posts also mention the maximal number of 3811, so I guess it is the same for everyone
p
@Johnny Wulgaru 
MemoizedDeepRecursiveFunction
has terrible performance for large caches as it uses an 
atomic<Map<K, V>
under the hood to ensure thread safety. I have the following for AoC usage:
Copy code
@Suppress("FunctionName")
fun <T, R> CachedDeepRecursiveFunction(block: suspend DeepRecursiveScope<T, R>.(T) -> R) =
    mutableMapOf<T, R>().run { DeepRecursiveFunction { getOrPut(it) { block(it) } } }
🙌 1
👍 1
j
About the limitations on number of different stones... (warning: NOT A KOTLIN solution) So - since the calculations are really super iterable, I tried to perform them in the google spreadsheet. Unfortunately, ran into really stupid 
#REF
problem after only 23 blinks 😆
mind blown 1
j
If you start with 1_000_000 stones labeled 0 to 999_999, you will have 91909 different numbers after the first blink, then 60595, 67653, 4898, 5783 …. dropping down to a repeating cycle of 3815/3815/3818 different stones
If you start with 1000 different stones labeled 0 to 999 you will have a repeating cycle of 3811 different stones. Looks like that repeating cycle for 1 million stones has 3826 distinct numbers; and 80_000 is the number that adds a repeating sequence that is not encountered in the smaller set
p
I thought about part 2 throughout the whole dinner, and then while brushing my kids teeth it clicked. 💡 No memoization but instead grouping the numbers and then blinking one of them and not every single one. https://github.com/PaulWoitaschek/AdventOfCode/blob/main/2024/src/main/kotlin/aoc/year2024/Day11.kt
p
I was happiest with this -
Copy code
Warming up 2 puzzles for 5s each for year 2024 day 11...
	CountUnique warmed up with 960 iterations
	Default warmed up with 581 iterations
year 2024 day 11 part 1
	 Default took 95.143us 👑: 207683
	 CountUnique took 118.958us (1.25x): 207683
year 2024 day 11 part 2
	 CountUnique took 4.783702ms 👑: 244782991106220
	 Default took 8.291658ms (1.73x): 244782991106220
Day11.kt
k
anyone had example result for p1 50370 and found what the issue was?
e
nobody can tell with that info alone. users have different inputs and different answers
k
I mean example input not my input
it works for first steps in example, but result is of by ~5k
and I can't find error 😕
not sure if I can post my uncomplete solution
ah nvm, found the issue. used set for temporary split keys
n
This one broke my brain in a good way and broke my brain in a bad way. It never crossed my mind to go down, not up. In fact, I still don't have an idea for how that would work and will actually have to look at some of the solutions here. I came up with a way to do it with DP, but it was very byzantine. So I was not surprised when the answer was wrong. And then it was nearly impossible to debug! I tried soooo many ways. I finally wrote a naive solution and then literally printed out every added stone line by line. And discovered... that I was multiplying by 2048 instead of 2024! 🤦‍♂️🤦‍♀️🤦.
😂 1
v
I was very naive with the part1, of course. Everyone on Reddit and on all the youtube videos says about caching and recursion and memoization. Saw a lot of similar code, but still can't understand the concept of what to cache and how to cache and how to apply that cache. Spent several hours on that until gave up eventually 😞
31 Views
Open in Slack
PreviousNext
Powered by