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()
    }
}