Advent of Code 2021 - Day 12

Graph theory and pathfinding are very important topics in Computer Science. Today’s problem shows an example of graph algorithms.

Problem description

The objective of this puzzle is to count the number of possible paths on a graph, considering some rules. The graph is defined, as a list of edges, with the format <from_edge>-<to_edge> where <from_edge> and <to_edge> can be uppercase or lowercase strings.

Below is an example of graph definition.

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

The first important rule is that all paths must begin from start and finish at end.

Data structure

I used the simplest possible data structure : a vector of tuples, each tuple containing the edge origin and the edge destination.

Part 1

In this part, an additional rule is that “uppercase” vertices (representing large caves in Advent of Code story) can be visited an unlimited number of times, but “lowercase” ones (representing smaller caves) can be visited only once.

I chose to implement a recursive depth-first search (DFS) algorithm. It was also possible to use a breadth-first search algorithm. The function implementing the algorithm, named possible_paths() returns all the possible paths beginning with a given partial path (or “prefix”).

In the code below, we can clearly see in the for loop the ignored edges (start and already visited small caves), and the stopping condition in the last conditional branching block.

pub fn possible_paths(edges: &Vec<(String, String)>, prefix: &Vec<String>) -> Vec<Vec<String>> {
    let mut paths = Vec::new();
    let last_cave = prefix.last().unwrap();
    let next_caves = edges.iter().cloned().filter(|x| &x.0 == last_cave).map(|x| x.1);

    for cave in next_caves {
        if cave == "start" {
            continue;
        }
        if cave.chars().next().unwrap().is_lowercase() && prefix.contains(&cave) {
            continue;
        }
        if cave == "end" {
            let mut new_path = prefix.clone();
            new_path.push("end".to_string());
            paths.push(new_path);
        }
        else {
            let mut new_prefix = prefix.clone();
            new_prefix.push(cave);
            paths.append(&mut possible_paths(edges, &new_prefix));
        }
    }

    paths
}

In the main function, the pathfinding function is called with the prefix ["start"].

pub fn solve_part1(input: &Vec<String>) -> usize {
    let edges = parse_edges(input);
    possible_paths(&edges, &vec!["start".to_string()]).len()
}

Part 2

An additional rule is set for part 2. It is now allowed to revisit a single small cave, but other small caves can be visited at most once. A consequence is that the number of possible paths will be significantly larger, like the execution time.

We make a little modification on our recursive function. An argument, called revisit is added and the second if block in the loop is completed

pub fn possible_paths(edges: &Vec<(String, String)>, prefix: &Vec<String>, revisit: bool) -> Vec<Vec<String>> {
    let mut paths = Vec::new();
    let last_cave = prefix.last().unwrap();
    let next_caves = edges.iter().cloned().filter(|x| &x.0 == last_cave).map(|x| x.1);

    for cave in next_caves {
        let mut next_revisit = revisit;
        if cave == "start" {
            continue;
        }
        if cave.chars().next().unwrap().is_lowercase() && prefix.contains(&cave) {
            if revisit {
                next_revisit = false;
            }
            else {
                continue;
            }
        }
        if cave == "end" {
            let mut new_path = prefix.clone();
            new_path.push("end".to_string());
            paths.push(new_path);
        }
        else {
            let mut new_prefix = prefix.clone();
            new_prefix.push(cave);
            paths.append(&mut possible_paths(edges, &new_prefix, next_revisit));
        }
    }

    paths
}

The part 1 main function is modified to add the revisit argument. In part 1, the pathfinding function is called with the argument revisit = false and in part 2, it is called with revisit = true.

pub fn solve_part1(input: &Vec<String>) -> usize {
    let edges = parse_edges(input);
    possible_paths(&edges, &vec!["start".to_string()], false).len()
}

pub fn solve_part2(input: &Vec<String>) -> usize {
    let edges = parse_edges(input);
    possible_paths(&edges, &vec!["start".to_string()], true).len()
}

Performances

Part 1 runs in 20 ms, and part 2 in 500 ms. This is the longest execution time so far.

My initial time was just below 1 second for part 1, and this didn’t satisfy me, so I tried to recode my pathfinding algorithm with a DFS algorithm, but I could not reach a correct implementation for part 2. Initially, the expression cave.chars().next().unwrap().is_lowercase() in the pathfinding function was returned from a little helper function. I removed this helper, and this little modification cut the execution time by 40 %.