class Day09 : AOCSolution {
    override val year = 2025
    override val day = 9

    override fun part1(inputFile: String): String {
        val corners = readCorners(inputFile)

        var largestRectangle = -1L
        for (i in 0 until corners.lastIndex) {
            val firstCorner = corners[i]
            for (j in i + 1 until corners.size) {
                largestRectangle = maxOf(largestRectangle, outsideArea(firstCorner, corners[j]))
            }
        }

        return largestRectangle.toString()
    }

    override fun part2(inputFile: String): String {
        val corners = readCorners(inputFile)

        val (horizontal, vertical) = buildAndPartitionLines(corners)
        // Sort the lines along their orthogonal axis
        // Horizontal lines are sorted top to bottom
        horizontal.sortBy { (from) -> from.y }
        // Vertical lines are sorted left to right
        vertical.sortBy { (from) -> from.x }

        var largestRectangleArea = -1L
        for (i in 0 until corners.lastIndex) {
            val first = corners[i]
            for (j in i + 1 until corners.size) {
                val second = corners[j]
                val area = outsideArea(first, second)
                if (area > largestRectangleArea) {
                    val topLeft = Point(minOf(first.x, second.x), minOf(first.y, second.y))
                    val bottomRight = Point(maxOf(first.x, second.x), maxOf(first.y, second.y))
                    if (intersectsNone(horizontal, vertical, topLeft, bottomRight)) {
                        largestRectangleArea = maxOf(largestRectangleArea, area)
                    }
                }
            }
        }

        return largestRectangleArea.toString()
    }

    private companion object {
        private fun readCorners(inputFile: String): List<Point> {
            val corners = readResourceLines(inputFile).map { line ->
                val splitIndex = line.indexOf(',')
                val x = JavaLong.parseLong(line, 0, splitIndex, 10)
                val y = JavaLong.parseLong(line, splitIndex + 1, line.length, 10)
                Point(x, y)
            }
            return corners
        }

        /**
         * Builds two lists of lines from connected corners in [corners].
         * The corners are required to construct lines that are orthogonal to their
         * predecessors and successors.
         *
         * @return two lists, the first one containing the horizontal lines and
         * the second one containing the vertical lines.
         */
        private fun buildAndPartitionLines(corners: List<Point>): Pair<Array<Line>, Array<Line>> {
            require(corners.size >= 2)

            // Origin point of the next line
            var from = corners.last()
            val lines = buildList {
                corners.forEach { to ->
                    add(Line(from, to))
                    from = to
                }
            }

            val (horizontal, vertical) = lines.partition { line -> line.from.y == line.to.y }
            return horizontal.toTypedArray() to vertical.toTypedArray()
        }

        private fun outsideArea(a: Point, b: Point): Long {
            val width = abs(a.x - b.x) + 1
            val height = abs(a.y - b.y) + 1
            return width * height
        }

        /**
         * Checks whether a rectangle intersects any line in the arrays of horizontal and vertical lines.
         *
         * @param horizontal the array of strictly horizontal lines
         * @param vertical the array of strictly vertical lines
         * @param topLeft the top-left corner of the rectangle to check
         * @param bottomRight the bottom-right corner of the rectangle to check
         * @return whether any of the lines intersect the rectangle
         */
        private fun intersectsNone(
            horizontal: Array<Line>,
            vertical: Array<Line>,
            topLeft: Point,
            bottomRight: Point
        ): Boolean {
            // Find the index of the first horizontal line above the rectangle
            val beginHorizontal = horizontal.binarySearchFirst(
                target = topLeft.y
            ) { (from) -> from.y }.coerceAtLeast(0)

            for (i in beginHorizontal until horizontal.size) {
                if (horizontal[i].from.y >= bottomRight.y) {
                    // End early, when encountering the first line on the bottom edge
                    break
                }
                if (isLineInsideRect(horizontal[i], topLeft, bottomRight)) {
                    return false
                }
            }

            // Find the index of the first vertical line on the left edge of the rectangle
            val beginVertical = vertical.binarySearchFirst(
                target = topLeft.x
            ) { (from) -> from.x }.coerceAtLeast(0)

            for (i in beginVertical until vertical.size) {
                if (vertical[i].from.x >= bottomRight.x) {
                    // End early, when encountering the first line on the right edge
                    break
                }
                if (isLineInsideRect(vertical[i], topLeft, bottomRight)) {
                    return false
                }
            }

            return true
        }

        /**
         * Axis-aligned line to rectangle intersection test.
         * Lines are considered inside, if and only if, they are inside the horizontal
         * or vertical bounds of the rectangle.
         * They are not considered inside, if they are on the edges of the rectangle.
         * @param line the line to check the intersection for
         * @param topLeft the top-left corner of the rectangle to check
         * @param bottomRight the bottom-right corner of the rectangle to check
         * @return whether the line intersects the rectangle
         */
        private fun isLineInsideRect(
            line: Line,
            topLeft: Point,
            bottomRight: Point
        ): Boolean {
            val (left, top) = topLeft
            val (right, bottom) = bottomRight

            val fromX = line.from.x
            val toX = line.to.x

            // Vertical
            if ((fromX <= left && toX <= left) || (fromX >= right && toX >= right)) {
                // Line is completely to the left or right of the rectangle
                return false
            }

            val fromY = line.from.y
            val toY = line.to.y
            // Horizontal
            if ((fromY <= top && toY <= top) || (fromY >= bottom && toY >= bottom)) {
                // Line is completely above or below the rectangle
                return false
            }
            return true
        }

        private fun <T> Array<T>.binarySearchFirst(
            from: Int = 0,
            to: Int = size,
            target: Long,
            extractor: ToLongFunction<T>
        ): Int {
            var low = from
            var high = to - 1
            var result = -1

            while (low <= high) {
                val mid = low + ((high - low) / 2)
                val comparison = extractor.applyAsLong(get(mid)).compareTo(target)
                if (comparison == 0) {
                    result = mid
                    high = mid - 1
                } else if (comparison < 0) {
                    low = mid + 1
                } else {
                    high = mid - 1
                }
            }
            return result
        }
    }
}

