import kotlin.math.floor
import kotlin.math.log
import kotlin.math.pow
import kotlin.time.DurationUnit

fun main() {
    fun part1(input: List<String>): Long = Day11Solver(input).solve(25)

    fun part2(input: List<String>): Long = Day11Solver(input).solve(75)

    val testInput = readInput("Day11_test")
    check(part1(testInput) == 55312L)
    //check(part2(testInput) == 0L)  No test output available.

    val input = readInput("Day11")
    part1(input).println()
    part2(input).println()

    timeTrials("Part 1", unit = DurationUnit.MICROSECONDS) { part1(input) }
    timeTrials("Part 2", repetitions = 1000) { part2(input) }
}

class Day11Solver(input: List<String>) {
    private val parsedInput = input[0].split(' ').map { it.toLong() }

    /*
     * i ∈ ℕ₀ ∪ {-1}, φᵢ: ℕ₀ → ℕ shall be the function mapping the amount of stones generated to the amount of steps
     * taken with a stone of starting number i.
     *
     * Furthermore, ѱ: ℕ₀ → ℕ₀ ⨯ (ℕ₀ ∪ {-1}) shall be the function mapping an index to two new indices after a step.
     *
     *         ⎧ (1, -1)       if i = 0
     * ѱ(i) := ⎨ (a, b)        if ⌊lg(i)⌋ + 1 ∈ 2 ℕ    with a := i/(10^((⌊lg(i)⌋ + 1) / 2)), b := i - 10^((⌊lg(i)⌋ + 1) / 2) * a
     *         ⎩ (2024 i, -1)  otherwise
     *
     *          ⎧ 0                      if i = -1
     * φᵢ(n) := ⎨ 1                      if n = 0
     *          ⎩ φₖ(n - 1) + φₗ(n - 1)  otherwise    with (k, l) := ѱ(i)
     *
     * With that φᵢ(n) is a sum with n up to 2ⁿ summands, that are either 0 or 1.
     */
    private val cacheIndices = mutableMapOf<Long, Pair<Long, Long>>()  // Cache the next indices for going from φᵢ(n) to φₖ(n - 1) + φₗ(n - 1).
    private val cacheValues = mutableMapOf<Pair<Long, Int>, Long>()  // Also cache already calculated φᵢ(n)

    fun calculatePsi(i: Long): Pair<Long, Long> = cacheIndices.getOrPut(i) {
        if(i == -1L) throw IllegalArgumentException("Advancement made: How did we get here?")
        else if (i == 0L) 1L to -1L
        else {
            val amountOfDigits = (floor(log(i.toDouble(), 10.0)) + 1)

            if (amountOfDigits.toLong() % 2 == 0L) {
                // Split digits at the midpoint.
                val a = floor(i / 10.0.pow(amountOfDigits / 2))
                val b = i - a * 10.0.pow(amountOfDigits / 2)
                a.toLong() to b.toLong()
            } else {
                2024 * i to -1L
            }
        }
    }

    fun calculatePhi(i: Long, n: Int): Long = cacheValues.getOrPut(i to n) {
        if (i == -1L) 0L
        else if (n == 0) 1L
        else {
            val (k, l) = calculatePsi(i)
            calculatePhi(k, n - 1) + calculatePhi(l, n - 1)
        }
    }

    fun solve(steps: Int): Long = parsedInput.sumOf {
        val debug = calculatePhi(it, steps)
        debug
    }
}

