https://kotlinlang.org logo
Join Slack
Powered by
:warning: Day 3 Solution Thread - here be spoilers...
# advent-of-code
j
⚠️ Day 3 Solution Thread - here be spoilers ⚠️
Today's puzzle is not that hard, but I'm thinking of the most Kotlin-y way to code it, and here's what I did so far:
Copy code
package advent2020.day03

fun part1(input: String): String {
    val lines = input.trim().lines()

    val result = countTrees(lines, 3, 1)

    return result.toString()
}

fun part2(input: String): String {
    val lines = input.trim().lines()

    val moves = listOf(1 to 1, 3 to 1, 5 to 1, 7 to 1, 1 to 2)
    val result = moves.map { countTrees(lines, it.first, it.second) }.reduce { a, b -> a * b }

    return result.toString()
}

private fun countTrees(lines: List<String>, x: Int, y: Int): Long = lines
    .filterIndexed { index, line -> index % y == 0 && line[index / y * x % line.length] == '#' }
    .count().toLong()
I don't want it to be overcomplicated with coroutines, just most readable, most clean and something that I can show as "here's how nice it can be coded in Kotlin"
👍 1
a
That's very neat. I did something v similar using a fold across the rows rather than a filter.
Copy code
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.
j
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
My solution. It's okay, but not very efficient. In particular using a 
List<Position>
is a terrible data structure and lookup performance sucks. I might rewrite it but then again it's fast enough for now
e
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).
t
Copy code
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.
👍 1
I guess now that I look at it, the sequence really could just be a list, but I'm going to keep it in because it's done and it's a nice opportunity to explain the concept.
e
tried a few things, but making a single pass over the input was the fastest
Untitled
e
@ephemient You could do 
return trees.reduce { acc, elem -> acc * elem }
e
@Edgars no, it's necessary to convert Int -> Long in order to not overflow the result
e
LongArray
instead of 
IntArray
then? 😄 Would there be any appreciable performance impact from that?
j
@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:
Copy code
val positions = generateSequence(Position.ORIGIN) {
    it.move(dx, dy)
}
My new attempt, 
CharMap
is a utility class that takes care of parsing a map and lookups, and knows how to 'wrap around' when needed
t
Nice! I forgot about 
generateSequence
. I might change to use that, thanks for the tip!
👍 1
e
@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)
@Joris PZ any reason for 
val p03 = suspend {
over 
suspend fun p03() {
?
j
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:
Copy code
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
b
j
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.
Copy code
| 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` |
b
That's the same code for all 3?
that's concerning
j
Yep, identical code
t
Huh, that sure is interesting that Node DNF'd
j
Hold on before we call JetBrains, I need to doublecheck if this isn't PEBKAC 🙂
e
@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
j
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
t
n
Today's challenge has made me realize another major Kotlin wart... using 32 bit integers everywhere by default
j
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.
Copy code
| 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` |
On that note, I hate Gradle....
b
@Nir why were 32 bit integers an issue for you?
n
have you done the AOC for today?
j
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
n
hah I didn't realize that AOC gives different input to different people, I guess that makes sense
silly me
b
oh the multiplication did overflow? I see
n
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
e
neither of those is true
n
what
e
C++ depends on the platform - int is still 32-bit on 64-bit platforms
n
try to reread
b
Nir what's your reference for that?
e
heck, even long is still 32-bit on Windows, due to history
n
C++ doesn't use int in its standard library, generally
except for the parts that come from C
it uses things like std:;size_t
my reference is writing C++ all day every day for 7 years
size_t is pretty much always 64 bits on any 64 bit native platform
b
oh that's what you mean
e
my experience with C++ is largely Qt
and they are not using size_t, it's int
n
Qt is not the standard library
so basically, the statements are both true
t
Heh, I just had a coworker mention he had to use Longs for his input.
e
it's not STL, no, but it is effectively standard for a huge portion of C++ development
n
And Rust uses usize
This is what The Rust Reference has to say about usize : usize and isize have a size big enough to contain every address on the target platform. For example, on a 32 bit target, this is 4 bytes and on a 64 bit target, this is 8 bytes. Note that the phrasing doesn't exclude sizes other than 4 bytes or 8 bytes.Aug 23, 2019
lol no it's not, I said standard library
e
STL isn't the only standard library out there, and I've worked in C++ projects without it.
n
....
it's literally the C++ standard library, and both the statements are quite literally true.
A single library maybe used by ~10% of developers in a language doesn't make it the "standard library", that term has a meaning
b
I'm not shocked with kotlin using Int for 32 and Long for 64
n
chocked?
does that mean you don't really mind?
b
I like it to be consistent that's all
j
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/
Since Python 3 there is no longer simple integer type, and all integers are represented as a bignum.
I guess for Kotlin being compatible with Java's Int and Long is rather crucial
n
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
Also, what's with the weird defensiveness of Kotlin by some of the people in this slack, sheesh. Some people here seem to be willing to fight tooth and nail just to avoid admitting something is a wart... all languages have them.
e
variable-sized types lead to portability issues
https://futhark-lang.org/ for example, uses 64-bit ints everywhere, even on 32-bit platforms
whether you choose 32-bit or 64-bit as the native integer type, it is still better than "oh it works for me, sorry it's broken for you" variable sized types
👆 1
b
You can't have 64-bit indexed arrays in java anyway
(not natively)
e
there's good reasons to keep using 32-bit pointers even on 64-bit platforms - hence compressed oops, x32-abi, etc.
n
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.
b
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
n
If your goal is maximum portability, over maximum performance, then simply being consistent is better
Yeah, it's different for different people, I agree.
Probably too many scope functions for some peoples taste, but fun 🙂 :
Copy code
package day3

import utils.*

fun getData() = (aocDataDir / "day3.txt").useLines { lines ->
    lines.map { line -> line.map { it == '#'} }.toList()
}

fun List<List<Boolean>>.countTrees(down: Int, right: Int) = asSequence()
    .withIndex().mapNotNull { if (it.index % down == 0) it.value else null }
    .withIndex()
    .count { (index, row) -> row[right * index % row.size] }


fun part1() = getData().countTrees(1, 3).also { println(it) }

fun part2() = getData().run { sequenceOf(1 to 1, 3 to 1, 5 to 1, 7 to 1, 1 to 2)
    .map { (right, down) -> countTrees(down, right).also { println(it) } }
    .fold(1L) { x, y -> x * y }
    .also { println("Product: $it") }
}
a
My solution:
Copy code
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")
}
Note that I refactored part 1 after completing part 2 lol
n
yeah me too
originally my part1 used sequences, and ended up computing the solution as it iterated through the file, never kept everything in memory at once
then in part2 that looked silly 🙂 I'll probably not do that anymore during AOC, doesn't seem like making inputs so huge that avoiding storing them is going to be the direction theyt ake
a
Ha, yeah makes sense
I messed up at first and forgot that the sequence repeated
Took 15 minutes to figure out I needed to add % 3
n
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
Copy code
fun List<List<Boolean>>.countTrees(down: Int, right: Int) = asSequence()
    .filterIndexed { i, _ -> i % down == 0 }
    .withIndex()
    .count { (index, row) -> row[right * index % row.size] }
Improved version of the function I wrote above with mapNotNull
a
I like it!
j
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 🙂
❤️ 1
b
ok just got time to get at it
2 Views
Open in Slack
PreviousNext
Powered by