From 9c9e9cc0f1be749398d0be3549cb39ff98fdb287 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Sat, 24 Dec 2022 14:35:04 +0200 Subject: Day 24 --- 2022/inputs/day_24.txt | 22 ++++++ 2022/src/bin/day_24.rs | 195 +++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 217 insertions(+) create mode 100644 2022/inputs/day_24.txt create mode 100644 2022/src/bin/day_24.rs (limited to '2022') diff --git a/2022/inputs/day_24.txt b/2022/inputs/day_24.txt new file mode 100644 index 0000000..e867e27 --- /dev/null +++ b/2022/inputs/day_24.txt @@ -0,0 +1,22 @@ +#.###################################################################################################################################################### +#.v><><<>^^^<><<>.^v<>v^>v^v^^<..^v>^>^vv.>v^<<>^.v>><^>><>^<>>>>v<^<>^.v..v^vv>v<>v.<..^>v>><^v>^<.vv^^<<><<>v>><# +#.vv.v<<<<<>>vv<>^v^^<^<>><.<^>^<^>^v>><.><.^><>vv<^^><<<<>^<.v>^.<<<><^^<^>>^.<^v>><^^<^^>>v^vv<><<^<>^<^vv>v>>^^><<<<^><>v>^<^v<<^>v>>.^v>v.>v<^<^^<><<>><<^^^>v<^>>^v>>vv.<>^<><<^v>><^.>v^v><<^^^^^v<>^><>^vv.v^v>><^^<>^<>>^><^.^^<.v...>^^.^<>>v^..^v.v<^><>.>v^.vv<^^vv>vv^.^.vv>^>v.^^^>>^^.v>.v^^<^>vvv^<<^>v<>># +#<.<^>>^<^>^^.>>v^>vv.v^<>^^>v<^v.<<<^>>>.^>vvv.^^^<^><<^>><^.^>vv^^vv.><v>^>v.^^<<^^^>^><><v>vv>><^^v>>vvv^<...<<# +#>vv>^^^>>>^^v>^>>>.<<.<.<..><>>>^v><.^^><<>v^<^<>^>>.v^v.v.>v>^>>>v>>^>><^<.v.v<^<<<<<^^>^^^^>^^>v><>.<>v><>.>><># +#<><<.>^<>^^v^><^>v^.>>.>.>>.vv.v<.^<^<>>^><><^.v>>v^^v><>><<v><>^.>>^>v^^><^>.<^<.^<^>vvv>^<.v<^<>.><.>>v<^>^v<<.^^<# +#<>..^<<^v^.<<^>v^^vv<^><^<^>>>^v><<>^>vvvvv^<^<.<^>.^>^>>.<<^^vv>>>^>vv>^vv><<<<>^v^^^.>.^>>^^v^v>v>vv^<<^vv^<>v<># +#<<>v>v>>v^^v><^<.vv<^>^^>.v^<.^^vv>.<>^<>v>^>vvvv^><<vv<..^v^v>v.v><^.<^>.vv^>^<<<<<>^.v<^.v^^^<^<<>v.<<^<<<<.<^><<<^>v>.><># +#>>.>vvv<<..>^^vv^>.<.v..v^^>^v<<>>>vv.vv^<..><^><<>^<<><><<^v^>.<.^<...v.^<^^<><><>v^<><^>^>^v^.>^^>^.vv.# +#>.<>vv>^v^^v>.v^.v>v>.<>>>^vv<>^>^.^<^vv.vvvv<<>v<^^.>v<^v<<^><^.^^v<>.vvvv>^^>v>..<<v..<^^^^^<>^^v^.vv<><^>>.^<<^>>v.># +#>>v<>..<^>v^^><.>vv^vv^<^^v<>vv<.vv^^<>^>>^v<^^<<>^vv>v><>v<^vvv^<>><>^^^v^>>>><^^>><^v>>vv^v><^>^<<^.v>vv>^.v^>>vv>v^v<^># +#...>>^.v.v..^>^<><<<^.vv>>>^v>>v<.^<^^v<^<><<<.^<>^v^^.v>.^.^>v^.v><^<<>>>^.<<<^v<<<><^>.^.^v><>^>># +#<^vv>>v>v<^><^^^<^>vv<>vv>^^^.><><^>v>>vv^^<^<<v^v>^<><><><><>^^>><>..^^>v<...vv<^>><.vv<^<>v^<>v.^>>>v<<^<<^vv.>^<.^<>^# +#>>^vv^.<<.<.<>>vvv<<<..<^<>^><<>^.<<^^^>vv^>.v^v<^<>>vv<<^>>.v>.v>^^^vvv^v<^><>><^<.>v^^^^v<>..^><.>^^<^>>..^.v^<^# +#<<><^^>>>>^><>>>v>v>v>v><>>^vv><>>v>>vvvv<<^><>v^>vv>^.>>v.^>>^^v>>>><.<<<<^<>v<<<^^>.^v>^^v<^^<# +#>v^^^^^<^v.v<><^^><^^>>>>>><^>^^.>vv>^><<v<^^^^>.^^vv<^<.><..><^>v><v>^v^>>^^>vv.v^^^>^^vv.<<<.# +#<^v<<^^vvv.>v>v>.v>^>^>^^v>v^vv^<.^.>>>>>v<>.<<.<^<^><^>^<^<<>><^>v^v^^^>>>>v>^>>^<.>>^^><^<^.^.v>^^vv^v.<>>>>.v.<<>^^vv># +#.>^v>^v^>^^.>.>v<>>>^>vv<>v<>^>v^<<^<.<<^>v^<><>><^^<^^v<>>vv<<.<>v>.>^^^>><^^<^vv.>^>><>v><^vv.>v^v^v..^<^>><<# +#<^v^<>v^<^<>>..>><>v<.^<.>v.>^v.>>^^<^v>>v^.v>^><>>vv.<<<>v>^.>v>..<<^>^<>v<^<^>^v><.<<^^^<^.<<<^.^v^^.>^.<^v><<>^<^v^^>^v><<^># +######################################################################################################################################################.# 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> { + 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, +} + +#[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 { + 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> { + 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) + } +} -- cgit v1.2.3