1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

//! This is my solution for [Advent of Code - Day 9: _Mirage Maintenance_](https://adventofcode.com/2023/day/9)
//!
//! [`parse_input`] uses [`parse_line`] to interpret the puzzle input as sequences of integers.
//!
//! [`analyse_sequences`] hands analysing each sequence to the provided extrapolator, either
//! [`extrapolate_sequence_forwards`] for part 1 or [`extrapolate_sequence_backwards`] for part 2.
//!
//! Both extrapolators rely on [`build_delta_sequences`], which uses [`iterate`] to recursively generate
//! the a sequence of sequences, each sequence in turn being generated by [`build_delta_sequence`]
//! from the previous sequence.

use itertools::{iterate, Itertools};
use std::fs;

/// The entry point for running the solutions with the 'real' puzzle input.
///
/// - The puzzle input is expected to be at `<project_root>/res/day-9-input`
/// - It is expected this will be called by [`super::main()`] when the user elects to run day 9.
pub fn run() {
    let contents = fs::read_to_string("res/day-9-input.txt").expect("Failed to read file");

    let sequences = parse_input(&contents);

    println!(
        "The sum of the forwards extrapolated numbers is: {}",
        analyse_sequences(&sequences, extrapolate_sequence_forwards)
    );

    println!(
        "The sum of the backwards extrapolated numbers is: {}",
        analyse_sequences(&sequences, extrapolate_sequence_backwards)
    );
}

/// Parse each line as a sequence of integers
fn parse_input(input: &String) -> Vec<Vec<i64>> {
    input.lines().map(parse_line).collect()
}

/// Parse a line as a space separated list of integers
fn parse_line(line: &str) -> Vec<i64> {
    line.split(" ").filter_map(|num| num.parse().ok()).collect()
}

/// Unwrap the sequence of delta sequences to extrapolate the next value in the original sequence.
/// This is equivalent to the sum of the last value in each of the delta sequences
fn extrapolate_sequence_forwards(sequence: &Vec<i64>) -> i64 {
    let sequences: Vec<Vec<i64>> = build_delta_sequences(sequence);

    sequences
        .iter()
        .rev()
        .map(|seq| seq.last().unwrap_or(&0))
        .sum()
}

/// Unwrap the sequence of delta sequences to extrapolate the previous value in the original
/// sequence. This is equivalent recursively subtracting the first value in the sequence.
fn extrapolate_sequence_backwards(sequence: &Vec<i64>) -> i64 {
    let sequences: Vec<Vec<i64>> = build_delta_sequences(sequence);

    sequences
        .iter()
        .rev()
        .map(|seq| seq.first().unwrap_or(&0))
        .fold(0, |acc, val| val - acc)
}

/// Given a list of integers, return the sequence of sequences generated by recursively calling
/// [`build_delta_sequence`] on the previous sequence until a sequence of `0`s is generated
fn build_delta_sequences(sequence: &Vec<i64>) -> Vec<Vec<i64>> {
    iterate(sequence.clone(), build_delta_sequence)
        .take_while(|seq| seq.iter().any(|&v| v != 0))
        .collect()
}

/// Generate a sequence of the difference between each consecutive pair of numbers
fn build_delta_sequence(sequence: &Vec<i64>) -> Vec<i64> {
    sequence
        .into_iter()
        .tuple_windows()
        .map(|(a, b)| b - a)
        .collect()
}

/// Extrapolate each sequence in the list, and sum the extrapolated values
fn analyse_sequences(
    sequences: &Vec<Vec<i64>>,
    extrapolator: fn(sequence: &Vec<i64>) -> i64,
) -> i64 {
    sequences.iter().map(extrapolator).sum()
}

#[cfg(test)]
mod tests {
    use crate::day_9::*;

    fn example_sequences() -> Vec<Vec<i64>> {
        vec![
            vec![0, 3, 6, 9, 12, 15],
            vec![1, 3, 6, 10, 15, 21],
            vec![10, 13, 16, 21, 30, 45],
        ]
    }

    #[test]
    fn can_parse_input() {
        let input = "\
0 3 6 9 12 15
1 3 6 10 15 21
10 13 16 21 30 45"
            .to_string();

        assert_eq!(parse_input(&input), example_sequences());
    }

    #[test]
    fn can_extrapolate_sequences_forwards() {
        let results: Vec<i64> = example_sequences()
            .iter()
            .map(extrapolate_sequence_forwards)
            .collect();

        assert_eq!(results, vec![18, 28, 68])
    }

    #[test]
    fn can_extrapolate_sequences_backwards() {
        let results: Vec<i64> = example_sequences()
            .iter()
            .map(extrapolate_sequence_backwards)
            .collect();

        assert_eq!(results, vec![-3, 0, 5])
    }
}