Learnings - Advent of Code 2024
Things I've learned from Advent of Code, 2024.
While solving problems for this year's Advent of Code, there were just a few things I wanted to note down that I learned from solving some of the challenges!
To preface, I haven't been able to fully keep up with solving all the challenges, but I will try my best to get to them!
Storage can be cheap - CPU is expensive
Sometimes, we need to store stuff to reserve the CPU to calculate new stuff. That means we may sometimes need to take up memory temporarily in order for the CPU to perform newer tasks. As long as the memory usage is temporary (or in some cases, permanent), we can store it pretty cheaply.
For example, in a lot of the tasks, the solution for part 2 depends on constraints from part 1. So if we need part 1's solutions, we can run both solutions together in sequence. If a situation has been already calculated once in part 1, we don't need to run it again in part 2.
In Day 7 this time, we could specifically run the entire sample set with day 1's constraints, and reuse the results to figure out day 2.
This can be seen as follows:
solved = []
unsolved = []
# part 1
input_values.each do |input|
matched = process_part1(input)
solved << input if matched
unsolved << input if !matched
end
# part 2
unsolved.each do |input|
solved << input if process_part2(input)
end
We solve for part 1, and then we only solve the remaining ones for part 2. There's no reason to run through the entire suite of inputs for part 2.
In real life, this might end up being a database or a cache where you store things that you need later - but don't want to calculate them again.
Memoization
During some challenges, there are a lot of calculations you're doing. Some of these calculations involve solving the same thing again and again. In this case, you can memoize the results once, so you don't need to calculate them again.
This is in line with the previous section about storage being cheaper, though memoization is short-lived a lot of the time.
In Ruby, we can use some built-in features to memoize a variable that can take a long time to process again, and the result would be the same.
Memoization works really well for pure functions, where given the inputs are the same, we will always get the same output.
If we consider this function in Ruby to calculate Fibonacci numbers, we would greatly benefit from memoizing the results we calculate because they would come up over and over.
def fibonacci(n, memo = {})
return n if n <= 1
memo[n] ||= fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
end
The differences here are staggering with, and without memoization.
Calling the following function: fibonacci(42)
- with memoization:
0.06s
- without memoization:
24.35s
This of course is an extreme example, but we have basically an infinite performance gain, with just memoizing some values temporarily.
Also, I tried to run fibonacci(100)
but ultimately got tired of waiting!
With that said, if you'd like to follow my progress after this, or just check out my solutions, feel free to look at my GitHub repository: aryascripts/advent-of-code!
Note: these are definitely not the best solutions out there, so I'm open to feedback about anything you find!