class Day08 : AOCSolution {
    override fun part1(inputFile: String): String {
        val numConnections = numberOfConnections(inputFile)
        val junctionBoxes = readResourceLines(inputFile).map { line ->
            val (x, y, z) = line.split(",").map { it.toInt() }
            JunctionBox(x, y, z)
        }

        val connections = buildShortestConnections(junctionBoxes, numConnections)
        val circuitSizes = buildCircuitSizes(junctionBoxes, connections)

        // Calculate the result as the product of the sizes
        // of the three largest circuits
        var result = circuitSizes[0]
        for (i in 1 until 3) {
            result *= circuitSizes[i]
        }
        return result.toString()
    }

    override fun part2(inputFile: String): String {
        val junctionBoxes = readResourceLines(inputFile).map { line ->
            val (x, y, z) = line.split(",").map { it.toInt() }
            JunctionBox(x, y, z)
        }

        val connections = buildHeuristicConnections(junctionBoxes, 12)

        val (box1Index, box2Index) = buildCompleteCircuit(junctionBoxes, connections)
        val (x1) = junctionBoxes[box1Index]
        val (x2) = junctionBoxes[box2Index]

        return (x1.toLong() * x2.toLong()).toString()
    }

    private fun buildShortestConnections(
        junctionBoxes: List<JunctionBox>,
        connectionLimit: Int
    ): Queue<Connection> {
        val shortestEdges = PriorityQueue<Connection>(connectionLimit)

        junctionBoxes.forEachIndexed { index, box ->
            for (j in index + 1 until junctionBoxes.size) {
                val distance = junctionBoxes[j].distanceSquared(box)
                if (shortestEdges.size >= connectionLimit) {
                    // Keep the set of connections the required size and
                    // only mutate (remove and add) when a shorter connection is found.
                    if (distance < shortestEdges.peek().distanceSquared) {
                        shortestEdges.poll()
                        shortestEdges.add(Connection(index, j, distance))
                    }
                } else {
                    shortestEdges.add(Connection(index, j, distance))
                }
            }
        }
        return shortestEdges
    }

