package y2019.w2.d14

import readText

val input = readText("y2019/w2/d14/input.txt")

class Stack(val name: String, val count: Long)

class Reaction(val result: Stack, val ingredients: List<Stack>)

fun parseStack(string: String): Stack {
    val (count, name) = string.split(" ")
    return Stack(name, count.toLong())
}

fun parseReaction(string: String): Reaction {
    val (ingredients, result) = string.split(" => ")
    return Reaction(parseStack(result), ingredients.split(", ").map(::parseStack))
}

private fun calculateOreUsed(reactions: Map<String, Reaction>, fuelCount: Long): Long {
    val usedCount = mutableMapOf<String, Long>().withDefault { 0 }
    val leftOvers = mutableMapOf<String, Long>().withDefault { 0 }

    fun request(stack: Stack) {
        usedCount[stack.name] = usedCount.getValue(stack.name) + stack.count
        val reaction = reactions[stack.name] ?: return

        val leftOver = leftOvers.getValue(stack.name)
        val reactionCount = (stack.count - leftOver) ceilDiv reaction.result.count

        leftOvers[stack.name] = leftOver - stack.count + reactionCount * reaction.result.count
        for (ingredient in reaction.ingredients)
            request(Stack(ingredient.name, ingredient.count * reactionCount))
    }

    request(Stack("FUEL", fuelCount))
    return usedCount.getValue("ORE")
}

private infix fun Long.ceilDiv(other: Long) = (this + other - 1) / other

fun main() {
    val reactions = input.lines().associate { line ->
        val reaction = parseReaction(line)
        reaction.result.name to reaction
    }

    val oreUsedForSingleFuel = calculateOreUsed(reactions, 1)
    println("Part 1: $oreUsedForSingleFuel")

    val oreAvailable = 1_000_000_000_000L
    val lowerBound = oreAvailable / oreUsedForSingleFuel

    val fuelCount = expBinarySearch(lowerBound) { calculateOreUsed(reactions, it) <= oreAvailable }
    println("Part 2: $fuelCount")
}

/**
 * Find the maximum Long value that matches [pred], starting from [lower].
 * [pred] is expected to be decreasing, so `!pred(x) => !pred(x+n)` for positive `n`.
 */
inline fun expBinarySearch(lower: Long, pred: (Long) -> Boolean): Long {
    check(lower > 0)
    check(!pred(Long.MAX_VALUE))

    var l = lower
    var r = lower

    //exponential search
    while (pred(r))
        r = if (r < Long.MAX_VALUE / 2) r * 2 else Long.MAX_VALUE

    //binary search
    while (r - l > 1) {
        val m = (r + l) / 2
        if (pred(m))
            l = m
        else
            r = m
    }

    return l
}