More camels and oasis-es, less cards.

In this puzzle, we're using our trusty Oasis And Sand Instability Sensor — OASIS — to analyse our surroundings.

The OASIS produces a history for each value, and we need to extrapolate the next value from the current set of values.

Part 1

Our input looks like this:

0 3 6 9 12 15
1 3 6 10 15 21
10 13 16 21 30 45

Each row represents the history of a value, with the earliest entry on the left.

The way we extrapolate a value is by finding the difference between the first and second values, the second and third, and so on. This will produce another set of values — this set will be 1 shorter than the initial set. We then repeat the process on the new set until all values are zero.

This is how the above process can be visualised.

0 3 6 9 12 15
  3 3 3 3 3
    0 0 0 0

Once we're at this stage, we can (starting from the array of all 0s), add the last element of the last array to the last element of the previous array until we're back at the top — the result will be the extrapolated item.

So in the above example, 0 + 3 = 3, 3 + 15 = 18, 18 is our extrapolated value.

def part1(input)  
  extrapolated_values = input.map do |line|  
    nums = [line.split(" ").map(&:to_i)]  

    while !nums.last.all?(&:zero?) do  
      nums << next_in_series(nums)  
    end  

    nums.reverse.inject(0) do |sum, numbers|  
      sum + numbers.last  
    end  
  end  
  extrapolated_values.sum  
end

def next_in_series(numbers)  
  numbers.last.map.with_index(1) do |n, i|  
    next if i+1 > numbers.last.count  

    numbers.last[i] - n  
  end.compact  
end

Here's all my code for the above algorithm.

The first piece maps over our input, creates the first set of numbers [[0, 3, 6, 9, 12, 15]], then, while the last set of numbers isn't all 0, calculates the next set.

Then, starting from the array of 0s, it adds the last number of each array to the next until we loop through each item and come up with our next number in the set!

⭐️ Success!

Part 2

Part 2 asked us to extrapolate in the other direction — what's the number that comes before 0 in this case?

Once we get that number for each row, we can again sum everything up.

This was almost identical to part 1, except the starting set of numbers is reversed:

nums = [line.split(" ").map(&:to_i).reverse]

⭐️ Success!

Code: https://github.com/dNitza/advent-of-code/tree/main/2023/09

Performance

Pretty snappy today — I was looking to see if there were any extrapolation algorithms that could reduce the time here, but my searching didn't produce much.

day 09
├─ part 1 — 0.003131s
╰─ part 2 — 0.00299s