 ## Solving Advent of Code Puzzles in Idiomatic Kotlin

What’s the best way to learn a language other than writing some code with it? Solving fun and short tasks like the ones from Advent of Code might be a great opportunity to practice your language skills, and you can learn a lot if you compare your solutions with how others have solved the same problem.

Lots of developers from around the world, including some from the Kotlin team, take part in the Advent of Code challenges created by Eric Wastl. Advent of Code is a series of tasks published every December, which you solve and compete with others. Many would agree that it’s the best advent calendar to celebrate Christmas and New Year!

To help the community learn idiomatic Kotlin, and motivate more developers to solve Advent of Code tasks in Kotlin in the future, we decided to prepare solutions for the tasks from Advent of Code 2020. It doesn’t matter if you solved it back in December, you’re ready to solve it now, or you just want to check the solutions – we hope you’ll find something useful in these materials. Of course, it works best if you try to solve the same task first yourself!

Below is the solution and video for the first task. If you find this format useful and want us to cover more tasks in a similar fashion, please share in the comments!

## Day 1. Report Repair

We’re fixing an expense report! Find the full task description at https://adventofcode.com/2020/day/1*.

You need to find the two (and in the second part, three) entries from the list of numbers that sum to 2020 and then multiply those two (or three) numbers together.

### How to solve the task

Register at https://adventofcode.com/, open the task at https://adventofcode.com/2020/day/1, write your solution in Kotlin, and check the result on the site. You can either write Kotlin code online or using an IDE:

Finally, compare your solution with the solution below.

We marked the

src

folder as a source set to put the code directly there. We copied input files, like

src/day1/input.txt

, to the source folder for convenience. You can find the solutions in this project.

### Solution

Here’s the sample input:

```1721
979
366
299
675
1456
```

First, we need to read and parse the input. We can use the Kotlin

function for reading a list of lines from a given file:

```File("src/day1/input.txt").readLines()
```

The

returns a list of Strings, and we convert it to a list of numbers:

```import java.io.File
fun main() {
val numbers = File("src/day1/input.txt")
.map(String::toInt)

}
```

You put this code inside the

main

function, the entry point for your program. When you start typing, IntelliJ IDEA imports the

java.io.File

automatically.

Now we can simply iterate through the list, and then for each number repeat the iteration and check the sum:

```for (first in numbers) {
for (second in numbers) {
if (first + second == 2020) {
println(first * second)
return
}
}
}
```

You put this code inside

main

, so

return

returns from

main

when the required numbers are found.

In a similar way, you check the sum of three numbers:

```for (first in numbers) {
for (second in numbers) {
for (third in numbers) {
if (first + second + third == 2020) {
println(first * second * third)
return
}
}
}
}
```

You can run it and get the result for a given input. That’s it! The first task is really a simple one.

However, we iterate over the same list again and again for each of the elements. Having two nested loops for finding two numbers makes it N2 operations, where N is the number of elements. When we need to find three numbers, that’s three nested loops, and N3 operations. If the list of numbers is large, that’s not the most efficient way to solve this type of problem. Surely there is a better way, right?

There definitely is and the Kotlin standard library can help us express that concisely. As often happens, we can replace the long calculation with some kind of smart storage used to find the result.

### Solving the task for two numbers

First, let’s build a map for number “complements” – numbers that together with the given number sum up to 2020:

```val complements = numbers.associateBy { 2020 - it }
```

We use the Kotlin

associateBy

function to build the map. Its lambda argument returns a key in this map, by which the list element is getting stored. For the sample input it’ll be the following map:

```numbers: [1721, 979, 366, 299, 675, 1456]
complements map: {299=1721, 1041=979, 1654=366, 1721=299, 1345=675, 564=1456}```

After this procedure, you can clearly see the answer! The very first number

1721

from the list is present in the

complements

map as a key:

1721=299

, which means it’s the complement for the number

299

, and they sum to

2020

.

Having stored this information in a map, we can check if any number from the list has a complement in this map. The following code finds the first number with an existing complement:

```val pair = numbers.mapNotNull { number ->
val complement = complements[number]
if (complement != null) Pair(number, complement) else null
}.firstOrNull()
```

We transform each number into a pair consisting of the number and its complement (if the complement exists) and then find the first non-null result.

We use

mapNotNull

, which transforms each element in a list and filters out all the resulting

null

s. It’s shorthand for calling first

map

, and then

filterNotNull

on the result.

firstOrNull

returns the first element in the list or

null

if the list is empty. Kotlin standard library often uses the

OrNull

suffix to mark functions returning

null

on failure rather than throwing an exception (like

elementAtOrNull

,

singleOrNull

, or

maxOrNull

).

Starting with Kotlin 1.5.0, you can also replace the two consequent operations

mapNotNull

and

first(OrNull)

with one function call:

firstNotNullOf(OrNull)

.

After building the auxiliary structure, we managed to find the resulting two numbers in N operations, not in N2 as before!

We need a multiplication of these numbers, so here’s the last step:

```println(pair?.let { (a, b) -> a * b })
```

The

pair

variable contains a nullable

Pair

of two numbers and is

null

if the initial list contains no numbers that sum up to 2020. We use safe access

?.

together with the

let

function and destructuring in a lambda syntax to display the result in case

pair

is not

null

.

### Solving the task for three numbers

The next step is solving this problem for three numbers. Let’s reuse what we’ve done so far and extract the logic of finding a pair of numbers summing up to a given number into a separate function:

```fun List<Int>.findPairOfSum(sum: Int): Pair<Int, Int>? {
// Map: sum - x -> x
val complements = associateBy { sum - it }
return firstNotNullOfOrNull { number ->
val complement = complements[number]
if (complement != null) Pair(number, complement) else null
}
}
```

We also used the

firstNotNullOfOrNull

function.

Now, we use

findPairOfSum

to build a helper map that stores the complement pair of values for each number which together with this number sums up to 2020:

```// Map: x -> (y, z) where y + z = 2020 - x
val complementPairs: Map<Int, Pair<Int, Int>?> =
numbers.associateWith { numbers.findPairOfSum(2020 - it) }
```

For the same initial input, here’s the complement pairs map:

```numbers: [1721, 979, 366, 299, 675, 1456]
complement pairs: {1721=null, 979=(366, 675), 366=(979, 675), 299=null, 675=(979, 366), 1456=null}```

As before, you already can see the answer! It’s the number that corresponds to a non-null pair in a map.

However, we don’t really need to build the whole map — we only need to find the first number that corresponds to a non-null pair! Let’s find it using the already familiar

firstNotNullOfOrNull

function:

```fun List<Int>.findTripleOfSum(): Triple<Int, Int, Int>? =
firstNotNullOfOrNull { x ->
findPairOfSum(2020 - x)?.let { pair ->
Triple(x, pair.first, pair.second)
}
}
```

Note Kotlin’s concise syntax – the function can return an expression directly.

The final step is to find the multiplication if the resulting triple is non-null, similar to how we did it before:

```println(triple?.let { (x, y, z) -> x * y * z} )
```

That’s all!

In the next part, we’ll discuss how to solve the second task. Please let us know if you find this content useful and would like us to provide solutions for more tasks!

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