From 881aff60c703f3929048405fd8bbf8f0533ded72 Mon Sep 17 00:00:00 2001 From: cos Date: Fri, 11 Dec 2020 23:32:19 +0100 Subject: Add day11, 2020 --- 2020/rust/Cargo.toml | 4 +- 2020/rust/day11/Cargo.toml | 10 ++ 2020/rust/day11/src/main.rs | 345 ++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 357 insertions(+), 2 deletions(-) create mode 100644 2020/rust/day11/Cargo.toml create mode 100644 2020/rust/day11/src/main.rs (limited to '2020') diff --git a/2020/rust/Cargo.toml b/2020/rust/Cargo.toml index a51672a..19751a7 100644 --- a/2020/rust/Cargo.toml +++ b/2020/rust/Cargo.toml @@ -10,8 +10,8 @@ members = [ "day07", "day08", "day09", -# "day10", -# "day11", + "day10", + "day11", # "day12", # "day13", # "day14", diff --git a/2020/rust/day11/Cargo.toml b/2020/rust/day11/Cargo.toml new file mode 100644 index 0000000..00a1103 --- /dev/null +++ b/2020/rust/day11/Cargo.toml @@ -0,0 +1,10 @@ +[package] +name = "day11" +version = "0.1.0" +authors = ["cos "] +edition = "2018" + +[dependencies] +aoc = { path = "../aoc" } +anyhow = "1.0" +thiserror = "1.0" diff --git a/2020/rust/day11/src/main.rs b/2020/rust/day11/src/main.rs new file mode 100644 index 0000000..014caed --- /dev/null +++ b/2020/rust/day11/src/main.rs @@ -0,0 +1,345 @@ +use anyhow::{Result, anyhow}; +use std::env::args; +use std::fmt; +use std::fs::File; +use std::io::{BufRead, BufReader}; +use std::ops::AddAssign; +use std::path::Path; +use thiserror::Error; + +#[derive(Clone, Copy)] +struct CoordPair { + x: isize, + y: isize, +} + +impl AddAssign for CoordPair { + fn add_assign(&mut self, other: Self) { + *self = Self { + x: self.x + other.x, + y: self.y + other.y, + }; + } +} + +#[derive(Clone, Copy, Debug, PartialEq)] +enum SeatState { + Floor, + Empty, + Occupied, +} + +#[derive(Error, Debug)] +pub enum SeatStateError { + #[error("Could not access SeatState")] + Invalid, +} + +#[derive(PartialEq)] +struct WaitingArea { + width: isize, + height: isize, + grid: Vec, +} + +#[derive(Error, Debug)] +pub enum WaitingAreaError { + #[error("Could not access WaitingArea")] + Invalid, +} + +impl WaitingArea { + fn get_seat_state(&self, pos: CoordPair) -> Option { + self.grid.get((pos.y * self.width + pos.x) as usize).copied() + } + + fn set_seat_state(&mut self, pos: CoordPair, state: SeatState) { + let entry = self.grid.get_mut((pos.y * self.width + pos.x) as usize).unwrap(); + *entry = state; + } + + fn count_neighbours(&self, pos: CoordPair) -> isize { + let mut neighbours = 0; + + let x_start = match (pos.x as isize)-1 { + n if n < 0 => 0, + n => n as isize, + }; + let y_start = match (pos.y as isize)-1 { + n if n < 0 => 0, + n => n as isize, + }; + let x_end = match pos.x+1 { + n if n > self.width-1 => self.width-1, + n => n, + }; + let y_end = match pos.y+1 { + n if n > self.height-1 => self.height-1, + n => n, + }; + + for y in y_start..=y_end { + for x in x_start..=x_end { + if x == pos.x && y == pos.y { + continue; + } + match self.get_seat_state(CoordPair {x, y}) { + Some(SeatState::Occupied) => neighbours += 1, + _ => { }, + } + } + } + + neighbours + } + + fn count_visible(&self, pos: CoordPair) -> isize { + let slopes = vec![ + CoordPair { x: 1, y: 0, }, + CoordPair { x: 1, y: 1, }, + CoordPair { x: 0, y: 1, }, + CoordPair { x: -1, y: 1, }, + CoordPair { x: -1, y: 0, }, + CoordPair { x: -1, y: -1, }, + CoordPair { x: 0, y: -1, }, + CoordPair { x: 1, y: -1, }, + ]; + + let visible_occupied = slopes.iter().map(|slope| { + let mut check_pos = CoordPair { x: pos.x, y: pos.y, }; + check_pos += *slope; + while check_pos.x < self.width && check_pos.y < self.height && + check_pos.x >= 0 && check_pos.y >= 0 + { + match self.get_seat_state(check_pos) { + Some(SeatState::Occupied) => return 1, + Some(SeatState::Floor) => {}, + _ => return 0, + } + check_pos += *slope; + } + + 0 + }).sum(); + + visible_occupied + } + + fn clone(&self) -> WaitingArea { + let mut grid = vec![]; + + for y in 0..self.height { + for x in 0..self.width { + match self.get_seat_state(CoordPair {x, y}) { + Some(SeatState::Floor) => grid.push(SeatState::Floor), + Some(SeatState::Empty) => grid.push(SeatState::Empty), + Some(SeatState::Occupied) => grid.push(SeatState::Occupied), + None => panic!("You've been eaten by a grue"), + }; + } + } + + WaitingArea { + height: self.height, + width: self.width, + grid, + } + } + + fn apply_rules(&self) -> WaitingArea { + let mut grid = vec![]; + + for y in 0..self.height { + for x in 0..self.width { + match self.get_seat_state(CoordPair {x, y}) { + Some(SeatState::Floor) => grid.push(SeatState::Floor), + Some(SeatState::Empty) => { + if self.count_neighbours(CoordPair {x, y}) > 0 { + grid.push(SeatState::Empty); + } else { + grid.push(SeatState::Occupied); + } + }, + Some(SeatState::Occupied) => if self.count_neighbours(CoordPair {x, y}) >= 4 { + grid.push(SeatState::Empty); + } else { + grid.push(SeatState::Occupied); + }, + None => panic!("You've been eaten by a grue"), + }; + } + } + + WaitingArea { + height: self.height, + width: self.width, + grid, + } + } + + fn apply_new_rules(&self) -> WaitingArea { + let mut grid = vec![]; + + for y in 0..self.height { + for x in 0..self.width { + match self.get_seat_state(CoordPair {x, y}) { + Some(SeatState::Floor) => grid.push(SeatState::Floor), + Some(SeatState::Empty) => { + if self.count_visible(CoordPair {x, y}) > 0 { + grid.push(SeatState::Empty); + } else { + grid.push(SeatState::Occupied); + } + }, + Some(SeatState::Occupied) => if self.count_visible(CoordPair {x, y}) >= 5 { + grid.push(SeatState::Empty); + } else { + grid.push(SeatState::Occupied); + }, + None => panic!("You've been eaten by a grue"), + }; + } + } + + WaitingArea { + height: self.height, + width: self.width, + grid, + } + } + + fn count_seats(&self) -> (isize, isize, isize ) { + let ( mut empty, mut occupied, mut floor ) = ( 0, 0, 0 ); + + for y in 0..self.height { + for x in 0..self.width { + match self.get_seat_state(CoordPair {x, y}) { + Some(SeatState::Floor) => floor += 1, + Some(SeatState::Empty) => empty += 1, + Some(SeatState::Occupied) => occupied += 1, + None => panic!("You've been eaten by a grue"), + }; + } + } + + ( empty, occupied, floor ) + } +} + +impl fmt::Debug for WaitingArea { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + writeln!(f, "WaitingArea: [")?; + for y in 0..self.height { + for x in 0..self.width { + match self.get_seat_state(CoordPair {x, y}) { + Some(SeatState::Floor) => write!(f, "."), + Some(SeatState::Empty) => write!(f, "L"), + Some(SeatState::Occupied) => write!(f, "#"), + None => write!(f, "You've been eaten by a grue"), + }?; + } + writeln!(f)?; + } + + f.write_str("] ") + } +} + + +fn read_input>(filename: T) -> Result { + let f = File::open(filename)?; + let reader = BufReader::new(f); + + let waiting_area = reader.lines() + .fold(Ok(WaitingArea { width: 0, height: 0, grid: vec![] }), |acc, l| { + let line = l?; + let row: Result> = line.chars().map(|c| match c { + 'L' => Ok(SeatState::Empty), + '.' => Ok(SeatState::Floor), + '#' => Ok(SeatState::Occupied), + _ => Err(anyhow!("Invalid map character: '{}'", c)), + }).collect(); + + match acc { + Ok(mut a) => { + a.grid.append(&mut row?); + a.height += 1; + Ok(a) + }, + Err(err) => Err(err) + } + }); + match waiting_area { + Ok(mut wa) => { + wa.width = wa.grid.len() as isize/wa.height; + Ok(wa) + }, + err => err, + } +} + +fn part1(input: &WaitingArea) -> Result { + let mut waiting_area = input.clone(); + loop { + let next = waiting_area.apply_rules(); + + if next == waiting_area { + break; + } + waiting_area = next; + } + + let ( _empty, occupied, _floor ) = waiting_area.count_seats(); + Ok(occupied) +} + +fn part2(input: &WaitingArea) -> Result { + let mut waiting_area = input.clone(); + loop { + let next = waiting_area.apply_new_rules(); + + if next == waiting_area { + break; + } + waiting_area = next; + } + + let ( _empty, occupied, _floor ) = waiting_area.count_seats(); + Ok(occupied) +} + +fn main() { + let ( do_part_1, do_part_2 ) = aoc::do_parts(); + + let filename = match args().nth(1) { + Some(f) => f, + None => { + eprintln!("Missing input filename"); + std::process::exit(1); + }, + }; + match read_input(filename) { + Ok(input) => { + if do_part_1 { + match part1(&input) { + Ok(solution) => println!("Part1: {}", solution), + Err(err) => { + eprintln!("Part1, no solution found: {}", err); + std::process::exit(1); + } + }; + } + if do_part_2 { + match part2(&input) { + Ok(solution) => println!("Part2: {}", solution), + Err(err) => { + eprintln!("Part2, no solution found: {}", err); + std::process::exit(1); + } + }; + } + }, + Err(err) => eprintln!("Could not read input: {}", err), + } +} + -- cgit v1.2.3