Removed redundant match statements left over from an old implementation
[advent-of-code-2019.git] / src / bin / day_24.rs
1 use rpds::RedBlackTreeSet;
2 use std::io;
3 use std::io::prelude::*;
4 use std::iter;
5 use std::iter::FromIterator;
6 use std::process;
7 use structopt::StructOpt;
8
9 #[derive(Debug, StructOpt)]
10 #[structopt(name = "Day 24: Planet of Discord")]
11 /// Simulates the life and death of Eris bugs
12 ///
13 /// See https://adventofcode.com/2019/day/24 for details.
14 struct Opt {
15     /// How many iterations of the game of life should be run
16     /// If not provided, runs until a state appears twice.
17     #[structopt(short = "n")]
18     depth: Option<usize>,
19     /// Interprets the map as being one part of an infinite fractal map
20     #[structopt(short = "f")]
21     fractal: bool,
22 }
23
24 fn main() {
25     let stdin = io::stdin();
26     let opt = Opt::from_args();
27
28     let initial_state: State = stdin
29         .lock()
30         .lines()
31         .map(|x| exit_on_failed_assertion(x, "Error reading input"))
32         .collect::<State>()
33         .with_fractal_mode(opt.fractal);
34
35     let final_state = match opt.depth {
36         Some(depth) => initial_state.n_steps_forward(depth),
37         None => initial_state.first_repeated_state(),
38     };
39
40     println!("Bugs: {}", final_state.alive.size());
41     println!("Biodiversity: {}", final_state.biodiversity_rating());
42 }
43
44 fn exit_on_failed_assertion<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
45     match data {
46         Ok(data) => data,
47         Err(e) => {
48             eprintln!("{}: {}", message, e);
49             process::exit(1);
50         }
51     }
52 }
53
54 #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
55 struct State {
56     alive: RedBlackTreeSet<Coordinate>,
57     fractal_mode: bool,
58 }
59
60 impl FromIterator<String> for State {
61     fn from_iter<T: IntoIterator<Item = String>>(iter: T) -> Self {
62         State {
63             alive: iter
64                 .into_iter()
65                 .enumerate()
66                 .flat_map(move |(y, line)| {
67                     line.chars()
68                         .enumerate()
69                         .filter(move |(_x, c)| *c == '#')
70                         .map(move |(x, _c)| Coordinate {
71                             x: x as isize,
72                             y: y as isize,
73                             depth: 0,
74                         })
75                         .collect::<Vec<Coordinate>>()
76                 })
77                 .collect(),
78             fractal_mode: false,
79         }
80     }
81 }
82
83 impl State {
84     fn with_fractal_mode(&self, fractal_mode: bool) -> State {
85         State {
86             fractal_mode,
87             ..self.clone()
88         }
89     }
90
91     fn n_steps_forward(&self, n: usize) -> Self {
92         iter::successors(Some(self.clone()), |state| Some(state.next()))
93             .nth(n)
94             .unwrap()
95     }
96
97     fn first_repeated_state(&self) -> State {
98         iter::successors(
99             Some((RedBlackTreeSet::new(), self.clone())),
100             |(seen, state)| Some((seen.insert(state.clone()), state.next())),
101         )
102         .find(|(seen, state)| seen.contains(state))
103         .unwrap()
104         .1
105     }
106
107     fn next(&self) -> State {
108         State {
109             alive: self
110                 .still_alive_next_round()
111                 .chain(self.comes_alive_next_round())
112                 .collect(),
113             ..self.clone()
114         }
115     }
116
117     fn biodiversity_rating(&self) -> usize {
118         self.alive
119             .iter()
120             .map(|coord| 2_usize.pow((coord.y * 5 + coord.x) as u32))
121             .sum()
122     }
123
124     fn still_alive_next_round<'a>(&'a self) -> impl Iterator<Item = Coordinate> + 'a {
125         self.alive
126             .iter()
127             .filter(move |coord| self.count_alive_neighbours(**coord) == 1)
128             .cloned()
129     }
130
131     fn comes_alive_next_round<'a>(&'a self) -> impl Iterator<Item = Coordinate> + 'a {
132         self.alive
133             .iter()
134             .flat_map(move |coord| self.neighbours(*coord))
135             .filter(move |coord| !self.alive.contains(coord))
136             .filter(move |coord| {
137                 self.count_alive_neighbours(*coord) == 1 || self.count_alive_neighbours(*coord) == 2
138             })
139     }
140
141     fn count_alive_neighbours(&self, coordinate: Coordinate) -> usize {
142         self.neighbours(coordinate)
143             .into_iter()
144             .filter(|coord| self.alive.contains(coord))
145             .count()
146     }
147
148     fn neighbours(&self, coordinate: Coordinate) -> Vec<Coordinate> {
149         if self.fractal_mode {
150             [(-1, 0), (1, 0), (0, -1), (0, 1)]
151                 .into_iter()
152                 .map(|(dx, dy)| Coordinate {
153                     x: coordinate.x + dx,
154                     y: coordinate.y + dy,
155                     depth: coordinate.depth,
156                 })
157                 .flat_map(move |coord| match (coord.x, coord.y) {
158                     (x, _y) if x < 0 => vec![Coordinate {
159                         x: 1,
160                         y: 2,
161                         depth: coord.depth - 1,
162                     }]
163                     .into_iter(),
164                     (_x, y) if y < 0 => vec![Coordinate {
165                         x: 2,
166                         y: 1,
167                         depth: coord.depth - 1,
168                     }]
169                     .into_iter(),
170                     (x, _y) if x >= 5 => vec![Coordinate {
171                         x: 3,
172                         y: 2,
173                         depth: coord.depth - 1,
174                     }]
175                     .into_iter(),
176                     (_x, y) if y >= 5 => vec![Coordinate {
177                         x: 2,
178                         y: 3,
179                         depth: coord.depth - 1,
180                     }]
181                     .into_iter(),
182                     (2, 2) => match (coordinate.x, coordinate.y) {
183                         (1, 2) => (0..5)
184                             .map(|y| Coordinate {
185                                 x: 0,
186                                 y,
187                                 depth: coord.depth + 1,
188                             })
189                             .collect::<Vec<_>>()
190                             .into_iter(),
191                         (2, 1) => (0..5)
192                             .map(|x| Coordinate {
193                                 x,
194                                 y: 0,
195                                 depth: coord.depth + 1,
196                             })
197                             .collect::<Vec<_>>()
198                             .into_iter(),
199                         (3, 2) => (0..5)
200                             .map(|y| Coordinate {
201                                 x: 4,
202                                 y,
203                                 depth: coord.depth + 1,
204                             })
205                             .collect::<Vec<_>>()
206                             .into_iter(),
207                         (2, 3) => (0..5)
208                             .map(|x| Coordinate {
209                                 x,
210                                 y: 4,
211                                 depth: coord.depth + 1,
212                             })
213                             .collect::<Vec<_>>()
214                             .into_iter(),
215                         (_, _) => vec![].into_iter(),
216                     },
217                     _ => vec![coord.clone()].into_iter(),
218                 })
219                 .collect()
220         } else {
221             [(-1, 0), (1, 0), (0, -1), (0, 1)]
222                 .into_iter()
223                 .map(|(dx, dy)| Coordinate {
224                     x: coordinate.x + dx,
225                     y: coordinate.y + dy,
226                     depth: coordinate.depth,
227                 })
228                 .filter(|coord| coord.x >= 0 && coord.x < 5 && coord.y >= 0 && coord.y < 5)
229                 .collect()
230         }
231     }
232 }
233
234 #[derive(Debug, Clone, Copy, PartialOrd, Ord, PartialEq, Eq)]
235 struct Coordinate {
236     x: isize,
237     y: isize,
238     depth: isize,
239 }