Advent of Code 2023 - Day 3, in Kotlin - Gear Ratios • Todd Ginsberg

I’m a big fan of this puzzle! I had a lot of fun with it and am happy with how my implementation turned out. Like yesterday, today’s solution has a lot of work in the input parsing phase.

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

Puzzle Input

The input to today’s puzzle can be handed to our Day03 solution class as a List<String> as a private value property.

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

The Annual Creation of Point2D

There comes a time during every Advent of Code when I create a Point2D class to represent x/y spacial coordinates, and this year is no different. Sure, I could do this once in a shared library and carry the implementation with me from year to year, but where’s the fun in that?

Here’s the start of the 2023 vintage Point2D class. We will implement it as a data class so we get hashcode, equals and toString for free. It has an x and y property representing its spacial coordinates, and a neighbors function to return all of the surrounding spots (including diagonals). We’ll probably expand this as the season goes on.

// In Point2D.kt

data class Point2D(val x: Int, val y: Int) {
    fun neighbors(): Set<Point2D> =
        setOf(
            Point2D(x - 1, y - 1),
            Point2D(x, y - 1),
            Point2D(x + 1, y - 1),
            Point2D(x - 1, y),
            Point2D(x + 1, y),
            Point2D(x - 1, y + 1),
            Point2D(x, y + 1),
            Point2D(x + 1, y + 1)
        )
}

Implementation Strategy

The first idea I had was that I could scan the input, find all of the symbols and then using some kind of traversal of neighbors, find the neighboring numbers. But then I realized that I’d have to maintain cursors somehow and keep track of a lot of data I didn’t otherwise really care about.

My next idea was why not store the location of each number, and all of its neighbors so we can detect if a symbol falls in that space. For example, pretend we have this map:

...
.1.
.&.
...

If we store the location of 1 and the location of &, we still have to do some math to figure out that they are next to each other. Instead of storing just 1, we store all of its neighbors. This means that the spot that & is taking up would be in that set. That gives us an easy way to determine if a number is next to a symbol, because we can test that a symbol location is in the set of number locations.

Note that we could do this the other way - add all of a symbol’s neighbors instead of number neighbors, but then part 2 gets really complicated, so let’s leave it like this.

The first thing we’ll need is a way to store a number and its location. I worked overtime on the name of this - NumberLocation. As is our custom, we’ll make this private to Day03 in case we want to reuse the name but not the implementation for a future puzzle.

// In Day03

private class NumberLocation {
    val number = mutableListOf<Char>()
    val locations = mutableSetOf<Point2D>()

    fun add(c: Char, location: Point2D) {
        number.add(c)
        locations.addAll(location.neighbors())
    }

    fun isNotEmpty() =
        number.isNotEmpty()

    fun isAdjacentToAny(points: Set<Point2D>): Boolean =
        locations.intersect(points).isNotEmpty()

    fun toInt(): Int =
        number.joinToString("").toInt()
}

Our new class has two properties - a number which is a MutableList<Char>, and locations, which is a Set<Point2D> to hold all of the adjacent spots.

With NumberLocation we can add a Char and its Point2D location to the set. When we do this, we’ll go grab all of the neighbors of the location. Yes, we may end up with locations that can’t be a symbol (because they’ll be a digit in the number) but we don’t really care in the end and I won’t spend time/energy/code optimizing that case away.

When we use a NumberLocation object, we’ll also need to see if it is empty or not. This is going to be important as we scan the input, so we’ll implement isNotEmpty (I guess if this were a library, we’d also implement this corresponding isEmpty, but it isn’t, so I didn’t). We also need to test that this location isAdjacentToAny set of points which we do by using the existing Set.intersect(Set) function that Kotlin provides. And of course, since we’re storing the “number” as a set of characters, we want to convert them to an Int, so we’ll define toInt for that.

Now for the parsing. I know this looks complicated at first, but let’s go through it.

// In Day03

private fun parseInput(
    input: List<String>,
    takeSymbol: (Char) -> Boolean = { it != '.' }
): Pair<Set<NumberLocation>, Set<Point2D>> {

    val numbers = mutableSetOf<NumberLocation>()
    val symbols = mutableSetOf<Point2D>()
    var workingNumber = NumberLocation()

    input
        .forEachIndexed { y, row ->
            row.forEachIndexed { x, c ->
                if (c.isDigit()) {
                    workingNumber.add(c, Point2D(x, y))
                } else {
                    if (workingNumber.isNotEmpty()) {
                        numbers.add(workingNumber)
                        workingNumber = NumberLocation()
                    }
                    if(takeSymbol(c)) {
                        symbols.add(Point2D(x, y))
                    }
                }
            }
            // Check at end of row that we don't miss a number.
            if (workingNumber.isNotEmpty()) {
                numbers.add(workingNumber)
                workingNumber = NumberLocation()
            }
        }
    return numbers to symbols
}

