This post continues our “Idiomatic Kotlin” series and provides the solution for the Advent of Code Day 9* challenge. While solving it, we’ll look into different ways to manipulate lists in Kotlin.

Day 9. Encoding error, part I

We need to attack a weakness in data encrypted with the eXchange-Masking Addition System (XMAS)! The data is a list of numbers, and we need to find the first number in the list (starting from the 26th) that is not the sum of any 2 of the 25 numbers before it. We’ll call the number valid if it can be presented as a sum of two numbers from the previous sublist, and invalid otherwise. Two numbers that sum to a valid number must be different from each other.

If the first 25 numbers are 1 through 25 in a random order, the next number must be the sum of two of those numbers to be valid:

• 26 would be a valid next number, as it could be 1 plus 25 (or many other pairs, like 2 and 24).
• 49 would be a valid next number, as it is the sum of 24 and 25.
• 100 would not be valid; no two of the previous 25 numbers sum to 100.
• 50 would also not be valid; although 25 appears in the previous 25 numbers, the two numbers in the pair must be different.

Solution, part I

Let’s solve the task in Kotlin! For a start, let’s implement a function that checks whether a given list contains a pair of numbers that sum up to a given number. We’ll later use this function to check whether a given number is valid by passing this number and the list of the previous 25 numbers as arguments.

For convenience, we can define the function as an extension on a List of Long numbers. We need to iterate over all the elements in the list, looking for the two with the given sum. The first naive attempt will be using forEach (we call it on this implicit receiver, our list of numbers) to iterate through the elements twice:

fun List<Long>.hasPairOfSumV1(sum: Long): Boolean {
   forEach { first ->
       forEach { second ->
           if (first + second == sum) return true
       }
   }
   return false
}
fun main() {
   val numbers = listOf(1L, 24, 25, 10, 13)
   println(numbers.hasPairOfSumV1(26)) // true; 26 = 1 + 25
   println(numbers.hasPairOfSumV1(49)) // true; 49 = 24 + 25
   println(numbers.hasPairOfSumV1(100)) // false

   // This is wrong:
   println(numbers.hasPairOfSumV1(50)) // true; 50 = 25 * 2
}

But this solution is wrong! Using this approach, first and second might refer to the same element. But as we remember from the task description, two numbers that sum to a valid number must be different from each other.

To fix that, we can iterate over a list of elements with indices and make sure that the indices of two elements are different:

fun List<Long>.hasPairOfSumV2(sum: Long): Boolean {
   forEachIndexed { i, first ->
       forEachIndexed { j, second ->
           if (i != j && first + second == sum) return true
       }
   }
   return false
}
fun main() {
   val numbers = listOf(1L, 24, 25, 10, 13)
   println(numbers.hasPairOfSumV2(50)) // false
}

This way, if first and second both refer to 25, they have the same indices, so they are no longer interpreted as a correct pair.

We can rewrite this code and delegate the logic for finding the necessary element to Kotlin library functions. For this case, any does the job. It returns true if the list contains an element that satisfies the given condition:

//sampleStart
fun List<Long>.hasPairOfSum(sum: Long): Boolean =
   indices.any { i ->
       indices.any { j ->
           i != j && this[i] + this[j] == sum
       }
   }
//sampleEnd

fun main() {
   val numbers = listOf(1L, 24, 25, 10, 13)
   println(numbers.hasPairOfSum(50)) // false
}

Our final version of the hasPairOfSum function uses any to iterate through indices instead of elements and checks for a pair that meets the condition. indices is an extension property on Collection that returns an integer range of collection indices, 0..size - 1; we call it on this implicit receiver, our list of numbers.

Finding an invalid number

Let’s implement a function that looks for an invalid number, one that is not the sum of two of the 25 numbers before it.

Before we start, let’s store the group size, 25, as a constant. We have a sample input that we can check our solution against which uses the group size 5 instead, so it’s much more convenient to change this constant in one place:

const val GROUP_SIZE = 25

We define the group size as const val and make it a compile-time constant, which means it’ll be replaced with the actual value at compile time. Indeed, if you use this constant (e.g. in a range GROUP_SIZE..lastIndex) and look at the bytecode, you’ll no longer be able to find the GROUP_SIZE property. Its usage will have been replaced with the constant 25.

For convenience, we can again define the findInvalidNumber function as an extension function on List. Let’s first implement it more directly, and then rewrite it using the power of standard library functions.

We use the example provided with the problem, where every number but one is the sum of two of the previous 5 numbers; the only number that does not follow this rule is 127:

//sampleStart
const val GROUP_SIZE = 5

fun List<Long>.findInvalidNumberV1(): Long? {
   for (index in (GROUP_SIZE + 1)..lastIndex) {
       val prevGroup = subList(index - GROUP_SIZE, index)
       if (!prevGroup.hasPairOfSum(sum = this[index])) {
           return this[index]
       }
   }
   return null
}

fun main() {
   val numbers = listOf<Long>(
       35, 20, 15, 25, 47, 40, 62,
       55, 65, 95, 102, 117, 150, 182,
       127, 219, 299, 277, 309, 576)
   println(numbers.findInvalidNumberV1()) // 127
}
//sampleEnd

fun List<Long>.hasPairOfSum(sum: Long): Boolean =
   indices.any { i ->
       indices.any { j ->
           i != j && this[i] + this[j] == sum
       }
   }

Because we need to find the first number in the input list that satisfies our condition starting from the 26th, we iterate over all indices starting from GROUP_SIZE + 1 up to the last index, and for each corresponding element check whether it’s invalid. prevGroup contains exactly GROUP_SIZE elements, and we run hasPairOfSum on it, providing the current element as the sum to check. If we find an invalid element, we return it.

You may think that the sublist() function creates the sublists and copies the list content, but it doesn’t! It merely creates a view. By using it, we avoid having to create many intermediate sublists!

We can rewrite this code using the firstOrNull library function. It finds the first element that satisfies the given condition. This allows us to find the index of the invalid number. Then we use let to return the element staying at the found position:

const val GROUP_SIZE = 5
//sampleStart
fun List<Long>.findInvalidNumberV2(): Long? =
   ((GROUP_SIZE + 1)..lastIndex)
       .firstOrNull { index ->
           val prevGroup = subList(index - GROUP_SIZE, index)
           !prevGroup.hasPairOfSum(sum = this[index])
       }
       ?.let { this[it] }
//sampleEnd

fun main() {
   val numbers = listOf<Long>(
       35, 20, 15, 25, 47, 40, 62,
       55, 65, 95, 102, 117, 150, 182,
       127, 219, 299, 277, 309, 576)
   println(numbers.findInvalidNumberV2()) // 127
}

fun List<Long>.hasPairOfSum(sum: Long): Boolean =
   indices.any { i ->
       indices.any { j ->
           i != j && this[i] + this[j] == sum
       }
   }

Note how we use safe access together with let to transform the index if one was found. Otherwise null is returned.

Using ‘windowed’

To improve readability, we can follow a slightly different approach. Instead of iterating over indices by hand and constructing the necessary sublists, we use a library function that does the job for us.

The Kotlin standard library has the windowed function, which returns a list or a sequence of snapshots of a window of a given size. This window “slides” along the given collection or sequence, moving by one element each step:

fun main() {
   val list = listOf('a', 'b', 'c', 'd', 'e')
   println(list.windowed(2)) // [[a, b], [b, c], [c, d], [d, e]]
   println(list.windowed(3)) // [[a, b, c], [b, c, d], [c, d, e]]
}

Here we build sublists, that is, snapshots, of size 2 and 3. To see more examples of how to use windowed and other advanced operations on collections, check out this video.

This function is perfectly suited to our challenge, as it can build sublists of the required size automatically for us. Let’s rewrite findInvalidNumber once more:

const val GROUP_SIZE = 5
//sampleStart
fun List<Long>.findInvalidNumberV3(): Long? =
    windowed(GROUP_SIZE + 1)
       .firstOrNull { window ->
           val prevGroup = window.dropLast(1)
           !prevGroup.hasPairOfSum(sum = window.last())
       }
       ?.last()
//sampleEnd

fun main() {
   val numbers = listOf<Long>(
       35, 20, 15, 25, 47, 40, 62,
       55, 65, 95, 102, 117, 150, 182,
       127, 219, 299, 277, 309, 576)
   println(numbers.findInvalidNumberV3()) // 127
}

fun List<Long>.hasPairOfSum(sum: Long): Boolean =
   indices.any { i ->
       indices.any { j ->
           i != j && this[i] + this[j] == sum
       }
   }

To have both the previous group and the current number, we use a window with the size GROUP_SIZE + 1. The first GROUP_SIZE elements form the necessary sublist to check, while the last element is the current number. If we find a sublist that satisfies the given condition, its last element is the result.

Note about the difference between sublist and windowed functions

Note, however, that unlike sublist(), which creates a view of the existing list, the windowed() function builds all the intermediate lists. Though using it improves readability, it results in some performance drawbacks. For parts of the code that are not performance-critical, these drawbacks usually are not noticeable. On the JVM, the garbage collector is very effective at collecting such short-lived objects. It’s nevertheless useful to know about these nuanced differences between the two functions!

There’s also an overloaded version of the windowed() function that takes lambda as an argument describing how to transform each window. This version doesn’t create new sublists to pass as lambda arguments. Instead, it passes “ephemeral” sublists (somewhat similar to sublist() views) that are valid only inside the lambda. You should not store such a sublist or allow it to escape unless you’ve made a snapshot of it:

fun main() {
   val list = listOf('a', 'b', 'c', 'd', 'e')
   // Intermediate lists are created:
   println(list.windowed(2).map { it.joinToString("") })

   // Lists passed to lambda are "ephemeral",
   // they are only valid inside this lambda:
   println(list.windowed(2) { it.joinToString("") })

   // You should make a copy of a window sublist
   // to store it or pass further:
   var firstWindowRef: List<Char>? = null
   var firstWindowCopy: List<Char>? = null
   list.windowed(2) {
       if (it.first() == 'a') {
           firstWindowRef = it // Don't do this!
           firstWindowCopy = it.toList()
       }
       it.joinToString("")
   }
   println("Ref: $firstWindowRef")   // [d, e]
   println("Copy: $firstWindowCopy") // [a, b]
}

If you try to store the very first window [a, b] by copying the reference, you see that by the end of the iterations this reference contains different data, the last window. To get the first window, you need to copy the content.

A function with similar optimization might be added in the future for Sequences, see KT-48800 for details.

We can further improve our findInvalidNumber function by using sequences instead of lists. In Kotlin, Sequence provides a lazy way of computation. In the current solution, windowed eagerly returns the result, the full list of windows. If the required element is found in the very first list, it’s not efficient. The change to Sequence causes the result to be evaluated lazily, which means the snapshots are built only when they’re actually needed.

The change to sequences only requires one line. We convert a list to a sequence before performing any further operations:

const val GROUP_SIZE = 5
//sampleStart
fun List<Long>.findInvalidNumber(): Long? =
    asSequence()
       .windowed(GROUP_SIZE + 1)
       .firstOrNull { window ->
           val prevGroup = window.dropLast(1)
           !prevGroup.hasPairOfSum(sum = window.last())
       }
       ?.last()
//sampleEnd

fun main() {
   val numbers = listOf<Long>(
       35, 20, 15, 25, 47, 40, 62,
       55, 65, 95, 102, 117, 150, 182,
       127, 219, 299, 277, 309, 576)
   println(numbers.findInvalidNumber()) // 127
}

fun List<Long>.hasPairOfSum(sum: Long): Boolean =
   indices.any { i ->
       indices.any { j ->
           i != j && this[i] + this[j] == sum
       }
   }

That’s it! We’ve improved the solution from the very first version, making it more “idiomatic” along the way.

The last thing to do is to get the result for our challenge. We read the input, convert it to a list of numbers, and display the invalid one:

