class Day08 : Puzzle {

    lateinit var boxes: List<Point3D>
    lateinit var edges: List<Pair<List<Point3D>, Double>>

    override fun readFile() {
        val input = readInputFromFile(2025, 8, false)
        boxes = input.lines().filter { it.isNotBlank() }
            .map { it.split(",") }
            .map { Point3D(it[0].toInt(), it[1].toInt(), it[2].toInt()) }
        edges = calculateEdges(boxes)
    }

    private fun calculateEdges(boxes: List<Point3D>): List<Pair<List<Point3D>, Double>> {
        val edges = mutableListOf<Pair<MutableList<Point3D>, Double>>()
        for (i in boxes.indices) {
            for (j in i + 1 until boxes.size) {
                edges.add(Pair(mutableListOf(boxes[i], boxes[j]), boxes[i].dist(boxes[j])))
            }
        }
        return edges.sortedBy { it.second }
    }

    override fun solvePartOne(): String {
        val connections = buildEmptyConnectionMatrix(boxes.size)
        val mutableEdges = edges.toMutableList()
        for (i in 0..<1000) {
            connectNextEdge(mutableEdges, connections)
        }

        val connectionSet = buildConnectionSet(boxes, connections)

        return connectionSet.map { it.size }
            .sortedByDescending { it }
            .take(3)
            .reduce(Int::times)
            .toString()
    }

    override fun solvePartTwo(): String {
        val connections = buildEmptyConnectionMatrix(boxes.size)
        val mutableEdges = edges.toMutableList()

        var result: Long? = null
        while (result == null) {
            result = connectNextEdge(mutableEdges, connections, true)
        }

        return result.toString()
    }

    // size: width & height of (square) matrix
    private fun buildEmptyConnectionMatrix(size: Int): Array<Array<Boolean>> {
        val connections = Array(size) { Array(size) { false } }
        for (i in connections.indices) {
            connections[i][i] = true
        }
        return connections
    }

    private fun connectNextEdge(mutableEdges: MutableList<Pair<List<Point3D>, Double>>, connections: Array<Array<Boolean>>, part2: Boolean = false): Long? {
        if (mutableEdges.isEmpty()) return null
        val next = mutableEdges[0]

        val point = next.first[0]
        val other = next.first[1]
        connectAll(boxes.indexOf(point), boxes.indexOf(other), connections)
        mutableEdges.remove(next)

        // all nodes are connected, assume that this is happening for the first time
        return if (part2 && connections[0].all { it }) {
            next.first[0].x.toLong() * next.first[1].x.toLong()
        } else {
            null
        }
    }

    private fun connectAll(index: Int, other: Int, connections: Array<Array<Boolean>>) {
        fun connectHelper(hIndex: Int) {
            val newConnections = mutableSetOf<Int>()
            for (i in connections[hIndex].indices) {
                if (connections[hIndex][i]) newConnections.add(i)
            }
            for (boxIndex in newConnections.filter { it != hIndex }) {
                for (conn in newConnections.filter { it != boxIndex }) {
                    connections[boxIndex][conn] = true
                }
            }
        }
        connections[index][other] = true

        connectHelper(index) // update matrix with all values from node at [index]
        connectHelper(other) // update matrix with all values from node at [other]
    }

    // returns 2D-list of all indices of currently active connections
    private fun buildConnectionSet(boxes: List<Point3D>, connections: Array<Array<Boolean>>): Set<List<Int>> {
        val connectionSet = mutableSetOf<List<Int>>()
        val indices = (0 until boxes.size).toMutableList()
        while (indices.isNotEmpty()) {
            val list = mutableListOf<Int>()
            val curr = indices.removeFirst()
            val array = connections[curr]
            for (j in array.indices) {
                if (array[j]) list.add(j)
            }
            connectionSet.add(list)
        }
        return connectionSet
    }

    data class Point3D(val x: Int, val y: Int, val z: Int) {
        fun dist(other: Point3D): Double {
            return sqrt(
                (x - other.x).toDouble().pow(2) +
                        (y - other.y).toDouble().pow(2) +
                        (z - other.z).toDouble().pow(2)
            )
        }
    }
}

class Day07 : Puzzle {

    val grid = mutableListOf<MutableList<Char>>()
    val partTwoCache = mutableMapOf<Pair<Int, Int>, Long>()

