Advent of code 2021: Day 12

This article is part of a series where I'll be diving head first into the Advent of code 2021. I'll be documenting the challenge of solving such a puzzle and how I got to the answer. I want to prefix this by stating that I can't cheat for any of these challenges; with that, I mean I can't look up any other implementations online.

In this article I'll be solving: Advent of code 2021: Day #12.

Part 1

The puzzle starts with explaining how to navigate caves. I get an example of a set of edges:

start-A
start-b
A-c
A-b
b-d
A-end
b-end

Which in their turn make the following graph:

    start
    /   \
c--A-----b--d
    \   /
     end

I always move from the node start to the node end. From the node start I can move to either A or b, if the cave is in uppercase I can return to the previous cave (i.e. move backwards), if it starts with a small letter I can’t move back and it’s only interesting to explore once with my submarine.

Considering my knowledge on graphs is mostly theoretical (yes, I know who Dijkstra is), this is going to be quite the challenge.

For me, it’s probably best if I ignore the “back travel” first, and assume the submarine can only move forward over each edge. This will leave me with three routes:

start-A-end
start-A-b-end
start-b-end

I started out with parsing the input; transforming the pairs to a list of adjacent nodes:

use std::collections::HashMap;

struct CaveSystem<'a> {
    map: HashMap<&'a str, Vec<&'a str>>
}

impl CaveSystem<'_> {
    fn from_vec<'a>(input: &'a Vec<&str>) -> CaveSystem<'a> {
        let mut map: HashMap<&str, Vec<&str>> = HashMap::new();
        for conn in input {
            let nodes: Vec<&str> = conn.split("-").collect();

            match map.get_mut(nodes[0]) {
                Some(n) => { n.push(nodes[1]); },
                None => {
                    map.insert(nodes[0], vec![nodes[1]]);
                }
            }
        }

        CaveSystem { map: map }
    }
}

Next up, I used Dijkstra’s algorithm [1] to count the amount of routes that’ll end up in the end node:

fn count_paths(&self, start: &str) -> usize {
    let mut to_visit = vec![];
    let mut routes = vec![];

    to_visit.push(vec![start]);

    while let Some(route) = to_visit.pop() {
        let current = route[route.len() - 1];

        if let Some(neighbors) = self.map.get(current) {
            for neighbor in neighbors {
                let mut new_route = route.clone();

                new_route.push(*neighbor);
                to_visit.push(new_route.clone());

                if *neighbor == "end" {
                    routes.push(new_route.clone());
                }
            }
        }
    }

    routes.len()
}

As previously mentioned, this will only return 3 routes because I don’t allow back-travel. To allow back-travel, I have to make my adjacent list a lot bigger, but this is probably where the trick comes kicking in. Considering both lower-case and upper-case routes, an edge like A-b means “A connects to b”, but also: “b connects to A”. How would I prevent my algorithm from traveling back and forth between A and b, until my computer disintegrates? An edge like b-d means, b connects to d, but there’s no back-travel, so d does not connect to b. A-B means the same as A-b or b-A, and back-travel is allowed in all three of those cases. Let’s first increase the adjacent list:

fn from_vec<'a>(input: &'a Vec<&str>) -> CaveSystem<'a> {
    let mut map: HashMap<&str, Vec<&str>> = HashMap::new();
    for conn in input {
        let nodes: Vec<&str> = conn.split("-").collect();

        match map.get_mut(nodes[0]) {
            Some(n) => { n.push(nodes[1]); },
            None => {
                map.insert(nodes[0], vec![nodes[1]]);

                if big_cave(&nodes[0]) {
                    map.insert(nodes[1], vec![nodes[0]]);
                }
            }
        }
    }

    CaveSystem { map: map }
}

The big_cave-method is a little helper method which merely tests if all the characters are written in uppercase. When executing this with the count_paths()-method I described earlier, my infinite-problem comes biting me in the butt. I need to test if route has already visited a small cave before. My first attempt looks like this:

let mut to_visit = vec![];
let mut routes = vec![];

to_visit.push(vec![start]);

while let Some(route) = to_visit.pop() {
    let current = route[route.len() - 1];

    if let Some(neighbors) = self.map.get(current) {
        for neighbor in neighbors {
            let mut new_route = route.clone();

            if big_cave(neighbor) || !new_route.contains(neighbor) {
                new_route.push(*neighbor);
                to_visit.push(new_route.clone());
            }

            if *neighbor == "end" {
                routes.push(new_route.clone());
            }
        }
    }
}

routes.len()

This gives me the following routes:

start-b-end
start-A-end
start-A-b-end
start-A-c-A-end
start-A-c-A-b-end

I gain 2 more routes, but that’s not enough as I should receive 10 routes in total. I’m clearly missing an edge, namely b-A and perhaps others. This has to do with how I’m building up the adjacent-list. I don’t know enough yet about Rust and lifetimes to do this nicely, so bare with me for some very large HashMap magic:

