https://kotlinlang.org logo
Join Slack
Powered by
:warning: Day 9 Solution Thread  :warning:
# advent-of-code
a
⚠️ Day 9 Solution Thread  ⚠️
d
Ready? Any predictions? I'm guessing new operations to boot code. Also, does your cover image also have a skipped line?
a
Ready! Also guessing it’ll add to boot code, but I’m not really prepared for it haha
Yes it does, and it’s bugging me 😄
d
that was pretty straight-forward.
a
Yeah it was
Accidentally misread part 2 and solved the wrong problem
d
my first run I added the first and the last in the order of the puzzle input, then I realized it said smallest and largest. Doh!
😄 1
BTW - lots of skipped rows now
a
Ha!
Wow.. is this water?
d
I'm thinking it's the North Pole -- maybe a map of Santa's movement?
a
@David Whittaker read part 2 as “find two contiguous numbers in the list that are both invalid” and solved that 😂
Hmm.. that would make sense? It is travel related
d
oh no!!!
a
Thought I had a clever solution for part 1 too haha
Copy code
val numbers = lines.map { it.toLong() }
val preamble = 25
override fun solvePart1(): Any {
    return (25..numbers.lastIndex).first { index ->
        numbers.subList(index - preamble, index).times(2).none { it.sum() == numbers[index] }
    }.let { numbers[it] }
}
p
@adamratzman Where does 
.times(2)
come from? I couldn't find it
a
ah, that’s an extension function I wrote to do a cartesian product x times on a list
Copy code
fun <T> List<T>.times(repetitions: Int, current: List<List<T>> = listOf()): List<List<T>> {
    return when {
        repetitions == 0 -> current
        current.isEmpty() -> times(repetitions - 1, map { listOf(it) })
        else -> {
            times(repetitions - 1, current.map { list ->
                map { value -> list + value }
            }.flatten())
        }
    }
}
@pavi2410
p
Cool! I feel Kotlin stdlib must have Python's itertools
a
Nope
Sadly
d
More literal triple loop - outside function calls 
find(i)
for each line number i:
Copy code
private fun find(i: Int): Boolean {
        for (j in i - 25 until i) {
            for (k in i - 25 until i) {
                if (j != k && lines[j] + lines[k] == lines[i]) {
                    return true
                }
            }
        }
        return false
    }
