https://kotlinlang.org logo
Join Slack
Powered by
And we're off! Are there any specific rules in thi...
# advent-of-code
j
And we're off! Are there any specific rules in this channel about spoilers? My solutions and performance measurements can be found at https://github.com/jorispz/aoc-2018, and I'll be posting the performance results in a thread from this message for those who are interested
Today's puzzle shows quite a difference between the platforms, with native an order of magnitude slower than JVM and Node. While this was a common pattern in the preparations, usually the changes aren't quite so dramatic:
Copy code
JVM     97,  18,  52,  11,  39,  16,  29,  14,  27,  14,  12,  13,  15,  49,  15,  14,  16,  16,  53,  11,  11,  11,  12,  10,  12
JS     102,  83,  61,  83,  71,  65,  62,  53,  81,  45,  71,  82,  87,  57,  46, 108,  59,  70,  49,  56, 147,  58,  51,  95,  75 
MinGW  447, 435, 447, 420, 390, 408, 452, 419, 426, 395, 403, 453, 406, 407, 437, 407, 439, 426, 380, 415, 397, 432, 394, 460, 442
a
Just love Kotlin's ability to generate infinite sequences 🙂
j
Ha, I just updated my solution to add this little utility function 🙂
Copy code
fun <T> Sequence<T>.infinite() = sequence {
    while (true) {
        yieldAll(this@infinite)
    }
}
a
That looks very familiar 🙂
s
Hah, I ended up in exactly the same spot!
Copy code
fun <T> List<T>.loopForever() = sequence { while (true) yieldAll(this@loopForever) }
Very handy extension for sure
t
I'm still cleaning up my code, but my sequence looks a bit different than yours does... (I check for empty):
Copy code
fun <T> List<T>.toInfiniteSequence(): Sequence<T> = sequence {
    if(this@toInfiniteSequence.isEmpty()) {
        return@sequence
    }
    while(true) {
        yieldAll(this@toInfiniteSequence)
    }
}
👍 1
I'm trying to find a way to do this without side effects (maintaining the sum and frequencies seen) but don't want to resort to recursion. I'll probably publish it as-is.
s
Yeah, I spent a while thinking about that same issue. In the end I hid the side effects in an extension rather than eradicating them.
Copy code
val part2 = frequencyShifts
    .loopForever()
    .accumulate(Int::plus)
    .firstRepeat()
🤷‍♂️
t
Ah, nice
I'm pretty close on a not ugly recursive function. I might go with that. 😄
😻 1
Works for sample input anyway... not so much for Actual Input.
😬 1
k
I kept it "old-school" today:
Copy code
println(numbers.sumBy { it })

val seen = mutableSetOf(0)
var curr = 0
outer@while (true) {
    for (number in numbers) {
        curr += number
        if (!seen.add(curr)) {
            println(curr)
            break@outer
        }
    }
}
👍 1
s
Is there an advantage to using 
sumBy
rather than 
sum
there?
k
Nope that's a mistake from when I still did 
.toInt
there simple smile
s
Ah, makes sense!
a
Think my solution is pretty close to Stuart's.
Copy code
fun firstRepeatedFrequency(frequencyShifts: List<Int>): Int {
    val prevFrequencies = mutableSetOf<Int>()
    val frequencies = frequencyShifts.asInfiniteSequence().accumulate()
    return frequencies.first { !prevFrequencies.add(it) }
}
k
accumulate
is something you wrote yourself too, right?
a
Yep, it's quick & dirty. Think Stuart has a better implementation which allows you to pass in the operator.
Copy code
fun Sequence<Int>.accumulate() : Sequence<Int> = sequence {
    var value = 0
    forEach {
        value += it
        yield(value)
    }
}
k
Then I think your solution fails for (1,-1) simple smile
a
Probably as I not initialising the frequencies with a zero. Is that a test case?
k
Ah looks like there's one like it: 
+1, +1, -2
results in 
0
I'm just being pedantic though.
a
+1, -1 is one of the test cases so I have failed 🙂
s
Yeah my implementation is more general but feels awkward:
Copy code
fun <T> Sequence<T>.accumulate(operation: (accumulated: T, next: T) -> T): Sequence<T> {
    val iterator = iterator()

    if (!iterator.hasNext()) return emptySequence()

    return sequence {
        var accumulated = iterator.next().also { yield(it) }

        for (next in iterator) {
            accumulated = operation(accumulated, next)
            yield(accumulated)
        }
    }
}
k
You could have made something fold-like I guess.
s
Ah, sequence has a fold so yeah, that might be nicer!
t
This is what I have for part 2. Not happy with the side effects, but the recursive solution seems just as clunky with default args that are complicated...
Copy code
fun solvePart2(): Int {
        val frequencies = mutableSetOf(0)
        var sum = 0
        return input.toInfiniteSequence()
            .map {
                sum += it
                sum
            }
            .first { !frequencies.add(it) }
    }
Finally able to focus on this, been running errands all morning! Doesn't the world realize AoC is here! 🙂
Also tried the fold thing but breaking out feels wrong too.
Oh! I'm just super impatient. Recursive does work, it just takes FOREVER (25s or so). 😄
At least I'm not going crazy for that reason.
k
Recursion: complicated and slow
t
Eh. Sometimes it's complicated. I think it has a place in some solutions. Not this one though. I'll live with the side effects. The fold solution was even uglier and more complicated.
Stupid bitbucket/ssh issues while pushing my blog update slowed me way down today. But I got it done. 🙂 https://todd.ginsberg.com/post/advent-of-code/2018/day1/
t
i couldn't find happiness with the stdlib or extension functions, so i just ended up with a while:
Copy code
val calibrations = File("input/day1_input.txt").readLines().map { it.toInt() }
val frequencies = mutableSetOf<Int>()
var count = 0
var frequency = 0
while (true) {
    frequency += calibrations[count % calibrations.size]
    if (frequencies.contains(frequency)) {
        return println("part2: $frequency")
    }
    frequencies.add(frequency)
    count++
}
m
@tipsy I believe you can just write
Copy code
if (!frequencies.add(frequency)) return println("part2: $frequency")
and replace 
while
and 
count
with 
for (count in 0..Int.MAX_VALUE)
11 Views
Open in Slack
PreviousNext
Powered by