6
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
this post was submitted on 10 Dec 2024
6 points (100.0% liked)
NotAwfulTech
385 readers
2 users here now
a community for posting cool tech news you don’t want to sneer at
non-awfulness of tech is not required or else we wouldn’t have any posts
founded 1 year ago
MODERATORS
Day 11!
discussion p1 + 2
I'd say this was pretty easy. My instinct was that 64 bit ints were big enough for this problem, and that memoising would also be a good idea. I didn't experiment with a control though, so I don't know if memoisation was truly necessary. Either way, my initial solution for 1. was performant enough for part 2.followup
So memoisation is predictably needed for part 2 to run in time. It's an O(e^n^), so it takes seconds by step 39 and minutes by step 47.re:followup
If you somehow wanted your whole final array it would also require over 1 Peta byte ^^, memoization definetely reccomended.spoiler
It's one AOC problem zogwarg, what could it cost? 10 PB?11 discussion with spoliers
Well my pt1 solution would require something like at least 1.5 petabytes RAM to hold the fully expanded array, so it was back to the drawing board for pt2 😁Luckily I noticed the numbers produced in every iteration were incredibly repetitive, so I assigned a separate accumulator to each one, and every iteration I only kept the unique numbers and updated the corresponding accumulators with how many times they had appeared, and finally I summed the accumulators.
The most unique numbers in one iteration were 3777, the 75 step execution was basically instant.
edit: other unhinged attempts included building a cache with how many pebbles resulted from a number after x steps that I would start using after reaching the halfway point, so every time I found a cached number I would replace that branch with the final count according to the remaining steps, but I couldn't think of a way to actually track how many pebbles result downstream from a specific pebble, but at least it got me thinking about tracking something along each pebble.
11 code
re: 11p2 discussion
I was also on my way to building a multilevel memoization cache with "branches", when I just happened to stumble on an incredibly elegant solution in the subreddit. I stole it and awarded myself only 1 point for today. Because I'm worth it.