    private fun buildHeuristicConnections(
        junctionBoxes: List<JunctionBox>,
        connectionLimit: Int,
    ): List<Connection> {
        return buildList {
            val shortestConnections = PriorityQueue<Connection>(junctionBoxes.size * connectionLimit)

            for (fromIndex in 0 until junctionBoxes.lastIndex) {
                val from = junctionBoxes[fromIndex]

                shortestConnections.clear()

                for (toIndex in fromIndex + 1 until minOf(fromIndex + connectionLimit, junctionBoxes.size)) {
                    val other = junctionBoxes[toIndex]
                    val distance = from.distanceSquared(other)
                    shortestConnections.add(Connection(fromIndex, toIndex, distance))
                }

                // Calculate the remaining distances
                for (toIndex in fromIndex + connectionLimit + 1 until junctionBoxes.size) {
                    val to = junctionBoxes[toIndex]
                    val distance = from.distanceSquared(to)
                    if (distance < shortestConnections.peek().distanceSquared) {
                        // Keep the set of connections the required size and
                        // only mutate (remove and add) when a shorter connection is found.
                        shortestConnections.poll()
                        shortestConnections.add(Connection(fromIndex, toIndex, distance))
                    }
                }
                addAll(shortestConnections)
            }

            // Sort by shortest length first
            sortWith { c1, c2 -> c2.compareTo(c1) }
        }
    }

    private fun buildCircuitSizes(
        junctionBoxes: List<JunctionBox>,
        connections: Iterable<Connection>
    ): IntArray {
        // Array of circuit ids, beginning with each junction box as their own circuit
        val circuits = IntArray(junctionBoxes.size) { it }

        // Add connections between junction boxes by
        // merging the circuits they are in
        connections.forEach { (box1, box2) ->
            val circuit1 = circuits[box1]
            val circuit2 = circuits[box2]
            if (circuit1 != circuit2) {
                // Merge the circuits
                circuits.replaceAll(circuit2, circuit1)
            }
        }

        val sizes = circuits.boundedFrequencies(junctionBoxes.size)
        sizes.sortDescending()

        return sizes
    }

    private fun buildCompleteCircuit(
        junctionBoxes: List<JunctionBox>,
        connections: List<Connection>
    ): Connection {
        // Array of circuit ids, beginning with each junction box as their own circuit
        val circuits = IntArray(junctionBoxes.size) { it }

        connections.forEach { connection ->
            val (box1, box2) = connection
            val circuit1 = circuits[box1]
            val circuit2 = circuits[box2]
            if (circuit1 != circuit2) {
                // Merge the circuits
                circuits.replaceAll(circuit2, circuit1)
                if (circuits.all { it == circuit1 }) {
                    // We are done, when all circuits are the same
                    return connection
                }
            }
        }
        throw AssertionError()
    }

