import java.util.*
import kotlin.math.max

// Some padding to hold negative values -OFFSET .. 0
// Negatives did not go below 6 in my input
const val OFFSET = 10
const val WINDOW_MASK = 0b00011111

fun main() {
    val rules = RULES.parseRules()
    val initialState = INITIAL_STATE.parseState()

    val plants = PlantAutomata(rules, initialState)

    while (plants.currentStep < 20) { plants.step() }
    val part1 = plants.sumOfPotsWithPlants()

    while (plants.step()) {}
    val prev = plants.sumOfPotsWithPlants()
    plants.step()
    val cur = plants.sumOfPotsWithPlants()
    val part2 = ((50_000_000_000L - plants.currentStep) * (cur - prev)) + cur

    println(part1)
    println(part2)
}

// Each bit of generation tracks whether or not there is a plant inside minus some OFFSET for negative numbers
class PlantAutomata(val rules: Int, initialState: BitSet) {
    var currentStep = 0

    private var curGen = BitSet(initialState.size()).apply { or(initialState) }

    private var nextGen = BitSet()

    /**
     * Step the automata
     * @return true while this has not converged
     */
    // Slide a bitwise window across the current generation, and apply the rules to the next generation
    // The value of the window corresponds to a bit in the rule mask, which indicates the status of the next gen
    fun step(): Boolean {
        // Only need to iterate from the lowest set bit to the highest, since we know a-priori is np "abiogenesis"
        // Could be more clever and skip to the next set bit once we hit a window of zero. Not implemented.
        val lo = max(2, curGen.nextSetBit(0))
        val hi = max(lo, curGen.previousSetBit(curGen.length()))
        var window = curGen[lo-4]
            .shlOr(curGen[lo-3])
            .shlOr(curGen[lo-2])
            .shlOr(curGen[lo-1])
            .shlOr(curGen[lo])

        for (i in lo-2..hi+2) {
            val mask = 1.shl(window)
            val nextValue = rules.and(mask) == mask

            nextGen[i] = nextValue

            window = window.shlOr(curGen[i + 3]).masked()
        }

        // If the next and current gen are equal with leading zeros removed we can terminate
        // This was enough for my input but if there is a rule which leads to a cycle this will not be sufficient
        val eq = curGen.toTrimmed() == nextGen.toTrimmed()

        val tmp = curGen
        curGen = nextGen
        nextGen = tmp
        nextGen.clear()
        currentStep++
        return !eq
    }

    fun sumOfPotsWithPlants(): Int {
        var sum = 0
        curGen.forEachSetBit {
            sum += it - OFFSET
        }
        return sum
    }
}


/** Return a nee copy of a bitset with leading and trailing zeros removed */
// I'm not aware of a non-allocating form of this
fun BitSet.toTrimmed(): BitSet = get(max(0, nextSetBit(0)), length())


// Parsing
// =======

fun String.parseState(): BitSet = asSequence()
    .map { it.toBoolean() }
    .foldIndexed(BitSet()) { i, acc, rule ->
        acc.apply {
            set(OFFSET + i, rule)
        }
    }

fun String.parseRules(): Int {
    return lineSequence()
        .sorted()
        .map { it[9] }
        .map { it.ruleBit() }
        .fold(0) { acc, rule ->
            acc.shl(1).or(rule)
        }
}

fun Char.ruleBit(): Int = when (this) {
    '.' -> 0
    '#' -> 1
    else -> throw IllegalArgumentException()
}

fun Char.toBoolean(): Boolean = when (this) {
    '.' -> false
    '#' -> true
    else -> throw IllegalArgumentException()
}

// Syntactic sugar

inline fun BitSet.forEachSetBit(action: (Int) -> Unit) {
    var i = nextSetBit(0)
    while (i >= 0) {
        action(i)
        i = nextSetBit(i + 1)
    }
}

fun Boolean.toInt(): Int = if (this) 1 else 0

fun Boolean.shlOr(other: Boolean): Int = toInt().shlOr(other)
fun Int.shlOr(other: Boolean): Int = shlOr(other.toInt())
fun Int.shlOr(other: Int): Int = shl(1).or(other)

fun Int.masked(): Int = and(WINDOW_MASK)