Advent of Code 2023 Day 23

Day 23: A Long Walk

https://adventofcode.com/2023/day/23

The water is flowing, you have some downtime and go for a walk.

A long walk, as long as possible!

Today’s input is a map of the surrounding area you are going to take a walk in.

An example input looks like this:

input.txt

#.#####################
#.......#########...###
#######.#########.#.###
###.....#.>.>.###.#.###
###v#####.#v#.###.#.###
###.>...#.#.#.....#...#
###v###.#.#.#########.#
###...#.#.#.......#...#
#####.#.#.#######.#.###
#.....#.#.#.......#...#
#.#####.#.#.#########v#
#.#...#...#...###...>.#
#.#.#v#######v###.###v#
#...#.>.#...>.>.#.###.#
#####v#.#.###v#.#.###.#
#.....#...#...#.#.#...#
#.#########.###.#.#.###
#...###...#...#...#.###
###.###.#.###v#####v###
#...#...#.#.>.>.#.>.###
#.###.###.#.###.#.#v###
#.....###...###...#...#
#####################.#

# is a forest
. is a path
^ is a slope going up
v is a slope going down
< is a slope going left
> is a slope going right
You start at the open position in the top left.
You end in the open position in the bottom right.

You never visit the same spot twice during the walk.

Parsing

A grid problem you say? With coordinates? Uh-huh.

struct Coord {
    row: usize,
    col: usize,
}

And the tiles:

enum Tile {
    Rock,
    Open,
    Slope(Dir),
}

enum Dir {
    Up,
    Down,
    Left,
    Right,
}

A function returning the coordinates of the starting position, the ending position, and a 2D grid of Tile:

fn parse(input: &str) -> (Coord, Coord, Vec<Vec<Tile>>) {
    let rows = input.lines().count();
    let cols = input.lines().next().unwrap().chars().count();

    let start = Coord { row: 0, col: 1 };
    let end = Coord {
        row: rows - 1,
        col: cols - 2,
    };

    let map = input
        .lines()
        .map(|line| {
            line.chars()
                .map(|c| match c {
                    '.' => Tile::Open,
                    '#' => Tile::Rock,
                    '^' => Tile::Slope(Dir::Up),
                    'v' => Tile::Slope(Dir::Down),
                    '<' => Tile::Slope(Dir::Left),
                    '>' => Tile::Slope(Dir::Right),
                    _ => panic!(),
                })
                .collect()
        })
        .collect();

    (start, end, map)
}

Part 1

The slopes are slippery, you can only cross them in the direction they are pointing.

The question asks how many steps the longest hike is.

Helpers

A function that returns the neighbouring coordinates for a position, but only if I’m allowed to go there. Again, I opted for verbosity because this was nice and quick to code:

impl Coord {
    fn neighbours(&self, map: &Vec<Vec<Tile>>) -> Vec<Coord> {
        let rows = map.len();
        let cols = map[0].len();
        let mut res = Vec::new();

        // up
        if self.row > 0 {
            let pos = Coord {
                row: self.row - 1,
                col: self.col,
            };
            let tile = map[pos.row][pos.col];
            let possible = match tile {
                Tile::Open => true,
                Tile::Slope(Dir::Up) => true,
                _ => false,
            };
            if possible {
                res.push(pos);
            }
        }

        // down
        if self.row < rows - 1 {
            let pos = Coord {
                row: self.row + 1,
                col: self.col,
            };
            let tile = map[pos.row][pos.col];
            let possible = match tile {
                Tile::Open => true,
                Tile::Slope(Dir::Down) => true,
                _ => false,
            };
            if possible {
                res.push(pos);
            }
        }

        // left
        if self.col > 0 {
            let pos = Coord {
                row: self.row,
                col: self.col - 1,
            };
            let tile = map[pos.row][pos.col];
            let possible = match tile {
                Tile::Open => true,
                Tile::Slope(Dir::Left) => true,
                _ => false,
            };
            if possible {
                res.push(pos);
            }
        }

        // right
        if self.col < cols - 1 {
            let pos = Coord {
                row: self.row,
                col: self.col + 1,
            };
            let tile = map[pos.row][pos.col];
            let possible = match tile {
                Tile::Open => true,
                Tile::Slope(Dir::Right) => true,
                _ => false,
            };
            if possible {
                res.push(pos);
            }
        }

        res
    }
}

Code

Now BFS every possible path, while keeping track of the maximum cost when I land on the ending tile.