    override fun readFile() {
        val input = readInputFromFile(2025, 7, false)
        for (line in input.lines().filter { it.isNotBlank() }) {
            grid.add(line.toCharArray().toMutableList())
        }
    }

    override fun solvePartOne(): String {
        grid[1][grid[0].indexOf('S')] = '|'

        var splits = 0
        for (r in 1..<grid.size - 1) {
            for (c in 0..<grid[r].size) {
                if (grid[r][c] == '|') {
                    if (grid[r+1][c] == '.') {
                        grid[r+1][c] = '|'
                    } else if (grid[r+1][c] == '^') {
                        grid[r+1][c-1] = '|'
                        grid[r+1][c+1] = '|'
                        splits++
                    }
                }
            }
        }
        return splits.toString()
    }

    override fun solvePartTwo(): String {
        val start = grid[0].indexOf('S')
        return (1 + processBeamPartTwo(1, start)).toString() // don't forget to count the original timeline
    }

    private fun processBeamPartTwo(row: Int, column: Int): Long {
        if (partTwoCache.contains(Pair(row, column))) {
            return partTwoCache[Pair(row, column)]!!
        }

        if (row == grid.size) return 0L
        if (column == grid[row].size || column < 0) return 0L

        val out = if (grid[row][column] == '^') { // splitter
            1L + processBeamPartTwo(row, column - 1) + processBeamPartTwo(row, column + 1)
        } else {
            processBeamPartTwo(row + 1, column)
        }
        partTwoCache[Pair(row, column)] = out
        return out
    }
}

class Day06 : Puzzle {

    val numsPartOne = mutableListOf<MutableList<Long>>()
    val numsPartTwo = mutableListOf<List<Long>>()
    val ops = mutableListOf<(Long, Long) -> Long>()

    override fun readFile() {
        val input = readInputFromFile("src/main/resources/a2025/day06.txt")
        val lines = input.lines().filter { it.isNotBlank() }

        // parse part1 input
        for (line in lines.dropLast(1)) {
            for ((c, num) in line.trim().split(" +".toRegex()).withIndex()) {
                if (numsPartOne.getOrNull(c) == null) numsPartOne.add(mutableListOf())
                numsPartOne[c].add(num.toLong())
            }
        }

        // parse part2 input
        var numList = mutableListOf<Long>()
        for (c in 0..<lines.maxOf { it.length }) {
            var numStr = ""
            for (r in 0..<lines.size - 1) {
                numStr += lines[r].getOrElse(c) { ' ' }
            }
            if (numStr.isBlank()) {
                numsPartTwo.add(numList)
                numList = mutableListOf()
            } else {
                numList.add(numStr.trim().toLong())
            }
        }
        numsPartTwo.add(numList)

        // parse operators
        ops.addAll(
            lines.last().split(" +".toRegex())
                .map { it.trim()[0] }
                .map {
                    when (it) {
                        '*' -> { a: Long, b: Long -> a * b }
                        '+' -> { a: Long, b: Long -> a + b }
                        else -> throw IllegalArgumentException("Unknown operator: $it")
                    }
                }
        )
    }

    override fun solvePartOne(): String {
        return numsPartOne.mapIndexed { c, list -> list.reduce { a, b -> ops[c](a, b) } }.sum().toString()
    }

    override fun solvePartTwo(): String {
        return numsPartTwo.mapIndexed { c, list -> list.reduce { a, b -> ops[c](a, b) } }.sum().toString()
    }
}

class Day05 : Puzzle {

    val validIds = mutableSetOf<LongRange>()
    val ids = mutableListOf<Long>()

    override fun readFile() {
        val input = readInputFromFile("src/main/resources/a2025/day05.txt")
        val inputList = input.split("\n\n", limit = 2)
        validIds.addAll(
            inputList[0].lines().filter { it.isNotBlank() }
                .map { it.split("-").map { it.toLong() } }
                .map { LongRange(it[0], it[1]) }
        )
        ids.addAll(inputList[1].lines().filter { it.isNotBlank() }.map { it.toLong() })
    }

    override fun solvePartOne(): String {
        return ids.count { id -> validIds.any { id in it } }.toString()
    }

