Advent of Code 2025 - Day 7

Problem description

The objective is to simulate a tachyon manifold. The input data is a 2-dimensional array representing the diagram of the manifold :

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

The beam is emitted from the location marked ‘S’ and moves downward. Whenever it reaches a splitter (marked ^), it stops, two beams are emitted by the splitter like shown on the schema below, and the process repeats until the bottom of the manifold is reached.

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

Part 1

The objective of Part 1 is to count how many times the beam is split, i.e how many splitters are hit by the beam.

I defined an immutable class named Manifold :

case class Manifold(val startIdx: Int, val size: Int, val splitters: Array[Set[Int]]):

startIdx represents the position from where the beam is emitted. size is the number of rows of the diagram. The splitters positions are represented as an array of sets, each element of the array containing the columns of the splitters located in a diagram row.

private def parseManifold(input: List[String]): Diagram =
  val startIdx = input.head.indexOf('S')
  val size = input.length
  var splitters: ArrayBuffer[Set[Int]] = ArrayBuffer()

  for line <- input do
    var rowSplitters: Set[Int] = Set()
    for i <- 0 until line.length do
      if line.charAt(i) == '^' then rowSplitters += i 
    splitters += rowSplitters.toSet

  Manifold(startIdx, size, splitters.toArray)

In order to get the requested result, I defined a method splits() in the Manifold class

def splits(): Int =
  var beams = Set(this.startIdx)
  var count = 0

  for row <- 1 until this.size do
    var nextBeams: Set[Int] = Set()
    for col <- beams do
      if this.splitters(row).contains(col) then
        nextBeams += col - 1
        nextBeams += col + 1
        count += 1
      else
        nextBeams += col
    beams = nextBeams
  count

The variable beams contains the set of columns where the beam goes, row after row.

Part 2

It is revealed that our tachyon manifold is actually a quantum tachyon manifold. Now, we have to compute the number of possible paths (called “timelines” in the puzzle text) for the beam.

I defined another method, called timelines() to compute this result, and I used a Dynamic Programming algorithm. An other possibility was to use a DFS (Depth-First Search) with memoization.

def timelines(): Long =
  var counts: HashMap[Int, Long] = HashMap(this.startIdx -> 1)

  for row <- 1 until this.size do
    var nextCounts: HashMap[Int, Long] = HashMap()
    for (col, value) <- counts do
      if this.splitters(row).contains(col) then
        nextCounts(col - 1) = nextCounts.getOrElse(col - 1, 0L) + value
        nextCounts(col + 1) = nextCounts.getOrElse(col + 1, 0L) + value
      else
        nextCounts(col) = nextCounts.getOrElse(col, 0L) + value
    counts = nextCounts

  counts.values.sum

This is essentially the same algorithm as Part 1, but this time I needed a HashMap to store, row after row, the number of paths going through each column.

My intuition told me that a 32-bit integer would not be enough to store the final result, and this happened to be true. With my input data, there are more than 48 trillion timelines.