https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2022 day 14> :thread:
# advent-of-code
a
d
Wow do I love Kotlin!
k
Am I the only one who just assumed I couldn't go through diagonal walls?
d
There was one example (after "Finally, ...") that shows it happening
m
m
My part 2. Yeah the water was much worse.
j
Oh man my solution did not perform well for part2 https://github.com/bulldog98/advent-of-code-2022/blob/main/advent2022/src/main/kotlin/Day14.kt my guess is I allocated to many new objects
j
I went with mutableSet today, which is way suboptimal for part 2 (takes about 1/8 of a second), but it was the quickest for me to code. Now - time to spend half a day optimizing it :)
jakubgwozdz_day14.kt
s
I cringe a little every time I have to write 
while(true)
instead of figuring out a proper termination condition or just rewriting everything in a functional style. But still, it works :D https://github.com/forketyfork/aoc-2022/blob/main/src/main/kotlin/year2022/Day14.kt
d
That was fun. Part 2 was a pretty simple edit of Part 1, now to make them both work in one run 🙂
def helped to write a 
print
function for my cave
w
i went top down for part 2, because my solution for part 1 did not perform well at all
Copy code
fun part2(input: List<String>): Int {
        val rocks = input.flatMap { parse(it) }
        val sand = mutableSetOf<Pair<Int, Int>>()
        val bottom = rocks.maxOf { it.second } + 2
        var nextSand = listOf(500 to 0)
        while (nextSand.isNotEmpty()) {
            sand.addAll(nextSand)
            nextSand = nextSand
                .flatMap { it.spread() }
                .toSet()
                .filter { !rocks.contains(it) && !sand.contains(it) && it.second < bottom }
        }
        return sand.size
    }

