Advent of Code 2023 - Day 24, in Kotlin - Never Tell Me The Odds • Todd Ginsberg

I think of all the puzzles in Advent of Code 2023, part 2 of this was the most difficult for me. I’m not great at math, and this just confused the heck out of me. I got a lot of help from Google and Reddit to solve it.

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

Puzzle Input

Our input today represents the position and velocity of a Hailstone, so we’ll model that as a data class. At this point in the implementation, Hailstone doesn’t do much. We have an of function like usual to turn a String into a Hailstone, and we have a slope, which is a Double. Take note that if the x velocity is 0, we can’t calculate the slope so we set it to NaN rather than null (you can change this to Double? if you want, so long as you account for it when we use the slope).

// In Day24

private data class Hailstone(val position: Point3D, val velocity: Point3D) {
    private val slope = if (velocity.x == 0L) Double.NaN else velocity.y / velocity.x.toDouble()

    companion object {
	    fun of(input: String): Hailstone = input.split("@").let { (left, right) ->
	        Hailstone(
	            Point3D.of(left),
	            Point3D.of(right)
	        )
	    }
	}
}

We made it all the way to Day 24 without needing a 3D point reference! Since this is the only day we’ll actually need it, and it really only exists to hold three points of data, we’ll define it as a private data class within the Day24 class. Note that x, y, and z are defined as Long here, rather than Int due to the size of our input. Also, there’s an of function to turn a String into a Point3D.

// In Day24

private data class Point3D(val x: Long, val y: Long, val z: Long) {
    companion object {
        fun of(input: String): Point3D =
            input.split(",").map { it.trim().toLong() }.let {
                Point3D(it[0], it[1], it[2])
            }
    }
}

And now we can parse our input and store it in a List<Hailstone> called hailstones. We won’t need the input after this, so we don’t need to define it as a property.

class Day24(input: List<String>) {

    private val hailstones = input.map { Hailstone.of(it) }

}

⭐ Day 24, Part 1

The puzzle text can be found here.

To solve part 1 we need to determine if and when one hailstone intersects with another. Let’s encode this data in a data class called Intersection. It has x, y, and time variables, all of which are Double. If there is an interaction between two hailstones, we will represent it with Intersection. Otherwise, we will represent it with null.

// In Day24

private data class Intersection(val x: Double, val y: Double, val time: Double)

Now that we have a way to describe a possible Intersection, we need to implement the math, which we’ll do as a function called intersectionWith on the Hailstone class. It takes another Hailstone class as an argument and returns an Intersection?. This will be non-null if the two hailstones intersect and null otherwise.

// In Hailstone

fun intersectionWith(other: Hailstone): Intersection? {
    if (slope.isNaN() || other.slope.isNaN() || slope == other.slope) return null

    val c = position.y - slope * position.x
    val otherC = other.position.y - other.slope * other.position.x

    val x = (otherC - c) / (slope - other.slope)
    val t1 = (x - position.x) / velocity.x
    val t2 = (x - other.position.x) / other.velocity.x

    if (t1 < 0 || t2 < 0) return null

    val y = slope * (x - position.x) + position.y
    return Intersection(x, y, t1)
}

The first check is to make sure that both hailstones have a slope and they don’t equal each other. If any of these is true, these hailstones will never meet up. The rest of this math I had a lot of help with from Google, but basically it figures out the x and y coordinates of when the two lines meet up, and when (t1 and t2). If the time is in the past, we don’t wan to return an Intersection, we return null. Otherwise we can say that yes, these two hailstones do intersect in the future at a specific point.

And to solve part 1, we ram all of the hailstones into each other and figure out which ones happen in the given range for both x and y. We’ll reuse our cartesianPairs() filter out the self references (we could skip this, the first check in intersectionWith would return null) and take any intersections that are not null.

// In Day24

fun solvePart1(range: ClosedFloatingPointRange<Double>): Int =
    hailstones
        .cartesianPairs()
        .filter { it.first != it.second }
        .mapNotNull { it.first.intersectionWith(it.second) }
        .count { (x, y, _) -> x in range && y in range }

Counting the number of resulting Intersection objects whose x and y coordinates happen in the range gives us our answer.

Star earned! Onward!

⭐ Day 24, Part 2

The puzzle text can be found here.

I won’t pretend that I came up with this solution. This part of this puzzle was the hardest one for me all year. I had a lot of help from Google and Reddit. And that’s fine.

Basically what we’re going to do is pretend that the rock we are throwing is still and the hailstones are all moving at some new velocity relative to the now still “thrown” rock. In theory, they should all intersect with some given point, which we can calculate with the code we wrote for part 1.

First up, we need a way to alter the Hailstone given a change (delta) to the x and y velocity.

// In Hailstone

fun withVelocityDelta(vx: Long, vy: Long): Hailstone =
    copy(
        velocity = Point3D(velocity.x + vx, velocity.y + vy, velocity.z)
    )

And we also need a function to predict the value of z given some amount of time the hailstone moves for, and the deltaZ (change in z).

// In Hailstone

fun predictZ(time: Double, deltaVZ: Long): Double =
    (position.z + time * (velocity.z + deltaVZ))

The strategy here is to run through every value for x and y (within some small range) to use as a velocity delta, and find four random hailstones that collide given those deltas. This gives us the x and y points that the rock must be thrown by. And from that, we can iterate through the same range to apply a delta to z, and find the point where all of those same hailstones meet up.

Since I’m picking random hailstones to start with, this may not actually work, so we run this over and over until it does work.

// In Day24

fun solvePart2(): Long {
    val range = -500L..500L
    while (true) {
        val hail = hailstones.shuffled().take(4)
        range.forEach { deltaX ->
            range.forEach { deltaY ->
                val hail0 = hail[0].withVelocityDelta(deltaX, deltaY)
                val intercepts = hail.drop(1).mapNotNull {
                    it.withVelocityDelta(deltaX, deltaY).intersectionWith(hail0)
                }
                if (intercepts.size == 3 &&
                    intercepts.all { it.x == intercepts.first().x } &&
                    intercepts.all { it.y == intercepts.first().y }
                ) {
                    range.forEach { deltaZ ->
                        val z1 = hail[1].predictZ(intercepts[0].time, deltaZ)
                        val z2 = hail[2].predictZ(intercepts[1].time, deltaZ)
                        val z3 = hail[3].predictZ(intercepts[2].time, deltaZ)
                        if (z1 == z2 && z2 == z3) {
                            return (intercepts.first().x + intercepts.first().y + z1).toLong()
                        }

                    }
                }
            }
        }
    }
}

Like I said, I had a lot of help on this one. I never could have figured it out on my own.

Star earned (kinda)! See you tomorrow!

⭐ Day 24, Part 1

⭐ Day 24, Part 2

Further Reading