let mut map: HashMap<&str, Vec<&str>> = HashMap::new();
for conn in input {
    let nodes: Vec<&str> = conn.split("-").collect();

    match map.get_mut(nodes[0]) {
        Some(n) => { n.push(nodes[1]); },
        None => {
            map.insert(nodes[0], vec![nodes[1]]);
        }
    }

    if big_cave(&nodes[0]) && nodes[1] != "end" {
        match map.get_mut(nodes[1]) {
            Some(n) => { n.push(nodes[0]); },
            None => {
                map.insert(nodes[1], vec![nodes[0]]);
            }
        }
    }
}

CaveSystem { map: map }

All this does is, if the left-node is a big-cave, add the reverse route to the mix. The only exception here is A-end, this shouldn’t add the reverse.

Rerunning my test for counting cave routes, I get the 10 routes from the example! The next step is to tackle a more complex example:

dc-end
HN-start
start-kj
dc-start
dc-HN
LN-dc
HN-end
kj-sa
kj-HN
kj-dc

The full graph looks like this:

        sa
         |
        kj- - - - -
       / | \___     \
      /  |      \    |
start - HN - - - end |
      \  |  ____/    |
       \ | /        /
        dc- - - - -
         |
        LN

The trouble here is that start is swapped around at some places for small caves (dc-start), resulting in some faulty moves (like being able to move back to start, which is illegal). I think in these cases I’ll swap around the values to make it look like start-dc. However, after spotting and fixing that problem, the code only returns 6 routes. After some digging, it seems like the adjacent list should contain back-travel for small caves as well:

let mut map: HashMap<&str, Vec<&str>> = HashMap::new();
for conn in input {
    let mut nodes: Vec<&str> = conn.split("-").collect();

    if nodes[1] == "start" {
        nodes.swap(1, 0);
    }

    match map.get_mut(nodes[0]) {
        Some(n) => { n.push(nodes[1]); },
        None => {
            map.insert(nodes[0], vec![nodes[1]]);
        }
    }

    if nodes[1] != "end" && nodes[0] != "start" {
        match map.get_mut(nodes[1]) {
            Some(n) => { n.push(nodes[0]); },
            None => {
                map.insert(nodes[1], vec![nodes[0]]);
            }
        }
    }
}

CaveSystem { map: map }

This works for the second example, but not for the full puzzle. The third example sheds some light on my problem, namely that we have another type of edge, one where the route starts with end. This is obviously another illegal move for the adjacent list, and we’ll equally swap those around. Full code of adjacent list:

fn from_vec<'a>(input: &'a Vec<&str>) -> CaveSystem<'a> {
    let mut map: HashMap<&str, Vec<&str>> = HashMap::new();
    for conn in input {
        let mut nodes: Vec<&str> = conn.split("-").collect();

        if nodes[1] == "start" {
            nodes.swap(1, 0);
        }

        if nodes[0] == "end" {
            nodes.swap(0, 1);
        }

        match map.get_mut(nodes[0]) {
            Some(n) => { n.push(nodes[1]); },
            None => {
                map.insert(nodes[0], vec![nodes[1]]);
            }
        }

        if nodes[1] != "end" && nodes[0] != "start" {
            match map.get_mut(nodes[1]) {
                Some(n) => { n.push(nodes[0]); },
                None => {
                    map.insert(nodes[1], vec![nodes[0]]);
                }
            }
        }
    }

    CaveSystem { map: map }
}

This results in the correct answer for the third example and for part 1! ⭐️ This code doesn’t deserve any beauty-pageants, but it gets the job done.

Part 2

The second part of the puzzle describes that you can visit a small cave exactly twice, however consecutive small caves can only be visited once. Considering the route I took, my first attempt is to tweak the predicate when we allow a route to be extended. The predicate looks something like this:

fn double_visit(route: &Vec<&str>, neighbor: &str) -> bool {
    let mut counts = HashMap::new();

    for c in route {
        if big_cave(c) || c == &"start" {
            continue
        }

        let counter = counts.entry(c).or_insert(0);
        *counter += 1;
    }

    let counter = counts.entry(&neighbor).or_insert(0);
    *counter += 1;

    let two_counts = counts.values().filter(|&&n| n >= 2).count();
    let neighbor_count = counts.get(&neighbor).unwrap() - 1;

    two_counts < 2 && neighbor_count < 2
}

I simply count all the small cave occurrences in the route and test if any of them count up to more than two (incl. the number that’s about join the route). The code is quite slow; it currently takes 10 seconds to resolve. It probably has something to do with me using vectors to store the full routes. However, for now it works. ⭐️


Improvements

I will revisit this for sure!

Sources

[1] Dijkstra’s algorithm

The full solution is available on GitHub.

1716151413121110987654321