fun main() {
   val numbers = File("src/day09/input.txt")
       .readLines()
       .map { it.toLong() }

   val invalidNumber = numbers.findInvalidNumber()
   println(invalidNumber)
}

For the sample input, the answer is 127, and for real input, the answer is also correct! Let’s now move on to solve the second part of the task.

Encoding error, part II

The second part of the task requires us to use the invalid number we just found. We need to find a contiguous set of at least two numbers in the list which sum up to this invalid number. The result we are looking for is the sum of the smallest and largest number in this contiguous range.

For the sample list, we need to find a contiguous list which sums to 127:

35 20 15 25 47 40 62 55 65 95 102 117 150 182 127 219 299 277 309 576

In this list, adding up all of the numbers from 15 through 40 produces 127. To find the result, we add together the smallest and largest number in this contiguous range; in this example, these are 15 and 47, producing 62.

Solution, part II

We need to find a sublist in a list with the given sum of its elements. Let’s first implement this function in a straightforward manner, then rewrite the same logic using library functions. We’ll discuss whether the windowed function from the previous part can help us here as well, and finally we’ll identify a more efficient solution.

To check the sum of every contiguous sublist of a given list, we try all the options for the list’s start and end indices, build each sublist, and calculate its sum. fromIndex belongs to a full range of indices, while toIndex should be greater than fromIndex and shouldn’t exceed the list size (the toIndex argument defines an exclusive, not inclusive, upper bound):

fun List<Long>.findSublistOfSumV1(targetSum: Long): List<Long>? {
   for (fromIndex in indices) {
       for (toIndex in (fromIndex + 1)..size) {
           val subList = subList(fromIndex, toIndex)
           if (subList.sum() == targetSum) {
               return subList
           }
       }
   }
   return null
}

fun main() {
   val numbers = listOf<Long>(
       35, 20, 15, 25, 47, 40, 62,
       55, 65, 95, 102, 117, 150, 182,
       127, 219, 299, 277, 309, 576
   )
   println(numbers.findSublistOfSumV1(127)) // [15, 25, 47, 40]
}

We can rewrite this logic using the firstNotNullOfOrNull function. Here, we iterate over possible values for fromIndex and for toIndex and look for the first value that satisfies the given condition:

//sampleStart
fun List<Long>.findSublistOfSumV2(targetSum: Long): List<Long>? =
   indices.firstNotNullOfOrNull { fromIndex ->
       ((fromIndex + 1)..size)
           .firstNotNullOfOrNull { toIndex ->
               subList(fromIndex, toIndex).takeIf { it.sum() == targetSum }
           }
   }

//sampleEnd
fun main() {
   val numbers = listOf<Long>(
       35, 20, 15, 25, 47, 40, 62,
       55, 65, 95, 102, 117, 150, 182,
       127, 219, 299, 277, 309, 576
   )
   println(numbers.findSublistOfSumV2(127)) // [15, 25, 47, 40]
}

The logic hasn’t changed, we’ve simply rewritten it using the firstNotNullOfOrNull. If a sublist with the required sum is found, it’s returned from both firstNotNullOfOrNull calls as the first found non-null value.

The takeIf function returns its receiver if it satisfies the given condition or null if it doesn’t. In this case, the takeIf call returns the found sublist if the sum of its elements is equal to the provided targetSum.

An alternative way to solve this problem is, for each possible sublist size, to build all the sublists of this size using the windowed function, and then check the sum of its elements:

//sampleStart
fun List<Long>.findSublistOfSumV3(targetSum: Long): List<Long>? =
   (2..size).firstNotNullOfOrNull { sublistSize ->
       asSequence()
           .windowed(sublistSize)
           .firstOrNull { sublist ->
               sublist.sum() == targetSum
           }
   }

//sampleEnd
fun main() {
   val numbers = listOf<Long>(
       35, 20, 15, 25, 47, 40, 62,
       55, 65, 95, 102, 117, 150, 182,
       127, 219, 299, 277, 309, 576
   )
   println(numbers.findSublistOfSumV3(127)) // [15, 25, 47, 40]
}

As before, we convert the input list to a sequence to perform the operation in a lazy manner: each new sublist is created when it needs to be checked for sum.

All the functions we’ve considered so far work for the challenge input and give the correct answer, but they have one common disadvantage: they manipulate the sublists of all possible sizes, and for each one, calculate the sum. This approach isn’t the most efficient. We can do better, can’t we?

We can precalculate all the sums of sublists from the first element in the list to each element, and use these “prefix” sums to easily calculate the sum between any two elements. If we have the sum of elements from 0 to fromIndex, and the sum of elements from 0 to toIndex, the sum of the elements from fromIndex to toIndex can be found by subtracting the former from the latter:

sum(fromIndex, toIndex) = sum(0, toIndex) - sum(0, fromIndex)

The following illustration shows that:

We need to precalculate the prefix sum for each element. We can use the standard library’s scan function for that! It also has another name, runningFold.

The fold and scan (runningFold) functions are related:

• They both “accumulate” value starting with the initial value. On each step, they apply the provided operation to the current accumulator value and the next element.
• fold returns only the final result, while scan (runningFold) returns the results for all the intermediate steps.

fun main() {
   println((1..4).fold(0) { acc, elem -> acc + elem }) // 10
   println((1..4).scan(0) { acc, elem -> acc + elem }) // [0, 1, 3, 6, 10]
}

The following animation illustrates the fold and scan functions in action:

After precalculating all the prefix sums, we use them to find the sums of all the possible sublists, and look for the required sum:

//sampleStart
fun List<Long>.findSublistOfSum(targetSum: Long): List<Long>? {
   val prefixSums = scan(0L) { acc, element -> acc + element }
   return indices.firstNotNullOfOrNull { fromIndex ->
       ((fromIndex + 1)..size).firstNotNullOfOrNull { toIndex ->
           val subListSum = prefixSums[toIndex] - prefixSums[fromIndex]
           if (subListSum == targetSum) subList(fromIndex, toIndex) else null
       }
   }
}
//sampleEnd
fun main() {
   val numbers = listOf<Long>(
       35, 20, 15, 25, 47, 40, 62,
       55, 65, 95, 102, 117, 150, 182,
       127, 219, 299, 277, 309, 576
   )
   println(numbers.findSublistOfSum(127)) // [15, 25, 47, 40]
}

