Advent of Code 2020 in Kotlin: Day 01

December is here, and with it came Advent of Code. Advent of Code is coding challenge that starts on December 1st and ends on December 25th. Every day a new puzzle is released. To win points (stars) you need to complete the puzzles.

Although I’ve followed the event in its past incarnations, I never took part in it. I decided to give it a go this year and since Kotlin has picked my interest recently, I chose to solve the challenges using the language. I’ll do this as an exercise, to learn more about the language and experiment.

Every day, I’ll make a new post with my solution for the day’s challenge. If you don’t want spoilers, please try to solve it on your own first!

The problem

The question is fairly straightforward. We are given a list of numbers (transaction values) as input and need to find numbers that match a certain criteria.

Part 1

In the first part of the challenge, we need to find two numbers that sum up to 2020. When we find them, we should return the result of multiplying those two numbers. That’ll be the answer to the problem.

Although the question masks it with a story, this is just a 2sum problem: We want to find two numbers that sum up to a given target (in this case, 2020).

Here’s how I solved it:

import java.io.File

fun solve(numbers: Array<Int>) : Int? {
    val complementMap = mutableMapOf<Int, Int>()

    for (index in numbers.indices) {
    val number: Int = numbers[index]

    if (complementMap.containsKey(number)) {
        return number * complementMap.get(number)!!
    }

    val complement: Int = 2020 - number
    complementMap[complement] = number
  }

    return null
}

fun main() {
    val numbers = mutableListOf<Int>()

    File("input.txt").forEachLine { numbers.add(it.toInt()) }

    print(solve(numbers.toTypedArray()))
}

How it works

The idea behind this solution is that we can simply iterate over the array of numbers and store their complements in a map. For each number of the array, we check if it is present in the map. If it is, that means we have seen its complement before and we can return the answer. If we haven’t seen the number yet, we put it in the map keyed by its complement.

With this, we get O(n) runtime complexity and O(n) space complexity.

Part 2

The second part is similar. We need to find three numbers that sum up to 2020 and return the result of multiplying them. This boils down to a 3SUMproblem.

import java.io.File

fun solve(numbers: Array<Int>) : Int? {
    numbers.sort()
    val count = numbers.size

    for (i in 0..count) {
        var left = i + 1
        var right = count - 1

    while (left < right) {
       val sum = numbers[left] + numbers[right] + numbers[i]

        if (sum == 2020) {
              return numbers[left] * numbers[right] * numbers[i]
        } else if (sum > 2020) {
              right--
        } else {
              left++
            }
        }
    }
    return null
}

How it works

This solution is a bit more involved. We start by sorting the array of numbers. For each number in the sorted array, we try to find two so that the three of them sum up to 2020.

Since we know the array is sorted, we can be smart when we search for those two numbers. We use two pointers: One after the number we “fixed” and the other at the end of the array. If the sum of the three numbers is larger than 2020, we move the right pointer to the left: We know there that then the sum will be either the same or less than current one. On the other hand, if the sum is less than 2020, we move the left pointer to the right: The new sum then will either be the same or greater than the current one.

When we find three elements that sum up to 2020, we just return the result.

This gives us O(n^2) runtime complexity and O(1) space complexity.

That’s all

It was quite fun to give this problem a go with Kotlin. The language is quite nice to write in and fairly readable, although I do have my beefs with it. Once thing i don’t get is why the for (i in 0..count) doesn’t require the keyword val/var since we are effectively declaring the variable i there. Seems like an inconsistency to me.

On the next post, I’ll go over how I solved day 02’s problem!