aoc/year2023/day09.rs
1//! # Mirage Maintenance
2//!
3//! We can solve this problem using
4//! [binomial coefficients](https://en.wikipedia.org/wiki/Binomial_coefficient).
5//!
6//! For example consider an sequence of 3 arbitrary values:
7//!
8//! ```none
9//! 1st: a b c
10//! 2nd: b - a c - b
11//! 3rd: c - 2b + a
12//!
13//! Part 1: (c - 2b + a) + (c - b) + (c) = a - 3b + 3c
14//! Part 2: a - (b - a) + (c - 2b + a) = 3a - 3b + c
15//! ```
16//!
17//! Looking at the coefficient of each value:
18//!
19//! ```none
20//! Part 1: [1, -3, 3]
21//! Part 2: [3, -3, 1]
22//! ```
23//!
24//! Doing this for values of a few different lengths:
25//!
26//! ```none
27//! Part 1: [-1, 4, -6, 4]
28//! Part 2: [4, -6, 4, -1]
29//!
30//! Part 1: [1, -5, 10, -10, 5]
31//! Part 2: [5, -10, 10, -5, 1]
32//!
33//! Part 1: [-1, 6, -15, 20, -15, 6]
34//! Part 2: [6, -15, 20, -15, 6, -1]
35//! ```
36//!
37//! Let `n` be the number of values and `k` the index of each value. The coefficient for each value
38//! is `(n k)` if `k` is even or `-(n k)` if `k` is odd. For part one we then flip the sign of the
39//! sum when `n` is odd.
40use crate::util::parse::*;
41
42type Input = (i64, i64);
43
44pub fn parse(input: &str) -> Input {
45 // Determine how many numbers are on each row. Assume each row has the same amount.
46 let (prefix, _) = input.split_once('\n').unwrap();
47 let row = prefix.iter_signed::<i64>().count() as i64;
48
49 // Calculate [Pascal's Triangle](https://en.wikipedia.org/wiki/Pascal%27s_triangle)
50 // for the required row, flipping the sign on each second coefficient.
51 let mut coefficient = 1;
52 let mut triangle = vec![1];
53
54 for i in 0..row {
55 coefficient = (coefficient * (i - row)) / (i + 1);
56 triangle.push(coefficient);
57 }
58
59 // Use adjusted binomial coefficients to calculate answers for each row.
60 let mut part_one = 0;
61 let mut part_two = 0;
62
63 for line in input.lines() {
64 for (k, value) in line.iter_signed::<i64>().enumerate() {
65 part_one += value * triangle[k];
66 part_two += value * triangle[k + 1];
67 }
68 }
69
70 (part_one, part_two)
71}
72
73pub fn part1(input: &Input) -> i64 {
74 input.0.abs()
75}
76
77pub fn part2(input: &Input) -> i64 {
78 input.1.abs()
79}