day_23.rs

pub fn part_1(input: &str) -> usize {
    let (start, end, grid) = parse(input);

    let mut q: VecDeque<(Coord, usize, HashSet<Coord>)> = VecDeque::new();
    let mut max = 0;

    q.push_back((start, 0, HashSet::from([start])));

    while let Some((pos, cost, mut seen)) = q.pop_front() {
        if pos == end {
            max = cost.max(max);
            continue;
        }

        for n in pos.neighbours(&grid) {
            if seen.insert(n) {
                q.push_back((n, cost + 1, seen.clone()))
            }
        }
    }

    max
}

Part 2

The slopes aren’t slippery at all, and these boots are made for walking. You can now cross slopes in any direction.

The question asks how many steps the longest hike is.

I first tried doing the logic thing, changing the logic for neighbours and seeing what happens.

What happens is my pc freezes.

The solution I’m working towards is the following: condense the map so each single-path chain is condensed into 1 point.

in pseudo/skeleton-code:

pub fn part_2(input: &str) -> usize {
    let (start, end, map) = parse(input);

    let points = /* only care about the interesting points: every fork in the road, the start, and the end */;
    // (this collapses all single path chains into a single point)
    let costmap =  /* calculate how much steps it takes to go from any 1 point to any other point */;

    /* use those points and costs to calculate the longest possible path */
}

Helpers

I’ll need that neighbours logic anyway, so here it is. I used a different technique now because I felt like it, but the result is the same, a list of adjacent tiles I am allowed to step on:

impl Coord {
    fn neighbours(self, map: &Vec<Vec<Tile>>) -> impl Iterator<Item = Self> + '_ {
        let rows = map.len();
        let cols = map[0].len();

        let up = if self.row > 0 {
            Some(Self {
                row: self.row - 1,
                col: self.col,
            })
        } else {
            None
        };

        let down = if self.row < rows - 1 {
            Some(Self {
                row: self.row + 1,
                col: self.col,
            })
        } else {
            None
        };

        let left = if self.col > 0 {
            Some(Self {
                row: self.row,
                col: self.col - 1,
            })
        } else {
            None
        };

        let right = if self.col < cols - 1 {
            Some(Self {
                row: self.row,
                col: self.col + 1,
            })
        } else {
            None
        };

        [up, down, left, right]
            .into_iter()
            .filter_map(|pos| pos)
            .filter(|pos| map[pos.row][pos.col] != Tile::Rock)
    }
}

A function to gather all points in the map where we can go more than a single direction:

fn all_forks(map: &Vec<Vec<Tile>>) -> HashSet<Coord> {
    let mut res = HashSet::new();

    for row in 0..map.len() {
        for col in 0..map[0].len() {
            let pos = Coord { row, col };
            let tile = map[pos.row][pos.col];
            if tile != Tile::Rock && pos.neighbours(map).count() > 2 {
                res.insert(pos);
            }
        }
    }

    res
}

A function to calculate the cost of going from 1 point to a different point. Make sure to track where I’ve been while reaching that point, to prevent going to impossible to reach points (backtracking is forbidden):

fn costmap(points: &HashSet<Coord>, map: &Vec<Vec<Tile>>) -> HashMap<Coord, HashMap<Coord, usize>> {
    let initial = HashMap::from_iter(points.iter().map(|node| (*node, HashMap::new())));

    points.iter().fold(initial, |mut acc, point| {
        // add the cost of every reachable point.
        // when you reach a point, keep going and remember where you've been so you don't try to visit impossible points
        let mut q: VecDeque<(Coord, usize)> = VecDeque::new();
        let mut seen: HashSet<Coord> = HashSet::new();
        q.push_back((*point, 0));

        while let Some((pos, cost)) = q.pop_front() {
            // record costs for positions in the points set (the condensed map)
            if points.contains(&pos) && cost != 0 {
                *acc.entry(*point).or_default().entry(pos).or_default() = cost;
                continue;
            }

            // go to an adjacent tile if it's not already seen during this path
            for n in pos.neighbours2(map) {
                if seen.insert(n) {
                    q.push_back((n, cost + 1));
                }
            }

            seen.insert(pos);
        }

        acc
    })
}

And a function that uses that costmap to calculate the longest path possible from one coordinate to an other:

