NickyMeulemanNime
Metadata
  • Date

  • Last update

  • By

    • Nicky Meuleman
  • Tagged

  • Part of series

  • Older post

    Advent of Code 2022 Day 23

  • Newer post

    Advent of Code 2022 Day 25

Table of contents
  1. Day 24: Blizzard Basin
  2. Parsing
  3. Part 1
    1. Helpers
    2. Final code
  4. Part 2
    1. Final code
  5. Make it go faster
  6. Final code

Advent of Code 2022 Day 24

Day 24: Blizzard Basin

https://adventofcode.com/2022/day/24

The expeditions needs to cross a valley that’s full of strong blizzards.

Today’s input is the starting state of the valley.

An example input looks like this:

input.txt
#.######
#>>.<^<#
#.<..<<#
#>v.><>#
#<^v^^>#
######.#

The valley is surrounded by walls (marked as #). On the perimeter, only the entrance at the top, and the exit at the bottom are not walls.

A flat ground spot without a blizzard is marked with a .. A flat ground spot with a blizzard is marked with an arrow:

  • < for a blizzard that moves left
  • > for a blizzard that moves right
  • ^ for a blizzard that moves up
  • > for a blizzard that moves down

In one minute, each blizzard moves one position. When a blizzard would move into a wall, it appears on the other side of the map (they’re Pacman blizzards or something, I don’t know).

Blizzards can move through each other.

Consider this line of blizzards, moving 1 step each minute:

  1. >.<
  2. .2.
  3. <.> The two blizzards occupied the same spot for a minute!.

You start at the entrance and want to reach the exit of the valley.

Each minute:

  1. You can move one position in the 4 directions (up, right, down, left).
  2. You can choose not to move.

You can never share a position with a blizzard.

You and the blizzards move at the same time.

That means that in a turn you can go to the right while a blizzard that was there can go to the left. You and the blizzard effectively swap positions.

Consider this state, where you are represented as E (for Elf, because they’re coming too!):

  1. E<
  2. <E

That’s a valid move. You go right, and the left-moving blizzard moved left.

Parsing

A 2D grid? If you have been following along, you know what that means, Coord!

I stored the original state of the input by keeping track of 3 things:

  1. The coordinates of walls
  2. The coordinates and directions of blizzards
  3. The size bounds of the rectangular grid
day_24.rs
#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]
struct Coord {
row: usize,
col: usize,
}
#[derive(Debug, PartialEq, Eq)]
enum Tile {
Wall,
Blizzard(Direction),
}
#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]
enum Direction {
Up,
Right,
Down,
Left,
}
fn parse(input: &str) -> (HashMap<Coord, Tile>, usize, usize) {
let mut map = HashMap::new();
let rows = input.lines().count();
let cols = input.lines().next().unwrap().chars().count();
for (row, line) in input.lines().enumerate() {
for (col, c) in line.chars().enumerate() {
if c == '.' {
continue;
}
let coord = Coord { row, col };
let tile = match c {
'#' => Tile::Wall,
'^' => Tile::Blizzard(Direction::Up),
'v' => Tile::Blizzard(Direction::Down),
'<' => Tile::Blizzard(Direction::Left),
'>' => Tile::Blizzard(Direction::Right),
_ => panic!("invalid input"),
};
map.insert(coord, tile);
}
}
(map, rows, cols)
}

Part 1

The question asks what the shortest time you can reach the goal while avoiding the blizzards is.

This is a shortest path graph question, so I’m going with Dijkstra’s algorithm again.

Before I fill it in, some skeleton code:

pseudocode.rs
let (map, rows, cols) = parse(input);
// start in the top row, in the top column
let start = Coord { row: 0, col: 1 };
// end in the bottom row, one from the last column (-1 because rows and cols are the lengths, not indexes)
let end = Coord {
row: rows - 1,
col: cols - 2,
};
let mut pq = BinaryHeap::new();
// backtracking is allowed, keep track of visited coords at a certain time
let mut seen = HashSet::new();
// insert starting node into priority queue
// insert (starting_coord, 0) into seen set
// keep stepping through time until the priority queue is empty
while let Some(Node { cost, pos }) = pq.pop() {
// did we pop a node that's at the target position? It's guaranteed to be the shortest path
if pos == end {
return cost;
}
// each step is one minute
let new_cost = cost + 1;
let candidates = pos
// moving to a neighbour is an option
.neighbours()
// not moving is an option
.chain(pos)
// can not share a coordinate with a wall
.filter(|coord| !walls.contains(coord))
// can not share a coordinate with a blizzard
.filter(|coord| !blizzards.contains(coord));
for new_pos in candidates {
// only push to pq if we didn't already see that coord at the same time
if seen.insert((new_pos, new_cost)) {
pq.push(Node {
cost: new_cost,
pos: new_pos,
});
}
}
}
// if this part is reached, there is no path through the blizzard
usize::MAX

Helpers

The Node that goes into the priority queue. Sorted so Nodes with the lowest cost get popped off the queue first.

#[derive(PartialEq, Eq)]
struct Node {
cost: usize,
pos: Coord,
}
impl Ord for Node {
fn cmp(&self, other: &Self) -> Ordering {
other.cost.cmp(&self.cost)
}
}
impl PartialOrd for Node {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}

The neighbours method on Coord takes into account the bounds of the map.

impl Coord {
fn neighbours(&self, rows: usize, cols: usize) -> Vec<Self> {
use Direction::*;
let mut neighbours = Vec::new();
if self.row > 0 {
neighbours.push(self.add_dir(&Up));
}
if self.col < cols - 1 {
neighbours.push(self.add_dir(&Right));
}
if self.row < rows - 1 {
neighbours.push(self.add_dir(&Down));
}
if self.col > 0 {
neighbours.push(self.add_dir(&Left));
}
neighbours
}
fn add_dir(&self, dir: &Direction) -> Self {
use Direction::*;
match dir {
Up => Coord {
row: self.row - 1,
col: self.col,
},
Right => Coord {
row: self.row,
col: self.col + 1,
},
Down => Coord {
row: self.row + 1,
col: self.col,
},
Left => Coord {
row: self.row,
col: self.col - 1,
},
}
}
}

The add_dir method is useful too when moving a blizzard in a Direction.

Getting the set of walls so the pseudocode where we check if there’s a wall at a coordinate is fairly straightforward.

let walls: HashSet<Coord> = map
.iter()
.filter(|(_, tile)| **tile == Tile::Wall)
.map(|(pos, _)| *pos)
.collect();
// later
walls.contains(coord);

Getting the set of blizzard coordinates is trickier. They’re dependant on the time. We get their coordinates at time 0, and their directions. Combined with the wrapping rules they can be simulated for every time.

Luckily, the blizzard positions repeat:

  • The horizontal ones repeat every cols - 2 turns.
  • The vertical ones repeat every rows - 2 turns.

(the -2 because we are considering the inner field, without the walls)

So the entire map of blizzard coordinates repeats every least common multiple of those 2 numbers.

This means we can compute all possible blizzard positions ahead of time. We run a simulation for “least common multiple” amount of minutes, and record the blizzard coordinates at every minute.

Some mathy helper functions to first find the greatest common divisor, and then the least common multiple.

fn lcm(first: usize, second: usize) -> usize {
first * second / gcd(first, second)
}
fn gcd(first: usize, second: usize) -> usize {
let mut max = first;
let mut min = second;
if min > max {
std::mem::swap(&mut max, &mut min);
}
loop {
let res = max % min;
if res == 0 {
return min;
}
max = min;
min = res;
}
}

A helper that given the original state, records the blizzard coordinates of every minute increment. It does this for max_time minutes. The blizzard position maps repeat after lcm minutes, so in the solution we pass in lcm as an argument to this function:

fn bliz_maps(
map: &HashMap<Coord, Tile>,
rows: usize,
cols: usize,
max_time: usize,
) -> HashMap<usize, HashSet<Coord>> {
// key: turn, val: set of a bliz locations
let mut cache = HashMap::new();
let mut blizzards: Vec<(Coord, Direction)> = map
.iter()
.filter_map(|(pos, tile)| match tile {
Tile::Wall => None,
Tile::Blizzard(dir) => Some((*pos, *dir)),
})
.collect();
let coords = blizzards.iter().map(|(coord, _)| *coord).collect();
cache.insert(0, coords);
// precompute every blizzard coord at every time before the coords repeat
for time in 1..max_time {
for (coord, dir) in blizzards.iter_mut() {
*coord = coord.add_dir(dir);
// if next coord went to an edge, wrap
match dir {
Direction::Left => {
if coord.col == 0 {
coord.col = cols - 2;
}
}
Direction::Right => {
if coord.col == cols - 1 {
coord.col = 1;
}
}
Direction::Up => {
if coord.row == 0 {
coord.row = rows - 2;
}
}
Direction::Down => {
if coord.row == rows - 1 {
coord.row = 1;
}
}
}
}
let coords = blizzards.iter().map(|(coord, _)| *coord).collect();
cache.insert(time, coords);
}
cache
}

Later, we can access the blizzards at any specific time. By looking up the remainder of a division with lcm in the map.

// lcm of inner area without the walls. patterns repeat every lcm steps
let lcm = lcm(rows - 2, cols - 2);
let blizzard_maps = bliz_maps(&map, rows, cols, lcm);
// later, in the while loop
let blizzards = &blizzard_maps[&(new_cost % lcm)];

Then the check in that pseudocode works, as blizzards is a HashSet<Coord>: blizzards.contains(coord)

Final code

day_24.rs
pub fn part_1(input: &str) -> usize {
let (map, rows, cols) = parse(input);
let walls: HashSet<Coord> = map
.iter()
.filter(|(_, tile)| **tile == Tile::Wall)
.map(|(pos, _)| *pos)
.collect();
// lcm of inner area without the walls. patterns repeat every lcm steps
let lcm = lcm(rows - 2, cols - 2);
let blizzard_maps = bliz_maps(&map, rows, cols, lcm);
let start = Coord { row: 0, col: 1 };
let end = Coord {
row: rows - 1,
col: cols - 2,
};
let mut pq = BinaryHeap::new();
// backtracking is allowed, keep track of visited coords at a certain time
let mut seen = HashSet::new();
pq.push(Node {
cost: 0,
pos: start,
});
seen.insert((start, 0));
// keep stepping through time until the priority queue is empty
while let Some(Node { cost, pos }) = pq.pop() {
// did we pop a node that's at the target position? It's guaranteed to be the shortest path
if pos == end {
return cost;
}
let new_cost = cost + 1;
let blizzards = &blizzard_maps[&(new_cost % lcm)];
let candidates = pos
// moving to a neighbour is an option
.neighbours(rows, cols)
.into_iter()
// not moving is an option
.chain(iter::once(pos))
// can not share a coordinate with a wall
.filter(|coord| !walls.contains(coord))
// can not share a coordinate with a blizzard
.filter(|coord| !blizzards.contains(coord));
for new_pos in candidates {
// only push to pq if we didn't already see that coord at the same time
if seen.insert((new_pos, new_cost)) {
pq.push(Node {
cost: new_cost,
pos: new_pos,
});
}
}
}
usize::MAX
}

Part 2

The minute you reach the goal, an Elf tells you they forgot their snacks at the starting point. You go through the blizzard again, then back to the end.

This reminds me of that Lord of the Rings book, but with one extra journey. There and back again. (then there again)

The question asks what the smallest numberof minutes is to travel from start to goal, back to start, back to goal.

Because of the moving blizzards, the return journey will not be the same as the initial journey.

I made the part with the Dijkstra algorithm a seperate function. It also takes an argument for the starting time of the search.

For part1, the starting time was 0.

  1. For the first start-end trip: starting time is still 0
  2. For the end-start trip: starting time is the endtime for the first start-end trip.
  3. For the second start-end trip: starting time is the endtime for the end-start trip.

Because that function would take a bunch of arguments, I created a struct to group a few of them: MapInfo.

struct MapInfo {
rows: usize,
cols: usize,
walls: HashSet<Coord>,
blizzard_maps: HashMap<usize, HashSet<Coord>>,
repeats_at: usize,
}

The function that does the shortest path calculation:

fn shortest(from: Coord, to: Coord, start_time: usize, map_info: &MapInfo) -> usize {
let MapInfo {
rows,
cols,
walls,
blizzard_maps,
repeats_at,
} = map_info;
let mut pq = BinaryHeap::new();
// backtracking is allowed, keep track of visited coords at a certain time
let mut seen = HashSet::new();
pq.push(Node {
cost: start_time,
pos: from,
});
seen.insert((from, start_time));
// keep stepping through time until the priority queue is empty
while let Some(Node { cost, pos }) = pq.pop() {
// did we pop a node that's at the target position? It's guaranteed to be the shortest path
if pos == to {
return cost;
}
let new_cost = cost + 1;
let blizzards = &blizzard_maps[&(new_cost % repeats_at)];
let candidates = pos
// moving to a neighbour is an option
.neighbours(*rows, *cols)
.into_iter()
// not moving is an option
.chain(iter::once(pos))
// can not share a coordinate with a wall
.filter(|coord| !walls.contains(coord))
// can not share a coordinate with a blizzard
.filter(|coord| !blizzards.contains(coord));
for new_pos in candidates {
// only push to pq if we didn't already see that coord at the same time
if seen.insert((new_pos, new_cost)) {
pq.push(Node {
cost: new_cost,
pos: new_pos,
});
}
}
}
usize::MAX
}

The solution to part2 then consists of gathering the info in MapInfo and running the shortest function three times. Each time:

  • swapping the starting and ending points of the search
  • feeding in the endtime of the previous search as starttime for the new one.

Final code

day_24.rs
pub fn part_2(input: &str) -> usize {
let (map, rows, cols) = parse(input);
let walls: HashSet<Coord> = map
.iter()
.filter(|(_, tile)| **tile == Tile::Wall)
.map(|(pos, _)| *pos)
.collect();
// lcm of inner area without the walls. patterns repeat every lcm steps
let lcm = lcm(rows - 2, cols - 2);
let blizzard_maps = bliz_maps(&map, rows, cols, lcm);
let start = Coord { row: 0, col: 1 };
let end = Coord {
row: rows - 1,
col: cols - 2,
};
let map_info = MapInfo {
rows,
cols,
repeats_at: lcm,
walls,
blizzard_maps,
};
let there = shortest(start, end, 0, &map_info);
let back = shortest(end, start, there, &map_info);
shortest(start, end, back, &map_info)
}

Make it go faster

For my next trick, I’ll make this solution about 30% faster with 5 lines of code (ish)!

A* is Dijkstra in a tophat. They’re nearly identical.

A* uses something called a heuristic. Which is a fancy way of saying: something that affects how nodes are sorted in the priority queue.

In Dijkstra, nodes in the priority queue are sorted based on cost. It doesn’t care about how close a node is to the goal, only about how much it costs.

In A*, nodes in the priority queue are sorted based on the cost and the heuristic combined. It cares about how close a node is to the goal.

In summary, A* is Dijkstra that includes a heuristic that says “We’re this far away from the goal”

This means that a node that costs more can get popped from the priority queue before a cheaper node, because it is closer to the goal.

Computerphile did a great video on it:

In this case, the nodes in the queue are sorted based on cost so far plus distance to go. Written differently: cost + heuristic.

A reasonable measure of how far a node is from the goal is the amount of steps it would take if there were no blizzards. It’s the shortest distance possible between the current node position and the goal. That’s the Manhattan distance

So, a method on Coord calculating that distance between 2 Coords:

impl Coord {
// -- snip --
fn manhattan(&self, other: Coord) -> usize {
other.col.abs_diff(self.col) + other.row.abs_diff(self.row)
}
}

Each Node now stores an extra field with the heuristic:

#[derive(PartialEq, Eq)]
struct Node {
cost: usize,
heuristic: usize,
pos: Coord,
}

That heuristic field contains the manhattan() from the current position to the goal.

The sorting of the Nodes is now not only based on the cost, but on the combined cost and heuristic:

impl Ord for Node {
fn cmp(&self, other: &Self) -> Ordering {
let self_total = self.cost + self.heuristic;
let other_total = other.cost + other.heuristic;
other_total.cmp(&self_total)
}
}

Every time we push a Node onto the priority queue, we include the heuristic. We don’t use it in the function in any other way, its only purpose is affecting how nodes are sorted inside the priority queue.

1fn shortest(from: Coord, to: Coord, start_time: usize, map_info: &MapInfo) -> usize {
2 let MapInfo {
3 rows,
4 cols,
5 walls,
6 blizzard_maps,
7 repeats_at,
8 } = map_info;
9
10 let mut pq = BinaryHeap::new();
11 // backtracking is allowed, keep track of visited coords at a certain time
12 let mut seen = HashSet::new();
13
14 pq.push(Node {
15 cost: start_time,
16 heuristic: from.manhattan(to),
17 pos: from,
18 });
19 seen.insert((from, start_time));
20
21 // keep stepping through time until the priority queue is empty
22 while let Some(Node { cost, pos, .. }) = pq.pop() {
23 // did we pop a node that's at the target position? It's guaranteed to be the shortest path
24 if pos == to {
25 return cost;
26 }
27
28 let new_cost = cost + 1;
29 let blizzards = &blizzard_maps[&(new_cost % repeats_at)];
30
31 let candidates = pos
32 // moving to a neighbour is an option
33 .neighbours(*rows, *cols)
34 .into_iter()
35 // not moving is an option
36 .chain(iter::once(pos))
37 // can not share a coordinate with a wall
38 .filter(|coord| !walls.contains(coord))
39 // can not share a coordinate with a blizzard
40 .filter(|coord| !blizzards.contains(coord));
41
42 for new_pos in candidates {
43 // only push to pq if we didn't already see that coord at the same time
44 if seen.insert((new_pos, new_cost)) {
45 pq.push(Node {
46 cost: new_cost,
47 heuristic: new_pos.manhattan(to),
48 pos: new_pos,
49 });
50 }
51 }
52 }
53 usize::MAX
54}

I made part1 also use the shortest function.

Part 1 Dijkstra: 230 (took: 168.1414ms)
Part 1 A-Star: 230 (took: 131.2488ms)
Part 2 Dijkstra: 713 (took: 309.7545ms)
Part 2 A-Star: 713 (took: 204.8432ms)

This was done on my local computer, a single run at a time, so take those numbers with a grain of salt. The point is: A-Star is significantly faster for a marginal code-change.

Final code

day_24.rs
1use std::{
2 cmp::Ordering,
3 collections::{BinaryHeap, HashMap, HashSet},
4 iter,
5};
6
7#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]
8struct Coord {
9 row: usize,
10 col: usize,
11}
12
13#[derive(Debug, PartialEq, Eq)]
14enum Tile {
15 Wall,
16 Blizzard(Direction),
17}
18
19#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]
20enum Direction {
21 Up,
22 Right,
23 Down,
24 Left,
25}
26
27impl Coord {
28 fn neighbours(&self, rows: usize, cols: usize) -> Vec<Self> {
29 use Direction::*;
30 let mut neighbours = Vec::new();
31 if self.row > 0 {
32 neighbours.push(self.add_dir(&Up));
33 }
34 if self.col < cols - 1 {
35 neighbours.push(self.add_dir(&Right));
36 }
37 if self.row < rows - 1 {
38 neighbours.push(self.add_dir(&Down));
39 }
40 if self.col > 0 {
41 neighbours.push(self.add_dir(&Left));
42 }
43 neighbours
44 }
45
46 fn add_dir(&self, dir: &Direction) -> Self {
47 use Direction::*;
48 match dir {
49 Up => Coord {
50 row: self.row - 1,
51 col: self.col,
52 },
53 Right => Coord {
54 row: self.row,
55 col: self.col + 1,
56 },
57 Down => Coord {
58 row: self.row + 1,
59 col: self.col,
60 },
61 Left => Coord {
62 row: self.row,
63 col: self.col - 1,
64 },
65 }
66 }
67
68 fn manhattan(&self, other: Coord) -> usize {
69 other.col.abs_diff(self.col) + other.row.abs_diff(self.row)
70 }
71}
72
73#[derive(PartialEq, Eq)]
74struct Node {
75 cost: usize,
76 heuristic: usize,
77 pos: Coord,
78}
79
80impl Ord for Node {
81 fn cmp(&self, other: &Self) -> Ordering {
82 let self_total = self.cost + self.heuristic;
83 let other_total = other.cost + other.heuristic;
84 other_total.cmp(&self_total)
85 }
86}
87
88impl PartialOrd for Node {
89 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
90 Some(self.cmp(other))
91 }
92}
93
94struct MapInfo {
95 rows: usize,
96 cols: usize,
97 walls: HashSet<Coord>,
98 blizzard_maps: HashMap<usize, HashSet<Coord>>,
99 repeats_at: usize,
100}
101
102fn lcm(first: usize, second: usize) -> usize {
103 first * second / gcd(first, second)
104}
105
106fn gcd(first: usize, second: usize) -> usize {
107 let mut max = first;
108 let mut min = second;
109 if min > max {
110 std::mem::swap(&mut max, &mut min);
111 }
112
113 loop {
114 let res = max % min;
115 if res == 0 {
116 return min;
117 }
118
119 max = min;
120 min = res;
121 }
122}
123
124fn bliz_maps(
125 map: &HashMap<Coord, Tile>,
126 rows: usize,
127 cols: usize,
128 max_time: usize,
129) -> HashMap<usize, HashSet<Coord>> {
130 // key: turn, val: set of a bliz locations
131 let mut cache = HashMap::new();
132
133 let mut blizzards: Vec<(Coord, Direction)> = map
134 .iter()
135 .filter_map(|(pos, tile)| match tile {
136 Tile::Wall => None,
137 Tile::Blizzard(dir) => Some((*pos, *dir)),
138 })
139 .collect();
140
141 let coords = blizzards.iter().map(|(coord, _)| *coord).collect();
142 cache.insert(0, coords);
143
144 // precompute every blizzard coord at every time before the coords repeat
145 for time in 1..max_time {
146 for (coord, dir) in blizzards.iter_mut() {
147 *coord = coord.add_dir(dir);
148 // if next coord went to an edge, wrap
149 match dir {
150 Direction::Left => {
151 if coord.col == 0 {
152 coord.col = cols - 2;
153 }
154 }
155 Direction::Right => {
156 if coord.col == cols - 1 {
157 coord.col = 1;
158 }
159 }
160 Direction::Up => {
161 if coord.row == 0 {
162 coord.row = rows - 2;
163 }
164 }
165 Direction::Down => {
166 if coord.row == rows - 1 {
167 coord.row = 1;
168 }
169 }
170 }
171 }
172 let coords = blizzards.iter().map(|(coord, _)| *coord).collect();
173 cache.insert(time, coords);
174 }
175
176 cache
177}
178
179fn shortest(from: Coord, to: Coord, start_time: usize, map_info: &MapInfo) -> usize {
180 let MapInfo {
181 rows,
182 cols,
183 walls,
184 blizzard_maps,
185 repeats_at,
186 } = map_info;
187
188 let mut pq = BinaryHeap::new();
189 // backtracking is allowed, keep track of visited coords at a certain time
190 let mut seen = HashSet::new();
191
192 pq.push(Node {
193 cost: start_time,
194 heuristic: from.manhattan(to),
195 pos: from,
196 });
197 seen.insert((from, start_time));
198
199 // keep stepping through time until the priority queue is empty
200 while let Some(Node { cost, pos, .. }) = pq.pop() {
201 // did we pop a node that's at the target position? It's guaranteed to be the shortest path
202 if pos == to {
203 return cost;
204 }
205
206 let new_cost = cost + 1;
207 let blizzards = &blizzard_maps[&(new_cost % repeats_at)];
208
209 let candidates = pos
210 // moving to a neighbour is an option
211 .neighbours(*rows, *cols)
212 .into_iter()
213 // not moving is an option
214 .chain(iter::once(pos))
215 // can not share a coordinate with a wall
216 .filter(|coord| !walls.contains(coord))
217 // can not share a coordinate with a blizzard
218 .filter(|coord| !blizzards.contains(coord));
219
220 for new_pos in candidates {
221 // only push to pq if we didn't already see that coord at the same time
222 if seen.insert((new_pos, new_cost)) {
223 pq.push(Node {
224 cost: new_cost,
225 heuristic: new_pos.manhattan(to),
226 pos: new_pos,
227 });
228 }
229 }
230 }
231 usize::MAX
232}
233
234fn parse(input: &str) -> (HashMap<Coord, Tile>, usize, usize) {
235 let mut map = HashMap::new();
236
237 let rows = input.lines().count();
238 let cols = input.lines().next().unwrap().chars().count();
239
240 for (row, line) in input.lines().enumerate() {
241 for (col, c) in line.chars().enumerate() {
242 if c == '.' {
243 continue;
244 }
245 let coord = Coord { row, col };
246 let tile = match c {
247 '#' => Tile::Wall,
248 '^' => Tile::Blizzard(Direction::Up),
249 'v' => Tile::Blizzard(Direction::Down),
250 '<' => Tile::Blizzard(Direction::Left),
251 '>' => Tile::Blizzard(Direction::Right),
252 _ => panic!("invalid input"),
253 };
254 map.insert(coord, tile);
255 }
256 }
257 (map, rows, cols)
258}
259
260pub fn part_1(input: &str) -> usize {
261 let (map, rows, cols) = parse(input);
262
263 let walls: HashSet<Coord> = map
264 .iter()
265 .filter(|(_, tile)| **tile == Tile::Wall)
266 .map(|(pos, _)| *pos)
267 .collect();
268 // lcm of inner area without the walls. patterns repeat every lcm steps
269 let lcm = lcm(rows - 2, cols - 2);
270 let blizzard_maps = bliz_maps(&map, rows, cols, lcm);
271 let start = Coord { row: 0, col: 1 };
272 let end = Coord {
273 row: rows - 1,
274 col: cols - 2,
275 };
276
277 let map_info = MapInfo {
278 rows,
279 cols,
280 repeats_at: lcm,
281 walls,
282 blizzard_maps,
283 };
284
285 shortest(start, end, 0, &map_info)
286}
287
288pub fn part_2(input: &str) -> usize {
289 let (map, rows, cols) = parse(input);
290
291 let walls: HashSet<Coord> = map
292 .iter()
293 .filter(|(_, tile)| **tile == Tile::Wall)
294 .map(|(pos, _)| *pos)
295 .collect();
296 // lcm of inner area without the walls. patterns repeat every lcm steps
297 let lcm = lcm(rows - 2, cols - 2);
298 let blizzard_maps = bliz_maps(&map, rows, cols, lcm);
299 let start = Coord { row: 0, col: 1 };
300 let end = Coord {
301 row: rows - 1,
302 col: cols - 2,
303 };
304 let map_info = MapInfo {
305 rows,
306 cols,
307 repeats_at: lcm,
308 walls,
309 blizzard_maps,
310 };
311
312 let there = shortest(start, end, 0, &map_info);
313 let back = shortest(end, start, there, &map_info);
314 shortest(start, end, back, &map_info)
315}

Series navigation for: Advent of Code 2022

1. Advent of Code 2022 Day 1

Designed and developed by Nicky Meuleman

Built with Gatsby. Hosted on Netlify.