The first thing to notice that in addition to the input (a List<String>), our parseInput function also defines takeSymbol. If you’ve never seen this kind of thing before, it can look a little odd. The type signature (Char) -> Boolean tells Kotlin that we expect takeSymbol to be a function that takes a Char and returns a Boolean. We’ll use this to allow the caller to determine which kinds of symbols we care about, without having to know what all of the symbols actually are (if we did know all of the symbols, it would probably be appropriate to make takeSymbol be a Set<Char> or something like that). Additionally, the = { it != '.'} part tells Kotlin that this is the default implementation if we don’t get a definition from the caller, and that implementation is to take anything that isn’t a . (because it isn’t a symbol).

Our function returns a Pair so we can have multiple sets of data returned at once. The first part is a Set<NumberLocation> which tells us where all the numbers are, and the second is a Set<Point2D> which tells us where all the symbols are.

Because we’re about to go through the input to find the things we care about, let’s set up our working variables. First, a MutableSet for numbers, another MutableSet for symbols, and a single workingNumber which we can add to when we discover digits without having to worry about initializing it later. Note that this is defined as a var rather than a val because we’ll keep re-initializing it.

To find all of these things, we’ll use a pattern we’ve seen before and will probably use quite often if we get more grid-based inputs - a forEachIndexed to give us each row and y index value, and for each row, another forEachIndexed to give us each character c and x value. In the future we may see these as mapIndexed instead of forEachIndexed.

Inside our loop, if c is a digit, we want it. So we add it and a Point2D representing its location to the current workingNumber. Remember, this has the effect of taking the point and all of its neighbors as well.

If c is not a digit, we may have just finished creating a NumberLocation, so we have to check to see if that’s happened. We do this by testing if it is not empty (meaning: we’ve added digits to it), and if so, add the workingNumber to the set of numbers we’ve found, and create a new NumberLocation to replace the previous workingNumber.

At this point, what we’re looking at is either a symbol or a space (.), so we can use our takeSymbol function to see if we care about this value of c. If so, we add its location to the symbols set.

One important thing to do is to repeat our check to see if we’re done creating a NumberLocation at the end of every row, or we may end up making a NumberLocation with the end of one row and the beginning of another (or not adding it to the set at all if it is the very last part of the input). I’m not a huge fan of the repeated checks, but the alternatives to that (including an inner function) seemed not worth the added complexity.

Finally, we return our numbers and symbols as a Pair using the to operator.

⭐ Day 3, Part 1

The puzzle text can be found here.

Because we did so much work already, we don’t have much left to do to actually solve part 1.

// In Day03

fun solvePart1(): Int {
    val (numbers, symbols) = parseInput(input)
    return numbers
        .filter { number -> number.isAdjacentToAny(symbols) }
        .sumOf { it.toInt() }
}

We first call parseInput and use Kotlin’s support for destructuring to turn the Pair<Set<NumberLocation>, Set<Point2D>> int numbers (the Set<NumberLocation>) and symbols (the Set<Point2D>).

Next, we look at all the numbers and keep only the ones that are next to any symbol via isAdjacentToAny. As you can see from our implementation before, this compares all of the Point2D objects that are stored by NumberLocation to all of the symbol locations.

Once we have the numbers that we still care about (those next to symbols), we use sumOf to convert each number to an Int and sum the results.

Star earned! Onward!

⭐ Day 3, Part 2

The puzzle text can be found here.

Since we made good choices when implementing part1, part 2 doesn’t require much new code.

We’ll add an isAdjacentTo function on NumberLocation to check if a NumberLocation contains a single point (rather than force our callers to give us make a Set<Point2D> for a single point. When we call this, point will be a symbol. Remember, this works because when we add a location to NumberLocation, we’re really adding all of its neighbors.

// In NumberLocation

fun isAdjacentTo(point: Point2D): Boolean =
    point in locations

Now that we have that, we can solve part 2.

// In Day03

fun solvePart2(): Int {
    val (numbers, symbols) = parseInput(input) { it == '*' }
    return symbols
        .sumOf { symbol ->
            val neighbors = numbers.filter { it.isAdjacentTo(symbol) }
            if(neighbors.size == 2) {
                neighbors.first().toInt() * neighbors.last().toInt()
            } else 0
        }
}

The first thing to note is that we’re still using destructuring like we did in part 1 to get numbers and symbols, except this time we’ll pass a lambda function to parseInput which will allow us to only get gear symbols (*). Other than that, parseInput will do the same thing it did in part 1.

The major difference between part 1 and part 2 is that this time we’ll iterate over symbols instead of numbers. We are only interested in symbols that have exactly two neighbors. So, for each symbol, we look at every number and use our new isAdjacentTo function to check which ones are touching. Remember, each number is really the neighbors of the original digits, so the symbol should be in that set if they are touching.

If we do find a symbol that has exactly two numbers, we multiply their integer representations together, otherwise we return 0 to the call to sumOf.

Star earned! See you tomorrow!

⭐ Day 3, Part 1

⭐ Day 3, Part 2

Further Reading