Advent of Code 2023 - Day 08

It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Kotlin. I’ll post my solutions and code to GitHub as well. If you haven’t given AoC a try, I encourage you to do so along with me!

Day 8 - Haunted Wasteland

Find the problem description HERE.

The Input - Mapping The Network Fantastic

Today’s input offers a bit of a twist, with two distinct sections, but the lines of each part are pretty simple, so we won’t have any issues there. I considered trying to map the input into a tree-based structure with nodes that pointed to each other, but it seemed like it might be a bit of a pain to make sure all the nodes got added, there might be cycles, etc. So, I opted for a simpler String > (left, right) kind of structure that I thought I might change out in refactoring. Turns out, that was the right approach, but you’ll have to read about part two to see why.


// More special utilities!
import dev.ericburden.aoc2023.Utils.repeating

/**
 * This enum represents a direction, either left or right.
 */
enum class Direction {
    LEFT,
    RIGHT;

    companion object {
        fun fromChar(char: Char): Direction {
            return when (char) {
                'L' -> LEFT
                'R' -> RIGHT
                else -> throw IllegalArgumentException("$char cannot be parsed to a Direction!")
            }
        }
    }
}

/**
 * This class represents a "node" on the map.
 *
 * Each node essentially serves as a signpost to the next node,
 * identifying the name of either the next node to the left or
 * the next node to the right.
 *
 * @property left The name of the next node to the left.
 * @property right The name of the next node to the right.
 */
data class Signpost(val left: String, val right: String) {
    fun nextFromDirection(direction: Direction): String {
        return when (direction) {
            Direction.LEFT -> left
            Direction.RIGHT -> right
        }
    }
}

/**
 * This class represents an instance of our mysterious map.
 *
 * @property directions A private iterator that can continually
 * produce the next [Direction] to take.
 * @property map The mapping of "node" name to the signpost for
 * the next possible nodes.
 */
class NodeMap(private val directions: Iterator<Direction>, val map: Map<String, Signpost>) {
    companion object {
        /**
         * Parses a [NodeMap] from the input file chunks.
         *
         * @param input A list of "chunks" of the input file, where
         * each "chunk" is a list of lines.
         */
        fun fromInput(input: List<List<String>>): NodeMap {
            val (directionChunk, nodeChunk) = input
            val directions = directionChunk.single().map(Direction::fromChar).repeating()

            // '.associate' is analagous to 'map().toMap().'
            val map = nodeChunk.associate { line ->
                val re = """(\w+) = \((\w+), (\w+)\)""".toRegex()
                val matchResult =
                    re.find(line)
                        ?: throw IllegalArgumentException(
                            "$line is not formatted properly!"
                        )
                val (label, left, right) = matchResult.destructured
                label to Signpost(left, right)
            }

            return NodeMap(directions, map)
        }
    }
}

class Day08(input: List<List<String>>) {

    // Parse that input!
    private val nodeMap = NodeMap.fromInput(input)

}

Today, I learned how to do one of my favorite things (implementing an iterator) in Kotlin. Yay! I’ve added it to my utilities package, since it seems like it will be handy to have a way to make a list loop over and over. Here’s what the implementation for that looks like:


/**
 * Return an iterator that outputs the contents of the list infinitely.
 *
 * This function extends the functionality of a [List<T>] by adding
 * a 'repeating` function that returns an iterator that returns the
 * values of the list, in order, starting over when the list is
 * exhausted.
 *
 * @return A RepeatingList over the list.
 */
fun<T> List<T>.repeating(): Iterator<T> = RepeatingList(this)

/**
 * This class represents an iterator that repeats the values in a list.
 *
 * @property list The list to repeat.
 */
class RepeatingList<T>(private val list: List<T>) : Iterator<T> {
    private var currentIndex = 0

    override fun hasNext(): Boolean {
        return list.isNotEmpty()
    }

    override fun next(): T {
        if (list.isEmpty()) {
            throw NoSuchElementException("List is empty")
        }

        val element = list[currentIndex]
        currentIndex = (currentIndex + 1) % list.size
        return element
    }
}

It may not be the most elegant way to handle this, but I like it!

Part One - That Rude Sandstorm

The elf was a ghost! And she left us in the path of a sandstorm! At least we have a map. Hopefully it’s a map to safety, although that isn’t really specified. If nothing else, it’s a bit of a network problem to work on while the storm rolls in… In true Advent of Code fashion, our goal is to find the shortest path through a ~graph~ desert.


class NodeMap(private val directions: Iterator<Direction>, val map: Map<String, Signpost>) {
    // companion object { ... }

