class CircularChain<T>(val value: T) {
    var next: CircularChain<T> = this
    var prev: CircularChain<T> = this

    fun remove() {
        prev.next = next
        next.prev = prev
    }

    fun add(chain: CircularChain<T>) {
        next.prev = chain
        chain.next = next
        chain.prev = this
        next = chain
    }

    fun getRight(n: Int): CircularChain<T> {
        var current = this
        repeat(n) { current = current.next }
        return current
    }

    fun takeRightInclusive(n: Int): List<CircularChain<T>> = sequence {
        var current = this@CircularChain
        yield(current)
        repeat(n) {
            current = current.next
            yield(current)
        }
    }.toList()

    fun getLeft(n: Int): CircularChain<T> {
        var current = this
        repeat(n) { current = current.prev }
        return current
    }

    fun takeLeftInclusive(n: Int): List<CircularChain<T>> = sequence {
        var current = this@CircularChain
        yield(current)
        repeat(n) {
            current = current.prev
            yield(current)
        }
    }.toList()

    override fun toString() = value.toString()
}


data class Elf(val id: Int, var currentRecipe: CircularChain<Recipe>)

data class Recipe(val value: Int)

class Kitchen(numberOfElves: Int, recipesInput: String) {

    val firstRecipe: CircularChain<Recipe>
    var lastRecipe: CircularChain<Recipe>
    var recipesSize: Long = recipesInput.length.toLong()

    init {
        recipesInput.toRecipes().map {
            CircularChain(it)
        }.toMutableList().also {
            it.windowed(2, 1) { (a, b) -> a.add(b) }
        }.also {
            lastRecipe = it.last()
            firstRecipe = it.first()
        }
    }


    val elves = (1..numberOfElves).zip(firstRecipe.takeRightInclusive(1)) { id, recipe ->
        Elf(id, recipe)
    }

    fun nextStep() {
        createNewRecipes()
        moveElvesToNewRecipes()
    }

    private fun moveElvesToNewRecipes() {
        for (elf in elves) {
            val newRecipe = elf.currentRecipe.getRight(elf.currentRecipe.value.value + 1)
            elf.currentRecipe = newRecipe
        }
    }

    private fun createNewRecipes() {
        val sum = elves.sumBy { it.currentRecipe.value.value }
        sum.toString().toRecipes().forEach {
            val newRecipe = CircularChain(it)
            lastRecipe.add(newRecipe)
            lastRecipe = newRecipe
            recipesSize++
        }
    }
}

private fun String.toRecipes() = map { Recipe(it.toString().toInt()) }


fun main() {
    val puzzleInput = "635041"

    val initialRecipes = "37"

    val kitchen = Kitchen(2, initialRecipes)

    val recipesAfter = 10
    val recipesBefore = puzzleInput.toInt()

    while (kitchen.recipesSize < recipesBefore + recipesAfter) {
        kitchen.nextStep()
    }

    val result = kitchen
        .firstRecipe.takeRightInclusive(recipesBefore + recipesAfter - 1)
        .drop(recipesBefore)
        .take(recipesAfter)
        .toStringSequence()

    //A
    assert(result == "1150511382")
    println(result)

    //B
    val kitchenB = Kitchen(2, initialRecipes)

    val reversedPuzzleInput = puzzleInput.reversed().map { it.toString().toInt() }

    while (true) {
        kitchenB.nextStep()

        if (reversedPuzzleInput.matchesPuzzleInput(kitchenB.lastRecipe)) {
            println(kitchenB.recipesSize - reversedPuzzleInput.size)
            break
        }

        if (reversedPuzzleInput.matchesPuzzleInput(kitchenB.lastRecipe.prev)) {
            println(kitchenB.recipesSize - reversedPuzzleInput.size -1 )
            break
        }
    }
}

private fun List<Int>.matchesPuzzleInput(initial: CircularChain<Recipe>): Boolean {
    var current = initial
    return all {
        (it == current.value.value).also {
            current = current.prev
        }
    }
}

private fun List<CircularChain<Recipe>>.toStringSequence() = joinToString("") { it.value.value.toString() }