https://kotlinlang.org logo
e

ephemient

12/25/2020, 1:45 PM
🎁 Day 25: Solutions Thread
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
t

todd.ginsberg

12/25/2020, 2:09 PM
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.
Copy code
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 🙂
👍 3
n

Nir

12/25/2020, 2:32 PM
indexOf on a sequence is slick, I didn't think of that
e

ephemient

12/25/2020, 2:47 PM
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
t

todd.ginsberg

12/25/2020, 2:48 PM
I ran into it at work a couple of weeks ago, it is pretty cool.
j

Jakub Gwóźdź

12/25/2020, 3:00 PM
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 :)
t

todd.ginsberg

12/25/2020, 3:21 PM
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.
👍 2
e

ephemient

12/25/2020, 3:21 PM
@Jakub Gwóźdź isn't it easier to skip the explicit binary encoding/decoding?
j

Jakub Gwóźdź

12/25/2020, 3:25 PM
Ugh. Of course you're right @ephemient. But somehow I haven't thought about the obvious solution. 🤦
e

ephemient

12/25/2020, 3:31 PM
@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
n

Nir

12/25/2020, 4:49 PM
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
e

ephemient

12/25/2020, 5:09 PM
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
b

bjonnh

12/28/2020, 8:55 PM
Copy code
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))
}
6 Views