@Test
    fun part1() {
        val total = input.map {
            SpringLine(it).numberOfOptions()
        }.sum()
        println("Part 1: $total")
    }

    @Test
    fun part2() {
        var count = 0
        val total = input.map {
            SpringLine(it, 5).numberOfOptions()
        }.sum()
        println("Part 2: $total")
    }

class SpringLine(val line: String, repeated: Int = 1) {
    private val springs = Array(repeated) { line.split(" ")[0] }.joinToString("?")
    private val hints = Array(repeated) { line.split(" ")[1] }.joinToString(",").split(",").map(String::toInt)
    private val knownBroken = springs.indices.filter { springs[it] == '#' }

    private val cache = mutableMapOf<String, Long>()
    fun numberOfOptions(hintIndex: Int = 0, startIndex: Int = 0, ranges: List<IntRange> = emptyList()): Long {
        val key = "$hintIndex-$startIndex"
        cache[key]?.let { return it }
        if (hintIndex == hints.size) return 0
        val minLength = hints.subList(hintIndex, hints.size).sum() + hints.size - hintIndex - 1
        val rightBound = springs.length - minLength
        if (startIndex > rightBound) return 0

        val endIndex = startIndex + hints[hintIndex]
        val possibleWorkingSprings = springs.substring(startIndex, endIndex)
        val options = if (
            possibleWorkingSprings.all { it == '#' || it == '?' } &&
            (startIndex == 0 || springs[startIndex - 1] != '#') &&
            (endIndex == springs.length || springs[endIndex] != '#')
        ) {
            val possibleRanges = ranges + listOf(startIndex until endIndex)
            (if (hintIndex == hints.size - 1
                && knownBroken.all {brokenSpring -> possibleRanges.any { brokenSpring in it } })
                1 else 0) + numberOfOptions(
                hintIndex + 1,
                endIndex + 1,
                possibleRanges
            )
        } else 0
        val total = options + numberOfOptions(hintIndex, startIndex + 1, ranges)
        cache[key] = total
        return total
    }
}