Day 9: Mirage Maintenance

In this case, rather than stopping once we see all zeros it's easier to just go all the way to when it's just a single digit (which will certainly be zero if a previous row is zero, and if not then the next row will contain no digits and be "all zeros" anyway).

After that, we can just take the last element of each array to build the next column in the consecutive differences.

Even if you don't go through the effort of proving that, if you kept all those consecutive difference arrays you can always just go back and extract the first values to go backwards one step.

#include <bits/stdc++.h>
using namespace std;
vector<long long> consecutive_diff(const vector<long long>& p) {
	vector<long long> ans;
	for(int i=1;i<p.size();i++) {
		ans.push_back(p[i]-p[i-1]);
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(0);cout.precision(20);cout.tie(0);cin.tie(0);
	string line;
	long long next_ans = 0;
	long long prev_ans = 0;
	while(1) {
		getline(cin,line);
		if(line.empty()) {break;}
		stringstream ss(line);

		vector<vector<long long>> diffs;
		diffs.emplace_back();
		long long t;
		while(ss >> t) {
			diffs.back().push_back(t);
		}
		while(diffs.back().size() > 1) {
			diffs.push_back(consecutive_diff(diffs.back()));
		}
		vector<long long> next(diffs.size()),prev(diffs.size());
		for(int i=diffs.size()-2;i>=0;i--) {
			prev[i] = diffs[i][0]-prev[i+1];
			next[i] = diffs[i].back()+next[i+1];
		}
		next_ans += next[0];
		prev_ans += prev[0];
	}
	cout << next_ans << '\n';
	cout << prev_ans << '\n';
}

We might hope that this algorithm terminates quickly for all inputs, but in fact you can find inputs that force it to run in O(n^2). Examples include 1,2,4,8,16,...,2^n or 0,1,0,-1,0,...,sin(pi*n/2).

The question is then:

Given a list of N elements, can you find the next value with this consecutive-differences algorithm in faster than quadratic time?

I already gave away that the answer is yes, but people smarter than me have shown connections to much cooler math in order to get there.

The big leap here is to realize that this problem is equivalent to Polynomial Interpolation which might feel crazy if you haven't seen it before.

The basic idea is this: Look at the consecutive differences for polynomials:

n:

0 1 2 3 4
 1 1 1 1
  0 0 0

n^2:

0 1 4 9 16
 1 3 5 7
  2 2 2
   0 0

n^3:

0 1 8 27 64
 1 7 19 37
  6 12 18
    6 6
     0

And you'll notice that n takes 1 step to reach fixed consecutive differences, n^2 takes two, and n^3 takes 3. We might wonder whether this pattern continues, and it does! Starting from first principles takes forever, but just as a next step you should consider how consecutive differences looks when expressed with polynomials.

From this fact with polynomals we can work backwards, i.e. looking at the consecutive differences from bottom to top and re-adding polynomials to get the original list of numbers.

That would look something like

1 2 4 7 11 16
 1 2 3 4  5
  1 1 1 1

-(1/2)n^2 =
1 1.5 2 2.5 3 3.5
.5  .5 .5 .5 .5 
   0  0  0  0  

-(1/2)n =
0 0 0 0 0 0

And working from the bottom means that this polynomial will have minimal degree (i.e. you can't magic a simpler polynomial using some other method).

Then, going back to our original problem, this is essentially transforming our list of numbers a_0,a_1,a_2,a_3,...,a_n into a set of coordinates (0,a_0),...,(n,a_n) and finding the least degree polynomial P where P(x) = a_x for 0 <= x <= n and this gives us our solutions for Part 1 and Part 2: The part 1 answer is P(n+1) and the Part 2 answer is P(-1).

Okay this all loops back around to that faster than quadratic solution because we have a much faster way to calculate a polynomial from its points: Lagrange Interpolation which is certified math by its math person name. Unfortunately the documentation on this is a little sketchy, but thanks to the ever cursed Fast Fourier Transform you can actually do this in O(n log^2(n)). The best source I found in my 1 minute of searching is here. I know that this algorithm works because I've used it before, but it's just really bad to describe without drowning in math.

As a bonus bonus, this also gives us a radically different way to prove that reversing the list works for Part 2:

Reinterpreting our list again as coordinates, we already know that there is some least degree polynomial P that will match every coordinate on the list, and that the next and previous values are P(n+1) and P(-1), respectively.

If we reverse our list, this list must also have a least degree polynomial (which we could call Q) that matches every coordinate on that list. But wait, Q(x) = P(n-x) works, doesn't it? P and Q should have the same degree so P(n-x) should work just as well to fit the description of such a Q. Furthermore, Q(n+1) = P(n-(n+1)) = P(-1) so the next element for the reversed array is indeed the previous element of the regular array.

There's even more bonus by the way: something missing from this is whether the least degree polynomial was unique. We secretly assumed this fact during the reversal proof, but you can get sucked into even more different math (in this case matrices) because there's always more math.

Total[InterpolatingPolynomial[#, Length@# + 1] & /@ Import["input.txt", "Table"]]

Total[InterpolatingPolynomial[#, 0] & /@ Import["input.txt", "Table"]]

import { getInput } from "./input";
import * as utils from "./utils";

const input = getInput();
const sequences = input
  .split("\n")
  .filter((s) => !!s)
  .map((s) => utils.ints(s));

let sum = 0;
sequences.forEach((seq) => {
  const stack = [];

  let arr = seq;
  let next = [];

  stack.push(seq);
  while (!arr.every((s) => s === 0)) {
    for (let i = 0; i < arr.length - 1; i++) {
      const v = arr[i + 1] - arr[i];
      next.push(v);
    }
    stack.push(next);
    arr = next;
    next = []; // forgot this line and had to chase a crazy Node crash
  }

  // here's my fun one-liner calculation to find the next value in the sequence
  const val = stack.map((s) => s[s.length - 1]).reduce((a, c) => a + c, 0);
  sum += val;
});

console.log(sum);

import { getInput } from "./input";
import * as utils from "./utils";

const input = getInput();
const sequences = input
  .split("\n")
  .filter((s) => !!s)
  .map((s) => utils.ints(s));

let sum = 0;
sequences.forEach((seq) => {
  const stack = [];

  let arr = seq;
  let next = [];

  stack.push(seq);
  while (!arr.every((s) => s === 0)) {
    for (let i = 0; i < arr.length - 1; i++) {
      const v = arr[i + 1] - arr[i];
      next.push(v);
    }
    stack.push(next);
    arr = next;
    next = [];
  }

  const vals = stack.slice(0, -1).map((x) => x[0]);
  // Stack math!
  while (vals.length > 1) {
    const right = vals.pop()!;
    const left = vals.pop()!;
    vals.push(left - right);
  }
  sum += vals[0];
});

console.log(sum);

use std::env;
use std::io::{self, prelude::*, BufReader};
use std::fs::File;

#[derive(Debug)]
struct History {
    values: Vec<isize>,
}
impl From<&String> for History {
    fn from(s: &String) -> Self {
        Self {
            values: s.split_whitespace().map(|n| n.parse::<isize>().unwrap()).collect(),
        }
    }
}
impl History {
    pub fn solve(&self) -> (isize,isize) {
        // Initializations
        let mut values:       Vec<isize> = self.values.clone();
        let mut first_values: Vec<isize> = vec![*values.first().unwrap()];
        let mut last_values:  Vec<isize> = vec![*values.last().unwrap()];
        // Do diffs
        loop {
            let diffs: Vec<_> = values.windows(2).map(|v| v[1] - v[0]).collect();
            values = diffs.clone();
            first_values.push(*diffs.first().unwrap());
            last_values.push( *diffs.last().unwrap());
            if diffs.iter().all(|v| *v == 0isize) { break; }
        }
        // Identify first value
        let first = first_values.iter().rev().fold(0, |acc,x| x - acc);
        (last_values.iter().sum(),first)
    }
}

fn solve(input: &str) -> io::Result<()> {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    // Input
    let input: Vec<String> = match reader.lines().collect() {
            Err(err) => panic!("Unknown error reading input: {err}"),
            Ok(result) => result,
    };
    let input: Vec<_> = input.iter().map(History::from).collect();

    let part1: isize = input.iter().map(|x| x.solve().0).sum();
    println!("Part 1: {part1}"); // 1684566095

    let part2: isize = input.iter().map(|x| x.solve().1).sum();
    println!("Part 2: {part2}"); // 1136

    Ok(())
}


fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    solve(&filename).unwrap();
}

import json
import re
from copy import copy, deepcopy


class Solver:

    def __init__(self):
        with open('input.txt', 'r', encoding='utf-8') as f:
            self.lines = [line.strip() for line in f.readlines()]
        self.data = [self.parse_line(line) for line in self.lines]

    @staticmethod
    def parse_line(line):
        return [int(i) for i in line.split(' ')]

    def run(self):
        total = 0
        for line in self.data:
            print(f"New line: {str(line)}")
            differences = []
            current = copy(line)
            while any([i != 0 for i in current]):
                new = []
                for i, x in enumerate(current):
                    if i == 0:
                        continue
                    new.append(x - current[i-1])
                differences.append(current[-1])
                current = new
                print(current)
            differences.reverse()
            total += sum(*[differences])

        return total


if __name__ == '__main__':
    print(Solver().run())

# Advent of Code 2023
# Day 9: Mirage Maintenance

histories = []

with open("inputs/day_9.txt") as file:
    for line in file:
        histories.append([int(n) for n in line.split(" ")])

next_prediction_sum = 0
prev_prediction_sum = 0

for history in histories:
    right_ends = [history[-1]]
    left_ends = [history[0]]

    working = history.copy()

    while True:
        for i in range(len(working) - 1, -1, -1):
            if i >= 1:
                working[i] = working[i] - working[i - 1]

        working = working[1:]

        if all(n == working[0] for n in working):
            next_prediction = working[-1]
            prev_prediction = working[0]

            for n in reversed(right_ends):
                next_prediction += n

            for n in reversed(left_ends):
                prev_prediction = n - prev_prediction

            next_prediction_sum += next_prediction
            prev_prediction_sum += prev_prediction

            break
        else:
            right_ends.append(working[-1])
            left_ends.append(working[0])

print(f"Part 1: {next_prediction_sum}")
print(f"Part 2: {prev_prediction_sum}")

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Aoc9 {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in).useDelimiter("\n");
        int accum = 0;
        while (scan.hasNext()) {
            String history = scan.next();
            accum += solve2(history);
        }
        System.out.println(accum);
    }

    private static int solve1(String history) {
        int[] input = Arrays.stream(history.split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        ArrayList<int[]> historyTiers = new ArrayList<>();
        historyTiers.add(input);

        int[] current = input;
        while(!isAllZero(current)){
            System.out.println(Arrays.toString(current));
            current = diff(current);
            historyTiers.add(current);
        }

        int nextValue = 0;
        for (int i = historyTiers.size() - 2; i >= 0; i--) {
            int[] currentTier = historyTiers.get(i);
            int lastValue = currentTier[currentTier.length - 1];
            nextValue = lastValue + nextValue;
        }

        return nextValue;
    }

    private static int solve2(String history) {
        int[] input = Arrays.stream(history.split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        ArrayList<int[]> historyTiers = new ArrayList<>();
        historyTiers.add(input);

        int[] current = input;
        while(!isAllZero(current)){
            current = diff(current);
            historyTiers.add(current);
        }

        int nextValue = 0;
        for (int i = historyTiers.size() - 2; i >= 0; i--) {
            int[] currentTier = historyTiers.get(i);
            int firstValue = currentTier[0];
            // lastNextValue = firstValue - nextValue
            // -nextValue = lastNextValue - firstValue
            // nextValue = firstValue - lastNextValue
            System.out.printf("Tier %d, %d - %d\n", i, firstValue, nextValue);
            nextValue = firstValue - nextValue;
        }
        System.out.printf("Input: %s, out = %d\n", Arrays.toString(input), nextValue);

        return nextValue;
    }

    private static int[] diff(int[] input) {
        int[] out = new int[input.length - 1];
        for(int i = 1; i < input.length; i++){
            out[i-1] = input[i] - input[i-1];
        }
        return out;
    }

    private static boolean isAllZero(int[] input) {
        return Arrays.stream(input).allMatch(i -> i == 0);
    }
}

object Day09 {
    fun parse(input: String): List<List<Long>> {
        return input.lines().map { longsOf(it).toList() }
    }

    fun diff1(l: List<Long>) = l.windowed(2).map { it[1] - it[0] }
    fun diffN(l: List<Long>): List<List<Long>> {
        val result = mutableListOf(l)
        while (!result.last().all { it == 0L }) {
            result.add(diff1(result.last()))
        }
        return result
    }

    fun fillForward(triangle: List<List<Long>>): List<List<Long>> {
        val result = mutableListOf<List<Long>>(triangle.last() + listOf(0))
        for (i in triangle.size - 2 downTo 0) {
            result.addFirst(triangle[i] + listOf(triangle[i].last() + result.first().last()))
        }
        return result
    }

    fun fillBackward(triangle: List<List<Long>>): List<List<Long>> {
        val result = mutableListOf<List<Long>>(listOf(0L) + triangle.last())
        for (i in triangle.size - 2 downTo 0) {
            result.addFirst(listOf(triangle[i].first() - result.first().first()) + triangle[i])
        }
        return result
    }

    fun part1(input: String): Long {
        val seqs = parse(input)
        return seqs.sumOf { fillForward(diffN(it)).first().last() }
    }

    fun part2(input: String): Long {
        val seqs = parse(input)
        return seqs.sumOf { fillBackward(diffN(it)).first().first() }
    }
}

Was it funny to anyone else that we had to construct a pyramid of numbers in the desert?

pub fn parse(input: &str) -> Vec<Vec<isize>> {
    input
        .lines()
        .map(|line| line.split(' ').map(|x| x.parse().unwrap()).collect())
        .collect()
}

pub fn extrapolate(report: Vec<isize>) -> isize {
    fn pyramid(report: Vec<isize>) -> Vec<Vec<isize>> {
        fn differences(history: &[isize]) -> Vec<isize> {
            history
                .windows(2)
                .map(|window| window[1] - window[0])
                .collect()
        }

        let mut difference_pyramid = vec![report];

        loop {
            let last = difference_pyramid.last().unwrap();
            let next = differences(last);
            let first = next.first().cloned().unwrap();

            // We can stop before we reach all zeros if all elements are the
            // same. That probably doesn't matter much in performance terms, 
            // because it only saves one additional row, but may as well...
            let stop = next.iter().all(|&n| n == first);

            difference_pyramid.push(next);

            if stop {
                break;
            };
        }

        difference_pyramid
    }

    fn next_value(pyramid: Vec<Vec<isize>>) -> isize {
        let mut current = *pyramid.last().unwrap().last().unwrap();

        for row in pyramid.iter().rev().skip(1) {
            current += row.last().unwrap();
        }

        current
    }

    next_value(pyramid(report))
}

For part 2 I just reversed the input array and handed that to extrapolate().

Pretty straightforward. Took advantage of itertools.pairwise.

def predict(history: list[int]) -> int:
    sequences = [history]
    while len(set(sequences[-1])) > 1:
        sequences.append([b - a for a, b in itertools.pairwise(sequences[-1])])
    return sum(sequence[-1] for sequence in sequences)

def main(stream=sys.stdin) -> None:
    histories   = [list(map(int, line.split())) for line in stream]
    predictions = [predict(history) for history in histories]
    print(sum(predictions))

Only thing that changed from the first part was that I used functools.reduce to take the differences of the first elements of the generated sequences (rather than the sum of the last elements for Part 1).

def predict(history: list[int]) -> int:
    sequences = [history]
    while len(set(sequences[-1])) > 1:
        sequences.append([b - a for a, b in itertools.pairwise(sequences[-1])])
    return functools.reduce(
        lambda a, b: b - a, [sequence[0] for sequence in reversed(sequences)]
    )

def main(stream=sys.stdin) -> None:
    histories   = [list(map(int, line.split())) for line in stream]
    predictions = [predict(history) for history in histories]
    print(sum(predictions))

def find_dif(list):
    new_list = []
    for i in range(len(list)-1):
        new_list.append(list[i+1] - list[i])
    return new_list

def part1(lines):
    print(f"Part 1!")
    total = 0
    for line in lines:
        history = list(map(int, line.split()))
        reading = [history]
        while len(history) != history.count(0):
            history = find_dif(history)
            reading.append(history)
        for l in reversed(range(len(reading) - 1)):
            reading[l].append(reading[l][-1] + reading[l+1][-1])
        total += reading[0][-1]
    print(f"Result: {total}")



def part2(lines):
    print(f"Part 2!")
    total = 0
    for line in lines:
        history = list(map(int, line.split()))
        reading = [history]
        while len(history) != history.count(0):
            history = find_dif(history)
            reading.append(history)
        for l in reversed(range(len(reading) - 1)):
            reading[l].insert(0,reading[l][0] - reading[l + 1][0])
        total += reading[0][0]
    print(f"Result: {total}")
def openFile():
    return open("input.txt", "r").readlines()


def main():
    f = openFile()
    part1(f)
    part2(f)


if __name__ == '__main__':
    main()

def differences(nums)
  diffs = []
  nums[1..].each_with_index do |n,i|
    diffs.append(n - nums[i])
  end
  diffs
end

def predict(nums)
  if nums.all? { |n| n == 0 }
    0
  else
    diffs = differences(nums)
    nums.last + predict(diffs)
  end
end

def compute_p1(input)
  histories = input.lines.map { |l| l.split(" ").map(&:to_i) }
  predictions = histories.map { |h| predict(h) }
  predictions.sum
end

def predict_back(nums)
  if nums.all? { |n| n == 0 }
    0
  else
    diffs = differences(nums)
    nums.first - predict_back(diffs)
  end
end

def compute_p2(input)
  histories = input.lines.map { |l| l.split(" ").map(&:to_i) }
  predictions = histories.map { |h| predict_back(h) }
  predictions.sum
end

#!/usr/bin/env pypy3

def kth_difference(a, k, n, c={}):
    if (k, n) not in c:
        if k == 1:
            c[(k, n)] = a[n] - a[n - 1]
        else:
            c[(k, n)] = kth_difference(a, k - 1, n, c) - kth_difference(a, k - 1, n - 1, c)
    return c[(k, n)]

def predict(a):
    k = 1
    c = {}
    prediction = a[-1]
    while not all(kth_difference(a, k, i, c) == 0 for i in range(k, len(a))):
        prediction += kth_difference(a, k, len(a) - 1, c)
        k += 1
    return prediction

print(sum(predict(tuple(map(int, line.split()))) for line in open(0)))

Same as part one but reverse the sequence first.

#!/usr/bin/env pypy3

def kth_difference(a, k, n, c={}):
    if (k, n) not in c:
        if k == 1:
            c[(k, n)] = a[n] - a[n - 1]
        else:
            c[(k, n)] = kth_difference(a, k - 1, n, c) - kth_difference(a, k - 1, n - 1, c)
    return c[(k, n)]

def predict(a):
    k = 1
    c = {}
    prediction = a[-1]
    while not all(kth_difference(a, k, i, c) == 0 for i in range(k, len(a))):
        prediction += kth_difference(a, k, len(a) - 1, c)
        k += 1
    return prediction

print(sum(predict(tuple(map(int, line.split()))[::-1]) for line in open(0)))

I did a tiny bit of optimization by reversing the lists of numbers depending on which end I was interested in, so that I could do hd(list) (constant time) rather than List.last(list) (linear time). Probably could have avoided a bunch of near-duplicate code, or the non-tail-call recursion for part 2, but meh this works.

defmodule AdventOfCode.Solution.Year2023.Day09 do
  def part1(input) do
    input
    |> parse_reverse()
    |> Enum.map(&extrapolate_forward/1)
    |> Enum.sum()
  end

  def part2(input) do
    input
    |> parse()
    |> Enum.map(&extrapolate_backward/1)
    |> Enum.sum()
  end

  defp extrapolate_forward(values, acc \\ 0)

  defp extrapolate_forward(values, acc) do
    if Enum.all?(values, &(&1 == 0)) do
      acc
    else
      values
      |> Enum.chunk_every(2, 1, :discard)
      # (List is reversed, so diff is left-right rather than right-left.)
      |> Enum.map(fn [b, a] -> b - a end)
      |> extrapolate_forward(acc + hd(values))
    end
  end

  defp extrapolate_backward(values)

  defp extrapolate_backward(values) do
    if Enum.all?(values, &(&1 == 0)) do
      0
    else
      sub_result =
        values
        |> Enum.chunk_every(2, 1, :discard)
        |> Enum.map(fn [a, b] -> b - a end)
        |> extrapolate_backward()

      hd(values) - sub_result
    end
  end

  defp parse_reverse(input) do
    for line <- String.split(input, "\n", trim: true) do
      line
      |> String.split()
      |> Stream.map(&String.to_integer/1)
      |> Enum.reverse()
    end
  end

  defp parse(input) do
    for line <- String.split(input, "\n", trim: true) do
      for num <- String.split(line), do: String.to_integer(num)
    end
  end
end