Functional List Segmentation

Striving to become a functional programmer first, I’m collecting together things I’ve learned. In this post the task is to break an input list into groups based on the contents of the list, rather than the size of the partitions, and then performing an operation on those groups.

Kotlin extension functions provide ways to split lists, such as sliced or chunked, but most appear to take a segment size as what is used to split the list. In my case, the list itself contains both data and the segmenting value. This example is taken from Day 1 of the Advent of Code challenge for 2022.

Spoiler alert: try the challenge yourself before seeing my approach.

I’m an advocate of Test Driven Development (TDD), so first task is to create a test. The puzzle gave a sample input with a solution as follows:

@Test
fun `should solve the sample part 1`() {
    val expected = 24000
    val result = Day01().solvePuzzle1("src/test/resources/2022/01-sample.txt")
    assertEquals(expected, result)
}

The Problem

I won’t go into the narrative behind the problem; feel free to read this from the site itself. But given groups of integers, each group containing one or more elements, part one is to find the group with the highest total. The test input is a file with integers on each line and groups separated by blank lines.

Non-Functional

With that in place, let’s look at a non-functional way of doing this. A simple for-loop is probably the way to go. We can use a mutable variable to collect the total of each group and then add to a mutable list when a blank line is encountered.

 fun solvePuzzle1(filename: String): Int {
    val input = FileSolver.asLines(filename)
    var groupSum = 0
    var amounts = mutableListOf<Int>()
    for (line in input) {
        if (line.isEmpty()) {
            // end of a group: add to our mutable list; reset group
            amounts.add(groupSum)
            groupSum = 0
        } else {
            // increse the groupSum
            val amt = line.toInt()
            groupSum = groupSum + amt
        }
    }
    // add the last group which is not followed by a new line!
    amounts.add(groupSum)
    return amounts.max()
}

Note that the mutable list is not strictly needed above; it can be replaced with another Int value to hold the max group seen to date. When solving AoC puzzles it is usually a good idea not to optimise until after you have unlocked the second part of that day’s puzzle as it will usually throw something new at you from the same input set. On day one, the second part required further processing on the whole list – getting the top highest three elements.

A primary goal in functional programming is to remove mutable variables as these are usually a source of bugs in the code. Mutable means changeable, so to be functional, all variables need to be declared with val rather than var so they cannot be change. Using a for loop with local variables to track the state is not allowed.

Folding

My functional solution was to use the fold function on the input list. This takes two parameters, an object to collect the data into some result and a function that will construct that object as the list is iterated. As the list of input data is traversed, a new object will be created all the way through to the end.

My first attempt is as follows:

fun solvePuzzle1(filename: String): Int {
    val input = FileSolver.asLines(filename)
    val folded = input.fold(Pair(0, emptyList<Int>())) { collect, line ->
        if (line.isEmpty()) {
           Pair(0, collect.second + collect.first)
        } else {
           Pair(collect.first + line.toInt(), collect.second)
        }
   }
   // append in the final group for which no new line happened
   val groups = folded.second + folded.first
   return groups.max()
}

The key element here is that I am using an object of type Pair<Int, List<Int>> to fold upon. The first element of the pair is the running total of the current group. The second is all the groups encountered to date. The initial object is constructed with Pair(0, emptyList<Int>) as there is zero running total and no groups collected.

The lambda function takes a collect variable and the input as line from the file. If the line is empty, then for the next Pair to be created, the first element is reset to zero and for the second element, the running group total is appended to the list. Note that Kotlin allows using the + symbol to append an element to a mutable list.

If the line was not empty then it can be converted to an integer and added to the previous running total (which is available in collect.first). Note here that the input is clean, so I have left out checking or exception handling for what to do if the integer conversion goes wrong (see below). The second element of the pair is the existing list of groups as we have not completed getting the totals from it.

After this, the folded variable contains a Pair with the last group in the file in the first position and a list of the previous to last groups in the second position. Append the last to the rest (note that this creates a new variable here because the list in the pair is immutable) and return the max.

But that is not satisfying! Let’s make it a little better.

This time rather than collecting the list of numbers in the group, let’s keep track of current maximum group size. That way there is no further processing of the list to find the maximum after the groups have been split. If the current group that is being collected goes above the current max, replace the max and still keep adding up the running total with the next element in the list. Here’s another possible solution to part one.

fun solvePuzzle1(filename: String): Int {
        val input = FileSolver.asLines(filename)
        return input.fold(Pair(0, 0)) { collected, line ->
            val newNumber = line.toIntOrNull()?:0
            val runningTotal = collected.first + newNumber
            val max = max(collected.second, runningTotal)
            if (line.isEmpty()) {
                Pair(0, max)
            } else {
                Pair(runningTotal, max)
            }
        }.second
    }

On line 4 we need to protect against the element that just contains a blank line by using toIntOrNull and then setting the value to zero if it is null. The next line increases the running total, and the next calculates the new maximum. The if statement becomes simple, either resetting the runningTotal to zero for a new group or keeping it going, and passing the latest maximum on. When the list has been folded, the second element will hold the maximum value.

Input Manipulation Approach

Sometimes a little manipulation of the input can make things easier. Folding over lists is tricky and can also lead to bugs. Here’s an approach to transform the input so that it’s easier to break up and sum each group and this helps with both part one and two of the puzzle.

Firstly, we can join each line together using a comma as the separator (rather than the default comma and space). This will remove the new lines but leave a double comma.

val longString = input.joinToString(separator = ",")

Second the double commas act as a nice way to split the long string into a list of comma separated numbers.

val groups = longString.split(",,")

Finally, this can be mapped by first splitting to a list of list of strings (there will be a comma between each part of the string representing an integer), then mapping each to its integer value before finally returning the sum of the list for each group.

val groupTotals = groups.map { it.split(",").map { it.toInt() }.sum() }

Doing this allows both part one and part two of Day 1 of the AoC to be solved. For the first part, simply find the maximum of the list of integers groupTotals.max(). For the second part, which asked that the sum of the largest three groups be returned, use something like the following:

groupTotals.sortedDescending().take(3).sum()

A list of integers can be easily sorted from high to low. The take(3) function returns the first three, the highest three values, and they are simply all summed.

Conclusion

During this year’s Advent of Code,  I am trying to find functional solutions to all the problems. I learned a little today just by trying this out and wanted to share how that is working for me. My desire is to write code with a functional-first paradigm – this does not come naturally to someone used to the the imperative style for their full career. But I have become convinced of the benefits of avoiding mutable variables. I’ll keep posting on this as I learn more.