import kotlin.math.abs

fun main() {

    data class Interval(var start: Int, var end: Int) {
        fun limit(minStart: Int, maxEnd: Int) {
            start = maxOf(minStart, start)
            end = minOf(maxEnd, end)
        }

        fun size(): Int {
            return 1 + end - start
        }
    }

    fun List<Interval>.maxReduce(): List<Interval> {
        if (isEmpty()) return emptyList()
        val iterator = this.sortedWith(compareBy({ it.start }, { it.end })).listIterator()

        var last = iterator.next()
        val reduced = mutableListOf(last)
        while (iterator.hasNext()) {
            val next = iterator.next()
            if (next.start <= last.end) {
                last.end = maxOf(next.end, last.end)
            } else {
                reduced.add(next)
                last = next
            }
        }
        return reduced
    }

    fun parseSensorsBeacons(input: List<String>): Map<Vector2D, Vector2D> {
        return input.associate { line ->
            val split = line.split("=", ",", ":")
            Vector2D(split[1].toInt(), split[3].toInt()) to Vector2D(split[5].toInt(), split[7].toInt())
        }
    }

    fun rangeAtY(sensor: Vector2D, distance: Int, y: Int): Interval? {
        val yDist = abs(sensor.y - y)
        if (yDist > distance) return null
        val restDist = distance - yDist
        return Interval(sensor.x - restDist, sensor.x + restDist)
    }

    fun part1(input: List<String>): Int {
        val sensorToBeacons = parseSensorsBeacons(input)
        val beaconsCount = sensorToBeacons.values.filter { it.y == 2_000_000 }.toSet().size
        val sensorToDistances = sensorToBeacons.mapValues { (s, b) -> s.manhattenDistance(b) }
        return sensorToDistances
            .mapNotNull { (s, d) -> rangeAtY(s, d, 2_000_000) }
            .maxReduce()
            .sumOf { it.size() } - beaconsCount
    }

    fun part2(input: List<String>): Long {
        val sensorToDistances = parseSensorsBeacons(input).mapValues { (s, b) -> s.manhattenDistance(b) }
        for (y in 0..4_000_000) {
            val intervals = sensorToDistances
                .mapNotNull { (s, d) -> rangeAtY(s, d, y) }
                .maxReduce()
                .onEach { it.limit(0, 4_000_000) }
            if (intervals.size > 1) {
                return 4_000_000L * (intervals.first().end + 1) + y
            }
        }
        return -1L
    }

    val input = readInput("Day15")

    println(part1(input))
    println(part2(input))
}





