Advent of Code 2022 - Day 4, in Kotlin - Camp Cleanup • Todd Ginsberg

Today’s puzzle reminds me of an interview question my workplace used to ask candidates to solve (and maybe still does? oops). It had to do with identifying ranges and when I first solved this puzzle during my interview in 2005 I wrote so much code to solve this that I thought I’d bombed the interview [Note: It turns out that most interviews are about the journey and not the destination. Or should be.]

So today’s puzzle was a nice blast from the past for me. :)

I had fun discussing this puzzle with JetBrains Developer Advocate Sebastian Aigner during a live stream event on December 4, 2022. Check it out!

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

Puzzle Input

Our test harness will deliver the input file as a List<String>, and since we don’t use it outside of the initial parsing we won’t define input as a property on Day04 as we’ve done in the past. Instead we’ll just use it as an argument to the class constructor.

Before we start with parsing let’s discuss how we want to represent our data. We have a few choices here and the major contenders appear to be -

Use Kotlin’s existing IntRange, which nicely encapsulates a contiguous range of Int,
Use Pair<Int,Int> to represent the start and end of a range (since ultimately, that’s all we care about)
Define our own class.

I strongly considered going with Pair<Int,Int> but then realized I’d have a List<Pair<Pair<Int,Int>,Pair<Int,Int>>> on my hands eventually. Of course, we could typealias our way out of that ugly mess, but we would end up picking a name that’s enough like IntRange to just go ahead and use IntRange.

The main point here is that you can solve this puzzle the same way I have but with different Int containers. Take your pick!

As usual, we’ll start at the end of the parsing adventure and work our way backwards. This way we have a feel for how our functions are being used.

First, let’s define an extension function on String called asIntRange() to turn a String in the format of X-Y into an IntRange(X,Y). We can do this by taking advantage of two wonderful functions from the Kotlin Standard Library - substringBefore and subStringAfter. Yes, we could split here and pick the values out of the resulting list, but I wanted to show you substringBefore and substringAfter because I think we’ll probably see them again before Advent of Code 2022 is over. Once we have the parts, we turn them into a range by converting the String to an Int via toInt(), and turning those Ints into an IntRange via the .. operator.

// In Day04

private fun String.asIntRange(): IntRange =
    substringBefore("-").toInt() .. substringAfter("-").toInt()

At this point we’re able to create a single IntRange, when we really need a Pair<IntRange,IntRange> to represent our input (which is in the format a-b,c-d). To do this, we’ll define an extension function on String called asRanges() which takes our input row, splits it up, and calls our String.asIntRange() function on each side. We’ll use substringBefore and substringAfter here as well, but with a comma as the delimiter and not a dash as above.

// In Day04

private fun String.asRanges(): Pair<IntRange,IntRange> =
    substringBefore(",").asIntRange() to substringAfter(",").asIntRange()

Note: These two functions may become generally useful later on during Advent of Code. If we end up needing to use them more than once, I’ll pull them out into an extensions file. But until then they can live in Day04. It is entirely up to you if you want to do this refactoring now or possibly wait until later.

Once we have those functions written, we can map our input to List<Pair<IntRange,IntRange>> and store it in ranges.

class Day04(input: List<String>) {

    private val ranges: List<Pair<IntRange,IntRange>> = input.map { it.asRanges() }
}

List<Pair<IntRange,IntRange>> is still an ugly type signature, and you can typealias it to something else if you want. I’ll leave it as-is for clarity so we know exactly what types we’re working with. Heck, Kotlin is smart enough to understand the types - if you just want to leave the type off of ranges entirely, go ahead. Again, I’ll leave it on for clarity.

⭐ Day 4, Part 1

The puzzle text can be found here.

The main point of Part One is to find out if a pair of ranges overlap each other fully. Meaning does range A fully overlap (or enclose) range B, or does range B fully overlap (or enclose) range A. To answer this question given two ranges, we’ll define an extension function on IntRange called fullyOverlaps. I was a bit disappointed to discover that IntRange doesn’t already have this function, but we can write it easily enough. We’ll define it as an infix function so we have the option of writing a fullyOverlaps b instead of a.fullyOverlaps(b) (use whichever style you prefer).

// In Day04

private infix fun IntRange.fullyOverlaps(other: IntRange): Boolean =
    first <= other.first && last >= other.last

In order to see if one range fully overlaps another we can compare the ends. If the first element of the range is equal to or less than the other range’s last element, and the last element of the range is equal to or grater than the other range’s first element then they overlap.

All that’s left to do is count up how many of our ranges overlap each other.

// In Day04

fun solvePart1(): Int =
    ranges.count { it.first fullyOverlaps it.second || it.second fullyOverlaps it.first  }

Because fullyOverlaps only measures the overlap one way, we need to see if either combination overlaps (A overlaps B or B overlaps A).

Star earned! Onward!

⭐ Day 4, Part 2

The puzzle text can be found here.

This is the part that’s like the old interview questions I mentioned in the intro to this post. Let’s define another extension function on IntRange called overlaps which will determine if two IntRanges overlap at all. To test if two ranges overlap, we can reduce it to two simple comparisons: Does the first element of this IntRange come before (or equal) the last element of the other IntRange AND does the first element of the other IntRange come before (or equal) the last element of this IntRange. This accounts for all the possible ways that two IntRanges could possibly overlap one another.

// Day04

private infix fun IntRange.overlaps(other: IntRange): Boolean =
    first <= other.last && other.first <= last

Unlike fullyOverlaps, if A overlaps B, then B overlaps A and we don’t need to execute this function twice. We can use count again to figure out how many of the ranges overlap at all.

// In Day04

fun solvePart2(): Int =
    ranges.count { it.first overlaps it.second }

Note: As with the parsing code, IntRange.fullyOverlaps() and IntRange.overlaps() may be good candidates to put in a generic extensions file rather than remain private functions in Day04. If we end up needing them again, I’ll refactor. But if you feel like you want to do that now, go ahead.

Star earned! See you tomorrow!

⭐ Day 4, Part 1

⭐ Day 4, Part 2

Further Reading