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:

#.#####################
#.......#########...###
#######.#########.#.###
###.....#.>.>.###.#.###
###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.

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

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

use std::collections::{HashMap, HashSet, VecDeque};

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy)]
struct Coord {
    row: usize,
    col: usize,
}

impl Coord {
    fn neighbours1(&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
    }

    fn neighbours2(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)
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
enum Tile {
    Rock,
    Open,
    Slope(Dir),
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
enum Dir {
    Up,
    Down,
    Left,
    Right,
}

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)
}

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
}

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.neighbours2(map).count() > 2 {
                res.insert(pos);
            }
        }
    }

    res
}

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
    })
}

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.neighbours1(&grid) {
            if seen.insert(n) {
                q.push_back((n, cost + 1, seen.clone()))
            }
        }
    }

    max
}

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)
}

Date

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