class Day12 : Day {

    override suspend fun solvePart1(input: String): String {
        val (init, rules) = parse(input)
        return init.sumOfPlantNumbersAfterGeneration(20, rules).toString()
    }

    override suspend fun solvePart2(input: String): String {
        val (init, rules) = parse(input)
        return init.sumOfPlantNumbersAfterGeneration(50_000_000_000, rules).toString()
    }

    private fun Set<Long>.sumOfPlantNumbersAfterGeneration(
        gen: Long,
        rules: Map<String, Boolean>
    ): Long {
        var currentState = this
        for (currentGen in 1L..gen) {
            val nextState = evolve(currentState, rules)

            if (currentState.getPattern() == nextState.getPattern()) {
                val rate = nextState.sum() - currentState.sum()
                return currentState.sum() + rate * (gen - currentGen + 1)
            }

            currentState = nextState
        }
        return currentState.sum()
    }

    private fun evolve(state: Set<Long>, rules: Map<String, Boolean>): Set<Long> {
        val next = mutableSetOf<Long>()
        for (i in state.min()!!-2..state.max()!!+2) {
            val region = (-2..2).map { if (state.contains(i + it)) '#' else '.' }.join()
            if (rules[region] == true) {
                next += i
            }
        }
        return next
    }

    private fun Set<Long>.getPattern(): String {
        val min = min()!!
        return (min..max()!!).map { if (it in this) '#' else '.' }.join()
    }

    data class Input(val initialState: Set<Long>, val rules: Map<String, Boolean>)
    private val initialStatePattern = Regex("""initial state: ([.#]+)\s""")
    private val rulePattern = Regex("""([.#]{5}) => ([.#])""")
    private fun parse(input: String): Input {
        return Input(
            initialState = initialStatePattern.find(input)!!.groupValues[1].let(this::parseState),
            rules = rulePattern.findAll(input).associate(this::parseRule)
        )
    }

    private fun parseRule(match: MatchResult): Pair<String, Boolean> =
        match.groupValues[1] to when (match.groupValues[2]) {
            "#" -> true
            "." -> false
            else -> throw IllegalArgumentException()
        }

    private fun parseState(input: String): Set<Long> =
        input.withIndex()
            .filter { (_, c) -> c == '#' }
            .map { it.index.toLong() }
            .toSet()

}