In this solution, we explicitly build only one sublist of the required sum to return it as the result.

Let’s now call the findSublistOfSum function to find the result for our initial challenge. After we found the invalid number in part I, we pass this value as an argument to the findSublistOfSum function, and then find the sum of the minimum and maximum values of the resulting list:

fun main() {
   val numbers = File("src/day09/input.txt")
       .readLines()
       .map { it.toLong() }

   val invalidNumber = numbers.findInvalidNumber()
       ?: error("All numbers are valid!")
   println("Invalid number: $invalidNumber")

   val sublist = numbers.findSublistOfSum(sum = invalidNumber)
       ?: error("No sublist is found!")
   println(sublist.minOf { it } + sublist.maxOf { it })
}

Note how we use the error function to report an error and throw an exception in the event that one of our functions returns null. In AdventOfCode puzzles, we assume that the input is correct, but it’s still useful to handle errors properly.

That’s all! We’ve discussed the solution for the Day 9 AdventOfCode challenge and worked with the any, firstOrNull, firstNotNullOfOrNull, windowed, takeIf and scan functions, which exemplify a more idiomatic Kotlin style.

—

*Used with the permission of Advent of Code (Eric Wastl).

This post continues our “Idiomatic Kotlin” series and provides the solution for the Advent of Code Day 9* challenge. While solving it, we’ll look into different ways to manipulate lists in Kotlin.

Day 9. Encoding error, part I

We need to attack a weakness in data encrypted with the eXchange-Masking Addition System (XMAS)! The data is a list of numbers, and we need to find the first number in the list (starting from the 26th) that is not the sum of any 2 of the 25 numbers before it. We’ll call the number valid if it can be presented as a sum of two numbers from the previous sublist, and invalid otherwise. Two numbers that sum to a valid number must be different from each other.

If the first 25 numbers are 1 through 25 in a random order, the next number must be the sum of two of those numbers to be valid:

• 26 would be a valid next number, as it could be 1 plus 25 (or many other pairs, like 2 and 24).
• 49 would be a valid next number, as it is the sum of 24 and 25.
• 100 would not be valid; no two of the previous 25 numbers sum to 100.
• 50 would also not be valid; although 25 appears in the previous 25 numbers, the two numbers in the pair must be different.

Solution, part I

Let’s solve the task in Kotlin! For a start, let’s implement a function that checks whether a given list contains a pair of numbers that sum up to a given number. We’ll later use this function to check whether a given number is valid by passing this number and the list of the previous 25 numbers as arguments.

For convenience, we can define the function as an extension on a List of Long numbers. We need to iterate over all the elements in the list, looking for the two with the given sum. The first naive attempt will be using forEach (we call it on this implicit receiver, our list of numbers) to iterate through the elements twice:

fun List<Long>.hasPairOfSumV1(sum: Long): Boolean {
   forEach { first ->
       forEach { second ->
           if (first + second == sum) return true
       }
   }
   return false
}
fun main() {
   val numbers = listOf(1L, 24, 25, 10, 13)
   println(numbers.hasPairOfSumV1(26)) // true; 26 = 1 + 25
   println(numbers.hasPairOfSumV1(49)) // true; 49 = 24 + 25
   println(numbers.hasPairOfSumV1(100)) // false

   // This is wrong:
   println(numbers.hasPairOfSumV1(50)) // true; 50 = 25 * 2
}

But this solution is wrong! Using this approach, first and second might refer to the same element. But as we remember from the task description, two numbers that sum to a valid number must be different from each other.

To fix that, we can iterate over a list of elements with indices and make sure that the indices of two elements are different:

fun List<Long>.hasPairOfSumV2(sum: Long): Boolean {
   forEachIndexed { i, first ->
       forEachIndexed { j, second ->
           if (i != j && first + second == sum) return true
       }
   }
   return false
}
fun main() {
   val numbers = listOf(1L, 24, 25, 10, 13)
   println(numbers.hasPairOfSumV2(50)) // false
}

This way, if first and second both refer to 25, they have the same indices, so they are no longer interpreted as a correct pair.

We can rewrite this code and delegate the logic for finding the necessary element to Kotlin library functions. For this case, any does the job. It returns true if the list contains an element that satisfies the given condition:

//sampleStart
fun List<Long>.hasPairOfSum(sum: Long): Boolean =
   indices.any { i ->
       indices.any { j ->
           i != j && this[i] + this[j] == sum
       }
   }
//sampleEnd

fun main() {
   val numbers = listOf(1L, 24, 25, 10, 13)
   println(numbers.hasPairOfSum(50)) // false
}

Our final version of the hasPairOfSum function uses any to iterate through indices instead of elements and checks for a pair that meets the condition. indices is an extension property on Collection that returns an integer range of collection indices, 0..size - 1; we call it on this implicit receiver, our list of numbers.

Finding an invalid number

Let’s implement a function that looks for an invalid number, one that is not the sum of two of the 25 numbers before it.

Before we start, let’s store the group size, 25, as a constant. We have a sample input that we can check our solution against which uses the group size 5 instead, so it’s much more convenient to change this constant in one place:

const val GROUP_SIZE = 25

We define the group size as const val and make it a compile-time constant, which means it’ll be replaced with the actual value at compile time. Indeed, if you use this constant (e.g. in a range GROUP_SIZE..lastIndex) and look at the bytecode, you’ll no longer be able to find the GROUP_SIZE property. Its usage will have been replaced with the constant 25.

For convenience, we can again define the findInvalidNumber function as an extension function on List. Let’s first implement it more directly, and then rewrite it using the power of standard library functions.