    /**
     * Advance from a position to some other position that satisfies a condition.
     *
     * Given the name of a node on the map, follow the directions and advance from
     * node to node until the current node satisfies some condition.
     *
     * @param start The name of the node to start at.
     * @param stop A predicate function that indicates when to stop advancing.
     * @return A pair of the number of steps taken and the name of the node stopped on.
     */
    fun advanceUntil(start: String, stop: (String) -> Boolean): Pair<Int, String> {
        var currentLocation = start
        var steps = 0

        while (!stop(currentLocation)) {
            currentLocation = this.advanceOnce(currentLocation)
            steps += 1
        }

        return steps to currentLocation
    }
}

class Day08(input: List<List<String>>) {

    // private val nodeMap = ...

    // In part one, we follow the signs from our starting position
    // to our target and count the steps taken.
    fun solvePart1(): Int = nodeMap.advanceUntil("AAA") { it == "ZZZ" }.first

}

That wasn’t so bad! Who needed that spooky elf anyway?

Part Two - Splitting Headache

Wait. What? I can’t tell if we’re actually trying to ignore the laws of space-time and walk multiple simultaneous paths the way we assume the ghost can or if we’re just kind of curious how the ghost managed to get away so fast. If I’m being honest, I’d suspect it has more to do with being a ghost than with map traversal, but what do I know? In part two, we need to somehow start on all the nodes that end with ‘A’ and walk to all the nodes that end with ‘Z’ all our versions land on a ‘Z’-ending node simultaneously. Guess ghosts don’t know how to just stop and wait for the others to catch up. Oh, actually, that sort of makes sense…


class NodeMap(private val directions: Iterator<Direction>, val map: Map<String, Signpost>) {
    // companion object { ... }

    // fun advanceUntil(start: String, stop: (String) -> Boolean): Pair<Int, String> {
    // ...
    // }

    /**
     * Advance one step from a given node.
     *
     * Given the name of a node on the map, follow the directions and advance
     * a single step forward.
     *
     * @param start The name of the node to start at.
     * @return The name of the next node in sequence.
     */
    fun advanceOnce(start: String): String {
        val direction = directions.next()
        val node = map[start] ?: throw IllegalArgumentException("$start is not a node on the map!")
        return node.nextFromDirection(direction)
    }
}

class Day08(input: List<List<String>>) {

    // private val nodeMap = ...

    // fun solvePart1(): Int = ...

    // In part two we pretend to be some sort of quantum ghost and
    // try to take multiple paths simultaneously. This seems like it
    // might be _more_ traumatic than the sandstorm...
    fun solvePart2(example: Boolean = false): Long {
        // Predicates to select lists that end with 'A' or 'Z'.
        val endsWithA: (String) -> Boolean = { str -> str[str.length - 1] == 'A' }
        val endsWithZ: (String) -> Boolean = { str -> str[str.length - 1] == 'Z' }

        // Our starting locations are the ones that end with 'A'
        val startingLocations = nodeMap.map.keys.filter(endsWithA)
        val destinations = startingLocations.map { loc -> nodeMap.advanceUntil(loc, endsWithZ) }

        // Need to check and be sure that each 'path' starting from a node whose
        // name ends with 'A' is actually cyclical. If it _does_ take the same
        // number of steps to get back to the _same_ end node as it took to get
        // there originally, then we can calculate the number of steps needed to
        // get to _all_ end nodes as the least common multiple of the number of
        // steps in each path in a cycle. If not... then my only other option
        // (that I know of) is to turn on the brute force method of just taking
        // one step on each path then checking to see if all paths found an end.
        // Oddly enough, this enters an endless loop on the part two example
        // (it's that "XXX = (XXX, XXX)" line), so I need to skip this bit when
        // running my test on the example input. _Kind_ of a bummer that the apparent
        // intended solution fails on the example.
        if (!example) {
            val nextDestinations = destinations.map { (_, loc) ->
                val start = nodeMap.advanceOnce(loc)
                val (steps, end) = nodeMap.advanceUntil(start, endsWithZ)
                steps + 1 to end// Account for that one extra step from the end
            }
            assert(destinations == nextDestinations) // Cross your fingers!
        }

        // I happen to know that this works, at least for my input.
        return destinations.map { it.first.toLong() }.lcm()
    }
}

Pro Tip: When your naive brute-force solution starts to make your computer fan kick on and run for more than thirty seconds, you’re missing something. Many times, that something is a cycle you can exploit in some way. In this case, it turns out that all the individual ‘__A’ -> ‘__Z’ paths were cyclical and it took the same number of steps to go from ‘__A’ to ‘__Z’ as it took to make another trip around starting from that same endpoint. With that discovery in place, the number of steps is as many as it takes for the periodicity of all the paths to line up.

Wrap Up

This was a good day! To be fair, I’m a wee bit miffed that the example input for part two breaks my code I used to check to see if the “one weird trick” for finding the total number of steps would work. That caused me a bit of a headache, I can tell you for free. On the other hand, I got to learn how to implement my own iterator, how to pass lambdas to functions (so that’s how you get that “curly-braces after the parentheses” syntax!), and how to extract regular expression matches from a string. All told, it was a very productive day for learning Kotlin, and that’s what I’m here for!