This was the first puzzle that took much longer than it should have to come up with the solution. Here's Day 7: Laboratories. Again, spoilers are below for this puzzle. Don't read it if you want to solve this yourself.

Puzzle Summary

After the cephalopods get you out of the compactor, you show up in a teleporter hub. You see a large teleporter pad and think, "There's nothing wrong with this! Try it out!" You proceed to be teleported into a room with no doors.

Because this is a teleporter lab, you have everything you need to troubleshoot the hardware. You find out something's wrong with the tachyon manifold.

You find a diagram of this device:

.......S.......
...............
.......^.......
...............
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............

A tachyon beam enters the manifold at location S and moves downward. Empty space (.) doesn't affect the beam. If a splitter (^) is hit, the beam stops and continues from the immediate left and immediate right of the splitter:

.......S.......
.......|.......
......|^|......
...............
......^.^......
...............
.....^.^.^.....
...............
....^.^...^....
...............
...^.^...^.^...
...............
..^...^.....^..
...............
.^.^.^.^.^...^.
...............

It continues to hit splitters and beam downwards until it's complete:

.......S.......
.......|.......
......|^|......
......|.|......
.....|^|^|.....
.....|.|.|.....
....|^|^|^|....
....|.|.|.|....
...|^|^|||^|...
...|.|.|||.|...
..|^|^|||^|^|..
..|.|.|||.|.|..
.|^|||^||.||^|.
.|.|||.||.||.|.
|^|^|^|^|^|||^|
|.|.|.|.|.|||.|

Your task is to analyze the diagram for issues.

Part 1 is to count how many times the beam splits.

Part 2 is to count how many different paths a tachyon particle could potentially follow.

General Strategy

Another puzzle input, another JSON array:

[
  ".......S.......",
  "...............",
  ".......^.......",
  "...............",
  "......^.^......",
  "...............",
  ".....^.^.^.....",
  "...............",
  "....^.^...^....",
  "...............",
  "...^.^...^.^...",
  "...............",
  "..^...^.....^..",
  "...............",
  ".^.^.^.^.^...^.",
  "...............",
];

When we scan each row, we turn the string into an array of single characters:

