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