advent_of_code/year2018/
day12.rs

1use crate::input::Input;
2
3struct Tunnel {
4    current_gen: std::vec::Vec<bool>,
5    next_gen: std::vec::Vec<bool>,
6    offset: usize,
7    evolutions: [bool; 32],
8}
9
10impl Tunnel {
11    fn parse(input_string: &str, space_for_generations: usize) -> Result<Self, String> {
12        let mut evolutions = [false; 32];
13
14        let mut lines = input_string.lines();
15        let next_line = lines.next().ok_or("Invalid tunnel format")?;
16        let prefix_length = "initial state: ".len();
17
18        let initial_line: &str = next_line.get(prefix_length..).ok_or("Invalid input")?;
19
20        let max_growth = space_for_generations * 2;
21        let state_length = initial_line.len() + 2 * max_growth;
22        let mut current_gen = vec![false; state_length];
23        let next_gen = vec![false; state_length];
24        for (i, byte) in initial_line.bytes().enumerate() {
25            current_gen[max_growth + i] = byte == b'#';
26        }
27
28        lines.next(); // Skip empty line
29        for line in lines {
30            let (part1, part2) = line
31                .split_once(" => ")
32                .ok_or_else(|| "Invalid input".to_string())?;
33            if part2 == "#" {
34                let from_bytes: Vec<u8> = part1.bytes().collect();
35                if from_bytes.len() != 5 {
36                    return Err("Invalid input".to_string());
37                }
38                let from = (usize::from(from_bytes[0] == b'#'))
39                    + ((usize::from(from_bytes[1] == b'#')) << 1)
40                    + ((usize::from(from_bytes[2] == b'#')) << 2)
41                    + ((usize::from(from_bytes[3] == b'#')) << 3)
42                    + ((usize::from(from_bytes[4] == b'#')) << 4);
43                evolutions[from] = true;
44            }
45        }
46
47        Ok(Self {
48            current_gen,
49            next_gen,
50            offset: max_growth,
51            evolutions,
52        })
53    }
54
55    fn evolve(&mut self) {
56        for i in 2..self.current_gen.len() - 2 {
57            let current = usize::from(self.current_gen[i - 2])
58                + (usize::from(self.current_gen[i - 1]) << 1)
59                + (usize::from(self.current_gen[i]) << 2)
60                + (usize::from(self.current_gen[i + 1]) << 3)
61                + (usize::from(self.current_gen[i + 2]) << 4);
62            self.next_gen[i] = self.evolutions[current];
63        }
64
65        std::mem::swap(&mut self.next_gen, &mut self.current_gen);
66    }
67
68    fn is_repeating(&self) -> bool {
69        self.current_gen
70            .iter()
71            .skip_while(|&&populated| !populated)
72            .zip(self.next_gen.iter().skip_while(|&&populated| !populated))
73            .all(|(a, b)| a == b)
74    }
75
76    fn score(&self) -> i64 {
77        let mut sum = 0;
78        for (index, &value) in self.current_gen.iter().enumerate() {
79            if value {
80                let index = index as i32 - self.offset as i32;
81                sum += i64::from(index);
82            }
83        }
84        sum
85    }
86}
87
88pub fn solve(input: &Input) -> Result<i64, String> {
89    let max_steps = input.part_values(20, 1000);
90
91    let mut tunnel = Tunnel::parse(input.text, max_steps)?;
92
93    if input.is_part_one() {
94        for _ in 0..20 {
95            tunnel.evolve();
96        }
97        return Ok(tunnel.score());
98    }
99
100    let mut previous_score = -1;
101    for generation in 1..=max_steps {
102        tunnel.evolve();
103
104        let score_diff = tunnel.score() - previous_score;
105        previous_score = tunnel.score();
106
107        if tunnel.is_repeating() {
108            let remaining_generations = 50_000_000_000_i64 - generation as i64;
109            let final_score = tunnel.score() + remaining_generations * score_diff;
110            return Ok(final_score);
111        }
112    }
113
114    Err("No cycle found".to_string())
115}
116
117#[test]
118fn tests() {
119    test_part_one!(
120            "initial state: #..#.#..##......###...###
121
122...## => #
123..#.. => #
124.#... => #
125.#.#. => #
126.#.## => #
127.##.. => #
128.#### => #
129#.#.# => #
130#.### => #
131##.#. => #
132##.## => #
133###.. => #
134###.# => #
135####. => #"
136        => 325
137    );
138
139    let input = include_str!("day12_input.txt");
140    test_part_one!(input => 2140);
141    test_part_two!(
142        input => 1_900_000_000_384
143    );
144}
advent_of_code/year2018/day12.rs

advent_of_code/year2018/
day12.rs