We use the example provided with the problem, where every number but one is the sum of two of the previous 5 numbers; the only number that does not follow this rule is 127:

//sampleStart
const val GROUP_SIZE = 5

fun List<Long>.findInvalidNumberV1(): Long? {
   for (index in (GROUP_SIZE + 1)..lastIndex) {
       val prevGroup = subList(index - GROUP_SIZE, index)
       if (!prevGroup.hasPairOfSum(sum = this[index])) {
           return this[index]
       }
   }
   return null
}

fun main() {
   val numbers = listOf<Long>(
       35, 20, 15, 25, 47, 40, 62,
       55, 65, 95, 102, 117, 150, 182,
       127, 219, 299, 277, 309, 576)
   println(numbers.findInvalidNumberV1()) // 127
}
//sampleEnd

fun List<Long>.hasPairOfSum(sum: Long): Boolean =
   indices.any { i ->
       indices.any { j ->
           i != j && this[i] + this[j] == sum
       }
   }

Because we need to find the first number in the input list that satisfies our condition starting from the 26th, we iterate over all indices starting from GROUP_SIZE + 1 up to the last index, and for each corresponding element check whether it’s invalid. prevGroup contains exactly GROUP_SIZE elements, and we run hasPairOfSum on it, providing the current element as the sum to check. If we find an invalid element, we return it.

You may think that the sublist() function creates the sublists and copies the list content, but it doesn’t! It merely creates a view. By using it, we avoid having to create many intermediate sublists!

We can rewrite this code using the firstOrNull library function. It finds the first element that satisfies the given condition. This allows us to find the index of the invalid number. Then we use let to return the element staying at the found position:

const val GROUP_SIZE = 5
//sampleStart
fun List<Long>.findInvalidNumberV2(): Long? =
   ((GROUP_SIZE + 1)..lastIndex)
       .firstOrNull { index ->
           val prevGroup = subList(index - GROUP_SIZE, index)
           !prevGroup.hasPairOfSum(sum = this[index])
       }
       ?.let { this[it] }
//sampleEnd

fun main() {
   val numbers = listOf<Long>(
       35, 20, 15, 25, 47, 40, 62,
       55, 65, 95, 102, 117, 150, 182,
       127, 219, 299, 277, 309, 576)
   println(numbers.findInvalidNumberV2()) // 127
}

fun List<Long>.hasPairOfSum(sum: Long): Boolean =
   indices.any { i ->
       indices.any { j ->
           i != j && this[i] + this[j] == sum
       }
   }

Note how we use safe access together with let to transform the index if one was found. Otherwise null is returned.

Using ‘windowed’

To improve readability, we can follow a slightly different approach. Instead of iterating over indices by hand and constructing the necessary sublists, we use a library function that does the job for us.

The Kotlin standard library has the windowed function, which returns a list or a sequence of snapshots of a window of a given size. This window “slides” along the given collection or sequence, moving by one element each step:

fun main() {
   val list = listOf('a', 'b', 'c', 'd', 'e')
   println(list.windowed(2)) // [[a, b], [b, c], [c, d], [d, e]]
   println(list.windowed(3)) // [[a, b, c], [b, c, d], [c, d, e]]
}

Here we build sublists, that is, snapshots, of size 2 and 3. To see more examples of how to use windowed and other advanced operations on collections, check out this video.

This function is perfectly suited to our challenge, as it can build sublists of the required size automatically for us. Let’s rewrite findInvalidNumber once more:

const val GROUP_SIZE = 5
//sampleStart
fun List<Long>.findInvalidNumberV3(): Long? =
    windowed(GROUP_SIZE + 1)
       .firstOrNull { window ->
           val prevGroup = window.dropLast(1)
           !prevGroup.hasPairOfSum(sum = window.last())
       }
       ?.last()
//sampleEnd

fun main() {
   val numbers = listOf<Long>(
       35, 20, 15, 25, 47, 40, 62,
       55, 65, 95, 102, 117, 150, 182,
       127, 219, 299, 277, 309, 576)
   println(numbers.findInvalidNumberV3()) // 127
}

fun List<Long>.hasPairOfSum(sum: Long): Boolean =
   indices.any { i ->
       indices.any { j ->
           i != j && this[i] + this[j] == sum
       }
   }

To have both the previous group and the current number, we use a window with the size GROUP_SIZE + 1. The first GROUP_SIZE elements form the necessary sublist to check, while the last element is the current number. If we find a sublist that satisfies the given condition, its last element is the result.

Note about the difference between sublist and windowed functions

Note, however, that unlike sublist(), which creates a view of the existing list, the windowed() function builds all the intermediate lists. Though using it improves readability, it results in some performance drawbacks. For parts of the code that are not performance-critical, these drawbacks usually are not noticeable. On the JVM, the garbage collector is very effective at collecting such short-lived objects. It’s nevertheless useful to know about these nuanced differences between the two functions!

There’s also an overloaded version of the windowed() function that takes lambda as an argument describing how to transform each window. This version doesn’t create new sublists to pass as lambda arguments. Instead, it passes “ephemeral” sublists (somewhat similar to sublist() views) that are valid only inside the lambda. You should not store such a sublist or allow it to escape unless you’ve made a snapshot of it:

fun main() {
   val list = listOf('a', 'b', 'c', 'd', 'e')
   // Intermediate lists are created:
   println(list.windowed(2).map { it.joinToString("") })

   // Lists passed to lambda are "ephemeral",
   // they are only valid inside this lambda:
   println(list.windowed(2) { it.joinToString("") })

   // You should make a copy of a window sublist
   // to store it or pass further:
   var firstWindowRef: List<Char>? = null
   var firstWindowCopy: List<Char>? = null
   list.windowed(2) {
       if (it.first() == 'a') {
           firstWindowRef = it // Don't do this!
           firstWindowCopy = it.toList()
       }
       it.joinToString("")
   }
   println("Ref: $firstWindowRef")   // [d, e]
   println("Copy: $firstWindowCopy") // [a, b]
}

