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
137
138
139
140
141
142
143
144
145
146

use crate::input::Input;

struct Tunnel {
    current_gen: std::vec::Vec<bool>,
    next_gen: std::vec::Vec<bool>,
    offset: usize,
    evolutions: [bool; 32],
}

impl Tunnel {
    fn parse(input_string: &str, space_for_generations: usize) -> Result<Self, String> {
        let mut evolutions = [false; 32];

        let mut lines = input_string.lines();
        let next_line = lines.next().ok_or("Invalid tunnel format")?;
        let prefix_length = "initial state: ".len();

        let initial_line: &str = next_line.get(prefix_length..).ok_or("Invalid input")?;

        let max_growth = space_for_generations * 2;
        let state_length = initial_line.len() + 2 * max_growth;
        let mut current_gen = vec![false; state_length];
        let next_gen = vec![false; state_length];
        for (i, byte) in initial_line.bytes().enumerate() {
            current_gen[max_growth + i] = byte == b'#';
        }

        lines.next(); // Skip empty line
        for line in lines {
            let (part1, part2) = line
                .split_once(" => ")
                .ok_or_else(|| "Invalid input".to_string())?;
            if part2 == "#" {
                let from_bytes: Vec<u8> = part1.bytes().collect();
                if from_bytes.len() != 5 {
                    return Err("Invalid input".to_string());
                }
                let from = (usize::from(from_bytes[0] == b'#'))
                    + ((usize::from(from_bytes[1] == b'#')) << 1)
                    + ((usize::from(from_bytes[2] == b'#')) << 2)
                    + ((usize::from(from_bytes[3] == b'#')) << 3)
                    + ((usize::from(from_bytes[4] == b'#')) << 4);
                evolutions[from] = true;
            }
        }

        Ok(Self {
            current_gen,
            next_gen,
            offset: max_growth,
            evolutions,
        })
    }

    fn evolve(&mut self) {
        for i in 2..self.current_gen.len() - 2 {
            let current = usize::from(self.current_gen[i - 2])
                + (usize::from(self.current_gen[i - 1]) << 1)
                + (usize::from(self.current_gen[i]) << 2)
                + (usize::from(self.current_gen[i + 1]) << 3)
                + (usize::from(self.current_gen[i + 2]) << 4);
            self.next_gen[i] = self.evolutions[current];
        }

        std::mem::swap(&mut self.next_gen, &mut self.current_gen);
    }

    fn is_repeating(&self) -> bool {
        self.current_gen
            .iter()
            .skip_while(|&&populated| !populated)
            .zip(self.next_gen.iter().skip_while(|&&populated| !populated))
            .all(|(a, b)| a == b)
    }

    fn score(&self) -> i64 {
        let mut sum = 0;
        for (index, &value) in self.current_gen.iter().enumerate() {
            if value {
                let index = index as i32 - self.offset as i32;
                sum += i64::from(index);
            }
        }
        sum
    }
}

pub fn solve(input: &mut Input) -> Result<i64, String> {
    let max_steps = input.part_values(20, 1000);

    let mut tunnel = Tunnel::parse(input.text, max_steps)?;

    if input.is_part_one() {
        for _ in 0..20 {
            tunnel.evolve();
        }
        return Ok(tunnel.score());
    }

    let mut previous_score = -1;
    for generation in 1..=max_steps {
        tunnel.evolve();

        let score_diff = tunnel.score() - previous_score;
        previous_score = tunnel.score();

        if tunnel.is_repeating() {
            let remaining_generations = 50_000_000_000_i64 - generation as i64;
            let final_score = tunnel.score() + remaining_generations * score_diff;
            return Ok(final_score);
        }
    }

    Err("No cycle found".to_string())
}

#[test]
fn tests() {
    use crate::input::{test_part_one, test_part_two};

    test_part_one!(
            "initial state: #..#.#..##......###...###

...## => #
..#.. => #
.#... => #
.#.#. => #
.#.## => #
.##.. => #
.#### => #
#.#.# => #
#.### => #
##.#. => #
##.## => #
###.. => #
###.# => #
####. => #"
        => 325
    );

    let input = include_str!("day12_input.txt");
    test_part_one!(input => 2140);
    test_part_two!(
        input => 1_900_000_000_384
    );
}