fn longest(from: Coord, to: Coord, map: &HashMap<Coord, HashMap<Coord, usize>>) -> usize {
    let mut q = VecDeque::new();
    let mut max = 0;

    q.push_back((from, 0, HashSet::from([from])));

    while let Some((pos, cost, seen)) = q.pop_front() {
        if pos == to {
            max = cost.max(max);
            continue;
        }

        for (n, add) in map
            .get(&pos)
            .unwrap()
            .iter()
            .filter(|(pos, _)| !seen.contains(pos))
        {
            let mut new_seen = seen.clone();
            new_seen.insert(*n);
            q.push_back((*n, cost + add, new_seen))
        }
    }

    max
}

Putting everything together means a few function calls, and final code that closely resembles that skeleton.

Code

day_23.rs

pub fn part_2(input: &str) -> usize {
    let (start, end, map) = parse(input);

    // only care about the interesting points, every fork in the road, the start, and the end
    // (this collapses all single path chains into a single point)
    let mut points = all_forks(&map);
    points.insert(start);
    points.insert(end);

    let costmap = costmap(&points, &map);

    longest(start, end, &costmap)
}

Final code

day_23.rs

1use std::collections::{HashMap, HashSet, VecDeque};
2
3#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy)]
4struct Coord {
5    row: usize,
6    col: usize,
7}
8
9impl Coord {
10    fn neighbours1(&self, map: &Vec<Vec<Tile>>) -> Vec<Coord> {
11        let rows = map.len();
12        let cols = map[0].len();
13        let mut res = Vec::new();
14
15        // up
16        if self.row > 0 {
17            let pos = Coord {
18                row: self.row - 1,
19                col: self.col,
20            };
21            let tile = map[pos.row][pos.col];
22            let possible = match tile {
23                Tile::Open => true,
24                Tile::Slope(Dir::Up) => true,
25                _ => false,
26            };
27            if possible {
28                res.push(pos);
29            }
30        }
31
32        // down
33        if self.row < rows - 1 {
34            let pos = Coord {
35                row: self.row + 1,
36                col: self.col,
37            };
38            let tile = map[pos.row][pos.col];
39            let possible = match tile {
40                Tile::Open => true,
41                Tile::Slope(Dir::Down) => true,
42                _ => false,
43            };
44            if possible {
45                res.push(pos);
46            }
47        }
48
49        // left
50        if self.col > 0 {
51            let pos = Coord {
52                row: self.row,
53                col: self.col - 1,
54            };
55            let tile = map[pos.row][pos.col];
56            let possible = match tile {
57                Tile::Open => true,
58                Tile::Slope(Dir::Left) => true,
59                _ => false,
60            };
61            if possible {
62                res.push(pos);
63            }
64        }
65
66        // right
67        if self.col < cols - 1 {
68            let pos = Coord {
69                row: self.row,
70                col: self.col + 1,
71            };
72            let tile = map[pos.row][pos.col];
73            let possible = match tile {
74                Tile::Open => true,
75                Tile::Slope(Dir::Right) => true,
76                _ => false,
77            };
78            if possible {
79                res.push(pos);
80            }
81        }
82
83        res
84    }
85
86    fn neighbours2(self, map: &Vec<Vec<Tile>>) -> impl Iterator<Item = Self> + '_ {
87        let rows = map.len();
88        let cols = map[0].len();
89
90        let up = if self.row > 0 {
91            Some(Self {
92                row: self.row - 1,
93                col: self.col,
94            })
95        } else {
96            None
97        };
98
99        let down = if self.row < rows - 1 {
100            Some(Self {
101                row: self.row + 1,
102                col: self.col,
103            })
104        } else {
105            None
106        };
107
108        let left = if self.col > 0 {
109            Some(Self {
110                row: self.row,
111                col: self.col - 1,
112            })
113        } else {
114            None
115        };
116
117        let right = if self.col < cols - 1 {
118            Some(Self {
119                row: self.row,
120                col: self.col + 1,
121            })
122        } else {
123            None
124        };
125
126        [up, down, left, right]
127            .into_iter()
128            .filter_map(|pos| pos)
129            .filter(|pos| map[pos.row][pos.col] != Tile::Rock)
130    }
131}
132
133#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
134enum Tile {
135    Rock,
136    Open,
137    Slope(Dir),
138}
139
140#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
141enum Dir {
142    Up,
143    Down,
144    Left,
145    Right,
146}
147
148fn parse(input: &str) -> (Coord, Coord, Vec<Vec<Tile>>) {
149    let rows = input.lines().count();
150    let cols = input.lines().next().unwrap().chars().count();
151
152    let start = Coord { row: 0, col: 1 };
153    let end = Coord {
154        row: rows - 1,
155        col: cols - 2,
156    };
157
158    let map = input
159        .lines()
160        .map(|line| {
161            line.chars()
162                .map(|c| match c {
163                    '.' => Tile::Open,
164                    '#' => Tile::Rock,
165                    '^' => Tile::Slope(Dir::Up),
166                    'v' => Tile::Slope(Dir::Down),
167                    '<' => Tile::Slope(Dir::Left),
168                    '>' => Tile::Slope(Dir::Right),
169                    _ => panic!(),
170                })
171                .collect()
172        })
173        .collect();
174
175    (start, end, map)
176}
177
178fn longest(from: Coord, to: Coord, map: &HashMap<Coord, HashMap<Coord, usize>>) -> usize {
179    let mut q = VecDeque::new();
180    let mut max = 0;
181
182    q.push_back((from, 0, HashSet::from([from])));
183
184    while let Some((pos, cost, seen)) = q.pop_front() {
185        if pos == to {
186            max = cost.max(max);
187            continue;
188        }
189
190        for (n, add) in map
191            .get(&pos)
192            .unwrap()
193            .iter()
194            .filter(|(pos, _)| !seen.contains(pos))
195        {
196            let mut new_seen = seen.clone();
197            new_seen.insert(*n);
198            q.push_back((*n, cost + add, new_seen))
199        }
200    }
201
202    max
203}
204
205fn all_forks(map: &Vec<Vec<Tile>>) -> HashSet<Coord> {
206    let mut res = HashSet::new();
207
208    for row in 0..map.len() {
209        for col in 0..map[0].len() {
210            let pos = Coord { row, col };
211            let tile = map[pos.row][pos.col];
212            if tile != Tile::Rock && pos.neighbours2(map).count() > 2 {
213                res.insert(pos);
214            }
215        }
216    }
217
218    res
219}
220
221fn costmap(points: &HashSet<Coord>, map: &Vec<Vec<Tile>>) -> HashMap<Coord, HashMap<Coord, usize>> {
222    let initial = HashMap::from_iter(points.iter().map(|node| (*node, HashMap::new())));
223
224    points.iter().fold(initial, |mut acc, point| {
225        // add the cost of every reachable point.
226        // when you reach a point, keep going and remember where you've been so you don't try to visit impossible points
227        let mut q: VecDeque<(Coord, usize)> = VecDeque::new();
228        let mut seen: HashSet<Coord> = HashSet::new();
229        q.push_back((*point, 0));
230
231        while let Some((pos, cost)) = q.pop_front() {
232            // record costs for positions in the points set (the condensed map)
233            if points.contains(&pos) && cost != 0 {
234                *acc.entry(*point).or_default().entry(pos).or_default() = cost;
235                continue;
236            }
237
238            // go to an adjacent tile if it's not already seen during this path
239            for n in pos.neighbours2(map) {
240                if seen.insert(n) {
241                    q.push_back((n, cost + 1));
242                }
243            }
244
245            seen.insert(pos);
246        }
247
248        acc
249    })
250}
251
252pub fn part_1(input: &str) -> usize {
253    let (start, end, grid) = parse(input);
254
255    let mut q: VecDeque<(Coord, usize, HashSet<Coord>)> = VecDeque::new();
256    let mut max = 0;
257
258    q.push_back((start, 0, HashSet::from([start])));
259
260    while let Some((pos, cost, mut seen)) = q.pop_front() {
261        if pos == end {
262            max = cost.max(max);
263            continue;
264        }
265
266        for n in pos.neighbours1(&grid) {
267            if seen.insert(n) {
268                q.push_back((n, cost + 1, seen.clone()))
269            }
270        }
271    }
272
273    max
274}
275
276pub fn part_2(input: &str) -> usize {
277    let (start, end, map) = parse(input);
278
279    // only care about the interesting points, every fork in the road, the start, and the end
280    // (this collapses all single path chains into a single point)
281    let mut points = all_forks(&map);
282    points.insert(start);
283    points.insert(end);
284
285    let costmap = costmap(&points, &map);
286
287    longest(start, end, &costmap)
288}

Date

Last update

By

Tagged

Part of series

Older post

Newer post

Advent of Code 2023 Day 23

Day 23: A Long Walk

Parsing

Part 1

Helpers

Code

Part 2

Helpers

Code

Final code