adventofcode-2023/day5/day5.kt

import java.io.File

typealias Map = Pair<LongRange, LongRange>

fun main() {
    val input = File("input")

    val (seeds, maps) = parseInput(input)

    println(part1(seeds, maps))

    val seedRanges = seeds.windowed(2, 2) { it.first() ..< it.first() + it.last() }
    println(part2(seedRanges, maps))
}

fun part1(seeds: List<Long>, maps: List<List<Map>>): Long {
    return seeds.map { seed -> maps.fold(seed) { toFind, map -> findMapping(toFind, map) } }.min()
}

fun findMapping(toFind: Long, maps: List<Map>): Long {
    for (map in maps) {
        if (toFind >= map.first.first && toFind <= map.first.last) {
            val index = toFind - map.first.first

            if (map.second.first + index <= map.second.last) {
                return map.second.first + index
            }
        }
    }

    // Any source numbers that aren't mapped correspond to the same
    // destination number. So, seed number 10 corresponds to soil
    // number 10.
    return toFind
}

fun part2(seedRanges: List<LongRange>, maps: List<List<Map>>): Long {
    return seedRanges
            .map { range ->
                maps
                        .fold(listOf(range)) { toReduce, map -> findReduction(toReduce, map) }
                        .map { it.first }
                        .min()
            }
            .min()
}

fun findReduction(toReduce: List<LongRange>, maps: List<Map>): List<LongRange> {
    var result: MutableList<LongRange> = mutableListOf()
    var reducing: MutableList<LongRange> = mutableListOf()
    reducing.addAll(toReduce)

    for (map in maps) {
        var next: MutableList<LongRange> = mutableListOf()
        val source = map.first
        val destination = map.second

        for (currentRange in reducing) {
            val (overlap, excess) = getOverlap(currentRange, source)
            if (overlap != null) {
                result.add(getDestinationForOverlap(overlap, source, destination))
            }
            next.addAll(excess)
        }
        reducing = next
    }

    result.addAll(reducing)
    return result
}

fun getDestinationForOverlap(
        overlap: LongRange,
        source: LongRange,
        destination: LongRange
): LongRange {
    val startDiff = overlap.first - source.first
    val endDiff = source.last - overlap.last

    return destination.first + startDiff..destination.last - endDiff
}

fun getOverlap(range1: LongRange, range2: LongRange): Pair<LongRange?, List<LongRange>> {
    val start =
            when {
                range1.first <= range2.first -> range2.first
                range1.first > range2.first -> range1.first
                else -> throw Exception("Unreachable")
            }

    val end =
            when {
                range1.last >= range2.last -> range2.last
                range1.last < range2.last -> range1.last
                else -> throw Exception("Unreachable")
            }

    if (start > end) {
        return Pair(null, listOf(range1))
    } else {
        val excess: MutableList<LongRange> = mutableListOf()

        if (start > range1.first) {
            excess.add(range1.first ..< start)
        }

        if (range1.last > end) {
            excess.add(end + 1L..range1.last)
        }

        return Pair(start..end, excess)
    }
}

fun parseInput(input: File): Pair<List<Long>, List<List<Map>>> {
    val text = input.bufferedReader()

    val seeds = text.readLine().split(": ")[1].split(" ").map { it.toLong() }
    text.readLine()

    var line = text.readLine()
    var maps: MutableList<MutableList<Map>> = mutableListOf()

    while (line != null) {
        when {
            line == "" -> Unit // Skip empty lines
            line.endsWith(':') -> maps.add(mutableListOf())
            else -> {
                val (destination, source, length) = line.split(" ").map { it.toLong() }
                maps.last()
                        .add(Pair(source ..< source + length, destination ..< destination + length))
            }
        }

        line = text.readLine()
    }

    return Pair(seeds, maps)
}