    private companion object {
        const val NUM_CONNECTIONS_SAMPLE = 10
        const val NUM_CONNECTIONS = 1000

        private fun numberOfConnections(inputFile: String): Int {
            return if (inputFile.endsWith("sample")) {
                NUM_CONNECTIONS_SAMPLE
            } else {
                NUM_CONNECTIONS
            }
        }

        @JvmRecord
        private data class JunctionBox(
            val x: Int,
            val y: Int,
            val z: Int,
        ) {
            fun distanceSquared(other: JunctionBox): Long {
                val dx = (x - other.x).toLong()
                val dy = (y - other.y).toLong()
                val dz = (z - other.z).toLong()
                return (dx * dx) + (dy * dy) + (dz * dz)
            }
        }

        @JvmRecord
        private data class Connection(
            val boxIndex1: Int,
            val boxIndex2: Int,
            val distanceSquared: Long,
        ) : Comparable<Connection> {
            override fun compareTo(other: Connection): Int {
                return other.distanceSquared.compareTo(this.distanceSquared)
            }
        }

        private fun IntArray.boundedFrequencies(upperBound: Int): IntArray {
            require(this.isNotEmpty())

            val frequencies = IntArray(upperBound)

            var element = this[0]
            var elementCount = 1

            for (i in indices) {
                val n = this[i]
                if (element == n) {
                    elementCount++
                } else {
                    frequencies[element] += elementCount
                    element = n
                    elementCount = 1
                }
            }
            // Add the last run to the frequencies
            frequencies[element] += elementCount

            return frequencies
        }

class Day07 : AOCSolution {
    override val year = 2025
    override val day = 7

    override fun part1(inputFile: String): String {
        val diagram = readResourceLines(inputFile)
            .mapArray { line -> line.mapArray { char -> Cell.byChar(char) } }
            .toGrid()

        var count = 0
        for (y in 1 until diagram.height) {
            for (x in 0 until diagram.width) {
                // Search for beam sources in the preceding row
                if (diagram[x, y - 1] in Cell.beamSourceTypes) {
                    // Simulate the beam moving down
                    when (diagram[x, y]) {
                        Cell.Empty -> diagram[x, y] = Cell.Beam
                        Cell.Splitter -> {
                            // Split the beam and count this splitter
                            diagram[x - 1, y] = Cell.Beam
                            diagram[x + 1, y] = Cell.Beam
                            count++
                        }

                        else -> continue
                    }
                }
            }
        }

        return count.toString()
    }

    override fun part2(inputFile: String): String {
        val diagram = readResourceLines(inputFile)
            .mapArray { line -> line.mapArray { char -> Cell.byChar(char) } }
            .toGrid()
        val height = diagram.height.toLong()

        val startPosition = diagram.positionOfFirst { it == Cell.Start }

        // Working stack of beam origin and split origin positions
        val stack = ArrayDeque<Pair<Position, Position>>()
        stack.add(startPosition to startPosition)

        // Splitter positions mapped to the count of timelines to them
        // Start with the start position and 1 timeline.
        val splitters = mutableMapOf<Position, Long>(startPosition to 1)

        // Keep track of all splitters for which new beams have been spawned already
        // Could be used to solve part 1, as well
        val spawnedSplitters = mutableSetOf<Position>()

        // Count the timelines per diagram exit, which is the bottom-most row
        val diagramExits = LongArray(diagram.width)

        while (stack.isNotEmpty()) {
            // Breadth first search for memorizing the amount of paths to a splitter
            val (beamOrigin, splitOrigin) = stack.poll()
            val originPathCount = splitters.getValue(splitOrigin)

            val nextPosition = beamOrigin + Direction.DOWN

            if (nextPosition.y < height) {
                if (diagram[nextPosition] == Cell.Splitter) {
                    if (nextPosition !in spawnedSplitters) {
                        // Only spawn new beams, if they weren't spawned already
                        stack.add((nextPosition + Direction.LEFT) to nextPosition)
                        stack.add((nextPosition + Direction.RIGHT) to nextPosition)
                        spawnedSplitters.add(nextPosition)
                        // Initialize the count
                        splitters[nextPosition] = originPathCount
                    } else {
                        splitters.computeIfPresent(nextPosition) { _, v -> v + originPathCount }
                    }
                } else {
                    // Just move down
                    stack.add(nextPosition to splitOrigin)
                }
            } else {
                diagramExits[nextPosition.x.toInt()] += originPathCount
            }
        }

        // Sum the count of timelines leading to the bottom row, i.e. leaving the diagram for each position
        return diagramExits.sum().toString()
    }

    private companion object {
        enum class Cell(val char: Char) {
            Start('S'),
            Empty('.'),
            Splitter('^'),
            Beam('|');

            override fun toString(): String {
                return char.toString()
            }

            companion object {
                fun byChar(char: Char) = entries.first { it.char == char }

                val beamSourceTypes = arrayOf(Start, Beam)
            }
        }
    }
}

class Day06 : AOCSolution {
    override val year = 2025
    override val day = 6

    override fun part1(inputFile: String): String {
        val worksheet = readResourceLines(inputFile)
        // Arrange the problem in a grid and transpose it, so that the operation is the last element of each row
        val problems = worksheet.map { line -> line.trim().split(spaceSplitRegex) }.toGrid().transposed()

        val grandTotal = problems.rows().sumOf { line ->
            // Map the all but the last element to a number
            val numbers = line.mapToLongArray(0, line.lastIndex - 1, String::toLong)
            // Extract the operation
            val operation = line.last()[0]

            // Call the correct reduction
            // The "else" branch is needed for the compiler
            when (operation) {
                ADD -> numbers.sum()
                MULTIPLY -> numbers.reduce { acc, value -> acc * value }
                else -> 0
            }
        }
        return grandTotal.toString()
    }

    override fun part2(inputFile: String): String {
        val worksheet = readResourceLines(inputFile)

        // In this part the problem is more complicated and dependent on the individual characters.
        val charGrid = worksheet.map(CharSequence::toList).toCharGrid().transposed()

        val numbers = mutableListOf<Long>()
        val sb = StringBuilder(charGrid.width)

        val problems = buildList {
            // Begin with an empty operation
            // Assume the operation will be set to a valid value
            var operation = SPACE
            for (y in 0 until charGrid.height) {
                // Extract each row (transposed column)
                sb.clear().append(charGrid[y])
                // Find the bounds of the number
                val numberOffset = sb.indexNotOf(SPACE)

                if (numberOffset != -1) {
                    // A number was found, parse it and add it to the list.
                    val endIndex = sb.indexOfAny(STOP_CHARACTERS, numberOffset + 1)
                    val number = java.lang.Long.parseLong(sb, numberOffset, endIndex, 10)
                    numbers.add(number)

                    // Check whether there is an operation in the last column.
                    // IF so, that's the next relevant operation
                    val lastColumn = sb[sb.lastIndex]
                    if (lastColumn != SPACE) {
                        operation = lastColumn
                    }
                } else {
                    // No number was found, that's the separator for two calculations.
                    // Finalize the collection and clear the numbers.
                    // `toLongArray` creates a neat copy of the Longs in the list.
                    add(Problem(operation, numbers.toLongArray()))
                    numbers.clear()
                }
            }
            // Add the last remaining problem to the list
            add(Problem(operation, numbers.toLongArray()))
        }

        // Reduce all problems to their solutions and sum them up.
        val grandTotal = problems.sumOf { problem ->
            when (problem.operation) {
                ADD -> problem.numbers.sum()
                MULTIPLY -> problem.numbers.reduce { acc, value -> acc * value }
                else -> 0
            }
        }

        return grandTotal.toString()
    }

    private companion object {
        private const val ADD = '+'
        private const val MULTIPLY = '*'
        private const val SPACE = ' '
        private val STOP_CHARACTERS = charArrayOf(SPACE, ADD, MULTIPLY)

        @JvmRecord
        @Suppress("ArrayInDataClass")
        private data class Problem(val operation: Char, val numbers: LongArray)
    }

class Day05 : AOCSolution {
    override val year = 2025
    override val day = 5

    override fun part1(inputFile: String): String {
        val (freshIngredients, availableIngredients) = readResourceTwoParts(inputFile)

        val freshRanges = buildRanges(freshIngredients)

        val ingredientIds = availableIngredients.lines().filterNot(String::isEmpty).map(String::toLong)

        val count = ingredientIds.count { id -> freshRanges.any { range -> id in range } }

        return count.toString()
    }

    override fun part2(inputFile: String): String {
        val (freshIngredients, _) = readResourceTwoParts(inputFile)

        val freshRanges = buildRanges(freshIngredients)

        return freshRanges.sumOf { range ->
            range.last - range.first + 1
        }.toString()
    }

    private companion object {
        private fun buildRanges(ingredients: String): List<LongRange> {
            val lines = ingredients.lines()
            val ranges = MutableList(lines.size) { i ->
                val line = lines[i]
                val hyphen = line.indexOf('-')
                val lower = line.take(hyphen).toLong()
                val upper = line.substring(hyphen + 1).toLong()
                LongRange(lower, upper)
            }

            // Sort the ranges
            // The ones with the smallest ID and the least upper end
            // get sorted to the beginning.
            // This allows for easy merging, as overlapping ranges are always adjacent
            ranges.sortWith(Comparator { r1, r2 ->
                val first = r1.first.compareTo(r2.first)
                if (first != 0) {
                    first
                } else {
                    r1.last.compareTo(r2.last)
                }
            })

            // Merge adjacent ranges backwards, modifying the list in-place
            for (i in ranges.lastIndex downTo 1) {
                val lowerRange = ranges[i - 1]
                val upperRange = ranges[i]

                // The two ranges do overlap, because the tail of the first range
                // is in the second range.
                if (upperRange.first <= lowerRange.last) {
                    ranges[i - 1] = LongRange(
                        lowerRange.first,
                        maxOf(lowerRange.last, upperRange.last)
                    )
                    ranges.removeAt(i)
                }
            }

            return ranges
        }
    }
}

class Day04 : AOCSolution {
    override val year = 2025
    override val day = 4

    override fun part1(inputFile: String): String {
        val grid = readResourceLines(inputFile).map(CharSequence::toList).toCharGrid()

        var accessiblePaperRolls = 0

        // Quickly iterate the grid in top-left to bottom-right order
        for (y in 0 until grid.height) {
            for (x in 0 until grid.width) {
                // Count the neighbours of each paper roll.
                if (grid[x, y] == PAPER_ROLL &&
                    grid.countNeighbours(x, y, 1) { it == PAPER_ROLL } < 4
                ) {
                    accessiblePaperRolls++
                }
            }
        }
        return accessiblePaperRolls.toString()
    }

    override fun part2(inputFile: String): String {
        val grid = readResourceLines(inputFile).map(CharSequence::toList).toCharGrid()

        var count = 0
        while (true) {
            var iterationCount = 0

            // Quickly iterate the grid in top-left to bottom-right order
            for (y in 0 until grid.height) {
                for (x in 0 until grid.width) {
                    if (grid[x, y] == PAPER_ROLL &&
                        grid.countNeighbours(x, y, 1) { it == PAPER_ROLL } < 4
                    ) {
                        // Remove the paper roll for the next iteration
                        grid[x, y] = REMOVED_PAPER_ROLL
                        iterationCount++
                    }
                }
            }
            count += iterationCount

            // Repeat the count until no paper rolls are accessible.
            if (iterationCount == 0) {
                break
            }
        }

        return count.toString()
    }

    private companion object {
        const val PAPER_ROLL = '@'
        const val REMOVED_PAPER_ROLL = 'x'

        /**
         * Count the neighbours of the given cell in the given [radius] of cells that satisfy the given predicate.
         *
         * @param startX the horizontal position of the center of the count in the grid
         * @param startY the vertical position of the center of the count in the grid
         * @param radius the radius counted in Manhattan distance to the center
         * @param predicate the test that needs to pass for a neighbour to count.
         */
        private fun CharGrid.countNeighbours(
            startX: Int,
            startY: Int,
            radius: Int,
            predicate: Predicate<Char>,
        ): Int {
            var count = 0
            for (y in maxOf(startY - radius, 0)..minOf(startY + radius, height - 1)) {
                for (x in maxOf(startX - radius, 0)..minOf(startX + radius, width - 1)) {
                    if (y == startY && x == startX) {
                        continue
                    }
                    if (predicate.test(this[x, y])) {
                        count++
                    }
                }
            }
            return count
        }
    }
}

class Day03 : AOCSolution {
    override val year = 2025
    override val day = 3

    override fun part1(inputFile: String): String {
        return readResourceBinary(inputFile).lineSequence().sumOf { batteryBank ->
            findHighestJoltage(batteryBank, 2)
        }.toString()
    }

    override fun part2(inputFile: String): String {
        return readResourceBinary(inputFile).lineSequence().sumOf { batteryBank ->
            findHighestJoltage(batteryBank, 12)
        }.toString()
    }

    private fun findHighestJoltage(
        bank: EightBitString,
        batteries: Int,
    ): Long {
        val digitsArray = ByteArray(batteries) { -1 }

        var lastDigitIndex = 0
        repeat(batteries) { currentDigit ->
            val remainingDigits = batteries - currentDigit
            val lastIndex = bank.length - remainingDigits + 1

            val maxIndex = bank.indexOfMax(lastDigitIndex, lastIndex)
            lastDigitIndex = maxIndex + 1
            digitsArray[batteries - remainingDigits] = bank[maxIndex].toDigit()
        }

        return digitsArray.fold(0L) { acc, i -> acc * 10L + i }
    }


    private companion object {
        private fun ByteArray.lineSequence(): Sequence<EightBitString> {
            val buffer = EightBitString(this)
            var currentOffset = 0
            return generateSequence {
                for (characterIndex in currentOffset until buffer.limit()) {
                    if (buffer[characterIndex] == '\n') {
                        val slice = buffer.subSequence(currentOffset, characterIndex)

                        // Despite believing that `currentIndex` is not read,
                        // it is indeed read the next time this generator is called.
                        @Suppress("AssignedValueIsNeverRead")
                        currentOffset = characterIndex + 1
                        return@generateSequence slice
                    }
                }
                // A '\n' is always found, because the files end with a new line.
                return@generateSequence null
            }
        }

        private fun EightBitString.indexOfMax(
            startIndex: Int,
            endIndex: Int,
        ): Int {
            if (startIndex >= endIndex) {
                return -1
            }
            var maxIndex = startIndex
            var max = 0.toByte()
            for (i in startIndex until endIndex) {
                val c = getByte(i)
                if (c > max) {
                    maxIndex = i
                    max = c
                }
            }
            return maxIndex
        }

        private fun Char.toDigit(): Byte = (this - '0').toByte()
    }
}

val lockRegex = Regex("""#{5}(\r?\n[.#]{5}){6}""")
val keyRegex = Regex("""([.#]{5}\r?\n){6}#{5}""")

fun parseLocksAndKeys(inputFile: String): Pair<List<IntArray>, List<IntArray>> {
    val input = readResource(inputFile)
    val locks = lockRegex
        .findAll(input)
        .map {
            it
                .value
                .lines()
                .map { line -> line.toList() }
                .transpose()
                .map { line -> line.count { c -> c == '#' } - 1 }
                .toIntArray()
        }
        .toList()

    val keys = keyRegex
        .findAll(input)
        .map {
            it
                .value
                .lines()
                .map { line -> line.toList() }
                .transpose()
                .map { line -> line.count { c -> c == '#' } - 1 }
                .toIntArray()
        }
        .toList()

    return locks to keys
}

fun part1(inputFile: String): String {
    val (locks, keys) = parseLocksAndKeys(inputFile)

    val matches = locks.map { lock ->
        keys.filter { key ->
            for (i in lock.indices) {
                // Make sure the length of the key and lock do not exceed 5
                if (lock[i] + key[i] > 5) {
                    return@filter false
                }
            }
            true
        }
    }
        .flatten()
        .count()

    return matches.toString()
}

class Day22 {

    private fun nextSecretNumber(start: Long): Long {
        // Modulo 2^24 is the same as "and" with 2^24 - 1
        val pruneMask = 16777216L - 1L
        // * 64 is the same as shifting left by 6
        val mul64 = ((start shl 6) xor start) and pruneMask
        // / 32 is the same as shifting right by 5
        val div32 = ((mul64 shr 5) xor mul64) and pruneMask
        // * 2048 is the same as shifting left by 11
        val mul2048 = ((div32 shl 11) xor div32) and pruneMask
        return mul2048
    }

    fun part1(inputFile: String): String {
        val secretNumbers = readResourceLines(inputFile)
            .map { it.toLong() }
            .toLongArray()

        repeat(NUMBERS_PER_DAY) {
            for (i in secretNumbers.indices) {
                secretNumbers[i] = nextSecretNumber(secretNumbers[i])
            }
        }

        return secretNumbers.sum().toString()
    }

    fun part2(inputFile: String): String {
        // There is a different sample input for part 2
        val input = if (inputFile.endsWith("sample")) {
            readResourceLines(inputFile + "2")
        } else {
            readResourceLines(inputFile)
        }
        val buyers = input
            .map {
                LongArray(NUMBERS_PER_DAY + 1).apply {
                    this[0] = it.toLong()
                    for (i in 1..NUMBERS_PER_DAY) {
                        this[i] = nextSecretNumber(this[i - 1])
                    }
                }
            }

        // Calculate the prices and price differences for each buyer.
        // The pairs are the price (the ones digit) and the key/unique value of each sequence of differences
        val differences = buyers
            .map { secretNumbers ->
                // Get the ones digit
                val prices = secretNumbers.mapToIntArray {
                    it.toInt() % 10
                }

                // Get the differences between each number
                val differenceKeys = prices
                    .zipWithNext { a, b -> (b - a) }
                    // Transform the differences to a singular unique value (integer)
                    .mapWindowed(4) { sequence, from, _ ->
                        // Bring each byte from -9 to 9 to 0 to 18, multiply by 19^i and sum
                        // This generates a unique value for each sequence of 4 differences
                        (sequence[from + 0] + 9) +
                                (sequence[from + 1] + 9) * 19 +
                                (sequence[from + 2] + 9) * 361 +
                                (sequence[from + 3] + 9) * 6859
                    }

                // Drop the first 4 prices, as they are not relevant (initial secret number price and 3 next prices)
                prices.dropFromArray(4) to differenceKeys
            }

        // Cache to hold the value/sum of each sequence of 4 differences
        val sequenceCache = IntArray(NUMBER_OF_SEQUENCES)
        val seenSequence = BooleanArray(NUMBER_OF_SEQUENCES)

        // Go through each sequence of differences
        // and get their *first* prices of each sequence.
        // Sum them in the cache.
        for ((prices, priceDifferences) in differences) {
            // Reset the "seen" array
            Arrays.fill(seenSequence, false)
            for (index in priceDifferences.indices) {
                val key = priceDifferences[index]
                if (!seenSequence[key]) {
                    sequenceCache[key] += prices[index]
                    seenSequence[key] = true
                }
            }
        }

        return sequenceCache.max().toString()
    }

    companion object {
        private const val NUMBERS_PER_DAY = 2000

        // 19^4, the differences range from -9 to 9 and the sequences are 4 numbers long
        private const val NUMBER_OF_SEQUENCES = 19 * 19 * 19 * 19
    }
}