fun main() {
    /**
     * The idea is simple: Just simulate the pathing and sum all the end points
     */
    fun part1(input: List<String>): Int {
        val topologicalMap = Day10Map(input)
        val startingPoints = topologicalMap.asIterable().indicesWhere { it == 0 }
        val directions = Orientation.entries.map { it.asVector() }
        return startingPoints.sumOf { startingPoint ->
            var wayPoints = setOf(VecNReal(startingPoint))
            val endPoints = mutableSetOf<VecNReal>()
            while (wayPoints.isNotEmpty()) {
                wayPoints = wayPoints.flatMap { wayPoint ->
                    directions.map { direction ->
                        val checkoutLocation = wayPoint + direction
                        checkoutLocation to runCatching { topologicalMap[checkoutLocation] }.getOrElse { -1 }
                    }.filter { nextLocation ->
                        val endPointHeight = topologicalMap[wayPoint]
                        if (nextLocation.second - 1 == endPointHeight && nextLocation.second == 9) false.also { endPoints.add(nextLocation.first) }
                        else if (nextLocation.second - 1 == endPointHeight) true
                        else false
                    }.map { it.first }
                }.toSet()
            }

            endPoints.count()
        }
    }

    /**
     * A bit more complicated, but not by much.
     * Main difference is, that node accumulates all the possible paths, thus adding all the possibilities of
     * its parent node.
     */
    fun part2(input: List<String>): Int {
        val topologicalMap = Day10Map(input)
        val startingPoints = topologicalMap.asIterable().indicesWhere { it == 0 }
        val directions = Orientation.entries.map { it.asVector() }

        return startingPoints.sumOf { startingPoint ->
            var pathNodes = setOf<Node>(Node(VecNReal(startingPoint), topologicalMap[VecNReal(startingPoint)], 1))
            val endNodes = mutableSetOf<Node>()
            while (pathNodes.isNotEmpty()) {
                pathNodes = pathNodes.flatMap { pathNode ->
                    directions.map { direction ->
                        val nextNodeLocation = pathNode.position + direction
                        val nextNodeHeight = runCatching { topologicalMap[nextNodeLocation] }.getOrElse { -1 }
                        Node(nextNodeLocation, nextNodeHeight, pathNode.weight)
                    }.filter { nextNode ->
                        nextNode.height == pathNode.height + 1
                    }
                }.groupBy { it.position }.map { (position, nodesUnadjusted) ->
                    val adjustedWeight = nodesUnadjusted.sumOf { node -> node.weight }
                    Node(position, nodesUnadjusted.first().height, adjustedWeight)
                }.filter { node ->
                    if (node.height == 9) false.also { endNodes.add(node) } else true
                }.toSet()
            }

            endNodes.sumOf { endNode -> endNode.weight }
        }
    }

    val testInput = readInput("Day10_test")
    check(part1(testInput) == 36)
    check(part2(testInput) == 81)

    val input = readInput("Day10")
    part1(input).println()
    part2(input).println()
}

class Day10Map(input: List<String>): Grid2D<Int>(input.map { row -> row.map { "$it".toInt() } }) {
    init { transpose() }
}

data class Node(val position: VecNReal, val height: Int, val weight: Int = 1)

import kotlin.text.flatMapIndexed

fun main() {
    fun part1(input: List<String>): Long {
        val disk = parseInputDay09(input)
        return disk.compactFragmented().checksum()
    }

    fun part2(input: List<String>): Long {
        val disk = parseInputDay09(input)
        return disk.blockify().compactContiguous().checksum()
    }

    val testInput = readInput("Day09_test")
    check(part1(testInput) == 1928L)
    check(part2(testInput) == 2858L)

    val input = readInput("Day09")
    part1(input).println()
    part2(input).println()
}

fun parseInputDay09(input: List<String>): DiscretizedDisk {
    var id = 0
    return input[0].flatMapIndexed { index, char ->
        val size = "$char".toInt()
        if (index % 2 == 0) List(size) { DiskBlockElement(id) }
        else (List(size) { DiskBlockElement(-1) }).also { id++ }
    }
}

data class DiskBlockElement(val id: Int)  // -1 id is empty
data class DiskBlock(val id: Int, val indexRange: IntRange)

typealias Disk = List<DiskBlock>
typealias DiscretizedDisk = List<DiskBlockElement>
fun DiscretizedDisk.compactFragmented(): DiscretizedDisk {
    val freeSpace = count { it.id < 0 }
    val onlyFiles = reversed().filter { it.id >= 0 }
    var indexIntoOnlyFiles = 0
    val discretizedCompacted = map { if (it.id < 0) onlyFiles[indexIntoOnlyFiles++] else it }.dropLast(freeSpace) + List(freeSpace) { DiskBlockElement(-1) }
    return discretizedCompacted
}

