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