If you try to store the very first window [a, b] by copying the reference, you see that by the end of the iterations this reference contains different data, the last window. To get the first window, you need to copy the content.

A function with similar optimization might be added in the future for Sequences, see KT-48800 for details.

We can further improve our findInvalidNumber function by using sequences instead of lists. In Kotlin, Sequence provides a lazy way of computation. In the current solution, windowed eagerly returns the result, the full list of windows. If the required element is found in the very first list, it’s not efficient. The change to Sequence causes the result to be evaluated lazily, which means the snapshots are built only when they’re actually needed.

The change to sequences only requires one line. We convert a list to a sequence before performing any further operations:

const val GROUP_SIZE = 5
//sampleStart
fun List<Long>.findInvalidNumber(): Long? =
    asSequence()
       .windowed(GROUP_SIZE + 1)
       .firstOrNull { window ->
           val prevGroup = window.dropLast(1)
           !prevGroup.hasPairOfSum(sum = window.last())
       }
       ?.last()
//sampleEnd

fun main() {
   val numbers = listOf<Long>(
       35, 20, 15, 25, 47, 40, 62,
       55, 65, 95, 102, 117, 150, 182,
       127, 219, 299, 277, 309, 576)
   println(numbers.findInvalidNumber()) // 127
}

fun List<Long>.hasPairOfSum(sum: Long): Boolean =
   indices.any { i ->
       indices.any { j ->
           i != j && this[i] + this[j] == sum
       }
   }

That’s it! We’ve improved the solution from the very first version, making it more “idiomatic” along the way.

The last thing to do is to get the result for our challenge. We read the input, convert it to a list of numbers, and display the invalid one:

fun main() {
   val numbers = File("src/day09/input.txt")
       .readLines()
       .map { it.toLong() }

   val invalidNumber = numbers.findInvalidNumber()
   println(invalidNumber)
}

For the sample input, the answer is 127, and for real input, the answer is also correct! Let’s now move on to solve the second part of the task.

Encoding error, part II

The second part of the task requires us to use the invalid number we just found. We need to find a contiguous set of at least two numbers in the list which sum up to this invalid number. The result we are looking for is the sum of the smallest and largest number in this contiguous range.

For the sample list, we need to find a contiguous list which sums to 127:

35 20 15 25 47 40 62 55 65 95 102 117 150 182 127 219 299 277 309 576

In this list, adding up all of the numbers from 15 through 40 produces 127. To find the result, we add together the smallest and largest number in this contiguous range; in this example, these are 15 and 47, producing 62.

Solution, part II

We need to find a sublist in a list with the given sum of its elements. Let’s first implement this function in a straightforward manner, then rewrite the same logic using library functions. We’ll discuss whether the windowed function from the previous part can help us here as well, and finally we’ll identify a more efficient solution.

To check the sum of every contiguous sublist of a given list, we try all the options for the list’s start and end indices, build each sublist, and calculate its sum. fromIndex belongs to a full range of indices, while toIndex should be greater than fromIndex and shouldn’t exceed the list size (the toIndex argument defines an exclusive, not inclusive, upper bound):

fun List<Long>.findSublistOfSumV1(targetSum: Long): List<Long>? {
   for (fromIndex in indices) {
       for (toIndex in (fromIndex + 1)..size) {
           val subList = subList(fromIndex, toIndex)
           if (subList.sum() == targetSum) {
               return subList
           }
       }
   }
   return null
}

fun main() {
   val numbers = listOf<Long>(
       35, 20, 15, 25, 47, 40, 62,
       55, 65, 95, 102, 117, 150, 182,
       127, 219, 299, 277, 309, 576
   )
   println(numbers.findSublistOfSumV1(127)) // [15, 25, 47, 40]
}

We can rewrite this logic using the firstNotNullOfOrNull function. Here, we iterate over possible values for fromIndex and for toIndex and look for the first value that satisfies the given condition:

//sampleStart
fun List<Long>.findSublistOfSumV2(targetSum: Long): List<Long>? =
   indices.firstNotNullOfOrNull { fromIndex ->
       ((fromIndex + 1)..size)
           .firstNotNullOfOrNull { toIndex ->
               subList(fromIndex, toIndex).takeIf { it.sum() == targetSum }
           }
   }

//sampleEnd
fun main() {
   val numbers = listOf<Long>(
       35, 20, 15, 25, 47, 40, 62,
       55, 65, 95, 102, 117, 150, 182,
       127, 219, 299, 277, 309, 576
   )
   println(numbers.findSublistOfSumV2(127)) // [15, 25, 47, 40]
}

The logic hasn’t changed, we’ve simply rewritten it using the firstNotNullOfOrNull. If a sublist with the required sum is found, it’s returned from both firstNotNullOfOrNull calls as the first found non-null value.

The takeIf function returns its receiver if it satisfies the given condition or null if it doesn’t. In this case, the takeIf call returns the found sublist if the sum of its elements is equal to the provided targetSum.

An alternative way to solve this problem is, for each possible sublist size, to build all the sublists of this size using the windowed function, and then check the sum of its elements:

//sampleStart
fun List<Long>.findSublistOfSumV3(targetSum: Long): List<Long>? =
   (2..size).firstNotNullOfOrNull { sublistSize ->
       asSequence()
           .windowed(sublistSize)
           .firstOrNull { sublist ->
               sublist.sum() == targetSum
           }
   }

//sampleEnd
fun main() {
   val numbers = listOf<Long>(
       35, 20, 15, 25, 47, 40, 62,
       55, 65, 95, 102, 117, 150, 182,
       127, 219, 299, 277, 309, 576
   )
   println(numbers.findSublistOfSumV3(127)) // [15, 25, 47, 40]
}

As before, we convert the input list to a sequence to perform the operation in a lazy manner: each new sublist is created when it needs to be checked for sum.

All the functions we’ve considered so far work for the challenge input and give the correct answer, but they have one common disadvantage: they manipulate the sublists of all possible sizes, and for each one, calculate the sum. This approach isn’t the most efficient. We can do better, can’t we?

