https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2024 day 21> (spoilers) :thread:
# advent-of-code
a
m
Finally, solved part 2. Took me forever
p
Yeah, today broke my head in many ways 😄 The cleanup of my solution would take some time
p
Copy code
Warming up 1 puzzles over 10s for year 2024 day 21...
Warmup finished after 10.000964875s with 5687 iterations
year 2024 day 21 part 1
	 Default took 184us 👑: 238078
year 2024 day 21 part 2
	 Default took 1.653916ms 👑: 293919502998014
urgh. now to clean up my code. Went for a recursive approach, luckily already had "robots: Int = 2" as a default param. Slapped some cacheing on it and 💥
if I share the cache between codes:
Copy code
Warmup finished after 10.000183334s with 60563 iterations
year 2024 day 21 part 1
	 Default took 65.541us 👑: 238078
year 2024 day 21 part 2
	 Default took 104.429us 👑: 293919502998014
m
my brain broke this morning
Day 21 Michael.cpp
same 1
p
Finaly got it to somewhat commitable form (part 2 ~50ms cold start) and resigning to refactor it more atm 😄 https://github.com/glubo/adventofcode/blob/main/src/main/kotlin/cz/glubo/adventofcode/y2024/day21/Day21.kt
m
j
Nice one for a Saturday. I solved part 1 building all the full move lists, and then for part2 changed it to recursing all the moves individually and counting their best expansions. It was a bit of guess that I could just count the expansions of individual moves, but since there is always the ‘Action’ move (and starting position) that seemed like a safe bet. https://github.com/JBeet/MyAdventOfCode2024/blob/main/src/Day21.kt
k
Whew! This was a really hectic one! Took a long break and came back to it. Implemented the approach that kept coming back to me all morning, and it finally worked. Cleaned up quite nicely: Solution
Copy code
Cold
Part1: ~8.0ms, Part2: ~6.8ms

Warm:
Part1: ~240µs, Part2: ~900µs
m
memoization today wasn't even that big of a cache: 509 unique keys but even in that small space, asking the same routes over and over is expensive
➕ 2
m
This one took forever. Tried a naive solution for part 1 which didn't even work. Spent ages trying to debug it, threw it away eventually and went for a recursive solution. Part 2 was relatively easy then (added a cache and done). Day21.kt
b
finally got mine cleaned up, and p2 is ~250us on my old computer
h
Ok, so without looking at the solutions posted up... I get the feeling that my solution that works on examples, doesn't work on the input, because I need to recursively check all path lengths... at ALL "levels" in the chain of robots to find the shortest path. right?
so, (at least for Part 1)... find possible paths on keypad (between start key and target key), then for each one, check the possible paths on robot dirpad, then foreach of those, check the possible paths on next robot dirpad, then foreach of those, check the possible paths on MY dirpad... and then I need to use the shortest moves on MY dirpad.
f
wow @kingsley I’ve struggled too much with this one now and more-or-less gave up, but glad I went through your code - so nice & clear - thanks. 🙇
❤️ 1
e
I got sooooo close to global leaderboard with my Haskell solution last night
decided to take a slightly more interesting approach for Kotlin, creating a lookup table with build time code generation https://github.com/ephemient/aoc2024/blob/main/kt/aoc2024-lib/src/jvmCodegen/kotlin/com/github/ephemient/aoc2024/codegen/Day21.kt
https://github.com/ephemient/aoc2024/actions/runs/12449295551/job/34754792536#step:6:918
Copy code
Day21Bench.part1  avgt    5        0.150 ±      0.002  us/op
Day21Bench.part2  avgt    5        0.150 ±      0.001  us/op
Day21Bench.solve  avgt    5        0.202 ±      0.003  us/op
nanosecond territory because it's just a few lookups :D
j
maybe I abused rules a bit, but... I had fun! (yesterday I was fighting for the way to generate these shortest mappings, today I was fighting for the way to fit gigabyte-long strings in the memory 🙂 )
Untitled.pas
d
Finally got a chance to work on this. Saw the right solution from the beginning (min of mins recursive with DP) and anticipated part 2. Minor off by 1 and int/long errors. Somewhat tedious to implement but 2 stars.
Precompute all pairwise shortest paths on number and dir pads. Will link code later.
Key insight is dir pad controller always starts and ends on A so it's effectively stateless
And thus partitionable
e
💯
and thanks to that, you "only" need a lookup table for the number of moves between pairs of keys. then as the lookup table for robot N is buildable from the lookup table for robot N-1, it can go rather fast
☝️ 1
I went with building it at runtime in Day21.hs day21.py day21.rs but for Kotlin I was cheeky and did it at build time 😛
honestly I like Haskell here for a few reasons, but one is that you can use arbitrary types (such as pairs of 2D coordinates) as array indices as long as they're enumerable 🙂
d
Actually have not committed part 2 final yet
Got the star, closed the laptop lol.
Ok cleaned it up
Most of the code is preprocessing
Core logic
30 Views
Open in Slack
PreviousNext
Powered by