Day 12 - Advent of Code 2021

Advent of Code 2021

The problem:

Given a graph with special node that can be visited multiple times, find all the possible path from start to end.

Initial thoughs

Right off the bat, i've been thinking about using DFS or BFS to travese our graph and print out all the results. It has been years since the last time i used those algorithm. From my rusty memories of DFS stands for Depth First Search and BFS stands for Breadth First Search.

The uses of DFS and BFS are different, normally BFS is used to find the shortest way to given node, as the siblings are visited before child nodes. DFS, on the other hand is more suitable for today's puzzle, which requires to print out multiple solutions. So DFS it is, let's go to how we can create our graph from input.

The input

We have our inputs as a list of connected node, separated by "-"

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

This is the first year that i participate in an Advent of code, i haven't prepared anything to speed up my process and i'm kind of lazy with all the input process so i go with the most simple thing that comes to my mind, using search and replace of vscode to create a js list. So, with my basic regex knowledge, i search for ^(.*)$  and replace all the occurrences with "$1", . As a result, we got our list:

"start-A",
"start-b",
"A-c",
"A-b",
"b-d",
"A-end",
"b-end",

Then wrap everything with a square  bracket and we have our input ?. Not my proudest achievement but hey, it worked !

So we have our list in JS, now the fun part begins, create our graph.

The graph

I will split every row into 2 pieces, start and end part. In the puzzle, we have small caves and large caves, we can visit a large cave multiple times and the small caves only once. I was thinking, how about the start and end node are both small cave, that would be a one way connection. If either start or end is large cave, it would be a two way connection, so our input can be visualize like this:

Which means we can go from A to c and go back to A because it is 2 ways connection.

This makes sense to me, let's begin to code this

const isLargeCave = caveName => caveName.toLowerCase() === caveName;

const connectPoints = (input) => {
  const tree = {};
  input.forEach((entry) => {
    const [src, dest] = entry.split("-");
    if (!tree[src]) {
      tree[src] = [];
    }

    // Create a new path from src to dest
    tree[src].push(dest);
	
    if (isLargeCave(src) || isLargeCave(dest)) {
    	if (!tree[dest]) {
          tree[dest] = [];
        }

       tree[dest].push(src);
    }
  
  });

  return tree;
};

With the previous input, we will have an object like this

{
  start: [ "A", "b"],
  A: ["c","b","end"],
  b: ["A", "d", "end],
  c: ["A"]
}

And with this, we can move on the next part of the puzzle, traverse all possible path.

Graph traversal

We are going to use recursive to traverse our graph, first thing is to determinate the stop condition, in this case is easy: we reached "end".

 if (currentItem === "end") {
    return;
 }

Next step is the recursive part ?. In DFS, we are going to visit all the child first.

Our first path can be visualize like this, start -> A because A is the first child of start. Then c is the first child of A so A -> c, c only have one child which is A so we have no choice, go back to A c -> A, now at A because we already visit c, move to next child in the list which is end. So we got "start,A,c,A,end"

const traversal = (currentItem, currentPath, tree, paths) => {
  if (currentItem === "end") {
    const result = currentPath.join(",");
    
    return;
  }

  if (!tree[currentItem]) {
    // dead end reached ! Cannot go anywhere else
    return;
  }
  
  tree[currentItem].forEach((leaf) => {
    if (leaf === "start") {
      // Dont go back to start
      return;
    }
    // If we haven't visited the leaf or leaf is large cave
    if (
      leaf.toUpperCase() === leaf ||
      !currentPath.includes(leaf)
    ) {
      traversal(leaf, [...currentPath, leaf], tree, paths);
    }
  });
};

 const paths = [];
 const tree = connectPoints(input);
 console.log("Tree", tree);
 // Start at "start", currentPath is ["start"] and an empty result array
 traversal("start", ["start"], tree, paths);
 console.log("Paths", paths);
 console.log("Result", paths.length);

With this implementation, the first given input is resolved correctly with 10 paths, so we got our first star ⭐

The second part

In the second part, we can have one small cave visited twice. First thing first, we need to update our graph, all of our connections need to be directional in order to traverse to a small cave and go back, ex: A -> b, b -> A, A -> b, b -> A, A - c

const connectPoints = (input, allTwoWay = false) => {
  const tree = {};
  input.forEach((entry) => {
    const [src, dest] = entry.split("-");
    if (!tree[src]) {
      tree[src] = [];
    }

    // Create a new path from src to dest
    tree[src].push(dest);

    if (isLargeCave(dest) || isLargeCave(src) || allTwoWay) {
      if (!tree[dest]) {
        tree[dest] = [];
      }

      tree[dest].push(src);
    }
  });

  return tree;
};

Next step is to refine our logic for a node that can be visit or revisit. Right now a node can be visit if it's a large cave or it has not been visited in the previous current iteration. With the second part of the requirement, our condition would be the same with an additional condition: there are no small cave duplication. Hence, with this condition, we can go back to a small cave.

The final code would be something like this

// Custom bfs
const traversal = (currentItem, currentPath, tree, paths, withSmallDup) => {
  if (currentItem === "end") {
    const result = currentPath.join(",");

    if (!paths.includes(result)) {
      paths.push(currentPath.join(","));
    }

    return;
  }

  if (!tree[currentItem]) {
    // dead end reached ! Cannot go anywhere else
    return;
  }
  tree[currentItem].forEach((leaf) => {
    if (leaf === "start") {
      // Dont go back to start
      return;
    }
    // Count every occurrences
    const counts = {};
    for (const a of currentPath)
      if (a.toLowerCase() === a) counts[a] = (counts[a] ?? 0) + 1;

    const hasLowDup = Object.values(counts).some((item) => item > 1);

    // If we haven't visited the leaf or leaf is large cave
    if (
      (withSmallDup && !hasLowDup) ||
      leaf.toUpperCase() === leaf ||
      !currentPath.includes(leaf)
    ) {
      traversal(leaf, [...currentPath, leaf], tree, paths);
    }
  });
};

It still a little bit slow and there are rooms for improvement, but for now we are able to calculate the final answer and have our second star ⭐

And that's it for now, thank you for reading.