Advent of Code 2024 - Day 7, in Kotlin - Bridge Repair • Todd Ginsberg

Today we’ll see the power of higher-order functions (the ability to pass functions as arguments to other functions, or to return functions from functions). Higher-order functions are a core concept when writing functional code.

If you’d rather just view the code, my GitHub Repository is here.

Puzzle Input

Today, we want to parse our input down to a List<List<Long>> where the inner list represents each Long on a row of input.

class Day07(input: List<String>) {

    private val equations: List<List<Long>> = input
        .map { row -> row.split("""\D+""".toRegex()).map { it.toLong() } }

}

To accomplish this, we’ll use a regular expression which reads as “Anything that isn’t a number” to split each row, mapping each of the parts toLong.

⭐ Day 7, Part 1

The puzzle text can be found here.

To solve Part 1, we’ll write a recursive function to perform all possible operations on the list of numbers until we either exceed the target (this attempt is a failure) or hit the target with no work remaining (success!). At each step, we will both add and multiply, branching off recursively in search of an answer.

To start, we’ll define some operators, which will be functions that take two Longs, do some calculation, and return a Long result. The two we need for Part 1 are addition and multiplication.

// In Day07

private val operators: List<(Long, Long) -> Long> = listOf(
    { a, b -> a + b },
    { a, b -> a * b }
)

Next, we’ll write a function to assist with calculating our answer. It takes a list of validOperators (foreshadowing!), passes each equation to a to-be-written hasSolution function, and gets the sumOf the equations that have solutions.

// In Day07

private fun solve(validOperators: List<(Long, Long) -> Long>): Long =
    equations
        .filter { hasSolution(validOperators, it[0], it[1], it.subList(2, it.size)) }
        .sumOf { it.first() }

I want to point out the use of subList here. This is nice because it doesn’t copy anything, it gives us a view over the underlying list. The only tricky part is that subList is exclusive meaning ~~it can get into clubs I can’t~~ we have to give it 1 past the last index we want, so we’ll use size here instead of lastIndex.

Now for the code that actually implements most of our strategy. The hasSolution takes a lot of arguments, so let’s go through them. First, the list of operators (again, foreshadowing!) followed by the target we’re trying to hit (the first number of the equation), the sum we’ve achieved so far, and how many numbers in the equation are remaining.

// In Day07

private fun hasSolution(
    operators: List<(Long, Long) -> Long>,
    target: Long,
    sum: Long,
    remaining: List<Long>
): Boolean =
    when {
        remaining.isEmpty() -> target == sum
        sum > target -> false
        else -> operators.any { operator ->
            hasSolution(
                operators,
                target,
                operator.invoke(sum, remaining[0]),
                remaining.subList(1, remaining.size)
            )
        }
    }

Remember the rule for writing a recursive function: Always define your end conditions first. In this case, if we don’t have any more numbers to operate on (the remaining list is empty) then we know we’ve got a valid solution if the target and the sum are equal. Otherwise sum is either higher or lower than target and we have no way to alter that.

The next end condition is if sum exceeds target. Since we don’t have any operators that will ever make sum smaller, we know for a fact we’ve overshot the target and can exit early.

All that remains is to test if any of our operators give us a solution. We use the any function from the Kotlin Standard Library to do this for us. It will stop evaluating possibilities as soon as one is true, or return false if none of them are. In this function we recursively call hasSolution with the same operators, the same target, a sum that is the result of the current operator invoked over the previous sum and the first element of the remaining numbers, and the rest of the remaining numbers.

Calling solve with our list of operators solves Part 1!

// In Day07

fun solvePart1(): Long =
    solve(operators)

Star earned! Onward!

⭐ Day 7, Part 2

The puzzle text can be found here.

To solve Part 2, we can reuse everything we wrote for Part 1. The only work to do is to add a new operator to concatenate two numbers. Rather than define a new list of operators for Part 2, we’ll use the operators list from Part 1 and concatenate (see what we did there?) our new operator to the end of the list before passing it to solve.

// In Day07

fun solvePart2(): Long =
    solve(operators + { a, b -> "$a$b".toLong() })

See the power of higher-order functions? We didn’t change anything except adding a new function to a list. That’s really powerful!

Star earned! See you tomorrow!

Puzzle Input

⭐ Day 7, Part 1

⭐ Day 7, Part 2

Further Reading