Den 11. byl opět performance peklo 🙂 . Jelikož jsem neznal “Summed-area table” algoritmus, pokusil jsem se přijít s něčím vlastním, což nebylo zdaleka tak efektivní, ale doběhlo to! (naštěstí se správným výsledkem):
class FuelCell(val x: Int, val y: Int, val serialNumber: Int) { val rackId = (x + 10).toLong() val powerLevel = run { var result = rackId * y result += serialNumber result *= rackId assert(result >= 0) val threeDigitResult = result % 1000 val hundredDigit = when { threeDigitResult >= 100 -> { "$threeDigitResult"[0].toString().toLong() } else -> 0 } hundredDigit - 5 } } interface Square { val refX: Int val refY: Int val serialNumber: Int val size: Int val totalPower: Long } data class FuelSquare( override val refX: Int, override val refY: Int, override val serialNumber: Int, override val size: Int ) : Square { override val totalPower = sequence { for (x in 0 until size) { for (y in 0 until size) { yield(FuelCell(refX + x, refY + y, serialNumber).powerLevel) } } }.sum() } class DiffSquare(val smallerSquare: Square, val diff: Int) : Square { override val refX = smallerSquare.refX override val refY = smallerSquare.refY override val serialNumber = smallerSquare.serialNumber override val size = smallerSquare.size + diff override val totalPower = run { val remainingPower = sequence { for (x in 0 until size) { for (y in 0 until size) { yield( when { x >= size - diff || y >= size - diff -> FuelCell( refX + x, refY + y, serialNumber ).powerLevel else -> 0 } ) } } }.sum() smallerSquare.totalPower + remainingPower } override fun toString() = "$refX,$refY,$size" } var squaresMap = mutableMapOf<Triple<Int, Int, Int>, Square>() private fun findMostPowerfulSquare( maxX: Int, maxY: Int, serialInput: Int, size: Int ): Square { var mostPowerfulSquare: Square? = null val newMap = mutableMapOf<Triple<Int, Int, Int>, Square>() for (x in 0 until maxX - size + 1) { for (y in 0 until maxY - size + 1) { val smallerSquareKey = Triple(x, y, size - 1) val fuelSquare = squaresMap[smallerSquareKey]?.let { DiffSquare(it, 1) } ?: FuelSquare(x, y, serialInput, size) newMap[Triple(x, y, size)] = fuelSquare if (mostPowerfulSquare != null) { if (fuelSquare.totalPower > mostPowerfulSquare.totalPower) { mostPowerfulSquare = fuelSquare } } else mostPowerfulSquare = fuelSquare } } squaresMap = newMap return mostPowerfulSquare ?: throw Exception("Couldn't find it!") } fun main() { val serialInput = 7803 val maxX = 300 val maxY = 300 //A val mostPowerfulSquareA = findMostPowerfulSquare(maxX, maxY, serialInput, 3) println("Most powerful square A is: $mostPowerfulSquareA") //B val mostPowerfulSquareB = (1..300).asSequence().map { size -> println("Searching for size $size") findMostPowerfulSquare(maxX, maxY, serialInput, size) }.maxBy { it.totalPower } println("Most powerful square B is: $mostPowerfulSquareB") }