diff options
Diffstat (limited to '2022/src/bin/day_23.rs')
| -rw-r--r-- | 2022/src/bin/day_23.rs | 346 |
1 files changed, 346 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..44483a5 --- /dev/null +++ b/2022/src/bin/day_23.rs @@ -0,0 +1,346 @@ +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.txt")?; + let elves = ElfMap::parser(&input).unwrap().1; + + { + let mut elves_1 = elves.clone(); + for _ in 0..10 { + elves_1.process_round(); + } + dbg!(elves_1.count_empty_ground()); + } + + { + let mut elves_2 = elves; + for round in 1.. { + if !elves_2.process_round() { + dbg!(round); + break; + } + } + } + + Ok(()) +} + +#[derive(Debug, Clone, PartialEq, Eq)] +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) -> bool { + // 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) { + use std::collections::btree_map::Entry; + match elf_moves.entry(destination) { + Entry::Occupied(elf_move_entry) => { + conflict_moves.insert(elf_move_entry.key().clone()); + elf_move_entry.remove_entry(); + } + Entry::Vacant(elf_move_entry) => { + if !conflict_moves.contains(elf_move_entry.key()) { + elf_move_entry.insert(elf.clone()); + } + } + } + } + } + + let any_elf_moved = !elf_moves.is_empty(); + + // 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); + + any_elf_moved + } + + 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 elf_x = self.elves.iter().map(|elf| elf.x); + let min_x = elf_x.clone().min().unwrap_or(0); + let max_x = elf_x.max().unwrap_or(0); + + let elf_y = self.elves.iter().map(|elf| elf.y); + let min_y = elf_y.clone().min().unwrap_or(0); + let max_y = elf_y.max().unwrap_or(0); + + 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::West) => ((-1..=1), (-1..=-1)), + Some(Direction::East) => ((-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() + } +} + +#[test] +fn follows_the_example() { + let mut elf_map = ElfMap::parser( + r".............. +.............. +.......#...... +.....###.#.... +...#...#.#.... +....#...##.... +...#.###...... +...##.#.##.... +....#..#...... +.............. +.............. +..............", + ) + .unwrap() + .1; + + elf_map.process_round(); + assert_eq!( + elf_map.elves, + ElfMap::parser( + r".............. +.......#...... +.....#...#.... +...#..#.#..... +.......#..#... +....#.#.##.... +..#..#.#...... +..#.#.#.##.... +.............. +....#..#...... +.............. +.............. +" + ) + .unwrap() + .1 + .elves + ); + + elf_map.process_round(); + assert_eq!( + elf_map.elves, + ElfMap::parser( + r".............. +.......#...... +....#.....#... +...#..#.#..... +.......#...#.. +...#..#.#..... +.#...#.#.#.... +.............. +..#.#.#.##.... +....#..#...... +.............. +.............. +" + ) + .unwrap() + .1 + .elves + ); + + elf_map.process_round(); + assert_eq!( + elf_map.elves, + ElfMap::parser( + r".............. +.......#...... +.....#....#... +..#..#...#.... +.......#...#.. +...#..#.#..... +.#..#.....#... +.......##..... +..##.#....#... +...#.......... +.......#...... +.............." + ) + .unwrap() + .1 + .elves + ); + + elf_map.process_round(); + assert_eq!( + elf_map.elves, + ElfMap::parser( + r".............. +.......#...... +......#....#.. +..#...##...... +...#.....#.#.. +.........#.... +.#...###..#... +..#......#.... +....##....#... +....#......... +.......#...... +.............." + ) + .unwrap() + .1 + .elves + ); + + elf_map.process_round(); + assert_eq!( + elf_map.elves, + ElfMap::parser( + r".......#...... +.............. +..#..#.....#.. +.........#.... +......##...#.. +.#.#.####..... +...........#.. +....##..#..... +..#........... +..........#... +....#..#...... +.............." + ) + .unwrap() + .1 + .elves + ); + + for _ in 0..5 { + elf_map.process_round(); + } + assert_eq!( + elf_map.elves, + ElfMap::parser( + r".......#...... +...........#.. +..#.#..#...... +......#....... +...#.....#..#. +.#......##.... +.....##....... +..#........#.. +....#.#..#.... +.............. +....#..#..#... +.............." + ) + .unwrap() + .1 + .elves + ); +} |