Advent of Code 2019 - Day 19, in Kotlin • Todd Ginsberg

I’m back from traveling, so let’s resume Advent of Code! I’ll solve and write up the 15th through the 18th as I have time to catch up (probably over the weekend). Meanwhile, let’s play around with this fancy new Tractor Beam we have!

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

Problem Input

This is another IntCode problem, so we’ll parse it like we do all IntCode input:

private val program: MutableMap<Long, Long> = input
    .split(",")
    .withIndex()
    .associateTo(mutableMapOf()) { it.index.toLong() to it.value.toLong() }

Yes, it’s probably time to encapsulate that into a function somewhere.

⭐ Day 19, Part 1

The puzzle text can be found here.

If we look at the diagram, it seems clear that our tractor beam forms a cone shape. That means there’s probably some way to optimize our search so that we only scan a little bit more than the area that the tractor beam takes up. However, a 50 x 50 area isn’t that much, so we’re just going to brute force it.

Let’s write a function to create an instance of our IntCodeComputerMk2 and ask it to calculate whether the tractor beam works for a given x/y point. I did some experimenting and unfortunately we can’t keep a single computer around and feed it new x/y values over and over. We’ll have to recreate the computer every time (because our IntCodeComputerMk2 doesn’t support resetting itself back to it’s initialized state).

private fun engageTractorBeam(x: Long, y: Long): Boolean = runBlocking {
    IntCodeComputerMk2(program.copyOf()).run {
        input.send(x)
        input.send(y)
        runProgram()
        output.receive() == 1L
    }
}

Since our computer takes two inputs and produces a single output, we don’t need to run it in the background like we have before. We can just run it until it halts and get the single output.

We also need a convenient way to copy our program input (a MutableMap), so let’s define an extension function for that:

// In Extensions.kt

fun <T, R> MutableMap<T, R>.copyOf(): MutableMap<T, R> =
    mutableMapOf<T, R>().also { it.putAll(this) }

And finally, to solve Part 1, we’ll run our program for every x and y pair between 0 and 49 inclusive:

fun solvePart1(): Int =
    (0..49L).sumBy { x ->
        (0..49L).count { y ->
            engageTractorBeam(x, y)
        }
    }

This might look like another use for flatMap and map, but since our engageTractorBeam returns a Boolean, we can count the number of trues it returns. And we can sum those up using sumBy instead of flatMap. This give us our answer for Part 1!

⭐ Day 19, Part 2

The puzzle text can be found here.

Let’s stop and think about this. We know that our tractor beam makes a cone shape. If we draw out the cone we get in Part 1, we can see there are no weird gaps in the middle of it. That means we can take a shortcut when finding the 100 x 100 area.

Let’s pretend we’re after a 3 x 3 area to make things simple. I’ll diagram this using the same method in the problem description:

#................
.#...............
..##.............
...###...........
....###..........
.....#ooB........
......ooo##......
......Aoo###.....
.......#######...
........########.

I’ve marked two interesting points in our grid as A and B. The area of our 3 x 3 square is marked with o. If we find A and B, we can assume that all of the other points between them are valid. If both A and B are in the beam, we can assume that anything “north” of A is in the beam (up to the y value of B). Similarly, we can assume anything “south” of B is in the beam down to the y of A. All this can be assumed because our beam is cone shaped.

So our strategy is going to be to find some point A in the beam and then calculate whether some point B is as well. Doing this should give us our answer!

fun solvePart2(): Long {
    var x = 0L
    var y = 0L
    while (true) {
        while (!engageTractorBeam(x, y + 99)) {
            x++
        }
        if (engageTractorBeam(x + 99, y)) {
            return (x * 10_000) + (y)
        }
        y++
    }
}

First we start off assuming that x and y are zero. While our tractor beam hasn’t found anything at x and y+99, we want to increase x. This moves our A point over to the east until we run into the beam. Once that happens, we test to see if B is in the beam by adding 99 to x. If it’s a match, we know we’ve found our square thanks to the explanation above. Otherwise we move our search down the grid by increasing y by 1. If we keep this up, we’ll have our answer!

Star earned!

⭐ Day 19, Part 1

⭐ Day 19, Part 2

Further Reading