https://kotlinlang.org logo
Join Slack
Powered by
Day 15 solution thread :kotlin-intensifies:
# advent-of-code
a
Day 15 solution thread K
d
Looking forward to seeing your functional solution.
Copy code
private fun runProgram() {
    val last = mutableMapOf<Int,Int>()
    val previous = mutableMapOf<Int,Int>()

    last[2] = 1
    last[0] = 2
    last[1] = 3
    last[7] = 4
    last[4] = 5
    last[14] = 6
    last[18] = 7

    var wasfirst = true
    var current = 18
    var pos = 8
    while (pos <= 30000000) {
        if (wasfirst) {
            last[current] = pos - 1
            current = 0
            if (last.containsKey(0)) {
                previous[0] = last[0]!!
            }
            last[0] = pos
            wasfirst = false
        } else {
            val d = last[current]!! - previous[current]!!
            if (last.containsKey(d)) {
                previous[d] = last[d]!!
            } else {
                wasfirst = true
            }
            current = d
            last[d] = pos
        }
        pos++
    }

    println("Puzzla answer: ${current}")
}
a
Just trying to clean it up now 😄 Yours looks clean!
🙏 1
d
Hahaha -- oops left that 
d
in there - all my solutions start with single letter variables to save time. Forgot to change that one.
😄 1
a
My solution (MutableMap.insertOrAppend is a utility function)
Copy code
package aoc2020

import common.*

class Aoc2020Day15 : Problem(2020, 15) {
    val numbers = input.split(",").map { it.toInt() }

    val numberGenerator = sequence {
        val memo = mutableMapOf<Int, MutableList<Int>>()
        numbers.forEachIndexed { index, i -> memo.insertOrAppend(i, index); yield(i) }
        var current = numbers.last()
        var i = numbers.size
        while (true) {
            val currentIndices = memo.getValue(current)
            val difference = if (currentIndices.size != 1) currentIndices[currentIndices.lastIndex] - currentIndices[currentIndices.lastIndex - 1]
            else 0
            yield(difference)
            memo.insertOrAppend(difference, i)
            memo[difference] = memo[difference]!!.takeLast(2).toMutableList()
            current = difference
            i++
        }
    }


    override fun solvePart1(): Any {
        return numberGenerator.take(2020).last()
    }

    override fun solvePart2(): Any {
        return numberGenerator.take(30000000).last()

    }
}

fun main() {
    Aoc2020Day15().solve()
}
a
That was pretty straightforward today
Day 15
Just realised that I can simplify my code by using
Copy code
val num = counter - previousNumbers.getOrDefault(speak, counter)
j
I did the first approach storing prev entries in HashMap and it was... 2.5s in JVM, but over 5 minutes in JS-Browser. It's probably because Kotlin transpilation to JS is heavily flawed regarding to maps. Then I thought "f... it, memory is cheap". And preallocated IntArray(30000000). Works instantly under 0.6s both on JS and JVM Stupid puzzle today 😕
e
https://github.com/ephemient/aoc2020/blob/dcca540f34bcd04aa16de7fd5b2d386a1d5b9487/kt/src/main/kotlin/io/github/ephemient/aoc2020/Day15.kt map-based version in git history was a little more elegant, but either way this is very little code (although it did take quite a while to figure out)
really, this was all it took…
Untitled
n
Copy code
val input = listOf(8,0,17,4,1,12)

fun run(lastTurn: Int): Int {
    val state = mutableMapOf<Int, Int>().also { map ->
        input.subList(0, input.size-1).withIndex().associateTo(map) { it.value to it.index+1 }
    }
    var lastNumber = input.last()

    for (turn in (input.size) until lastTurn) {
        val curNumber = turn - state.getOrPut(lastNumber) { turn }
        lastNumber = curNumber
    }

    return lastNumber
}

fun part1() = run(2020)
fun part2() = run(30000000)
t
I ended up writing a sequence:
Copy code
class Day15(input: String) {

    private val startingNumbers = input.split(",").map { it.toInt() }

