I’ve been learning Scala for my new job, and decided I’d try doing Advent of Code as another way of practicing.

The problem

You have a list of additions and subtractions, that looks something like this:

+1
-3
+8
-3
...

Starting with a value of 0, you perform the operations in the list, cycling back to the beginning when you’ve reached the end. Return the first repeated value.

A first cut

At first blush, this seems pretty easy to do. Keep adding numbers in the list, keeping track of the current sum in some kind of Set data structure, and then returning when you’ve seen the first duplicate number.

import scala.collection.mutable.Set

def getFirstRepeatedSum(numList: List[Int]): Int = {
  val set = Set[Int]()
  var sum = 0
  for (number <- Stream.continually(numList.toStream).flatten) {
    if (set contains sum) {
      return sum
    } else {
      set += sum
    }
    sum = sum + number
  }
  return 0
}

Stream.continually cycles through any Stream of elements. We could have also simply iterated over the list indices modulo the list size.

Let’s do this functionally!

This works, but this is very imperative, and relies completely on mutating data. We mutate data in two ways:

1. Using var to keep track of the sum

2. Using mutable data structures (in this example, a Set)

Scala has support for both immutable data structures and for the functional paradigm.

The tricky thing with this particular problem is that it’s not clear from the onset how many times we might have to iterate over the list. There isn’t a simple map or reduce operation that we can do here to figure out what that first repeated sum is.

So, where to go from here? Well, like with the solutions to many problems in functional programming, the answer is recursion.

@tailrec
def getFirstRepeatedFrequencyRecurse( nums: Vector[Int], currIndex: Int, currSum: Int, seenFreqs: Set[Int]) : Int = {
  (seenFreqs contains currSum) match {
    case true => currSum
    case false => {
      val nextIndex = (currIndex + 1) % nums.length
      val nextSum = currSum + nums(nextIndex)
      getFirstRepeatedFrequencyRecurse(nums, nextIndex, nextSum, seenFreqs + currSum )
    }
  }
}

def getFirstRepeatedFrequency(numList: List[Int]): Int = {
  /* We convert to a Vector to get efficient random access */
  val vec = numList.toVector

  getFirstRepeatedFrequencyRecurse(vec, -1, 0, Set[Int]())

}

Note that Scala has a @tailrec annotation that optimizes tail recursive functions such that they don’t blow up your stack, a key feature of any functional language.

Conclusion

This was a pretty good exercise in how to effectively use the functional paradigm to solve problems. This happened to be a situation where the functional solution was not clear or obvious.

Is it an improvement over the imperative form? It’s hard to say for something this simple and without a lot more context. But for something more complex, removing mutability can really improve the testability and maintainability of the code.