Channels
#advent-of-code
Title
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 PMI 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
}
}👍 3
n
Nir
12/25/2020, 2:32 PMindexOf on a sequence is slick, I didn't think of that
e
ephemient
12/25/2020, 2:47 PMyeah 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 PMI ran into it at work a couple of weeks ago, it is pretty cool.
j
Jakub Gwóźdź
12/25/2020, 3:00 PMspent 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 PMI 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 PMUgh. 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 PMSurely 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 PMfor 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