:gift: Day 25: Solutions Thread

# advent-of-code

[ephemient]

🎁 Day 25: Solutions Thread

[ephemient]

https://github.com/ephemient/aoc2020/blob/main/kt/src/main/kotlin/io/github/ephemient/aoc2020/Day25.kt BigInteger must have a fastpath for small moduli, it has performance on par with a inlined, unwrapped exponentiation-by-squaring loop

[todd.ginsberg]

I originally did this like I normally do - a bunch of ugly code to get the right answers and make my tests pass, then iterate until the solution is presentable.

class Day25(input: List<String>) {

    private val cardPk = input.first().toLong()
    private val doorPk = input.last().toLong()

    fun solvePart1(): Long =
        transform(findLoopSize(cardPk), doorPk)

    private fun transform(loopSize: Int, subject: Long): Long =
        generateSequence(1L) { (it * subject) % MAGIC_NUMBER }.drop(loopSize).first()

    private fun findLoopSize(target: Long): Int =
        generateSequence(1L) { (it * MAGIC_SUBJECT) % MAGIC_NUMBER }.indexOf(target)

    companion object {
        const val MAGIC_NUMBER = 20201227
        const val MAGIC_SUBJECT = 7
    }
}

It was faster with while loops, but I like this better 🙂

[Nir]

indexOf on a sequence is slick, I didn't think of that

[Nir]

Untitled

[ephemient]

yeah I was doing generateSequence(){..}.indexOf() at first too, but replacing it with a while loop was 20% faster https://github.com/ephemient/aoc2020/commit/d51c96c72d0844db6f3429e368108860f062e8bd

[todd.ginsberg]

I ran into it at work a couple of weeks ago, it is pretty cool.

[Jakub Gwóźdź]

spent way too much time on own implementation of modPow because I didn't find any in kotlin-common, and falling back to JVM was not an option for me (browser-js target). And yes, I should work on my "dec2bin" code :)

[todd.ginsberg]

I always feel a bit weird about writing code that isn't as fast, but is "fast enough". Like this one. It's faster with while loops (as others have noted as well), but even without it, it's a clean implementation that's fast enough. I treat puzzle code way different than production code, and even then, I'll give up a bit of performance for clarity if I can.

[ephemient]

@Jakub Gwóźdź isn't it easier to skip the explicit binary encoding/decoding?

Untitled.kt

[Jakub Gwóźdź]

Ugh. Of course you're right @ephemient.
But somehow I haven't thought about the obvious solution. 🤦

[ephemient]

@todd.ginsberg I feel a bit differently about my AoC solutions. for production code, what's "fast enough" depends on priorities well beyond the code itself; maybe flexibility and testability is more important, or maybe ugliness is okay for the sake of performance. but in AoC, it's not like there's a serious developer/machine cost trade-off - I am spending all of December on it no matter what, so why not make use of all the techniques

[Nir]

Surely most prod situations with Kotlin are based on "good enough" performance? If you're really trying to microoptimize everything it seems very exhausting, and you may as well use a lower level language

[ephemient]

for actual work: not much is performance sensitive, but some parts really are. on Android there are modern devices with 240Hz displays, so you get <5ms on the main thread between frames before you start dropping. if the user flings a scrolling screen you may need to lay out dozens of views at once without judder. yes, this is almost all in Kotlin, because going to JNI is much more painful, and introduces other costs - forces memory pins which slow down GC, requires building NDK x 4 architectures, can no longer test that part on desktop, and marshalling can take more time than whatever you were saving in the first place

[bjonnh]

const val COLOR = 20201227
const val SUBJECT = 7

fun encrypt(turns: Int, subject: Long) = generateSequence(1L) { (it * subject) % COLOR }.elementAtOrNull(turns) ?: -1L
fun findLoopsForValue(value: Long): Int = generateSequence(1L) { (it * SUBJECT) % COLOR }.indexOf(value)

fun main() {
    val cardPubKey = 2959251L //5764801L
    val doorPubKey = 4542595L //17807724L
    val cardTurns = findLoopsForValue(cardPubKey)
    println(encrypt(cardTurns, doorPubKey))
}