Idiomatic Kotlin: Solving Advent of Code Puzzles, Working With Lists
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
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:
But this solution is wrong! Using this approach,
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:
This way, if
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:
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:
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
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
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:
Note how we use safe access together with
let to transform the index if one was found. Otherwise
null is returned.
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:
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:
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
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:
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:
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:
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:
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
toIndex argument defines an exclusive, not inclusive, upper bound):
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:
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-
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
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:
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
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
fromIndex, and the sum of elements from
toIndex, the sum of the elements from
toIndex can be found by subtracting the former from the latter:
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) 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.
foldreturns only the final result, while
(runningFold)returns the results for all the intermediate steps.
The following animation illustrates the
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:
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:
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
scan functions, which exemplify a more idiomatic Kotlin style.