    fun solve(turns: Int): Int =
        memoryGame().drop(turns-1).first()

    private fun memoryGame(): Sequence<Int> = sequence {
        yieldAll(startingNumbers)
        val memory = startingNumbers.mapIndexed { index, i -> i to index }.toMap().toMutableMap()
        var turns = startingNumbers.size
        var sayNext = 0
        while(true) {
            yield(sayNext)
            val lastTimeSpoken = memory[sayNext] ?: turns
            memory[sayNext] = turns
            sayNext = turns - lastTimeSpoken
            turns++
        }
    }
}
f
b
not happy because it is slow
but it works
n
You can get a roughly x2 speedup simply by only accessing the cache once
Copy code
lastNum = cache[lastNum]?.let { pos - it } ?: 0L
        cache[oldNum] = pos
I had this initially too but you can have a single 
getOrPut
call instead
as a bonus it even looks nicer
b
I don't see how to replace that with a getorput
oh i see
nevermind
n
yeah it wasn't that obvious to me at first either
hmm actually now I'm doubting myself... 🙂
i could have sworn I ran it with getOrPut and got the same answer, but now I'm wondering how that can work, will need to double checkl ater
b
your map construction is complicated
there is a much simpler way
val map = input.mapIndexed { idx, it -> it to idx }.toMap().toMutableMap()
n
toMap.toMutableMap?
can't just do toMutableMap?
b
I don't think so
n
Anyhow, I didn't do it that way on purpose, I don't like creating the extra map
b
well you made a sublist…
n
yes
that doesn't create an extra list
creates a view
b
hmm
didn't know that, cool
n
Yeah, it's like a slice in python basically with more awkward syntax 🙂
I have been trying to write kotlin where I'm not dumping tons of extra copies of data structures around even if it is not necessary
Sorry it's not getOrPut, but simply put
that's needed
b
wouldn't mutableMapOf<Int,Int>().also { itputAll(list.mapIndexed { idx,it->it to idx})}
be as fast as your solution anyway?
put wouldn't work either
oh if I use ?:pos
yeah
n
yeah, I did 
turn - (state.put(lastNumber, turn) ?: turn)
or obviously 
state.put(lastNumber, turn)?.let { turn - it } ?: 0
b
makes me win ~500ms not bad
n
That's surprising, still takes me a good 5-6 seconds for part 2 even with this trick
b
oh takes 3 on my machine
(the full thing)
n
yeah makes sense. With your mapIndexed, you'll still have to insert it into the map afterwards though so I don't think you're gaining anything
I think you pretty much need to have 
associateTo
there unless there's another function that does that
b
what's your CPU?
n
that was on a laptop
i dunno, maybe an i7 or something
I didn't benchmark or anything, just looking at how long it says in grade 🙂
b
Copy code
fun
    val cache = mutableMapOf<Int, Int>().also { it.putAll(list.mapIndexed { idx, it -> it to idx }) }
    val num = turns - 1
    if (num < list.size) return list[num]
    var lastNum = list.last()
    (list.size - 1 until num).forEach { pos -> lastNum = pos - (cache.put(lastNum, pos) ?: pos) }
    return lastNum
}

