Advent of Code v Kotlinu (Den 11.)

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")
}