diff options
-rw-r--r-- | 2022/inputs/day_24.txt | 22 | ||||
-rw-r--r-- | 2022/src/bin/day_24.rs | 195 |
2 files changed, 217 insertions, 0 deletions
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<vvv<.>><v>><^>><>^<><v<>>>><v>v<^<>^.v..v^vv<v<<vv.v>>v<>v.<..^<vv<^v^v.v>>v>><^v>^<.vv^^<<><<>v>><# +#.vv<vv<>.v<<<<<>>vv<>^v^^<^<>><.<^>^<^>^<v<<<<v>v>><.><.^><>vv<^^><<<<>^<.<v^.vv^vv>v>^.<<<><v<.v.<><<v^^v>^^<^>>^.<v^v.v><<v^vv<<v>^v>><^^<^<v>^>><v<# +#<v^>v^vv<><v><<^<>^<^vv>v>>^^><<<vv><v.v.^><<^><>v>^<^v<<^>v<vv><v<<^.vv^>>>.^v>v.><v>v<^<^^<><<>><<^^^>v<^>>^v>>vv.<>^<><<^v>><^.>v^v><<^^^^<v<>^v<v.# +#<<^<vv^<^><>^><>^vv.v^v>><^^<>^<>>^><^.^^<.v...>^^.^<<v<vvv>>>v^..^v.v<^><>.>v^.vv<^^vv>vv^.^.vv<v>>^>v.^^^<v<>><vv^>>^^.v>.v^^<^>vvv^<<v^<v<^><^>v<>># +#<.<^>>^<v><^>^^.>>v^<v^vvv>>vv.v^<>^^>v<<vv^<>^v.<<<^>>>.^>vvv.^^^<^><<^><v>><^.^>vv^^vv.><<v<^<v^^^.>v>^>v.^^<<^^^>^><><<vv<.<>v>vv>><^^v>>vvv^<...<<# +#><v.v>vv>^^^>>><v>^^v>^>>><vv^<^<^<<<>.<<.<.<..><><v.v^^.v..v^>>>^v><.^^><<>v^<^<>^>>.v^v.v.>v>^>>>v>>^>><^<.v.v<^<<<<<^^>^^^^>^^<v^>>v><>.<>v><>.>><># +#<><<.>^<>^^v<v>^><^>v^.>><vv^vv^<v<<>.>.>>.vv.v<.^<^<>>^><><^.v>>v^^v><>><<<vv<<>v><>^.>>^>v^^><^<v<<><vv^>>.<^<.^<^>vvv>^<.v<^<>.><.>>v<^>^v<<.^<v>^<# +#<>.<v^>.^<<^v^.<<^>v^^vv<^><^<^>><v^^vvv<<vvvv>>^v><<>^>vvvvv^<<v^.>^<.<^>.^>^><v^<>>.<<^^vv>>>^>vv><vvv^v.>^vv><<<<>^v^^^.>.^>>^^v^v>v>vv^<<^vv^<>v<># +#<<>v>v>>v^^v><^<.vv<^>^^>.v^<.^^vv>.<>^<>v>^>vvv<vv^>v^><<<v>vv<..^v^v>v.v><^.<^>.v<v><v>v^>^<<<<<>^.v<^.<v.<<^>v^^^<^<<>v.<<^<<<<.<^><<<^<v<v>>v>.><># +#>>.>vvv<<..>^^vv^>.<.v..v^^>^v<<>>>vv.<v>vv^<vv^v><v^^.<<.><..><^><<>^<<><v<.<v.<^<^.^<^<<><><<^v^>.<<v^^>.^<...v.^<^^<><><>v^<><^>^>^v^.>^^>^.vv.<v^># +#>.<><v>v<v>v>^v^^v>.v^.v>v>.<>>>^vv<<v>>^>^.^<^vv.vvvv<<>v<^^.>v<^v<<^><^.^^v<>.v<vv><v<v>vvv>^^>v>..<<<v..>v..<^^^<v>^^<<vv<>>^^v^.vv<><^>>.^<<^>>v.># +#><v..vv^<v^<>>v<>..<^>v^^><.>vv^vv^<^^v<>vv<.vv^^<>^>>^v<^^<<>^vv>v><>v<^vvv^<>><>^^^v^<v.v^<<^^>>>>><^^>><^v>>vv^v><^>^<<^.v>vv>^.v^<vv^v>>>vv>v^v<^># +#...>><v.<v<>^.v.v..^>^<><vv^><<<vv^<vv.><^.vv>>><v^v^>^v>>v<.^<^^<v^<>v<^<><<<.^<<vv.<>>^v^^.v>.<v>^.^>v^.v><^<<>>>^.<<<^v<<<><^>.^.^v><>^>><vv<v.<.^># +#<^vv>>v>v<^><^^^<^>vv<>vv>^^^.><><^>v>><v.<>vv^^<^<<<v^<><v>v^v>^<><><><><>^^>><>..^^>v<...vv<^>><.vv<^<v><v<vv^.><>v^<>v.^>>>v<<^<<^vv.>^<.^<>^<v^^^># +#>>^vv^.<<.<.<>>vvv<<<..<v><^<>^><<>^.<<^^^<v^<<v.<vv<^<>>vv^>.v^v<^<>>vv<<^>>.v>.v>^^^vvv^v<^><v^><>><^<.>v^^^<vv^>^v<v^<vv><>..^><.>^^<^>>..^.v^<^<v># +#<<><^^><v^v<^^<vv>><v..>>>^><>>>v>v>v>v><>>^vv><>>v>>vvvv<<^><>v^>vv>^.>>v.^<v<^.>>>^^v>>><vvv>><.<v<^<v<^v<v<<vvv..^^<<^<.<><<<<^<>v<<<^^>.^v>^^v<^^<# +#>v^^^<v>^^<v<<<vv><^v.v<v^^^vvv<<><><^^><^^>>>>>><^>^^.>vv>^><<<v<<<^vv.^^^<v>v<^^^^>.^^vv<^<.<v^<vv^^^>><..><^>v><<v>v>^v^>>^^>vv.v^^^>^^vv.<<v.^><<.# +#<^v<<^^vvv.>v>v>.v><v<^^>^>^>^^v>v^vv^<.^.>>>>>v<>.<<.<^<<vvv..<^>^><^>^<^<<>><^>v<v^v>^v^^^>>>>v>^>>^<v..><.>>^^><^<^.<v^>^.v>^^vv^v.<>>>>.v.<<>^^vv># +#<v^v.>.>^v>^<v.<^<^>v^>^^.>.>v<>>>^>vv<>v<>^>v^<<^<.<<^>v^<><>><^^<^^v<>>vv<<.<>v>.>^^^>><^^<^vv.><v<.<<^^>^>><>v><^vv.>v^v^v..<vvv..<<v<v^<<v>^<^>><<# +#<^v<v^^v^>^<>v^<^<>>..>><>v<.^<.>v.>^v.>>^^<^v>>v^.v>^><>>vv.<<<>v>^.>v>..<<<v.<v^<>^>^<>v<^<v<><^>^v><.<<^^^<^.<<<^.^v^^.>^.<<vv>^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<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) + } +} |