AoC Day 25: Four-Dimensional Adventure

twitter logo github logo ・1 min read

Advent of Code (26 Part Series)

1) AoC Day 1: Chronal Calibration 2) AoC Day 2: Inventory Management System 3 ... 24 3) AoC Day 3: No Matter How You Slice It 4) AoC Day 4: Repose Record 5) AoC Day 5: Alchemical Reduction 6) AoC Day 6: Chronal Coordinates 7) AoC Day 7: The Sum of Its Parts 8) AoC Day 8: Memory Maneuver (Placeholder) 9) AoC Day 9: Marble Mania 10) AoC Day 10: The Stars Align 11) AoC Day 11: Chronal Charge 12) AoC Day 12: Subterranean Sustainability 13) AoC Day 13: Mine Cart Madness 14) AoC Day 14: Chocolate Charts 15) AoC Day 15: Beverage Bandits 16) AoC Day 16: Chronal Classification 17) AoC Day 17: Reservoir Research 18) AoC Day 18: Settlers of The North Pole 19) AoC Day 19: Go With the Flow 20) AoC Day 20: A Regular Map 21) AoC Day 21: Chronal Conversion 22) AoC Day 22: Mode Maze 23) AoC Day 23: Experimental Emergency Teleportation 24) AoC Day 24: Immune System Simulator 20XX 25) AoC Day 25: Four-Dimensional Adventure 26) Advent of Code Wrap-Up

Merry Christmas everybody! We made it! One last puzzle to save Christmas. On Day 25, the reindeer is still sick despite our best efforts. In order to save him, we need to calibrate our device to constellations of 4-D points in space-time. But first, we need to figure out which points are in which constellations.

Good luck!

twitter logo DISCUSS (1)
markdown guide
 

Last year's Christmas Day was a couple of bonus stars with no actual puzzle to solve so I was expecting the same. But no there's real work to do today, although thankfully part 1 is pretty straightforward.

Parsing

data class Point(val w: Int, val x: Int, val y: Int, val z: Int)

fun parse(input: String): List<Point> {
    val integer = or(
        INTEGER.map(String::toInt),
        isChar('-').next(INTEGER).map { s -> -s.toInt() }
    )

    val point = sequence(
        integer.followedBy(isChar(',')),
        integer.followedBy(isChar(',')),
        integer.followedBy(isChar(',')),
        integer,
        ::Point
    )

    return point.sepBy(WHITESPACES).parse(input.trim())
}

Part 1

Manhattan distance. We've done this before:

typealias Manhattan = Int

fun Point.distance(p: Point): Manhattan =
    Math.abs(w - p.w) + Math.abs(x - p.x) + Math.abs(y - p.y) + Math.abs(z - p.z)

You could model the constellations as a set of set of points but type inference gets a bit hairy in Kotlin so we'll make a wrapper. The inline classes feature coming in the future will make this possible with no runtime overhead. I'll add a few syntactic conveniences such as adding points to constellations and merging them.

data class Constellation(val points: Set<Point>) {
    constructor(p: Point): this(setOf(p))
}

fun Constellation.shouldContain(point: Point): Boolean = 
    points.any { p -> p.distance(point) <= 3 }

operator fun Constellation.plus(p: Point): Constellation =
    Constellation(points + p)

operator fun Constellation.plus(c: Constellation): Constellation = 
    Constellation(points + c.points)

fun Collection<Constellation>.merge(p: Point): Constellation =
    fold(Constellation(p), Constellation::plus)

With all that done, solving part 1 is a fold over the input points. For each point, partition the existing constellations into the ones it should join and the ones it should not. Merge the ones that the point should join and leave the others alone.

fun part1(input: Collection<Point>): Int {
    val constellations = input.fold(setOf<Constellation>()) { cs, p ->
        val (join, dontJoin) = cs.partition { c -> c.shouldContain(p) }
        (dontJoin + join.merge(p)).toSet()
    }
    return constellations.size
}

Part 2

I don't have enough stars to unlock part 2. Will try to get there before the end of the year!

Classic DEV Post from May 22

Coding Best Practices, Chapter One: Functions.

Code best practices, how to write readable functions.

Ryan Palo profile image
Ryan is a mechanical engineer in the East SF Bay Area with a focus on dynamic languages like Ruby & Python. Goal: learn a ton and become a physics, math, and programming teacher. Message me on DEV.TO

Sore eyes?

dev.to now has dark mode.

Go to the "misc" section of your settings and select night theme ❤️