    override fun solvePartTwo(): String {
        val idsSorted = validIds.sortedBy { it.first }
        val merged = mutableSetOf<LongRange>()

        var current = idsSorted.first()
        for (i in 1..<idsSorted.size) {
            val next = idsSorted[i]

            if (next.first <= current.last) {
                current = LongRange(current.first, max(current.last, next.last()))
            } else {
                merged.add(current)
                current = next
            }
        }
        merged.add(current)
        return merged.sumOf { it.last + 1 - it.first }.toString()
    }
}

class Day04 : Puzzle {

    val grid = mutableListOf<MutableList<Char>>()

    override fun readFile() {
        val input = readInputFromFile("src/main/resources/a2025/day04.txt")
        for ((r, line) in input.lines().filter(String::isNotBlank).withIndex()) {
            grid.add(mutableListOf())
            for (char in line) {
                grid[r].add(char)
            }
        }
    }

    override fun solvePartOne(): String {
        return countRolls(grid).toString()
    }

    override fun solvePartTwo(): String {
        var sum = 0
        var removed = -1
        while (removed != 0) {
            // main grid is modified here, not the best but doesn't really matter
            // also no idea how to clone 2D list in Kotlin
            removed = countRolls(grid, true)
            sum += removed
        }
        return sum.toString()
    }

    private fun countRolls(grid: MutableList<MutableList<Char>>, removeRolls: Boolean = false): Int {
        val dr = listOf(-1, -1, -1, 0, 0, 1, 1, 1)
        val dc = listOf(-1, 0, 1, -1, 1, -1, 0, 1)

        var sum = 0
        for (r in grid.indices) {
            for (c in grid[r].indices) {
                if (grid[r][c] != '@') continue

                var neighborCount = 0
                for (i in dr.indices) {
                    if (gridGet(grid, r + dr[i], c + dc[i]) == '@') neighborCount++
                }
                if (neighborCount < 4) {
                    sum++
                    if (removeRolls) grid[r][c] = '.'
                }
            }
        }
        return sum
    }

    private fun gridGet(grid: List<List<Char>>, r: Int, c: Int, default: Char = '.'): Char {
        return if (r in grid.indices && c in grid[r].indices) {
            grid[r][c]
        } else {
            default
        }
    }
}

class Day03 : Puzzle {

    val banks = mutableListOf<String>()

    override fun readFile() {
        val input = readInputFromFile("src/main/resources/a2025/day03.txt")
        banks.addAll(input.lines().filter(String::isNotBlank))
    }

    override fun solvePartOne(): String {
        val sum = banks.map { buildNumber(it, 2) }.sumOf { it.toLong() }
        return sum.toString()
    }

    override fun solvePartTwo(): String {
        val sum = banks.map { buildNumber(it, 12) }.sumOf { it.toLong() }
        return sum.toString()
    }

    private fun buildNumber(bank: String, remainingDigits: Int): String {
        if (remainingDigits <= 0) return ""
        val current = bank.dropLast(remainingDigits - 1)
        val max = current.max()
        return max + buildNumber(bank.split(max, limit = 2)[1], remainingDigits - 1)
    }
}

class Day02 : Puzzle {

    val ids = mutableSetOf<String>()

    override fun readFile() {
        val input = readInputFromFile("src/main/resources/a2025/day02.txt")
        ids.addAll(
            input.replace("\n", "")
                .split(",")
                .map { it.split("-") }
                .map(this::buildList)
                .flatten()
        )
    }

    private fun buildList(rangeList: List<String>): List<String> {
        val start = rangeList[0].toLong()
        val end = rangeList[1].toLong()
        val ids = mutableListOf<String>()
        for (i in start..end) {
            ids.add(i.toString())
        }
        return ids
    }

    override fun solvePartOne(): String {
        return ids.filter(this::idNotValid)
            .sumOf(String::toLong).toString()
    }

    override fun solvePartTwo(): String {
        return ids.filter { idNotValid(it, true) }
            .sumOf(String::toLong).toString()
    }

    private fun idNotValid(id: String, multipleSplits: Boolean = false): Boolean {
        val length = id.length

        // try all splits
        var split = 2
        while (split <= length) {
            if (length % split == 0) {
                val splits = mutableListOf<String>()
                var beg = 0
                var end = length / split
                val step = end
                for (i in 0..<split) {
                    splits.add(id.substring(beg, end))
                    beg += step
                    end += step
                }
                if (splits.all { it == splits[0] }) return true
            }
            if (multipleSplits) {
                split++
            } else {
                break
            }
        }
        return false
    }
}