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:

Using
var
to keep track of the sum 
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.