Advent of Code 2020 - Day 14, in Kotlin - Docking Data • Todd Ginsberg

Today we’re going to write some imperative, rather than functional code in order to solve both parts of the puzzle.

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

Problem Input

Today we will read our input in as a List<String> and parse it in each part’s solution. While we are here, let’s define a companion object and set up what our DEFAULT_MASK is. I don’t want to have to make our mask variables (see below) nullable, so we need a sensible default.


class Day14(private val input: List<String>) {

    private val memory: MutableMap<Long, Long> = mutableMapOf()

    companion object {
        const val DEFAULT_MASK = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
    }
}

We will also define a MutableMap for our memory.

⭐ Day 14, Part 1

The puzzle text can be found here.

Since we’ll have to convert a String version of a Long into a binary representation as another String a couple of times, let’s write an extension function for that:

// In Day14

private fun String.toBinary(): String =
    this.toLong().toString(2).padStart(36, '0')

This extension takes advantage of the toString() on Long, which allows us to specify a radix. It also uses padStart to pad out our binary string to 36 digits.

The next function we’ll need is something to mask one String with another.

// In Day14

private infix fun String.maskedWith(mask: String): Long =
    this.toBinary().zip(mask).map { (valueChar, maskChar) ->
        maskChar.takeUnless { it == 'X' } ?: valueChar
    }.joinToString("").toLong(2)

This is an infix function so we can make the calling syntax look like an operator: someValue maskedWith mask, for example. We convert the subject of the call to binary, and zip each Char with each Char in the mask. This will give us a List<Pair<Char,Char>>. We convert (via map) each of those pairs into a single Char, but comparing what the mask says to do. We use takeUnless to only use the mask it is not “X”, and if that is the case we will use the original character. We join the resulting List<Char> into a String and convert it back to a Long, telling it that we’re in radix 2.

Now we can solve part 1:

// In Day14

fun solvePart1(): Long {
    var mask = DEFAULT_MASK
    input.forEach { instruction ->
        if (instruction.startsWith("mask")) {
            mask = instruction.substringAfter("= ")
        } else {
            val address = instruction.substringAfter("[").substringBefore("]").toLong()
            val value = instruction.substringAfter("= ")
            memory[address] = value maskedWith mask
        }
    }

    return memory.values.sum()
}

This is a lot more imperative than I usually like to write my code, but I feel that this is easier to explain. First, we create our mask as a var, because it will change every few rows. Then we start looping through each row of input. We parse the instruction and if it is a mask, we parse that out and set it. If the instruction is a memory operation, we’ll parse out the address and the value. We use our infix function maskedWith to create the properly masked value and set that in our memory. The last thing we need to do is sum up all of the values in memory and return it for the answer to part 1.

Star earned! Onward!

⭐ Day 14, Part 2

The puzzle text can be found here.

The big change with Part 2 is how we mask our addresses. Let’s tackle that first…

// In Day14

private fun String.generateAddressMasks(mask: String): List<Long> {
    val addresses = mutableListOf(this.toBinary().toCharArray())
    mask.forEachIndexed { idx, bit ->
        when (bit) {
            '1' -> addresses.forEach { it[idx] = '1' }
            'X' -> {
                addresses.forEach { it[idx] = '1' }
                addresses.addAll(
                    addresses.map {
                        it.copyOf().apply {
                            this[idx] = '0'
                        }
                    }
                )
            }
        }
    }
    return addresses.map { it.joinToString("").toLong(2) }
}

I really wanted to write this as a recursive function, but since today’s theme is apparently “Todd Writes Imperative Code”, I figured why deviate from that? Also, I think the recursive version of that would be harder to explain here, and I want to save a potential lengthy explanation of a recursive function for another day.

Anyway. This function will seed a List<CharArray> with the address we stat off with. Don’t worry that it isn’t correct yet, we’ll fix that as we go through it. We set up a loop over all of the characters in mask. If it is a 1, we go through every address we know about and set the value to 1. Otherwise, if it is an X, we have to do some work. When the mask specifies X for a given position, we need to go set that position in every address we have to 0, and then get a copyOf that address, and set that position to 1. This is how our original address eventually becomes correct.

Now we have this, we can solve Part 2, which looks a lot like Part 1.

// In Day14

fun solvePart2(): Long {
    var mask = DEFAULT_MASK
    input.forEach { instruction ->
        if (instruction.startsWith("mask")) {
            mask = instruction.substringAfter("= ")
        } else {
            val unmaskedAddress = instruction.substringAfter("[").substringBefore("]")
            val value = instruction.substringAfter("= ").toLong()
            unmaskedAddress.generateAddressMasks(mask).forEach { address ->
                memory[address] = value
            }

        }
    }

    return memory.values.sum()
}

Sure, we could have passed a function for the “what do I do with this memory address” part, like we did the other day, but I feel like this is fine for such a small problem. Also, I’m super busy today. :)

Star earned!

See you tomorrow!

⭐ Day 14, Part 1

⭐ Day 14, Part 2

Further Reading