const Day7A = (d) => {
  d[0] = d[0].split("");
  for (let i = 1; i < d.length; i++) {
    let curRow = d[i].split(""),
      prevRow = d[i - 1];

We also want to have a reference of the previous row.

Now let's get into specifics.

Part 1 Solution

Because we've split the rows into arrays, we can now cycle through it and find notable symbols, specifically the | symbol (we also include S, but that comparison really only occurs once). Find the symbol in the previous row array:

for (let j = 0; j < curRow.length; j++) {
  if (prevRow[j] == "|" || prevRow[j] == "S") {

When found, check the current row for a ^ symbol. If found, we start splitting and tick up the counter:

if (curRow[j] == "^") {
  curRow[j - 1] = "|";
  curRow[j + 1] = "|";
  totalSplits++;
  treePaths.AddNode(new TachNode(i, j));
} else {
  curRow[j] = "|";
}

Otherwise, we fill in the character with a | symbol. When all is said and done, you don't really need to do this, but I was displaying the final result to make sure it matches any samples online. Regardless, return totalSplits when done, and part 1 is complete.

Part 2 Solution

Search trees! To determine paths, we need custom classes that hold node data, such as what other nodes it connects to.

We need a node class, and let's call it TachNode:

class TachNode {
  constructor(x, y) {
    this.row = x;
    this.col = y;
    this.left = null;
    this.right = null;
  }
}

We store its position on the manifold and the nodes it connects to on the left & right.

We also need another class to build our tree, called TachTree:

class TachTree {
  constructor() {
    this.nodeArray = [];
  }
  AddNode(n) {
    this.nodeArray.push(n);
  }
  BuildTree() {
    this.nodeArray.forEach((i) => {
      i.left = this.nodeArray.find((j) => j.col == i.col - 1 && j.row > i.row);
      i.right = this.nodeArray.find((j) => j.col == i.col + 1 && j.row > i.row);
    });
  }
}

We store our nodes in an array, and when all of our nodes have been loaded, we call BuildTree to connect all of our nodes to each other. Any nodes that have no connections will have undefined values in the left and/or right properties.

So now in our main function, we create a TachTree instance:

let treePaths = new TachTree();

And when we find a ^ symbol, we create a new TachNode at its position in the manifold:

treePaths.AddNode(new TachNode(i, j));

When all the scanning is done, we can build the tree. But what about all of our potential paths? Now it's time to do some recursion.

Create a function called GetPaths in our TachTree class:

GetPaths(n) {
  if (n) {
    let paths = this.GetPaths(n.left) + this.GetPaths(n.right);
    return paths;
  } else {
    return 1;
  }
}

Really simple call that goes through each node and what they connect to. If we don't have a node, we assume it's the end of the manifold that goes on forever as a single path, so we return 1. That return goes back into itself and continues counting every path until we reach the final count.

We have to have a starting point, so we create a function that loads the first node into the recursive function:

GetPathsAtStart() {
  return this.GetPaths(this.nodeArray[0]);
}

We can change our main function to include our part 2 results:

treePaths.BuildTree();
return `${totalSplits} - ${treePaths.GetPathsAtStart()}`;

And technically, this will produce your answer.

Code Improvements

However, you're going to be waiting an incredibly long time for it. Even on my MacBook Pro with an M4 Max chip, it takes well into 30 minutes to produce a result. So, we need to speed this up.

Looking on the AoC Reddit thread for help, the idea of memorization was mentioned. You cache the total paths a node already takes, instead of scanning all of its node over and over.

We start by adding another array to our TachTree class to memorize our paths:

this.pathMemory = [];

Then we change our GetPaths recursive function to cache nodes that have already been calculated, then use those cached results when it calls for it:

if (n) {
  let cachePath = this.pathMemory.find(
    (i) => i.row == n.row && i.col == n.col,
  );
  let paths =
    cachePath?.paths || this.GetPaths(n.left) + this.GetPaths(n.right);
  if (!cachePath) {
    this.pathMemory.push({ row: n.row, col: n.col, paths: paths });
  }
  return paths;
} else {
  return 1;
}

This optimization changes a 30 minute job to something that's more or less instantaneous. Very nice.

Final Thoughts and Code

Puzzles like this are great because it requires optimization to get the answer quickly, but it's technically not necessary if you're patient enough.

My final code:

var data7 = require("./day07.json");

class TachTree {
  constructor() {
    this.nodeArray = [];
    this.pathMemory = [];
  }
  AddNode(n) {
    this.nodeArray.push(n);
  }
  BuildTree() {
    this.nodeArray.forEach((i) => {
      i.left = this.nodeArray.find((j) => j.col == i.col - 1 && j.row > i.row);
      i.right = this.nodeArray.find((j) => j.col == i.col + 1 && j.row > i.row);
    });
  }
  GetPathsAtStart() {
    return this.GetPaths(this.nodeArray[0]);
  }
  GetPaths(n) {
    if (n) {
      let cachePath = this.pathMemory.find(
        (i) => i.row == n.row && i.col == n.col,
      );
      let paths =
        cachePath?.paths || this.GetPaths(n.left) + this.GetPaths(n.right);
      if (!cachePath) {
        this.pathMemory.push({ row: n.row, col: n.col, paths: paths });
      }
      return paths;
    } else {
      return 1;
    }
  }
}

class TachNode {
  constructor(x, y) {
    this.row = x;
    this.col = y;
    this.left = null;
    this.right = null;
  }
}

const Day7A = (d) => {
  let totalSplits = 0;
  d[0] = d[0].split("");
  let treePaths = new TachTree();
  for (let i = 1; i < d.length; i++) {
    let curRow = d[i].split(""),
      prevRow = d[i - 1];
    for (let j = 0; j < curRow.length; j++) {
      if (prevRow[j] == "|" || prevRow[j] == "S") {
        if (curRow[j] == "^") {
          curRow[j - 1] = "|";
          curRow[j + 1] = "|";
          totalSplits++;
          treePaths.AddNode(new TachNode(i, j));
        } else {
          curRow[j] = "|";
        }
      }
    }
    d[i] = curRow;
  }
  treePaths.BuildTree();
  return `${totalSplits} - ${treePaths.GetPathsAtStart()}`;
};

console.log(Day7A(data7));