První část už byla trochu známá (viz podobná úloha s kuličkami v kruhu), ale druhá část byla opět zapeklitá z pohledu performance. Už jsem to chtěl pomalu vzdát, ale ještě jsem zkusil své řešení přeimplementovat kompletně bez použití Listu a zde jsem se již správné odpovědi dočkal!
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() }