https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2021 day 24> :thread:
# advent-of-code
a
d
Memoization to the rescue yet again! Still my poor CPU fan...
same 1
e
Has anyone figured out a smart way to solve it? It looks like the whole code is actually doing something quite logical, doing computations and checks modulo 26.
i
I found one solution manually by reverse engineering, then figured out which pair of digits nullify each other and minimized/maximized solution in each pair one by one.
šŸ’Ŗ 1
It seems to be also possible to find all solutions knowing these pairs of digits affecting each other by minimizing the program result in each pair until it reaches 0.
p
I stopped at day 18 as the puzzles took more time than I could fill into my short "kids are sleeping while I am not" window.
same 1
šŸ™Œ 1
n
I'm a bit disappointed: this looks more like "advent of genius" than "advent of code" because I cannot see how a "coding solution" will work for this day. This is not about coding an interpreter, this is about analyzing the input and finding a hidden pattern. Or I am just not smart enough to see what coding approach to use.
šŸ’Æ 2
e
I have what I think is a relatively elegant solution - recursive brute-force with some cut-offs - but it takes a few minutes to run https://github.com/ephemient/aoc2021/blob/main/kt/src/commonMain/kotlin/com/github/ephemient/aoc2021/Day24Common.kt
n
hmm, would your cut-offs work for any input or are you using some "hidden" aspects of the "program". I see that it is using the same subset of instructions repeated 14 times (once per input digit) with some variations of constant values. But I hesitate to make use of that because the problem description suggests that the input could be any valid "program".
e
The standard dynamic programming (memoization) approach works here. Takes a little of code, really stupid, no genius needed. Runs part 1 is one minute for me.
d
A*, finally ā€” dijkstra works for part 1 but not part 2. https://github.com/dfings/advent-of-code/blob/main/src/2021/problem_24.main.kts
Mine exploits patterns in the input program
e
@nkiesel works for any input, it's just avoiding re-computation if multiple 
inp
lead to the same state
solves my part 1 in 5 seconds and part 2 in 3Ā½ minutes
e
Mine is the opposite - fast on part2, because my part2 answer starts with 11, while my part1 answer starts with 94, so thereā€™s 9 down to 5 digits to check and eliminate in the second position to find the answer.
e
my part 2 starts with 62 šŸ˜µ
d
Part 1: 650ms, Part 2: 50 seconds
Iā€™m confused, my part 2 answer starts with 93
And part 1 with 99
Looks like it still works if I generalize my Vertex to contain the complete state of the registers instead of just the Z register (thus doesnā€™t depend on the fact that each block resets X and Y to zero each time and W is always used as the input register). Runtime goes up, 1.8s for part 1, 6.5 min for part 2.
Oh I didnā€™t realize the puzzle inputs are different
DP approach somewhat faster, 450 ms for part 1, 34 sec for part 2 (exploiting structure)
e
https://github.com/ephemient/aoc2021/blob/main/kt/src/jvmMain/kotlin/com/github/ephemient/aoc2021/Day24Jvm.kt wrote some code to convert ALU instructions into Java bytecode. even without changing any of my logic, it runs ~20x faster than interpreting the instructions in Kotlin code
šŸ’Ŗ 2
n
I finally found time to work on this. My code works for part 1, but does not find any valid solution for part 2. I thought that the only difference is that for part 1 we need to iterate from 9 downTo 1 while for part 2 we need to iterate from 1 to 9. Am I still missing something ? BTW: Happy Holidays to all of you and please stay healthy!!!
never mind, I found my bug.
j
since it works in mod 26, I hoped there will be a hidden message when I use 
z.toString(26).map { 'A' + it.digitToInt(26) }.joinToString("")
, but unfortunately, itā€™s just random letters, even after rot13
k
Video of me walking through it:

https://www.youtube.com/watch?v=Yodga7UAg-o&amp;ab_channel=XenoTacticā–¾