fun Pair<Int, Int>.spread(): List<Pair<Int, Int>> {
    return listOf(first to second + 1, first - 1 to second + 1, first + 1 to second + 1)
}
fun parse(input: String): Set<Pair<Int, Int>> {
    val pairs = input.split("->")
        .map { it.trim() }
        .map { it.split(",") }
        .map { it[0].toInt() to it[1].toInt() }
    return pairs.zipWithNext { a, b ->
        (minOf(a.first, b.first)..maxOf(a.first, b.first))
            .flatMap { x ->
                (minOf(a.second, b.second)..maxOf(a.second, b.second))
                    .map { y -> x to y }
            }
    }
        .flatten()
        .toSet()
}
m
@Sergei Petunin Even if you refactor it the way you describe, it is still an endless loop. No way around it for this one 🙂
r
I refactored it to 
generateSequence { ... }.last()
to avoid the 
while(true)
.
m
@rocketraman then you’ve hidden the loop. Not sure whether that makes it more or less readable …
r
Not sure either, but it looks cleaner :)
s
Maybe something with 
takeWhile()
...
r
I actually didn't have 
while(true)
in mine, I had 
while(nextSand()) { }
with 
nextSand()
writing to a mutable set. Doing it as a generator gets rid of the mutable set as well as the empty while loop body, and just generates the updated set on each iteration.
m
Sometimes it’s better to have a simple loop than to obfuscate the code with clever functional constructs. But the latter is fun 🙂
c
Haven't settled on whether using string.split or regex for parsing is faster/less buggy 🤔
r
String.split was super-easy for this one, just two splits
m
^ This is why I did a season of AoC in Python in January - the simplicity of the (usually) iterative Python solutions fascinated me. This experience has led me to resist the temptation to do everything with a fold 😉
d
I have not yet used regex this year
j
@Dan Fingal-Surma I did and it was a mistake 🙂
m
This year even the complex inputs did not need regexes, 
mapNotNull(String::toIntOrNull)
works wonders 🙂
e
I made an off-by-one on part 2 (allowed sand to maxY+2, instead of floor at maxY+2) that took me a long time to debug, because I didn't write any visualization code
a
reading part 1 (not an early riser) - wanted to check if I was thinking of the correct shortcut for the sand drops: each 'next' piece of sand has to visit the previous pieces second-last position, right? (visit = not its endpoint but where the next piece can first deviate from the previous piece's path)
d
Hmmm
Given that the test grid looks like this
Copy code
......o...
.....ooo..
....XoooXX
...oXoooX.
..XXXoooX.
....ooooX.
.o.oooooX.
XXXXXXXXX.
doesn’t seem like it
a
(not including the infinite drops part) running the test example in my head with fingerprints on screen at each sandpoint, it does appear that way. will try with code
d
Ah I see what you’re saying
I’m going to test
a
that's like 80-90 drops we can skip for each piece of sand 😂
d
Hmm I’m not sure how you do that
once you skip it for one, you don’t have the path anymore
I guess a stack works
a
it would be each piece of sand's unique data, overwritten for each next piece. then I would do 
takeLast(2).take(1)
as the starting point
d
running the whole simulation for part 2 takes like 1 millisecond once the VM has warmed up on part 1 though
a
yeah, not really a "CPU optimisation" just dumping the repetitive initial steps every sand piece takes (no spoilers! 😛 especially if there's an Indiana Jones moment later. I see some mention of water...)
d
(checking my work)
j
WOOOHOOO! The “Stack for previous sand unit” approach reduced my time for part2 from ~15ms to ~1.5ms 🙂
a
great! then I'm going to make some coffee, clean the finger smudges from my screen and start writing code with my pathing shortcut
d
lol I was timing the test maps… for my real map it’s 90ms without optimization, 20ms with on part 2
nice insight
r
I'm always proud of a solution that has a single function for both parts but using smart parameters... even though there's plenty of mess here
Day14_kts.cpp
t
I hacked the input 😄 adding
Copy code
0, maxY+2 -> maxX*2, maxY+2
and everything worked from part 1 😄 😄
d
It does makes sense that after a piece of sand is dropped, the map is the same except the point where the sand came to rest, so the only place that the next piece can deviate is where it comes into contact with that piece
m
Two in one 🙂
Copy code
package aoc2022

import kotlin.math.max
import kotlin.math.min

fun main() {
    data class Pos(val x: Int, val y: Int) {
        fun flowTo(p: (Pos) -> Boolean) =
            sequenceOf(copy(y = y + 1), copy(x = x - 1, y = y + 1), copy(x = x + 1, y = y + 1)).firstOrNull(p)
    }

    val rock = buildSet {
        generateSequence(::readlnOrNull).forEach { row ->
            row.split(" -> ").map { it.split(",").map(String::toInt) }.windowed(2).forEach { (from, to) ->
                for (x in min(from[0], to[0])..max(from[0], to[0]))
                    for (y in min(from[1], to[1])..max(from[1], to[1])) this.add(Pos(x, y))
            }
        }
    }

    val maxY = rock.maxOf { it.y }
    val source = Pos(500, 0)

    val stableSand = mutableSetOf<Pos>()

    var hitFloor = false
    var s: Pos = source
    while (source !in stableSand) {
        s = s.flowTo { it.y < maxY + 2 && it !in rock && it !in stableSand } ?: source.also { stableSand += s }
        if (!hitFloor && s.y == maxY + 1) {
            hitFloor = true
            println(stableSand.size)
        }
    }

    println(stableSand.size)
}
r
My next goal is to refactor so each next piece of sand starts from the last place the previous piece was before it got to its resting location
d
lol i’m stealing that floor trick
d
This was fun!
I (tried) to make a cool animation of the sand falling down for the example input (part 1) with OBS Studio, but it's a bit buggy on Linux, let me know what you think 🙂
2022-12-14 09-37-50.mkv
Code as always at https://github.com/Davio/advent-of-code/blob/main/src/main/kotlin/com/github/davio/aoc/y2022/Day14.kt, it's the rough first draft which gets the answer without any refactoring / cleanup / optimization 🙂
r
Turns out adding the stack was almost trivial... Took my python implementation from 2.526 sec to 0.180 sec
d
My approach was: parse the input (duh), convert the lines in the cave to a set of points, track the grain of sand as a point and keep trying to fall down until hitting something in the set of blocked points or set of sand at rest
d
val floor = Point(source.x - yMax - 3, yMax + 2).to(Point(source.x + yMax + 3, yMax + 2))
worked for me and kept nice rendering
k
e
replacing 
Set<IntPair>
with 
BooleanArray
(and some helper accessors) gave me a pretty sizable speed boost
m
Down to 24 sloc. Parrticularly pleased with the input parsing 🙂
Copy code
package aoc2022

import kotlin.math.max
import kotlin.math.min

fun main() {
    infix fun Int.range(i: Int) = min(this, i)..max(this, i)
    val rock = generateSequence(::readlnOrNull).flatMap { row ->
        row.split(" -> ", ",").map(String::toInt).windowed(4, 2).flatMap { (x1, y1, x2, y2) ->
            if (x1 == x2) (y1 range y2).map { Pair(x1, it) } else (x1 range x2).map { Pair(it, y1) }
        }
    }.toSet()

    val maxY = rock.maxOf { it.second }
    val source = Pair(500, 0)
    fun Pair<Int, Int>.flowTo() = let { (x, y) -> sequenceOf(x to y + 1, x - 1 to y + 1, x + 1 to y + 1) }
        .filterNot { it in rock || it.second >= maxY + 2 }

    val stableSand = mutableSetOf<Pair<Int, Int>>()

    var reachedFloor = false
    var s: Pair<Int, Int> = source
    while (source !in stableSand) {
        s = s.flowTo().firstOrNull { it !in stableSand } ?: source.also { stableSand += s }
        if (s.second == maxY + 1 && !reachedFloor) println(stableSand.size).also { reachedFloor = true }
    }

    println(stableSand.size)
}
o
Compose sand animation ⏳
sand.mp4
c
Enjoyed todays. Not terribly difficult but an interesting scenario. https://github.com/CfGit12/aoc-2022/blob/master/src/main/kotlin/14.kt
j
r
Nice, today was fun. I did the same thing, took a hashset for rocks without talking 2D grid. I had a hunch, part2 might throw 00M.
a
@Oleksandr Balan do you have the source code to generate that compose ?
o
@Alex LO Nothing I am really proud of, but here you are 😅 https://gist.github.com/oleksandrbalan/c71aafc89c5f25907fed9430f2490339
j
This puzzle was so awesome
I immediately visualised the grid, made it so much fun to look at the results while building
And the part 2 result looks badass
r
Like most, I wrote my visualization out to the terminal, replacing "#" with █ to make it look a bit better, but as I was doing it I was thinking of using https://github.com/JakeWharton/mosaic (terminal output via Compose) to animate it 🙂. Cool to see it done to canvas though.
p
Late to post, but I was happy with how this came out: https://github.com/tKe/aoc-22/blob/main/kt/src/main/kotlin/year2022/Day14.kt although I’d like to visualize it at some point 🙂
My initial solution this morning had a 
MutableMap<Int, BitSet>
and used 
computeIfAbsent(y) { BitSet() }.set(x)
but I switched to 
Array<BitSet>
for a little extra speed 🚤
e
change all my solutions to what is effectively a post-order tree traversal instead of starting from the origin with every particle. that made a excellent improvement to my running times as well
t
Well that was fun. As mentioned in the puzzle text, this was a lot like a puzzle we had in 2018 except with sand instead of water. This one seemed less complicated. I tried to implement this with all sequences but it ultimately felt too confusing so I settled on this approach. • Blog • Code
x
out of curiosity - how long did simulating part 2 takes you all?
p
Runtime? I think my current fastest is ~4-6ms
14 Views
Open in Slack
PreviousNext
Powered by