diff options
Diffstat (limited to '2022/src/bin/day_24.rs')
| -rw-r--r-- | 2022/src/bin/day_24.rs | 195 |
1 files changed, 195 insertions, 0 deletions
diff --git a/2022/src/bin/day_24.rs b/2022/src/bin/day_24.rs new file mode 100644 index 0000000..71edc71 --- /dev/null +++ b/2022/src/bin/day_24.rs @@ -0,0 +1,195 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::line_ending, + combinator::{map, value}, + multi::{many1, separated_list1}, + sequence::{delimited, tuple}, + IResult, +}; +use std::{collections::BTreeSet, fs}; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_24.txt")?; + let blizzard_map = BlizzardMap::parser(&input).unwrap().1; + let start = Point { x: 0, y: 0 }; + let end = Point { + x: blizzard_map.width - 1, + y: blizzard_map.height - 1, + }; + let there_the_first_time = + dbg!(blizzard_map.find_shortest_path_through(start.clone(), end.clone(), 1)); + let back_again = dbg!(blizzard_map.find_shortest_path_through( + end.clone(), + start.clone(), + there_the_first_time + 1 + )); + dbg!(blizzard_map.find_shortest_path_through(start, end, back_again + 1)); + + Ok(()) +} + +#[derive(Debug, Clone, PartialEq, Eq)] +struct BlizzardMap { + width: usize, + height: usize, + blizzards: Vec<Blizzard>, +} + +#[derive(Debug, Clone, PartialEq, Eq)] +struct Blizzard { + start: Point, + direction: Direction, +} + +#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct Point { + y: usize, + x: usize, +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] +enum Direction { + North, + South, + West, + East, +} + +impl BlizzardMap { + fn parser(input: &str) -> IResult<&str, Self> { + map( + delimited( + tuple((many1(tag("#")), tag("."), many1(tag("#")), line_ending)), + separated_list1( + line_ending, + delimited(tag("#"), many1(Direction::parser), tag("#")), + ), + tuple((line_ending, many1(tag("#")), tag("."), many1(tag("#")))), + ), + |blizzard_directions| BlizzardMap { + width: blizzard_directions[0].len(), + height: blizzard_directions.len(), + blizzards: blizzard_directions + .into_iter() + .enumerate() + .flat_map(|(y, row)| { + row.into_iter() + .enumerate() + .filter_map(move |(x, direction)| { + direction.map(|direction| Blizzard { + start: Point { x, y }, + direction, + }) + }) + }) + .collect(), + }, + )(input) + } + + fn find_shortest_path_through( + &self, + start: Point, + end: Point, + mut current_round: usize, + ) -> usize { + // Not sure if "visited" makes sense here because of the time + // delay. Same position at different times is different. Maybe + // makes sense if I keep time in too. + let mut frontier = BTreeSet::new(); + frontier.insert(start); + while !frontier.contains(&end) { + current_round += 1; + let last_frontier = std::mem::take(&mut frontier); + + let blizzards = self.blizzards_at_time(current_round); + + for frontier_state in last_frontier { + let mut possible_moves = vec![frontier_state.clone()]; + if frontier_state.x > 0 { + possible_moves.push(Point { + x: frontier_state.x - 1, + y: frontier_state.y, + }); + } + if frontier_state.x < self.width - 1 { + possible_moves.push(Point { + x: frontier_state.x + 1, + y: frontier_state.y, + }); + } + if frontier_state.y > 0 { + possible_moves.push(Point { + x: frontier_state.x, + y: frontier_state.y - 1, + }); + } + if frontier_state.y < self.height - 1 { + possible_moves.push(Point { + x: frontier_state.x, + y: frontier_state.y + 1, + }); + } + + for next in possible_moves { + if !blizzards.contains(&next) { + frontier.insert(next); + } + } + } + } + + current_round + 1 // extra minute to leave + } + + fn blizzards_at_time(&self, t: usize) -> BTreeSet<Point> { + self.blizzards + .iter() + .map(|blizzard| match blizzard.direction { + Direction::North => { + let t = t % self.height; + Point { + y: if blizzard.start.y > t { + blizzard.start.y - t + } else { + blizzard.start.y + self.height - t + }, + ..blizzard.start + } + } + Direction::South => Point { + y: (blizzard.start.y + t) % self.height, + ..blizzard.start + }, + Direction::West => { + let t = t % self.width; + Point { + x: if blizzard.start.x > t { + blizzard.start.x - t + } else { + blizzard.start.x + self.width - t + }, + ..blizzard.start + } + } + Direction::East => Point { + x: (blizzard.start.x + t) % self.width, + ..blizzard.start + }, + }) + .collect() + } +} + +impl Direction { + fn parser(input: &str) -> IResult<&str, Option<Self>> { + alt(( + value(None, tag(".")), + value(Some(Direction::South), tag("v")), + value(Some(Direction::West), tag("<")), + value(Some(Direction::East), tag(">")), + value(Some(Direction::North), tag("^")), + ))(input) + } +} |