⚠️ Day 3 Solution Thread - here be spoilers ⚠️

That's very neat. I did something v similar using a fold across the rows rather than a filter.

fun List<String>.checkSlope(angle: Int) = this.fold(Pair(0,0L)){ acc, row -> Pair( acc.first + angle, acc.second + row.isTree(acc.first)) }.second

Used a filter to extract out the rows that I didn't want for the case where we only looked at even rows.

Hey @Jakub Gwóźdź do you mind renaming this thread to ⚠️ Day 3 Solution Thread - here be spoilers ⚠️? It really helps people find these solution threads easily

https://github.com/edgars-supe/advent-of-code/blob/master/src/main/kotlin/lv/esupe/aoc/year2020/Day3.kt I'm always thorn between writing efficient code or something that I won't get a headache trying to comprehend the next day. I'm okay with the whole solution taking 3ms (init, part 1 and part 2, avg. of 18k runs).

class Day03(private val forest: List<String>) {

    private val width: Int = forest.first().length
    private val height: Int = forest.size

    fun solvePart1(): Int =
        evaluateSlope(3 to 1)

    fun solvePart2(): Int =
        listOf(1 to 1, 3 to 1, 5 to 1, 7 to 1, 1 to 2)
            .map { evaluateSlope(it) }
            .reduce { a, b -> a * b }

    private fun evaluateSlope(ratio: Pair<Int,Int>) =
        slope(ratio).count { it in forest }

    private fun slope(ratio: Pair<Int,Int>): Sequence<Pair<Int, Int>> = sequence {
        var latest = Pair(0, 0)
        while (latest.second < height) {
            yield(latest)
            latest += ratio
        }
    }

    private operator fun Pair<Int,Int>.plus(that: Pair<Int,Int>): Pair<Int,Int> =
        Pair(this.first+that.first, this.second+that.second)

    private operator fun List<String>.contains(location: Pair<Int, Int>): Boolean =
        this[location.second][location.first % width] == '#'
}

Pretty happy with that.

tried a few things, but making a single pass over the input was the fastest

@ephemient You could do

return trees.reduce { acc, elem -> acc * elem }

@Edgars no, it's necessary to convert Int -> Long in order to not overflow the result

LongArray

instead of

IntArray

then? 😄 Would there be any appreciable performance impact from that?

@todd.ginsberg I just finished rewriting mine as I wasn't very pleased with it, and mine uses sequences now too. You can make your implementation a bit neater by using

generateSequence

, which saves you from doing the 'folding' by hand. From my own code:

val positions = generateSequence(Position.ORIGIN) {
    it.move(dx, dy)
}

Nice! I forgot about

generateSequence

. I might change to use that, thanks for the tip!

@Edgars hmm, in theory it takes ... 20 more bytes of memory, but if there's any performance difference, it's below the noise floor of what JMH can detect (I just tested)

Yes, there is! I am using a

Runner

that takes the day and the number of iterations, and runs it a number of times to do some crude performance measurements:

println("Running day $day $repeat times on platform $platform")
val puzzles = listOf(p01, p02, p03)
val times = (1..repeat).map {
    measureNanos {
        val p = puzzles[day - 1]
        p()
    }
}
println("Done")

If

p03

where just a fun, I would have to have a

when

statement here to map the day to the correct solution, I found this slightly easier

My solution: https://github.com/bjonnh/advent_of_code/blob/master/src/main/kotlin/y2020/day03/main.kt

These are the timings for my last implementation of day 3. Interestingly, the JS version errored out with an IndexOutOfBoundsException, while JVM and native finished correctly. All times in ms.

| JVM (OpenJDK 11) | 5.7 ± 11.1   | `53,  7,  4,  4,  2,  5,  5,  4,  3,  3,  3,  1,  1,  1,  1,  1,  1,  1,  1,  1` |
| Node JS          | DNF          | `DNF`                                                                            |
| Native           | 25.2 ± 6.4   | `20, 20, 29, 31, 22, 17, 36, 17, 30, 26, 20, 18, 31, 22, 33, 27, 25, 18, 36, 17` |

That's the same code for all 3?

Yep, identical code

Huh, that sure is interesting that Node DNF'd

Hold on before we call JetBrains, I need to doublecheck if this isn't PEBKAC 🙂

@Joris PZ if

p03

were

fun

, you could get a lambda with

::p03

. but I suppose it doesn't matter much, it just looks unusual

Ah that's right, I guess that's a bit more idiomatic. This is something I set up three years ago and never really touched again

Code: https://github.com/tginsberg/advent-2020-kotlin/blob/main/src/main/kotlin/com/ginsberg/advent2020/Day03.kt Blog: https://todd.ginsberg.com/post/advent-of-code/2020/day3/

