https://kotlinlang.org logo
Join SlackCommunities
Powered by
<Advent of Code 2021 day 5> :thread:
# advent-of-code
a
d
Ok I brute-forced y=mx+b. I'm sure there's an easier way.
s
e
Just do what the problem says. Mark those points in 2D array.
d
Is there another data structure we can use instead of a 2D array?
e
You can also map coordinate to count.
Btw, with such a map you can have the whole solution as a functional pipeline from input to answer.
m
m
@elizarov Just refactored my solution a bit, now it’s one chain of calls for both solutions in one. 🙂
Copy code
fun main() = generateSequence(::readLine).toList().day05().let { (p1, p2) -> println(p1); println(p2) }

fun List<String>.day05() = map { row -> row.replace(" -> ", ",").split(",").map { it.toInt() } }
    .let { listOf(it.filter { (x1, y1, x2, y2) -> x1 == x2 || y1 == y2 }, it) }
    .map { lines -> lines.points().groupingBy { it }.eachCount().count { it.value > 1 } }

private fun List<List<Int>>.points() = flatMap { (x1, y1, x2, y2) ->
    sequence {
        var pos = x1 to y1
        while (true) {
            yield(pos)
            if (pos == x2 to y2) break
            pos = pos.let { (x1, y1) -> closerTo(x1, x2) to closerTo(y1, y2) }
        }
    }
}

private fun closerTo(a: Int, b: Int) = when {
    a > b -> a - 1
    a < b -> a + 1
    else -> a
}
e
I'm using a map of coordinates to counts. performance isn't great, though. I implemented a solution using bit-manipulation in Haskell for a 2x speedup there, I'm considering porting it over to see how it'll compare… https://github.com/ephemient/aoc2021/blob/main/kt/src/commonMain/kotlin/com/github/ephemient/aoc2021/Day5.kt
p
You are all too fast...I did not start todays task until now😂 So will compare later
p
e
This is probably not very optimized. Naive implementation which turned out good enough 🙂 https://github.com/Kantis/aoc2021/blob/main/src/main/kotlin/day05.kt
e
m
refactored and tinified my code:
Copy code
typealias Point = Pair<Int, Int>
operator fun Point.rangeTo(other: Point): List<Point>{
    val yDiv = other.first - first
    val xDiv = other.second - second
    return List(maxOf(abs(yDiv), abs(xDiv)) + 1) { index -> first + yDiv.sign * index to second + xDiv.sign * index }
}

object Day5 : Challenge("--- Day 5: Hydrothermal Venture ---") {
    val parsed = input.split("""[^(\d+)]+""".toRegex()).map(String::toInt).chunked(4)

    override fun part1() = solve(diagonals = false)
    override fun part2() = solve(diagonals = true)

    private fun solve(diagonals: Boolean) = parsed
        .filter { (x1, y1, x2, y2) -> diagonals || x1 == x2 || y1 == y2 }
        .flatMap { (x1, y1, x2, y2) -> (y1 to x1)..(y2 to x2) }
        .groupingBy { it }.eachCount().values.count { it > 1 }
}
k
t
p
t
I woke up late and ran errands this morning and am now about to start a road trip so I'll look at other solutions tonight when I get in. Today was fun, I like my solution quite a bit: • Blog • Code
❤️ 2
m
@todd.ginsberg 
.map { .. }.flatten()
could just be 
.flatMap { .. }
t
Doh! You know what? I was using 
mapNotNull
before and it didn’t have a 
flatMapNotNull
and when I changed my impl to not have a null list (refactoring!) I just spaced on that. Thanks Marcin. Racing to get out the door but I’ll correct it later! 🙂
😄 2
p
Even spending on weekend time for writing blog 👍
e
you don't need a 
flatMapNotNull
, just return empty from the lambda block. or make a wrapper if you want to,
Copy code
inline fun <T, R> Iterable<T>.flatMapNotNull(transform: (T) -> Iterable<R>?): List<R> = flatMap { transform(it) ?: emptyList() }
👍🏻 1
p
m
@Michael de Kaste Awesome! What did your code look like when you had first solved the challenge - did you already have that range idea? EDIT: One tiny thing that strikes me as confusing: Your choice to make y the first element in the Pair makes the flatMap lambda seem wrong (different order for x and y). 🙂
Got rid of my when clause … it dawned on me that it can be replaced with the good old compareTo method from Java. Now down to 16 lines total for the solution, while it should hopefully still be quite readable 🙂
Copy code
fun main() = generateSequence(::readLine).toList().day05().let { (p1, p2) -> println(p1); println(p2) }

fun List<String>.day05() = map { row -> row.replace(" -> ", ",").split(",").map { it.toInt() } }
    .let { listOf(it.filter { (x1, y1, x2, y2) -> x1 == x2 || y1 == y2 }, it) }
    .map { lines -> lines.points().groupBy { it }.count { it.value.size > 1 } }

private fun List<List<Int>>.points() = flatMap { (x1, y1, x2, y2) ->
    sequence {
        var pos = x1 to y1
        while (true) {
            yield(pos)
            if (pos == x2 to y2) break
            pos = pos.let { (x1, y1) -> x1 + x2.compareTo(x1) to y1 + y2.compareTo(y1) }
        }
    }
}
👍 1
e
oh that looks more direct than the 
(x1 - x0).sign
I used. but I'm not sure if 
compareTo
guarantees that it return -1, 0, 1? I thought it was only required to return <0, 0, >0
m
^ Fair point. The contract just says negative/positive integer, but then the javadoc of the method refers to the sgn function. I don’t think the current implementation will ever change for Integers, so I’m going with it in the context of AoC. One could always add 
.sign
for additional assurance 🙂
m
@Michael Böiers I always prefer y -> x in my coordinates in whatever assignment or puzzle I get, this is so I personally never get confused while programming. And yeah, having made an open range implementation for my work, the first thing I thought of was to make it a rangeTo thing, makes it very readable (according to my own experience ofcourse)
👍 1
m
Down to 9 lines, replaced the sequence/yield construction with generateSequence. 🙂
Copy code
fun main() = generateSequence(::readLine).toList().day05().let { (p1, p2) -> println(p1); println(p2) }

fun List<String>.day05() = map { row -> row.replace(" -> ", ",").split(",").map { it.toInt() } }
    .let { listOf(it.filter { (x1, y1, x2, y2) -> x1 == x2 || y1 == y2 }, it) }
    .map { lines -> lines.points().groupBy { it }.count { it.value.size > 1 } }

private fun List<List<Int>>.points() = flatMap { (x1, y1, x2, y2) ->
    generateSequence(x1 to y1) { (x, y) -> if (x to y == x2 to y2) null else x + x2.compareTo(x) to y + y2.compareTo(y) }
}
t
Neat. I had no idea about the 
sign
function. Cool!
d
e
now that I notice, this day actually marks an interesting turning point in my repository: there's enough computation time going on that JVM's higher throughput performance overcomes its longer startup time, and makes the my full Kotlin/JVM program execution faster than the full Kotlin/Native program execution (it was the other way around up to day 4) https://ephemient.github.io/aoc2021/hyperfine.html
K 1
6 Views
Open in Slack
PreviousNext
Powered by