diff options
author | Justin Wernick <justin@worthe-it.co.za> | 2022-12-23 11:59:12 +0200 |
---|---|---|
committer | Justin Wernick <justin@worthe-it.co.za> | 2022-12-23 11:59:16 +0200 |
commit | 99e87a92e8c0d5faa8e928ad35f4931b220c908f (patch) | |
tree | 518858a28bf06fb8be306558415970523ed1a1f8 /2022/src | |
parent | 37e32f67481bd1c1c49a91ed6b1ea447e96b877f (diff) |
Day 23 (incomplete)
Diffstat (limited to '2022/src')
-rw-r--r-- | 2022/src/bin/day_23.rs | 173 |
1 files changed, 173 insertions, 0 deletions
diff --git a/2022/src/bin/day_23.rs b/2022/src/bin/day_23.rs new file mode 100644 index 0000000..5f58dea --- /dev/null +++ b/2022/src/bin/day_23.rs @@ -0,0 +1,173 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::line_ending, + combinator::{map, value}, + multi::{many1, separated_list1}, + IResult, +}; +use std::{ + collections::{BTreeMap, BTreeSet, VecDeque}, + fs, +}; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_23_test.txt")?; + let mut elves = ElfMap::parser(&input).unwrap().1; + + dbg!(&elves); + for _ in 0..10 { + elves.process_round(); + dbg!(&elves); + } + + dbg!(elves.count_empty_ground()); + + Ok(()) +} + +#[derive(Debug, Clone)] +struct ElfMap { + elves: BTreeSet<Point>, + check_order: VecDeque<Direction>, +} + +#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct Point { + y: i64, + x: i64, +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] +enum Direction { + North, + South, + West, + East, +} + +impl ElfMap { + fn parser(input: &str) -> IResult<&str, Self> { + map( + separated_list1( + line_ending, + map( + many1(alt((value(true, tag("#")), value(false, tag("."))))), + |row| { + row.into_iter() + .enumerate() + .filter_map(|(x, occupied)| occupied.then_some(x as i64)) + .collect::<Vec<i64>>() + }, + ), + ), + |rows| { + let elves = rows + .into_iter() + .enumerate() + .flat_map(|(y, row)| row.into_iter().map(move |x| Point { x, y: y as i64 })) + .collect(); + ElfMap { + elves, + check_order: [ + Direction::North, + Direction::South, + Direction::West, + Direction::East, + ] + .into(), + } + }, + )(input) + } + + fn process_round(&mut self) { + // key is destination! + let mut elf_moves: BTreeMap<Point, Point> = BTreeMap::new(); + let mut conflict_moves: BTreeSet<Point> = BTreeSet::new(); + + // phase 1: figure out where each elf wants to move + for elf in &self.elves { + if let Some(destination) = self.find_elf_move(&elf) { + if elf_moves.contains_key(&destination) { + elf_moves.remove(&destination); + conflict_moves.insert(destination); + } else if !conflict_moves.contains(&destination) { + elf_moves.insert(destination, elf.clone()); + } + } + } + + // phase 2: move the elves + for (dest, src) in elf_moves { + self.elves.remove(&src); + self.elves.insert(dest); + } + + let rotate = self + .check_order + .pop_front() + .expect("Where did the directions go?"); + self.check_order.push_back(rotate); + } + + fn find_elf_move(&self, elf: &Point) -> Option<Point> { + let all_adjacent = elf.adjacent(None); + let any_adjacent_elves = all_adjacent.into_iter().any(|p| self.elves.contains(&p)); + if !any_adjacent_elves { + None + } else { + self.check_order + .iter() + .filter_map(|dir| { + let adjacent = elf.adjacent(Some(*dir)); + let any_adjacent_elves = adjacent.iter().any(|p| self.elves.contains(p)); + if !any_adjacent_elves { + Some(adjacent[1].clone()) + } else { + None + } + }) + .next() + } + } + + fn count_empty_ground(&self) -> i64 { + let mut min_x = 0; + let mut min_y = 0; + let mut max_x = 0; + let mut max_y = 0; + for elf in &self.elves { + min_x = min_x.min(elf.x); + min_y = min_y.min(elf.y); + max_x = max_x.max(elf.x); + max_y = max_y.max(elf.y); + } + + let all_ground = (max_x - min_x + 1) * (max_y - min_y + 1); + let covered_ground = self.elves.len() as i64; + all_ground - covered_ground + } +} + +impl Point { + fn adjacent(&self, direction: Option<Direction>) -> Vec<Point> { + let (y_range, x_range) = match direction { + None => ((-1..=1), (-1..=1)), + Some(Direction::North) => ((-1..=-1), (-1..=1)), + Some(Direction::South) => ((1..=1), (-1..=1)), + Some(Direction::East) => ((-1..=1), (-1..=-1)), + Some(Direction::West) => ((-1..=1), (1..=1)), + }; + + y_range + .flat_map(|dy| { + x_range.clone().map(move |dx| Point { + x: self.x + dx, + y: self.y + dy, + }) + }) + .filter(|p| p != self) + .collect() + } +} |