fun main() {
    val input = listOf(9, 3, 1, 0, 8, 4)
    println(finalNumCached(input, 2020))
    println(finalNumCached(input, 30000000))
}
gradle tells me 3s but that's a ryzen 3700X that's a pretty fast machine
n
What would you name this function
Copy code
fun MutableMap<K, V>.foo(k: K, v: V) = put(k, v) ?: v
b
updateOrDefault?
also I can run it in ~2s by disabling the GC and giving it 2g of ram (Epsilon GC)
n
maybe updateAndDefault
it always does the update is the thing
getAndUpdate maybe
since it's doing the get first in the typical use case
b
yeah getThenUpdate
maybe And is clear enough though
n
I think maybe actually putOrDefault; in a vacuum it's less clear but given that 
put
already exists it makes sense
b
putWithDefault?
n
yeah that's probably better actually
👍
I love extension functions
been using this as well:
Copy code
fun <K, V> MutableMap<K, V>.update(k: K, transform: (V?) -> V) = set(k, transform(get(k)))
b
Using graalVM, 5.4s 😄
n
very useful, e.g. incrementing 
foo.update(key) { (it ?: 0) + 1}
for loop vs for each? Interesting. technically for each does not need to support break or continue really, right... though you could do qualified returns from the lambda I believe, so I'm not sure
b
no I deleted 😄
that was a mistake
I didn't use the same GC parameters that's why
n
hah ok
makes sense
b
they have the exact same performance
Using large pages I won another 500ms
I may reach the below 2s 😄
nope
too bad 😄
n
just use a giant array instead of a map
it's kind of gross because you need to preallocate it and if it's not big enough then it's no bueno
but it's pretty fast if it is big enough
b
1.1s
yep that's fast
n
hard to imagine how to really beat that at this point; it's an O(N) algorithm with just a couple of very cheap steps in the main loop
b
yeah in the jvm probably not
oh 0.7s
IntArray instead of Array
0.356s
using the epsilonGC and quite a few other optimizations (large pages, compressed class pointers and compressed oops)
I'll stop here, but probably using jaotc would go even faster
interesting, the few rust solutions I found are all slower than that
n
with an identical approach?
b
seems so I don't know rust enough
but they are preallocating yes
n
pretty strange. maybe they forgot to turn on optimizations 😂
a lot of people come to rust from languages like ruby and actually forget this
b
no I did compile it and turned them on
but yeah I was expecting it to be 2-5 times faster
but in term of number of operations (CPU measured using perf), solutions are pretty similar
and the code is small, so I expect the AOT to have optimized it pretty well
n
I wouldn't expect 5 times, the JVM tends to actually do well on this kind of microbenchmark
But it is strange it's not at least moderately faster
The big question is did they have hash table API so that they only have to go through it once
This problem is basically a hash table benchmark :-)
Unless of course they used Vec in which case it's definitely surprising
b
looks like vec to me
I couldn't find any solution that runs in less than 400ms
(in rust)
e
@bjonnh at least for my solution, Rust debug vs Rust release makes a huge difference
Untitled
using Linux's 
perf stat
to measure a bare-bones C solution I whipped up, I'm pretty sure it's not possible for me to do better than that on this hardware
Untitled
all the time is going into L1 cache misses
b
Yes I did run every code I found in rust as opt level 3
didn't even dare to try non optimized
@ephemient Can you give me your c solution so I test on my machine ? see how it compares to my kotlin optimized version?
e
b
that's fast 😄
with my input you are at 670 million instructions
my kotlin optimized version is 1 billion
so it is not that far
Perf says 350 ms for my kotlin solution, 342ms for your C version
e
perf stat -d
will give some more detail (such as L1 hit rates)
b
7.83% misses for the kotlin version 14.6% for your version
there is a slight difference that you are loading the file on disk, I hard coded the solution though
so that may play a little
e
tiny input file so that shouldn't account for much
so I'd estimate that JVM is touching more local memory to do its own housekeeping work, which isn't actually taking much more time
but the root of the problem is that there's a lot of data to work through and that is limited by hardware regardless of the language
b
(I compiled with -O3 -march=native for your program)
JVM I disabled the GC (epsilonGC)
interestingly, doing nums[x]=y for all my inputs adds 30ms to the program compared to reading the file
I'm a bit confused as why but it seems consistent
oh and also I'm running it two times in my kotlin program
didn't thought about that, I run it twice for 2020 and 30m
that's another optimization right here
e
well, in theory the extra branch could be bad
in practice it's always* predicted correctly
b
yeah the 2020 was so fast that it doesn't change much
I get the same time (within error range)
I could cheat and duplicate the code to remove the branch
no difference except an higher cache miss rate (but still within error)
11 Views
Open in Slack
PreviousNext
Powered by