diff options
Diffstat (limited to '2021/rust/day11/src')
| -rw-r--r-- | 2021/rust/day11/src/main.rs | 310 |
1 files changed, 310 insertions, 0 deletions
diff --git a/2021/rust/day11/src/main.rs b/2021/rust/day11/src/main.rs new file mode 100644 index 0000000..79972e3 --- /dev/null +++ b/2021/rust/day11/src/main.rs @@ -0,0 +1,310 @@ +use { + anyhow::{ + anyhow, + Context, + Result, + }, + num::cast::AsPrimitive, + std::{ + env::args, + fmt::{ + Display, + Formatter, + Result as FmtResult, + Write, + }, + fs::File, + io::{ + BufRead, + BufReader, + }, + path::Path, + }, + termion::style, +}; + +#[derive(Clone,Copy,Debug)] +enum Direction { + North, + NorthEast, + East, + SouthEast, + South, + SouthWest, + West, + NorthWest, +} + +impl Direction { + // FIXME Returning an unordered collection sush as e.g. HashSet<Direction> could possibly be + // cleaner, but meh! + fn all() -> Vec<Direction> { + [ + Direction::North, + Direction::NorthEast, + Direction::East, + Direction::SouthEast, + Direction::South, + Direction::SouthWest, + Direction::West, + Direction::NorthWest, + ].into_iter().collect() + } +} + +#[derive(Clone,Copy,Debug)] +struct Point { + x: usize, + y: usize, +} + +impl Point { + fn neighbour(&self, dir: Direction) -> Point { + match dir { + Direction::North => Point { + x: self.x, + y: self.y.overflowing_sub(1).0 + }, + Direction::NorthEast => Point { + x: self.x + 1, + y: self.y.overflowing_sub(1).0 + }, + Direction::East => Point { + x: self.x + 1, + y: self.y + }, + Direction::SouthEast => Point { + x: self.x + 1, + y: self.y + 1 + }, + Direction::South => Point { + x: self.x, + y: self.y + 1 + }, + Direction::SouthWest => Point { + x: self.x.overflowing_sub(1).0, + y: self.y + 1 + }, + Direction::West => Point { + x: self.x.overflowing_sub(1).0, + y: self.y + }, + Direction::NorthWest => Point { + x: self.x.overflowing_sub(1).0, + y: self.y.overflowing_sub(1).0 + }, + } + } +} + +#[derive(Copy,Clone,Debug)] +struct Dumbo { + energy: u8, + flashed: bool, +} + +impl Dumbo { + fn new(e: impl AsPrimitive<u8>) -> Result<Self> { + let energy = e.as_(); + let flashed = false; + Ok(Self { + energy, + flashed, + }) + } + + fn step(&mut self) { + self.energy += 1; + } + + fn flash(&mut self) -> bool { + if self.energy > 9 && !self.flashed { + self.flashed = true; + true + } else { + false + } + } + + fn _reset(&mut self) { + if self.flashed { + self.energy = 0; + self.flashed = false; + } + } + + fn reset_energy(&mut self) { + if self.flashed { + self.energy = 0; + } + } + + fn reset_flashed(&mut self) { + self.flashed = false; + } +} + +impl Display for Dumbo { + fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult { + if self.flashed { + write!(f, "{}", style::Bold)?; + } + write!(f, "{}", self.energy)?; + write!(f, "{}", style::Reset) + } +} + +#[derive(Clone)] +struct CaveMap { + size: Point, + dumbos: Vec<Dumbo>, +} + +impl CaveMap { + fn dumbo_mut(&mut self, pos: &Point) -> Option<&mut Dumbo> { + if pos.x < self.size.x && pos.y < self.size.y { + self.dumbos.get_mut(pos.y * self.size.y + pos.x) + } else { + None + } + } + + fn step(&mut self) -> usize { + let mut flash_count = 0; + let mut done = false; + + for y in 0..self.size.y { + for x in 0..self.size.x { + if let Some(dumbo) = self.dumbos.get_mut(y * self.size.y + x) { + dumbo.step(); + } + } + } + + while !done { + done = true; + for y in 0..self.size.y { + for x in 0..self.size.x { + if let Some(dumbo) = self.dumbo_mut(&Point {x, y}) { + if dumbo.flash() { + done = false; + flash_count += 1; + for dir in Direction::all() { + let pos = Point {x, y}; + let neighbour = pos.neighbour(dir); + if let Some(recipient) = self.dumbo_mut(&neighbour) { + recipient.step(); + } + } + } + } + } + } + } + + for y in 0..self.size.y { + for x in 0..self.size.x { + if let Some(dumbo) = self.dumbo_mut(&Point {x, y}) { + dumbo.reset_energy(); + } + } + } + flash_count + } + + fn reset(&mut self) { + for y in 0..self.size.y { + for x in 0..self.size.x { + if let Some(dumbo) = self.dumbo_mut(&Point {x, y}) { + dumbo.reset_flashed(); + } + } + } + } +} + +impl Display for CaveMap { + fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult { + let mut s = String::new(); + + for y in 0..self.size.y { + for x in 0..self.size.x { + if let Some(d) = self.dumbos.get(y * self.size.y + x) { + write!(&mut s, "{}", d)?; + } + } + writeln!(&mut s)?; + } + write!(f, "{}", s) + } +} + +fn read_input<T: AsRef<Path>>(filename: T) -> Result<CaveMap> { + let reader = BufReader::new(File::open(filename)?); + let mut x_opt = None; + let mut y = 0; + + let dumbos = reader.lines().map( |v| { + let s = v?; + let dumbo_row: Vec<Dumbo> = s.chars().map(|c| Dumbo::new(c.to_digit(10) + .ok_or_else(|| anyhow!("Invalid digit: {}", c))?)).collect::<Result<Vec<_>>>()?; + match (x_opt, dumbo_row.len()) { + (None, len) => x_opt = Some(len), + (Some(this), other) => if this != other { + return Err(anyhow!("Inconsistent map width encountered: {} != {}", this, other)); + }, + } + y += 1; + Ok(dumbo_row) + }).collect::<Result<Vec<Vec<_>>>>()?.into_iter().flatten().collect(); + + let x = x_opt.ok_or(anyhow!("Could not determine size of cave map."))?; + let size = Point { + x, + y, + }; + Ok(CaveMap { + size, + dumbos, + }) +} + +fn part1(input: &CaveMap) -> Result<usize> { + let mut cave = (*input).clone(); + let mut flash_count = 0; + // println!("Before any steps\n{}", cave); + for _step in 1..=100 { + flash_count += cave.step(); + // println!("After step: {}\n{}", _step, cave); + cave.reset(); + } + Ok(flash_count) +} + +fn part2(input: &CaveMap) -> Result<usize> { + let mut cave = (*input).clone(); + let mut step = 1; + while cave.step() != cave.size.x * cave.size.y { + // println!("After step: {}\n{}", step, cave); + step += 1; + cave.reset(); + } + // println!("After step: {}\n{}", step, cave); + Ok(step) +} + +fn main() -> Result<()> { + let ( do_part_1, do_part_2 ) = aoc::do_parts(); + + let filename = args().nth(1).ok_or(anyhow!("Missing input filename"))?; + let input = read_input(filename).context("Could not read input")?; + if do_part_1 { + let solution = part1(&input).context("No solution for part 1")?; + println!("Part1, solution found to be: {}", solution); + } + if do_part_2 { + let solution = part2(&input).context("No solution for part 2")?; + println!("Part2, solution found to be: {}", solution); + } + Ok(()) +} |