Skip to Content

Advent of Code 2019 - Day 3, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2019, Day 3: 'Crossed Wires'

Posted on

Today’s problem shows us the importance of reading the description and ignoring the pictures. It might be tempting to make our data structures look like the pictures, but that approach could end up making our solution a lot more difficult.

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

 Problem Input

We receive two rows of input, each representing one wire. We’ll pass that to today’s solution class as a List<String> and parse it from there.

class Day03(input: List<String>)

Let’s turn those String objects into something more useful.

But first…

 We Need a 2D Point

In years past, I’ve been reluctant to refactor code into a common 2-dimensional point class because I always felt like I wouldn’t end up using it more than once. Sometimes I’ve used Pair<Int,Int> and some extension functions to represent a point, and sometimes I’ve had a proper class for it. Since I feel that this is a pretty safe abstraction (meaning: I do not believe we will only need this for the Day 3 puzzle), let’s go ahead and create a 2-dimensional point. We’ll call it Point2D, because predictability is good. At some point, we may end up need a 3-dimensional point, so we won’t call it Point for that reason.

// In Points.kt

data class Point2D(val x: Int, val y: Int) {

    fun up(): Point2D = copy(y = y + 1)

    fun down(): Point2D = copy(y = y - 1)

    fun left(): Point2D = copy(x = x - 1)

    fun right(): Point2D = copy(x = x + 1)
    
    fun distanceTo(other: Point2D): Int =
        abs(x - other.x) + abs(y - other.y)

    companion object {
        val ORIGIN = Point2D(0, 0)
    }
}

Since Point2D represents an x/y position, we’ll name our properties x and y. We’ll also provide a function in order to calculate the Manhattan Distance to another point. In principle, we could add a distanceTo(otherX: Int, otherY: Int) as well, but since we don’t have a need for that now, we’ll leave it out.

When working with grids of points it is common to start at the origin (0,0), so lets define a static instance called ORIGIN in the companion. That way we can avoid having to redefine it in several places, since it’s so common.

The last thing to notice in this class is we have functions to represent adjacent Point2D objects. These use the copy ability of Kotlin data classes.

We may have to come back and add more functionality to our point, but hopefully we’ll see it again after Day 3!

 Parsing Our Input

Now that we have a way to store positions, we can think about how we want to structure our data. The way I approached this was to parse each wire into a List<Point2D>. Each wire is represented as a list of points in the order they are encountered.

Let’s write some code to turn the program input into a List<Point2D>:

private fun parseWire(line: String): List<Point2D> {
    var current = Point2D.ORIGIN
    return line.split(",").flatMap {
        val direction = it.first()
        val steps = it.drop(1).toInt()
        (0 until steps).map {
            val next = when(direction) {
                'U' -> current.up()
                'D' -> current.down()
                'L' -> current.left()
                'R' -> current.right()
                else -> throw IllegalArgumentException("Invalid direction: $direction")
            }
            current = next
            next
        }
    }
}

Let’s go over that. Since our wire starts at the grid’s origin, we will consider the current position to be our predefined Point2D.ORIGIN. Next comes splitting the input by , and parsing each segment. Each segment itself has two parts: a direction and a number of steps. We’ll take the first character of each segment and set it aside as our direction. We’ll take the rest, turn it into an Int and call that steps. Once we have that, we can use a when expression to turn each step into a new Point2D.

It’s important to remember a few things here while paring our input. First, while we have to start with the origin, we can’t make it part of our output line or we’ll have to account for it when checking for where lines intersect. Since I don’t want to have to account for that later, we’ll just skip putting it in the List<Point2D> in the first place. The other thing to remember is the flatMap / map structure. Since we’re mapping over single things (a String representing a direction and number of steps) that ends up creating multiple things (a Point2D for each step), we have to be careful. If we map both of these, we’ll end up with a List<List<Point2D>>. What flatMap does is say “I realize you are going to return a collection from this map operation, remove the collection that surrounds them and treat them as individuals”.

We can now go back and parse our input into two separate wires:

class Day03(input: List<String>) {

    private val wire1: List<Point2D> = parseWire(input[0])
    private val wire2: List<Point2D> = parseWire(input[1])

}

⭐ Day 3, Part 1

The puzzle text can be found here.

Thanks to the fact that a) we parsed everything already and b) Kotlin has a function to do the hard work here, we’re nearly done.

The main thing we will do is create a Set<Point2D> of all the places that wire1 and wire2 intersect. This is done with a function in the Kotlin Standard Library called… wait for it… intersect:

private val intersections: Set<Point2D> = wire1.intersect(wire2)

The intersect function creates a Set of objects that are the same in both collections. Since Point2D is a data class, it has hashcode and equals defined for us, which aids in this purpose. We will declare our intersections set as a private val because we’ll end up using it again in Part 2.

In order to solve Part 1, we just need to find the Point2D in or list of intersections that is the closest to the ORIGIN. Again, we’ll make Kotlin do the hard work for us:

fun solvePart1(): Int =
    intersections.map { it.distanceTo(Point2D.ORIGIN) }.min()!!

(Yes, I know, I don’t like using the !! Hold My Beer Operator either, but we know there is a min value, so I’m going to let it happen).

Running this solves Part 1 and earns us a star! Our 5th star! We’re 10% of the way done with Advent of Code 2019!

⭐ Day 3, Part 2

The puzzle text can be found here.

Thankfully, solving part 2 doesn’t require much new code:

fun solvePart2(): Int =
    intersections.map { cross ->
        wire1.indexOf(cross) + wire2.indexOf(cross) + 2
    }.min()!!

We go through our Set of intersection points and for each one calculate how far that point is down each wire. We add 2 to the end because the indexOf function is 0-based (starts at zero). To account for that we have to add 1 to each distance calculation. Once we have all of the distances, we take the min value, and that’s our answer.

Running this solves Part 2 and earns us another star!

Further Reading

  1. Index of All Solutions - All posts and solutions for 2019, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 3
  4. Advent of Code - Come join in and do these challenges yourself!