We can precalculate all the sums of sublists from the first element in the list to each element, and use these “prefix” sums to easily calculate the sum between any two elements. If we have the sum of elements from 0 to fromIndex, and the sum of elements from 0 to toIndex, the sum of the elements from fromIndex to toIndex can be found by subtracting the former from the latter:

sum(fromIndex, toIndex) = sum(0, toIndex) - sum(0, fromIndex)

The following illustration shows that:

We need to precalculate the prefix sum for each element. We can use the standard library’s scan function for that! It also has another name, runningFold.

The fold and scan (runningFold) functions are related:

• They both “accumulate” value starting with the initial value. On each step, they apply the provided operation to the current accumulator value and the next element.
• fold returns only the final result, while scan (runningFold) returns the results for all the intermediate steps.

fun main() {
   println((1..4).fold(0) { acc, elem -> acc + elem }) // 10
   println((1..4).scan(0) { acc, elem -> acc + elem }) // [0, 1, 3, 6, 10]
}

The following animation illustrates the fold and scan functions in action:

After precalculating all the prefix sums, we use them to find the sums of all the possible sublists, and look for the required sum:

//sampleStart
fun List<Long>.findSublistOfSum(targetSum: Long): List<Long>? {
   val prefixSums = scan(0L) { acc, element -> acc + element }
   return indices.firstNotNullOfOrNull { fromIndex ->
       ((fromIndex + 1)..size).firstNotNullOfOrNull { toIndex ->
           val subListSum = prefixSums[toIndex] - prefixSums[fromIndex]
           if (subListSum == targetSum) subList(fromIndex, toIndex) else null
       }
   }
}
//sampleEnd
fun main() {
   val numbers = listOf<Long>(
       35, 20, 15, 25, 47, 40, 62,
       55, 65, 95, 102, 117, 150, 182,
       127, 219, 299, 277, 309, 576
   )
   println(numbers.findSublistOfSum(127)) // [15, 25, 47, 40]
}

In this solution, we explicitly build only one sublist of the required sum to return it as the result.

Let’s now call the findSublistOfSum function to find the result for our initial challenge. After we found the invalid number in part I, we pass this value as an argument to the findSublistOfSum function, and then find the sum of the minimum and maximum values of the resulting list:

fun main() {
   val numbers = File("src/day09/input.txt")
       .readLines()
       .map { it.toLong() }

   val invalidNumber = numbers.findInvalidNumber()
       ?: error("All numbers are valid!")
   println("Invalid number: $invalidNumber")

   val sublist = numbers.findSublistOfSum(sum = invalidNumber)
       ?: error("No sublist is found!")
   println(sublist.minOf { it } + sublist.maxOf { it })
}

Note how we use the error function to report an error and throw an exception in the event that one of our functions returns null. In AdventOfCode puzzles, we assume that the input is correct, but it’s still useful to handle errors properly.

That’s all! We’ve discussed the solution for the Day 9 AdventOfCode challenge and worked with the any, firstOrNull, firstNotNullOfOrNull, windowed, takeIf and scan functions, which exemplify a more idiomatic Kotlin style.

—

*Used with the permission of Advent of Code (Eric Wastl).

Grouping and counting the characters in strings and collections is a very typical task given in coding interviews. Usually, the solutions for such tasks are quite simple. In this blog post, we learn about a few useful functions in Kotlin that make set operations really simple.

The task: custom customs

The task for the Advent of Code Day 6 challenge requires us to count the answers on customs declaration forms. We are provided with the results of the filled-in forms for different groups of people. Below is the original sample provided in the AoC Day 6 challenge:

abc

a
b
c

ab
ac

a
a
a
a

b

This list represents answers from 5 groups:

1. The first group contains one person who answered “yes” to 3 questions: a, b, and c.
2. The second group contains three people who collectively answered “yes” to 3 questions: a, b, and c.
3. The third group contains two people who collectively answered “yes” to 3 questions: a, b, and c.
4. The fourth group contains four people who collectively answered “yes” to only 1 question, a.
5. The last group contains one person who answered “yes” to only 1 question, b.

Our task is to calculate the total number of “yes” answers in each group. For the example above, that would be 3 + 3 + 3 + 1 + 1 = 11.

Sounds easy, right? It seems like we could solve this task by just iterating the data, counting, and summing it up to get the final result. Let’s try that!

Solving the puzzle

First, we need to read the data. We can use the File.readText() function and then trim off the whitespace at the beginning and the end of the file. As per the description, group answers are always separated by blank lines, so we’ll use two line separators to split our input into separate groups:

val newLine = System.lineSeparator()

val groups: List<string> = File("src/day06/input.txt")
   .readText()
   .trim()
   .split("$newLine$newLine")</string>

The result is a list of strings. Each string in the list represents the data about a group of answers to the questions from the customs declaration form. 

Our goal is to count the unique answers within the group. We don’t need to count the answers for each individual person. This boils down to counting the unique characters in the string that represents the answers of each group. 

A naive approach to solving the task above would be to iterate over the list of strings, eliminate duplicate characters by converting each string to a set, and calculate the size of all the sets. The sum would be the final answer.

var total = 0
for (group in groups) {
   total += group.replace(newLine, "").toSet().size
}

The group of answers is one string, but it may include answers from multiple people, one line per person. Line breaks should not be taken into account when counting the unique characters. Therefore, I’m removing the line breaks before converting them to a set.

The solution is simple, but can it be improved in any way? As you might have guessed –  it can! In fact, summing up numbers by iterating over a data structure is a pretty common task. IntelliJ IDEA would even suggest using the sumOf function if we place the caret on the for loop and press Alt+Enter.

val total = groups.sumOf {
   it.replace(newLine, "").toSet().size
}

The sumOf function eliminates the need for the mutable variable to calculate the total. The function comes from Kotlin’s standard library, and if we look at the implementation, it does exactly what we did above:

public inline fun <T> Iterable<T>.sumOf(selector: (T) -> Int): Int {
   var sum: Int = 0.toInt()
   for (element in this) {
       sum += selector(element)
   }
   return sum
}

The selector parameter is the function that returns a number. In our task, that’s the size of the set with unique answers for the group.

The puzzle continues

There’s a second part to the task. Just like in real life – there’s a change in the requirements! According to the story, we have misread the rules for counting the answers in the group. Instead of finding the questions to which anyone answered “yes”, we need to find the questions to which everyone in the group answered “yes”. For the same input:

abc

a
b
c

ab
ac

a
a
a
a

b

The rules for counting the answers are the following:

• In the first group, everyone (the 1 person) answered “yes” to all 3 questions: a, b, and c.
• In the second group, there is no question to which everyone answered “yes”.
• In the third group, there is 1 question to which everyone answered “yes”, a. Since some people did not answer “yes” to b or c, the answers to these questions don’t count.
• In the fourth group, everyone answered yes to 1 question only, a.
• In the fifth group, everyone (the 1 person) answered “yes” to 1 question, b.

The final answer is 3 + 0 + 1 + 1 + 1 = 6

Let’s make a plan for solving this task. We need to iterate over the list of answer groups (1). Each group is represented by a multi-line string, and each line in a string represents answers by an individual person. Hence, we need to split the string to analyze the individual answers (2). We need to find the characters that are present in each line in a group (3). Each line is “a set of answers” by an individual person. So, we have a number of sets and we need to find the elements that are included in all the sets. This means we need to find the intersection (4) of the sets and reduce (5) the sets to only those elements that belong to the intersection.

Luckily, intersect is a standard library function in Kotlin. Additionally, the collection of sets can be reduced to a single set with the reduce function.

var total = 0
for (group in groups) { // (1)
   val answers: List<String> = group.split(newLine) // (2)
   val answerSets: List<Set<Char>> = answers.map { it.toSet() } // (3)
   val intersection: Set<Char> = 
         answerSets.reduce /* (5) */ { a, b -> a intersect b /* (4) */}
   total += intersection.size
}

This is a reasonably straightforward approach for solving the task. However, we can definitely do better by using more functions from the Kotlin standard library.

We can logically split this code into two parts. First, we can shape the input into a data structure that can be used to implement the “business logic”. To do this, we need to split each string in the list that we have read from the file, and then we need to convert each element to a set. This can be implemented using the map function as follows:

val data = groups.map {
   it.split(newLine).map { s -> s.toSet() }
}

Next, we need to find the characters that are found in all the sets for each group. The reduce and intersect operations are still applicable for this part.

Let’s take a look at the intersect function first. Given two sets of characters, “abc” and “cde”, the intersection is only the character “c”:

val setA = "abc".toSet()
val setB = "cde".toSet()
val setC = setA intersect setB
println(setC) // prints [c]

If there are more sets, we can chain the operations by iterating the list of sets:

val setA = "abc".toSet()
val setB = "cde".toSet()
val setC = "cfg".toSet()
val setD = "czy".toSet()
val list = listOf(setA, setB, setC, setD)

var result = setA
for (set in list) {
    result = result intersect set
}
println(result) // prints [c]

The loop above is effectively the same as using the reduce function with the intersect operation as follows:

val setA = "abc".toSet()
val setB = "cde".toSet()
val setC = "cfg".toSet()
val setD = "czy".toSet()
val list = listOf(setA, setB, setC, setD)

val result = list.reduce { a, b -> a intersect b }

println(result) // prints [c]

All we need to do now is call the count() function on the result to get the number of answers that were the same in the specific group. The code looks like this:

val data = groups.map { 
   it.split(newLine).map(String::toSet)
}

var total = 0
for (listOfSets in data) {
   total += listOfSets.reduce { a, b -> a intersect b}.count()
}

We can see a familiar pattern for summing up the total. This is definitely a hint that we can use the sumOf function to calculate the same:

val total = data.sumOf { it ->
   it.reduce { a, b -> a intersect b }.count()
}

Now we can chain the operations to put all the calculations in one pipeline:

val total = groups.map {
   it.split(newLine).map(String::toSet)
}.sumOf { 
   it.reduce { a, b -> a intersect b }.count()
}

This code looks concise, but it is not perfectly readable yet. You can see that we are using the implicit variable name, 'it', in both code blocks. First, in the part where we transform the grouped answers into sets. Then, when working with the sets to find the intersections. The variable type in the different blocks is also different.

To make this more readable, we recommend giving an explicit name to the lambda argument, instead of 'it', if the code blocks are chained like in our example. 

val total = groups.map { group ->
   group.split(newLine).map(String::toSet)
}.sumOf { groupAnswers ->
   groupAnswers.reduce { a, b -> a intersect b }.count()
}

At this point, we can make an interesting observation: the first part of our task can be solved exactly like the second part, but using union instead of intersect. So here’s a crazy idea, what if we wanted to support the different operations within the same code. For this, we can extract the logic into a function and use the operation as a parameter for the function as follows:

private fun transformAndReduce(groups: List<String>, operation: (Set<Char>, Set<Char>) -> Set<Char>) =
   groups.map { lines ->
       lines.split(newLine).map(String::toSet)
   }.sumOf { characters ->
       characters.reduce { a, b -> operation(a , b) }.count()
   }

val firstAnswer = transformAndReduce(groups, Set<Char>::union)
val secondAnswer = transformAndReduce(groups, Set<Char>::intersect)

For this specific task, this might be overthinking things a bit. However, it demonstrates the use of functional types as parameters quite well.

Summary

Today’s puzzle did not require a complex solution. The final solution makes use of a few standard library functions: map, reduce, sumOf, intersect, and union. Using these functions we are able to elegantly compose a data manipulation pipeline to solve the puzzle. 

The scenario is quite common in real-life applications. Hopefully, the demo code will provide you with a good reference that you can use for your everyday tasks.

You can find the final solution in the GitHub repository here: https://github.com/kotlin-hands-on/advent-of-code-2020/blob/master/src/day06/day6.kt