j
Since x, y will reset every time in each section, and w is 1 .. 9 all the time, we can keep track of z only and increase a bit in memory and speed performance. Here's my solution: https://github.com/Jintin/AdventCode2021/blob/main/src/Day24.kt
p
I finally got around to finishing this. Took much longer than I'd have liked but got there in the end. I attempted to flatten each output register into an expression of the input digit and existing registers - it allowed me determine the set of input registers used by subsequent steps and cache appropriately. I'm hoping it means it would adapt to situations where not only z registers are propagated between steps but šŸ¤· https://github.com/tKe/aoc-21/blob/main/kotlin/src/main/kotlin/year2021/Day24.kt either way it runs in ~70ms for part1 (result starting 999997) and ~20s for part2 (result starting 4531) so I'm happy.
m
Late to the party ā€¦ hereā€™s my solution anyway. šŸ™‚ https://github.com/MikeEnRegalia/AdventOfCode2021/blob/main/kotlin/src/main/kotlin/Day24.kt
I wonder whether anyone else did what I did? Was thinking about how to approach this all through the christmas celebrations. Then I finally discovered the pattern in the algorithm - thereā€™s seven inputs for which given the preceding z value, exactly one digit will lead to x being 0 and thus z will be divided by 26, and thus is the only way to get z=0 at the end (the last digit divides by 26 and truncates to zero). This cuts down the number of states so much that brute force works (takes ~3 seconds for the combined part1/part2 solution). This is the shortcut in code:
Copy code
// I only know my input, so no idea whether this works for other users :-)
private val monadReductions = input.windowed(2).filter { it[0].startsWith("div z ") }.map {
    if (it[0].endsWith(" 1")) null else it[1].substringAfterLast(" ").toInt()
}

private fun digitsToTry(data: List<Int>, r0: List<Int>) =
    when (val offset = monadReductions[data.size]) {
        null -> 1..9
        else -> ((r0.last() % 26) + offset).let { if (it !in 1..9) emptyList() else listOf(it) }
    }
So in these seven digits, we donā€™t need to try 1..9, but only (z % 26) + offset, where offset is a negative value (add x -n).
šŸ‘Œ 1
Itā€™s surely no coincidence that in the algorithm, all the digits that have ā€œdiv z 26ā€ have such a negative offset, whereas the other seven digits that have ā€œdiv z 1" donā€™t šŸ™‚
p
@Michael Bƶiers I kept my initial solution as a "proper" ALU processor, however I've taken your approach on board along with isolating the 3 changing constants in each block and having an optimized invocation for defined for each one - it now solves my part1 in ~9ms and part 2 in ~6ms
e
I've come up with a Haskell solution that runs in <1s without relying on the input structure, by validating each brute-force guess with a lookahead of "what are the ranges of all possible values". haven't had the energy to port it to Kotlin yet though, so many other things to optimize firstā€¦
plus I rather like my bytecode JIT solution that can brute-force in 3s šŸ™‚
p
I tried translating the input text into kotlin code and compiling/running it through jsr223 but it was horrendously slow.
e
it's important to prune duplicate states. I implemented a fixed-size self-evicting mutable set backed by a Array<State?> indexed by hash - faster than a HashSet, and false negatives are OK (it just fails to avoid duplicate work, but it's still a win overall), I'm only checking for dups right before 
inp
instructions since that's where it's effective, and I'm clearing the target register as well to increase hit rates
p
I assume you have a reason for not just applying the salt to the hashcode of the element within the CacheSet instance (i.e. 
data[(element.hashCode() * 31 + salt) % data.size] == element
)
e
not very important, it's pretty much just a port from my previous Haskell solution
I should probably drop the salt entirely and use 
.hashCode()
directly
gone now
šŸ‘Œ 1
p
So this CacheSet is effectively lowing the overhead of HashSet at the expense of losing any collisions - so the idea would be the overhead of recomputing an older state that was overwritten by a collision is lower than the overhead of maintaining collisions?
e
yes, exactly. also I needed to have a cap on the size of the set to avoid OOM on part 2, and this is an easy way to do it (I have a previous commit using an LruSet with least-recently-used eviction policy, but that also ended up being more costly than the simpler CacheSet)
d
I increased heap size to 16G and then got no OOMs without an eviction policy
e
I'm running my solutions on GitHub Actions runners that have 7GB memory available, so that's not an option šŸ™‚ (also how much memory it uses is highly dependent on your input)
6 Views
Open in Slack
PreviousNext
Powered by