https://kotlinlang.org logo
j

Jakub Gwóźdź

12/03/2020, 8:25 AM
⚠️ 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

andyb

12/03/2020, 8:43 AM
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

Joris PZ

12/03/2020, 9:14 AM
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

Edgars

12/03/2020, 9:45 AM
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

todd.ginsberg

12/03/2020, 1:43 PM
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

ephemient

12/03/2020, 2:43 PM
tried a few things, but making a single pass over the input was the fastest
e

Edgars

12/03/2020, 3:10 PM
@ephemient You could do
return trees.reduce { acc, elem -> acc * elem }
e

ephemient

12/03/2020, 3:11 PM
@Edgars no, it's necessary to convert Int -> Long in order to not overflow the result
e

Edgars

12/03/2020, 3:12 PM
LongArray
instead of
IntArray
then? 😄 Would there be any appreciable performance impact from that?
j

Joris PZ

12/03/2020, 3:15 PM
@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

todd.ginsberg

12/03/2020, 3:17 PM
Nice! I forgot about
generateSequence
. I might change to use that, thanks for the tip!
👍 1
e

ephemient

12/03/2020, 3:18 PM
@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

Joris PZ

12/03/2020, 3:24 PM
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
j

Joris PZ

12/03/2020, 3:33 PM
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

bjonnh

12/03/2020, 3:33 PM
That's the same code for all 3?
that's concerning
j

Joris PZ

12/03/2020, 3:34 PM
Yep, identical code
t

todd.ginsberg

12/03/2020, 3:34 PM
Huh, that sure is interesting that Node DNF'd
j

Joris PZ

12/03/2020, 3:35 PM
Hold on before we call JetBrains, I need to doublecheck if this isn't PEBKAC 🙂
e

ephemient

12/03/2020, 3:38 PM
@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

Joris PZ

12/03/2020, 3:39 PM
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
n

Nir

12/03/2020, 3:47 PM
Today's challenge has made me realize another major Kotlin wart... using 32 bit integers everywhere by default
j

Joris PZ

12/03/2020, 3:48 PM
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

bjonnh

12/03/2020, 3:52 PM
@Nir why were 32 bit integers an issue for you?
n

Nir

12/03/2020, 3:52 PM
have you done the AOC for today?
j

Joris PZ

12/03/2020, 3:55 PM
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

Nir

12/03/2020, 3:56 PM
hah I didn't realize that AOC gives different input to different people, I guess that makes sense
silly me
b

bjonnh

12/03/2020, 3:56 PM
oh the multiplication did overflow? I see
n

Nir

12/03/2020, 3:56 PM
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

ephemient

12/03/2020, 3:58 PM
neither of those is true
n

Nir

12/03/2020, 3:58 PM
what
e

ephemient

12/03/2020, 3:58 PM
C++ depends on the platform - int is still 32-bit on 64-bit platforms
n

Nir

12/03/2020, 3:58 PM
try to reread
b

bjonnh

12/03/2020, 3:58 PM
Nir what's your reference for that?
e

ephemient

12/03/2020, 3:58 PM
heck, even long is still 32-bit on Windows, due to history
n

Nir

12/03/2020, 3:58 PM
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

bjonnh

12/03/2020, 3:59 PM
oh that's what you mean
e

ephemient

12/03/2020, 4:00 PM
my experience with C++ is largely Qt
and they are not using size_t, it's int
n

Nir

12/03/2020, 4:00 PM
Qt is not the standard library
so basically, the statements are both true
t

todd.ginsberg

12/03/2020, 4:00 PM
Heh, I just had a coworker mention he had to use Longs for his input.
e

ephemient

12/03/2020, 4:01 PM
it's not STL, no, but it is effectively standard for a huge portion of C++ development
n

Nir

12/03/2020, 4:01 PM
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

ephemient

12/03/2020, 4:02 PM
STL isn't the only standard library out there, and I've worked in C++ projects without it.
n

Nir

12/03/2020, 4:02 PM
....
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

bjonnh

12/03/2020, 4:03 PM
I'm not shocked with kotlin using Int for 32 and Long for 64
n

Nir

12/03/2020, 4:03 PM
chocked?
does that mean you don't really mind?
b

bjonnh

12/03/2020, 4:04 PM
I like it to be consistent that's all
j

Joris PZ

12/03/2020, 4:05 PM
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

Nir

12/03/2020, 4:07 PM
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

ephemient

12/03/2020, 4:09 PM
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

bjonnh

12/03/2020, 4:13 PM
You can't have 64-bit indexed arrays in java anyway
(not natively)
e

ephemient

12/03/2020, 4:13 PM
there's good reasons to keep using 32-bit pointers even on 64-bit platforms - hence compressed oops, x32-abi, etc.
n

Nir

12/03/2020, 4:14 PM
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

bjonnh

12/03/2020, 4:14 PM
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

Nir

12/03/2020, 4:15 PM
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

adamratzman

12/03/2020, 8:07 PM
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

Nir

12/03/2020, 8:09 PM
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

adamratzman

12/03/2020, 8:26 PM
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

Nir

12/03/2020, 8:31 PM
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

adamratzman

12/03/2020, 9:05 PM
I like it!
j

Jakub Gwóźdź

12/04/2020, 4:42 PM
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

bjonnh

12/07/2020, 8:24 PM
ok just got time to get at it
2 Views