fun Disk.compactContiguous(): DiscretizedDisk {
    var (onlyFiles, spaaaaace) = (this.partition { it.id >= 0 })
    onlyFiles = onlyFiles.reversed()

    val emptySpacesCreatedIndexes = mutableListOf<List<Int>>()
    var spaceRemaining = spaaaaace.first().indexRange.size()
    val emptyBlockReplacements = spaaaaace.map { emptyBlock ->
        buildList {
            spaceRemaining = emptyBlock.indexRange.size()
            while (spaceRemaining > 0) {
                val fittingBlockIndex = onlyFiles.indexOfFirst { it.indexRange.size() <= spaceRemaining }
                if (fittingBlockIndex == -1) {
                    add(DiskBlock(-1, (emptyBlock.indexRange.last() - spaceRemaining + 1)..emptyBlock.indexRange.last()))
                    break
                }
                val fittingBlock = onlyFiles[fittingBlockIndex]
                if (fittingBlock.indexRange.first <= emptyBlock.indexRange.last) {
                    add(DiskBlock(-1, (emptyBlock.indexRange.last() - spaceRemaining + 1)..emptyBlock.indexRange.last()))
                    break
                }

                val newDiscretizedIndex = with(emptyBlock.indexRange.last() - spaceRemaining + 1) { this until (this + fittingBlock.indexRange.size()) }
                add(fittingBlock.copy(indexRange = newDiscretizedIndex))
                spaceRemaining -= fittingBlock.indexRange.size()
                onlyFiles = onlyFiles.withoutElementAt(fittingBlockIndex)
                emptySpacesCreatedIndexes.add(fittingBlock.indexRange.toList())
            }
        }
    }

    val replaceWithEmpty = emptySpacesCreatedIndexes.flatten()
    var replacementIndex = 0
    return flatMap {
        if (it.id >= 0) listOf(it) else emptyBlockReplacements[replacementIndex++]
    }.discretize().mapIndexed { index, blockElement -> if (index in replaceWithEmpty) DiskBlockElement(-1) else blockElement }
}

fun DiscretizedDisk.blockify(): Disk = buildList {
    var blockID = this@blockify.first().id
    var blockStartIndex = 0
    this@blockify.forEachIndexed { index, blockElement ->
        if (blockElement.id != blockID) {
            add(DiskBlock(blockID, blockStartIndex until index))
            blockStartIndex = index
            blockID = blockElement.id
        } else if (index == this@blockify.lastIndex) add(DiskBlock(blockElement.id, blockStartIndex.. this@blockify.lastIndex))
    }
}

fun Disk.discretize(): DiscretizedDisk = flatMap { block -> List(block.indexRange.size()) { DiskBlockElement(block.id) } }

fun DiscretizedDisk.checksum(): Long = foldIndexed(0) { index, acc, blockElement ->
    if (blockElement.id >= 0) acc + index * blockElement.id else acc
}

import kotlin.math.abs
import kotlin.math.pow

fun main() {
    fun part1(input: List<String>): Int {
        val inputMap = Day08Map(input)
        return inputMap.isoFrequencyNodeVectorsByLocations
            .flatMap { (location, vectors) ->
                vectors.map { (2.0 scaleVec it) + location }
            }
            .toSet()
            .count { inputMap.isInGrid(it) }
    }

    fun part2(input: List<String>): Int {
        val inputMap = Day08Map(input)
        return buildSet {
            inputMap.isoFrequencyNodeVectorsByLocations.forEach { (location, vectors) ->
                vectors.forEach { vector ->
                    var i = 0.0
                    val scaledDownVector = smallestIntegerVectorInSameDirection2D(vector)
                    while (inputMap.isInGrid(location + (i scaleVec scaledDownVector))) {
                        add(location + (i scaleVec scaledDownVector))
                        i++
                    }
                }
            }
        }.count()
    }

    val testInput = readInput("Day08_test")
    check(part1(testInput) == 14)
    check(part2(testInput) == 34)

    val input = readInput("Day08")
    part1(input).println()
    part2(input).println()
}

tailrec fun gcdEuclid(a: Int, b: Int): Int =
    if (b == 0) a
    else if (a == 0) b
    else if (a > b) gcdEuclid(a - b, b)
    else gcdEuclid(a, b - a)

fun smallestIntegerVectorInSameDirection2D(vec: VecNReal): VecNReal {
    assert(vec.dimension == 2)  // Only works in two dimensions.
    assert(vec == vec.roundComponents())  // Only works on integer vectors.

    return (gcdEuclid(abs(vec[0].toInt()), abs(vec[1].toInt())).toDouble().pow(-1) scaleVec vec).roundComponents()
}

