Dec 11, 2024

Advent of Code 2024 - Day 11: Plutonian Pebbles

Attention!

Check Advent of Code for the full challenge details. They created everything we need to know about the challenge - give them your support.
My solutions are not ‘the’ solutions - I target one of the possible solutions. They might not be the most efficient, but they are a way to solve the problem. I do not plan to spend too much time the challenges.
Every challenge = different language - just for fun and learning.
I do not include the input data, but you can find it on the Advent of Code website or in the repository of the code.

In the 11th Advent of Code challenge, I’m tasked with simulating the behavior of a set of stones on Pluto. These stones follow some peculiar rules that cause them to transform every time I “blink.” My goal is to compute how many stones remain after 25 (part one) and 75 (part two) blinks.

The stones begin with a set of numbers engraved on them, and every time I blink, each stone transforms based on one of three rules:

If a stone is engraved with the number 0, it turns into a stone engraved with the number 1.
If the stone has an even number of digits, it splits into two stones, with the left and right halves of the number engraved on the new stones.
Otherwise, the stone is multiplied by 2024.

The solution for today’s challenge will be written in Ruby.

Breaking Down the Problem

The problem requires me to determine how the stones evolve as I simulate a number of blinks. Each stone can undergo one of the three transformations in a single blink, and the transformation depends on the number of digits or the value of the stone.

Part One: Blink Simulation

In Part One, the task is to determine how many stones there will be after 25 blinks. I need to simulate the process for a given sequence of stones, applying the transformation rules for each blink.

To accomplish this, I wrote a recursive function count_stones that keeps track of how stones evolve. It accepts parameters for the current number, the depth of recursion (how many more blinks), a cache for memoization (to avoid recalculating results for the same numbers at the same depth), and a dictionary of lengths for numbers. Here’s the core logic of the function:

# main.rb
def count_stones(num, depth, cache, lengths)
  return 1 if depth == 0
  return cache[num][depth] if cache[num] &&  cache[num][depth]
  if lengths[num].nil?
    lengths[num] = num_length(num)
  end
  queue = []
  if num == 0
   queue << 1
  elsif lengths[num].even?
    f_half, s_half = split_num(num, lengths[num])
    queue << f_half
    queue << s_half
  else
    queue << num * 2024
  end

  count = 0
  queue.each { |num|
    count += count_stones(num, depth - 1, cache, lengths)
  }

  cache[num] ||= {}
  cache[num][depth] = count
  count
end

The function count_stones handles each stone’s transformation based on its number.
For stones with an even number of digits, it splits them into two parts (split_num). For stones with an odd number of digits, they are multiplied by 2024. The exception is when the stone is engraved with 0, in which case it turns into a stone with the number 1.
The result for each number at each depth is stored in a cache to avoid redundant calculations.

Example Input and Output:

For an initial set of stones, such as 125 17, I start by applying the blink transformation rules. After several iterations, the number of stones increases as they split and multiply. After six blinks, the number of stones becomes 2097446912 14168 4048 2 0 2 4 40 48 2024 40 48 80 96 2 8 6 7 6 0 3 2, so it grows significantly - 22 stones.

For 25 blinks, the total number of stones is 55312.

Part Two: Scaling to 75 Blinks

Part Two asks us to compute how many stones there will be after 75 blinks. The main difference here is the increased depth of recursion, which means the simulation needs to handle more complex transformations.

To compute this efficiently, the same count_stones function is used. However, due to the high recursion depth, memoization is crucial to avoid recalculating the same results multiple times.

Today there is no need to implement a separate function for Part Two, as the same function can handle both parts of the challenge.

Fact is, there isn’t really a problem to run the first part wihout any cache, but the second part is a bit more complex and the cache is needed to avoid recalculating the same results multiple times.

Code Structure

I split the problem into several smaller helper functions:

num_length(num): Calculates the number of digits in a number. It is de facto the same logic I used in one of the previous challenges (Day 7).

# main.rb
def num_length(num)
if num < 10
  return 1
end
count = 0
n = num
while n > 0
  n /= 10
  count += 1
end
count
end

split_num(num, length): Splits the number into two parts based on its length.

# main.rb
def split_num(num, length)
  return num / 10**(length/2), num % 10**(length/2)
end

main(filename, iterations): Reads the input file and initiates the simulation for the given number of blinks.

def main(filename, iterations)
file = File.open(filename)
contents = file.read.split(" ")
file.close

cache = {}
lengths = {}

result = 0
contents.each do |value|
  num = value.to_i
  count = count_stones(num, iterations, cache, lengths)
  cache[num][iterations] = count
  result += count
end
result
end

puts main "input.txt", 75

Final Solution Code

The final solution code can be found on my GitHub repository.

If you like the content, don’t forget to give it a star ⭐.

Time Complexity: O(N * D), where N is the number of stones and D is the number of blinks (iterations). For each stone, my solution performs a transformation based on its number of digits, which involves splitting or multiplying the number. This operation is repeated for each blink. Due to memoization (caching), each unique number at a given depth is computed only once.

Space Complexity: O(N * D), where N is the number of distinct stones and D is the depth (number of blinks). This space is used by the cache, which stores the result for each number at each depth to avoid redundant calculations.

Conclusion

This challenge was fun because it required both recursive problem-solving and optimization using memoization. The primary challenge was efficiently simulating how stones evolve over multiple blinks, especially when the depth of recursion increases to 75.

This day’s challenge was a great exercise, although it was not as complex as some of the previous ones. It was a good opportunity to practice recursion and memoization in Ruby.

Ruby - a language that is not my primary one, but I enjoyed it more that Python.

Tomorrow, I’ll be solving Day 12 using Scala.