Today's challenge has made me realize another major Kotlin wart... using 32 bit integers everywhere by default

Ah, there was something else going on with the NodeJS DNF. I switched to the new IR compiler backend for NodeJS, but didn't test properly and was just running an earlier build. The new build somehow doesn't generate a JS file I can use, so I switched back to the old compiler and now it just works.

| Platform         | Average (ms)           | Measurements (ms) |
| -----------------| ----------------------:|------------------:|
| JVM (OpenJDK 11) | 5.7±11.1   | `53, 7, 4, 4, 2, 5, 5, 4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1` |
| Node JS          | 13.1±17.0  | `73, 41, 34, 11, 7, 9, 6, 10, 6, 7, 6, 5, 6, 8, 5, 3, 3, 4, 4, 4` |
| Native           | 25.2±6.4   | `20, 20, 29, 31, 22, 17, 36, 17, 30, 26, 20, 18, 31, 22, 33, 27, 25, 18, 36, 17` |

@Nir why were 32 bit integers an issue for you?

have you done the AOC for today?

That bit me too, but apparently it depends on the specific input - I spent 30 minutes not understanding why my solution worked on everything but part 2 of the actual input, but for some of my colleagues this wasn't an issue as their result didn't overflow

hah I didn't realize that AOC gives different input to different people, I guess that makes sense

oh the multiplication did overflow? I see

But yeah, it makes you wince to see such bad defaults in Kotlin. Even in much more performance anal languages like C++ and Rust, you typically see 64 bit integers as the default in the standard library

neither of those is true

what

C++ depends on the platform - int is still 32-bit on 64-bit platforms

try to reread

Nir what's your reference for that?

heck, even long is still 32-bit on Windows, due to history

C++ doesn't use int in its standard library, generally

oh that's what you mean

my experience with C++ is largely Qt

Qt is not the standard library

Heh, I just had a coworker mention he had to use Longs for his input.

it's not STL, no, but it is effectively standard for a huge portion of C++ development

And Rust uses usize

STL isn't the only standard library out there, and I've worked in C++ projects without it.

....

I'm not shocked with kotlin using Int for 32 and Long for 64

chocked?

I like it to be consistent that's all

A colleague of mine is using Python 3 and he was very smug about Python having arbitrary-precision integers https://rushter.com/blog/python-integer-implementation/

Yeah, I mean I can accept that it's the right choice for Kotlin given the JVM and Java of it all. It's just annoying, it's not a decision that would make any sense in a vacuum (for a language that's just about entirely targeting 64 bit systems

variable-sized types lead to portability issues

You can't have 64-bit indexed arrays in java anyway

there's good reasons to keep using 32-bit pointers even on 64-bit platforms - hence compressed oops, x32-abi, etc.

variable sized types are not a great decision for most programming languages, yes. But in ultra high performance programming languages, it's a pretty logical choice. But I'd disagree that consistent 32 bit is better necessarily, depends for whom. For me, all the C++ I ever write is targeting systems where size_t is 64 bits, so I get the benefits of 64 bit integers in my standard library, and avoid exactly the kind of bug I ran into today with Kotlin, for free.

I'm writing scientific software, having variable sized types is a huge pain (for me). because you have to put shims for all kind of platforms

If your goal is maximum portability, over maximum performance, then simply being consistent is better

My solution:

private val input = readInput("input3.txt")

fun main() {
    var part1 = 1L
    var part2 = 1L

    val lines = input.split("\n")

    for ((x, y) in listOf(3 to 1)) {
        var currentX = 0
        var currentY = 0

        var temp = 0

        while (currentY< lines.size) {
            if (lines[currentY][currentX % lines[0].length] == '#') temp++
            currentX += x
            currentY += y
        }
        part1 *= temp

    }

    for ((x, y) in listOf(1 to 1, 3 to 1, 5 to 1, 7 to 1, 1 to 2)) {
        var currentX = 0
        var currentY = 0

        var temp = 0

        while (currentY< lines.size) {
            if (lines[currentY][currentX % lines[0].length] == '#') temp++
            currentX += x
            currentY += y
        }
        part2 *= temp

    }

    println("Part 1: $part1")
    println("Part 2: $part2")
}

yeah me too

Ha, yeah makes sense

when I switched to the non-lazy solution I messed up how the filtering works by rows as you move down, this was after I had the righ tanswer, a bit funny 🙂 I discovered

filterIndexed

though which is super nice

I like it!

Aaaand because I need to stay at my mac to not let it go to sleep (because of reasons), I also prepared visualisation to https://jakubgwozdz.github.io/advent-of-code-2020/day03/ 🙂 Hey HTML is fun. Unless it's not. Then it's nightmare 🙂

ok just got time to get at it