class Day08Map(input: List<String>): Grid2D<Char>(input.reversed().map { it.toList() }) {
    init {
        transpose()
    }

    val isoFrequencyNodesLocations = asIterable().toSet().filter { it != '.' }.map { frequency -> asIterable().indicesWhere { frequency == it } }
    val isoFrequencyNodeVectorsByLocations = buildMap {
        isoFrequencyNodesLocations.forEach { isoFrequencyLocationList ->
            isoFrequencyLocationList.mapIndexed { index, nodeLocation ->
                this[VecNReal(nodeLocation)] = isoFrequencyLocationList
                    .slice((0 until index) + ((index + 1)..isoFrequencyLocationList.lastIndex))
                    .map { VecNReal(it) - VecNReal(nodeLocation) }
            }
        }
    }
}

import kotlin.collections.any
import kotlin.math.pow

fun main() {
    fun part1(input: List<String>): Long {
        val operations = setOf(CalibrationOperation.Plus, CalibrationOperation.Multiply)
        return generalizedSolution(input, operations)
    }

    fun part2(input: List<String>): Long {
        val operations = setOf(CalibrationOperation.Plus, CalibrationOperation.Multiply, CalibrationOperation.Concat)
        return generalizedSolution(input, operations)
    }

    val testInput = readInput("Day07_test")
    check(part1(testInput) == 3749L)
    check(part2(testInput) == 11387L)

    val input = readInput("Day07")
    part1(input).println()
    part2(input).println()
}

fun parseInputDay7(input: List<String>) = input.map {
    val calibrationResultAndInput = it.split(':')
    calibrationResultAndInput[0].toLong() to calibrationResultAndInput[1].split(' ').filter { it != "" }.map { it.toLong() }
}

fun generalizedSolution(input: List<String>, operations: Set<CalibrationOperation>): Long {
    val parsedInput = parseInputDay7(input)
    val operationsPermutations = CalibrationOperation.operationPermutationSequence(*operations.toTypedArray()).take(calculatePermutationsNeeded(parsedInput, operations)).toList()
    return sumOfPossibleCalibrationEquations(parsedInput, operationsPermutations)
}

fun calculatePermutationsNeeded(parsedInput: List<Pair<Long, List<Long>>>, operations: Set<CalibrationOperation>): Int {
    val highestNumberOfOperations = parsedInput.maxOf { it.second.size - 1 }
    return (1..highestNumberOfOperations).sumOf { operations.size.toDouble().pow(it).toInt() }
}

fun sumOfPossibleCalibrationEquations(parsedInput: List<Pair<Long, List<Long>>>, operationPermutationCollection: Collection<OperationPermutation>): Long {
    val permutationsGrouped = operationPermutationCollection.groupBy { it.size }
    return parsedInput.sumOf { (equationResult, equationInput) ->
        if (permutationsGrouped[equationInput.size - 1]!!.any { operations ->
                equationResult == equationInput.drop(1)
                    .foldIndexed(equationInput[0]) { index, acc, lng -> operations[index](acc, lng) }
            }) equationResult else 0
    }
}

typealias OperationPermutation = List<CalibrationOperation>

sealed class CalibrationOperation(val operation: (Long, Long) -> Long) {
    operator fun invoke(a: Long, b: Long) = operation(a, b)
    object Plus : CalibrationOperation({ a: Long, b: Long -> a + b })
    object Multiply : CalibrationOperation({ a: Long, b: Long -> a * b })
    object Concat : CalibrationOperation({ a: Long, b: Long -> "$a$b".toLong() })

    companion object {
        fun operationPermutationSequence(vararg operations: CalibrationOperation) = sequence<OperationPermutation> {
            val cache = mutableListOf<OperationPermutation>()
            val calculateCacheRange = { currentLength: Int ->
                val sectionSize = operations.size.toDouble().pow(currentLength - 1).toInt()
                val sectionStart = (1 until currentLength - 1).sumOf { operations.size.toDouble().pow(it).toInt() }
                sectionStart..(sectionStart + sectionSize - 1)
            }

            // Populate the cache with initial values for permutation length 1.
            operations.forEach { operation -> yield(listOf(operation).also { cache.add(it) }) }

            var currentLength = 2
            var offset = 0
            var cacheRange = calculateCacheRange(currentLength)
            var rotatingOperations = operations.toList()
            yieldAll(
                generateSequence {
                    if (cacheRange.count() == offset) {
                        rotatingOperations = rotatingOperations.rotated(1)
                        if (rotatingOperations.first() == operations.first()) {
                            currentLength++
                        }

                        offset = 0
                        cacheRange = calculateCacheRange(currentLength)
                    }

                    val cacheSlice = cache.slice(cacheRange)

                    return@generateSequence (cacheSlice[offset] + rotatingOperations.first()).also {
                        cache += it
                        offset++
                    } 
                }
            )
        }
    }
}

