🎄 Advent of Code 2'023 - Day 09

Published data: 9 December 2023

Day 09: Mirage Maintenance

* Cf. aoc. d. ix xxiii

Abridged Problem Description: Given a dataset of numbers, we are required to predict the next number in the sequence.

Parsing The Input

First, I’d like to have a line-by-line vector<string> of the input. Then I can parse it further.

vector<string> input = Utils::split_lines(Utils::read_file("input/day_09_input"));

To parse every line into a vector<int64>, we can do the following:

vector<vector<int64>> day_09_input(input.size(), vector<int64>());

for (auto &n : input) day_09_input.push_back(Utils::parse_v_numbers(n));

Bene Nota: I’m ignoring the first line because that is our instructions.

PARS I

The first part is straightforward. We need to get the last number of the input after each iteration, also taking into account that the result is always n - 1.

int64 sum = 0;

for (vector<int64> data : lines) {
  do {
    if (data.empty()) continue;
    sum += data.back();
    std::adjacent_difference(data.begin(), data.end(), data.begin());
    data.erase(data.begin());
  } while (!std::all_of(data.begin(), data.end(), [](auto d) { return d == 0; }));
}

return sum;

That was an easy star 🌟

PARS II

For the second part, we need to predict the previous number in the sequence instead of the next one. This requires a slight modification to our approach.

α

The key insight is that we need to work backwards through the difference sequences. Instead of adding the last number of each level, we need to subtract the first number of each level from the previous value.

int64 sum = 0;

for (vector<int64> data : lines) {
  vector<vector<int64>> sequences;
  sequences.push_back(data);
  
  // Build difference sequences
  while (true) {
    vector<int64> diff;
    for (size_t i = 1; i < data.size(); ++i) {
      diff.push_back(data[i] - data[i-1]);
    }
    sequences.push_back(diff);
    data = diff;
    
    if (all_of(diff.begin(), diff.end(), [](auto d) { return d == 0; })) {
      break;
    }
  }
  
  // Extrapolate backwards
  int64 prev_value = 0;
  for (int i = sequences.size() - 2; i >= 0; --i) {
    prev_value = sequences[i][0] - prev_value;
  }
  
  sum += prev_value;
}

return sum;

β

The algorithm works by:

1. Building the same difference sequences as in Part 1
2. Starting from the all-zeros sequence with prev_value = 0
3. For each level going backwards, we calculate prev_value = first_number - prev_value
4. The final prev_value is the predicted previous number in the original sequence

Here’s the complete solution:

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

class Solution_09 {
public:
    static int64 part1(const vector<vector<int64>>& lines) {
        int64 sum = 0;

        for (vector<int64> data : lines) {
            do {
                if (data.empty()) continue;
                sum += data.back();
                std::adjacent_difference(data.begin(), data.end(), data.begin());
                data.erase(data.begin());
            } while (!std::all_of(data.begin(), data.end(), [](auto d) { return d == 0; }));
        }

        return sum;
    }

    static int64 part2(const vector<vector<int64>>& lines) {
        int64 sum = 0;

        for (vector<int64> data : lines) {
            vector<vector<int64>> sequences;
            sequences.push_back(data);
            
            // Build difference sequences
            while (true) {
                vector<int64> diff;
                for (size_t i = 1; i < data.size(); ++i) {
                    diff.push_back(data[i] - data[i-1]);
                }
                sequences.push_back(diff);
                data = diff;
                
                if (all_of(diff.begin(), diff.end(), [](auto d) { return d == 0; })) {
                    break;
                }
            }
            
            // Extrapolate backwards
            int64 prev_value = 0;
            for (int i = sequences.size() - 2; i >= 0; --i) {
                prev_value = sequences[i][0] - prev_value;
            }
            
            sum += prev_value;
        }

        return sum;
    }
};

Awesome! We solved the spooky puzzle! 🌟🌟