a
ooh I like that use of infix until
d
I need to get more fluent with functional grammars though so I can think the way you do
p
I couldn't think of it in any functional way
Copy code
for (i in 25..numbers.size) {
    val number = numbers[i]

    val preamble = numbers.drop(i - 25).take(25)

    var found = false
    for (a in preamble) {
        for (b in preamble) {
            if (a != b && a + b == number) {
                found = true
                continue
            }
        }
    }

    if (!found) {
        output = number
        break
    }
}
🎉 2
a
Ha! It’s all the same as long as it works & is readable, right
d
takes longer to type though...lol
a
Right 😂 My part 2 is a mix of functional/non-functional, need to clean it up
Functional part 2 (25 was just an arbitrary upper bound)
Copy code
override fun solvePart2(): Any {
    val toFind = solvePart1() as Long
    return (2..25).asSequence().map { size ->
        (0..numbers.lastIndex - size)
            .map { numbers.subList(it, it + size) }
            .find { it.sum() == toFind }
    }.first { it != null }!!.let { found -> found.minOrNull()!! + found.maxOrNull()!! }
}
j
I think I got it in very optimised O(n^2) complexity (can't say O(n) ofc but it fails very fast and goes to next index):
(part 1 is O(n), given that preamble length is constant)
e
I wanna try writing part 1 without windowed and run across the list in place, instead of creating the windows. But part 1 takes 0.2ms anyway. 20ms for part 2. https://github.com/edgars-supe/advent-of-code/blob/master/src/main/kotlin/lv/esupe/aoc/year2020/Day9.kt
j
Relatively straightforward, and a nice reuse of my 
pairs
extension function I wrote for day 1. Was a bit worried this approach would have performance issues but it runs fast enough. Also, for the first time I think this year, KotlinJS slightly outperforms the JVM!
Copy code
| Platform         | Average (ms)| Measurements (ms) |
| -----------------| ------------|------------------:|
| GraalVM          |  32.6 ± 36.3| `183, 68, 41, 25, 18, 19, 21, 19, 26, 20, 24, 18, 24, 20, 18, 20, 19, 18, 26, 17`|
| Node JS          |  32.5 ± 22.5| `118, 57, 59, 33, 32, 22, 24, 29, 21, 20, 20, 21, 21, 20, 24, 24, 21, 25, 21, 26`|
| Native           | 105  ±  3.7 | `103, 106, 106, 102, 109, 108, 100, 100, 105, 108, 100, 106, 114, 109, 107, 105, 106, 100, 107, 101`|
e
.windowed()
doesn't fit great here, since it always wants to construct a list of results
doing part 1 "by hand" is fine enough… the O(n) algorithm for part 2 just doesn't look as clean as the O(n³) that you could more easily write with built-in collections functions though
Untitled
j
Yeah, that's why I was worried about performance, but the list is small enough that the computational complexity doesn't ultimately bother me.
j
ok - here's the better part2. Sliding window of variable size, only one pass, O(n) complexity.
a
Part 2 solution using a single pass through the number:
Copy code
fun part2(numbers:List<Long>, target: Long): List<Long>{
    val queue = ArrayDeque(numbers)
    val window = ArrayDeque<Long>()
    var runningTotal = 0L

    while (runningTotal != target || window.size < 2){
        while (runningTotal < target || window.size < 2){
            val next = queue.removeFirst()
            runningTotal += next
            window.addLast(next)
        }
        while (runningTotal > target){
            runningTotal -= window.removeFirst()
        }
    }
    return window.toList()
}
t
My part 2 is pretty inefficient but I think easy to understand. Part 1 I was happy with. 🙂
Copy code
private fun List<Long>.preambleIsValid(): Boolean {
    val target = this.last()
    val subjects = this.dropLast(1).toSet()
    return subjects.any { target - it in subjects }
}
I would be very curious to see if that does not work for real inputs, it worked for mine.
a
@todd.ginsberg Do you need an additional check that (target -it) != it in your preambleIsValid() function?
t
That's the shortcut I took. I think according to "The two numbers will have different values", it implies that that can't happen. But I could just be optimistic with my reading of that.
a
I assumed that was a different rule
m
i
For the part 2, it may be useful to precompute prefix sums of the number list. Then you could compute the sum of any subrange instantly:
Copy code
val prefixSum = numbers.scan(0L) { acc, e -> acc + e }
for (start in numbers.indices) {
    for (end in start + 2..numbers.size) {
        val sum = prefixSum[end] - prefixSum[start]
        if (sum == outlier) {
            val range = numbers.subList(start, end)
            println(range.minOrNull()!! + range.maxOrNull()!!)
        }
    }
}
👍 1
b
is there any function that does
Boolean.ifTrue( f: ()->T): T ?
e
prefix sums can be used to bring the naive O(n³) solution down to O(n²), but there's an O(n) solution that doesn't require them
@bjonnh what would the (Any) parameter there be for?
b
well just to say, execute that thing
so not Any sorry
(corrected)
what's the O(n) solution, doing + and minus on the calculated sum (- the element that went out + the one that went in) ?
j
So something like 
fun <T> Boolean.ifTrueOrNull(f: () -> T): T = if (this) f() else null
? I don't think it's in the standard library, but if this is what you're talking about then there you have it 🙂
b
yeah yeah that's exactly what I thought about
thanks now I don't have to write it 😄
n
@bjonnh doesn't takeIf do that
ah, not exactly
Then O(N) solution, yeah, you don't use any data structure at all (except the list of data), just a start index, end index, and the current sum
the basic idea is that when the sum is too low, you push the end index, when its too high, you push the start index (and adjust the sum appropriately in either case)
it's good to prove to yourself that you can't miss the solution doing this; i think some people take it for granted but it's not completely trivial
i
The important precondition for using this heuristic is that all numbers should be positive (which they are in the current task)
j
I lost some time trying to figure out why it's safe. and yes, the "positivenes" is the key - list does not need to be sorted as long as the sum is sorted. after all we're searching for the sum here 🙂
enjoy the moving window visualisation 🙂 https://jakubgwozdz.github.io/advent-of-code-2020/day09/
❤️ 1
n
Yes, positive-ness is definitely necessary. The easiest way to convince yourself is to picture the solution already being there, say it's in the range [i, j). You can easily convince yourself that if endIndex < j, startIndex will never move past i, because at startIndex = i clearly the sum is too low and startIndex would not continue moving. Conversely, if startIndex < i, endIndex can never move past j, since at endIndex = j the sum would already be too large.
I suspect that a sufficiently "weird" condition on the subrange length might also make this approach trickier, or at leas tmake you want to examine the proof more carefully. The proof doesn't really need any adjustment for a length >= 2 condition but maybe if you had something weird like list.size is divisible by 3, you'd need to be careful
e
I don't think that's a problem - the sliding window should hit every window of the desired sum, weird length conditions just mean that you should continue sliding if they're not satisfied
8 Views
Open in Slack
PreviousNext
Powered by