fun main() {
    fun part1(input: List<String>): Int {
        val puzzleMap = PuzzleMap.fromPuzzleInput(input)
        puzzleMap.simulateGuardPath()
        return puzzleMap.asIterable().indicesWhere { it is MapObject.Visited }.count()
    }

    fun part2(input: List<String>): Int {
        val puzzleMap = PuzzleMap.fromPuzzleInput(input)
        puzzleMap.simulateGuardPath()

        return puzzleMap.asIterable().indicesWhere { it is MapObject.Visited }.count {
            val alteredPuzzleMap = PuzzleMap.fromPuzzleInput(input)
            alteredPuzzleMap[VecNReal(it)] = MapObject.Obstacle()
            alteredPuzzleMap.simulateGuardPath()
        }
    }

    val testInput = readInput("Day06_test")
    check(part1(testInput) == 41)
    check(part2(testInput) == 6)

    val input = readInput("Day06")
    part1(input).println()
    part2(input).println()
}

enum class Orientation {
    NORTH, SOUTH, WEST, EAST;

    fun rotateClockwise(): Orientation {
        return when (this) {
            NORTH -> EAST
            EAST -> SOUTH
            SOUTH -> WEST
            WEST -> NORTH
        }
    }
    
    fun asVector(): VecNReal {
        return when (this) {
            NORTH -> VecNReal(listOf(0.0, 1.0))
            SOUTH -> VecNReal(listOf(0.0, -1.0))
            WEST -> VecNReal(listOf(-1.0, 0.0))
            EAST -> VecNReal(listOf(1.0, 0.0))
        }
    }
}

class PuzzleMap(objectElements: List<List<MapObject>>): Grid2D<MapObject>(objectElements) {
    private val guard = Grid2D(objectElements).asIterable().first { it is MapObject.Guard } as MapObject.Guard

    companion object {
        fun fromPuzzleInput(input: List<String>): PuzzleMap = PuzzleMap(
            input.reversed().mapIndexed { y, row -> row.mapIndexed { x, cell ->  MapObject.fromCharAndIndex(cell, x to y) } }
        ).also { it.transpose() }
    }

    fun guardStep() {
        if (guardScout() is MapObject.Obstacle) guard.orientation = guard.orientation.rotateClockwise()
        else {
            guard.position += guard.orientation.asVector()
        }
    }

    fun simulateGuardPath(): Boolean {
        while (true) {
            markVisited()
            val scouted = guardScout()
            if (scouted is MapObject.Visited && guard.orientation in scouted.inOrientation) return true
            else if (scouted is MapObject.OutOfBounds) return false
            guardStep()
        }
    }

    fun guardScout(): MapObject = runCatching { this[guard.position + guard.orientation.asVector()] }.getOrElse { MapObject.OutOfBounds }

    fun markVisited() {
        val previousMapObject = this[guard.position]
        if (previousMapObject is MapObject.Visited) this[guard.position] = previousMapObject.copy(previousMapObject.inOrientation.plus(guard.orientation))
        else this[guard.position] = MapObject.Visited(listOf(guard.orientation))
    }
}

sealed class MapObject {
    class Empty: MapObject()
    class Obstacle: MapObject()
    object OutOfBounds: MapObject()

    data class Visited(val inOrientation: List<Orientation>): MapObject()
    data class Guard(var position: VecNReal, var orientation: Orientation = Orientation.NORTH): MapObject()

    companion object {
        fun fromCharAndIndex(c: Char, index: Pair<Int, Int>): MapObject {
            return when (c) {
                '.' -> Empty()
                '#' -> Obstacle()
                '^' -> Guard(VecNReal(index))
                else -> throw IllegalArgumentException("Unknown map object $c")
            }
        }
    }
}