https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2023 day 14> :thread:
# advent-of-code
a
kodee happy 1
e
Finally, the kind of day I waited for 🙂 No need to think much, not much actual code to write either, yet it somehow makes a lot of people struggle. Even though my solution has a bunch of code in part 2, it is just careful copy and paste.
m
for part1 I started with logic of only storing a node his northern neighbour and an ability to moveUp(). So for me it was the same logic of copy pasting code and making sure east, south and west also work. Which I failed to copy carefully 👀
n
I very much brute-forced part 1: for each of the columns, go from start to end. Whenever I see an empty space, add that to a queue, cubes clear the queue, and rounds take place of the first position in the queue. For part 2, add reversing x/y and reverse ranges, and then memorize the area after every cycle.
b
i just iterated over the map, everything that could do a single step did a single step, then repeated that until the map didn't change. slow but effective
as roman said, not a long to think about, just a lot of coding and debuggin to slow me down
e
I’ve made a slightly more efficient version where each individual O rolls as far as it can go, but this requires scanning the map in the right order, which made copy-pasting it over four directions more cumbersome, with more details to get right in each copy.
e
n
In my code, the only difference between north and south or east and west is a 
.reversed
on a range. Thus, I have 2 tilting methods.
Copy code
private fun northSouth(area: CharArea, north: Boolean) {
        val yRange = if (north) area.yRange else area.yRange.reversed()
        for (x in area.xRange) {
            val next = ArrayDeque<Int>()
            for (y in yRange) {
                when (area.get(x, y)) {
                    '.' -> next.addLast(y)
                    '#' -> next.clear()
                    'O' -> if (next.isNotEmpty()) {
                        area.set(x, next.removeFirst(), 'O')
                        area.set(x, y, '.')
                        next.addLast(y)
                    }
                }
            }
        }
    }
e
I have one tilt method, I just rotate the whole map with 
.asReversed().transpose()
, re-using the 
fun Iterable<String>.transpose(): List<String>
I wrote yesterday
n
I thought to rotate as well, but then thought that might be more expensive.
e
it might be expensive, my part 2 runs in ~60ms which makes it the slowest of all the days so far. but it didn't require extra debugging :)
e
Such efficiency does not really matter in AoC. Actually, caring about efficiency usually backfires in AoC, like it backfired for me here. Have I done like you did (move everything one step until it moves), I could have adapted it to part 2 much faster and without any copy-paste. A loop over four directions could have been added instead.
n
Agreed. I normally aim much more for easy to read code than for fastest code (esp. because I share/discuss with my team). (Of course, you can also take that as an excuse because I'm not smart enough to create the highly efficient code).
m
my initial cleanup: https://github.com/mdekaste/AdventOfCode2023/blob/master/src/main/kotlin/day14/Day14.kt I especially like doing this when building graphs:
Copy code
buildMap {
    input.lines().forEachIndexed { y, s ->
        s.forEachIndexed { x, c ->
            put(y to x, Node(y to x, c, this))
        }
    }
}

class Node(val pos: Point, var currentItem: Char, graph: Map<Point, Node>) {
    private val neighbours by lazy {
        Direction.entries.associateBy({ it }, { graph[pos + it.direction] })
    }
}
after this I can simply discard looking at a Map<Point, Node> altogether, and work out my logic from there. getting the neighbours lazily prevents needing another loop, meaning I only need to declare the logic once.
m
The one day all my utility methods for grids, points, directions and rotations would be most useful, I had to solve it on a different computer where I didn’t have them due to some travel. 😄 But it was a nice one to solve! For part 2 I looked for repetitions in the scores themselves, instead of saving the entire grid history, so just a List<Int> to look at.
e
Repetitions in scores don’t have to work. You are lucky they did.
j
Bit challenging, but not too much code. Not that happy with my code yet, but it works https://github.com/JBeet/MyAdventOfCode2023/blob/main/src/aoc14/Day14.kt
I was worried about false patterns, so I just tried it with the entire object stored, and luckily it didn’t take too much data before repetitions started
m
> Repetitions in scores don’t have to work. I’m aware, but with a big enough chunk to compare it shouldn’t be a fluke. Or maybe I was indeed just lucky. 😄
👍 1
a
Hi all, my code is fairly straightforward but I had to implement all those matrix rotations so my head is spinning ) https://github.com/andriyo/advent-of-code-kotlin-2023/blob/main/src/Day14.kt I figured they don't really want us to run cycles for 10000000000000 times or whatever, and it would be converging to stable at some point. As usual, all immutable data structures, no recursion
j
I cleaned it up slightly; https://github.com/JBeet/MyAdventOfCode2023/blob/main/src/aoc14/Day14.kt It’s interesting that when I move my repeatCycle function inside my class, it doesn’t detect the tailrecursion anymore. It works as an extension function, but not as a member function. (but tail recursion is not really needed for the cached version)
Copy code
private tailrec fun Rocks.repeatCycle(repeat: Int, cache: MutableMap<Rocks, Pair<Int, Rocks>>): Long {
    if (repeat == 0) return load()
    val (prevRep, next) = cache.getOrPut(this) { repeat to cycle() }
    val nextRepeat = if (prevRep == repeat) repeat - 1 else (repeat - 1) % (prevRep - repeat)
    return next.repeatCycle(nextRepeat, cache)
}
e
I shaved about 20% off my runtime by exploiting the fact that the default 
MutableMap
iterates its entries in original insertion order
a
yeah, it's linkedhashmap under the hood
btw, what I find confusing in the requirments is that load is measured NOT on tilted grid. I don't think it's obvious especially since Part 1 we measure laod on tilted grid
j
@andriyo It doesn’t converge to stable, it converges to a repeating sequence with a cycle length of 18; the test set converges to a cycle length of 7. But (1000000000-1000) % 7 == 0 && (1000000000-1000) % 18 == 0
a
@Jaap Beetstra I got lucky with my number of cycles then 🙂 yeah, I saw it jumping really but for 1000 cycles I got the test and real data correct - I guess 1000 is multiple of both
j
Being lucky is a good quality to have 😁
d
Being lucky now is not a guarantee of being lucky in the future @Jaap Beetstra 😇
t
Perhaps I was also lucky because I stored the last 8 results in an array by 
results[i % 8]
(starting 
i
was 
1
), iterated 1000 times, and then took 
results[1000000000 % 8]=results[0]
😮‍💨
k
Part 1 was smooth. But spent too much time debugging part 2 • Had some problems finding the cycle. Turns out my load calculation for horizontal moves was wrong • Also had a back and forth with arrays and hashes https://github.com/kingsleyadio/adventofcode/blob/main/src/com/kingsleyadio/adventofcode/y2023/Day14.kt
m
For some reason my brain today just won’t spit out the modulo formula for part 2 … so I just chose to naively iterate the cycle 😉 https://github.com/MikeEnRegalia/advent-of-code/blob/master/src/main/kotlin/aoc2023/day14.kt
^ Refactored to 35 readable LOC 🙂
🙌 1
m
I figured out later that to 'roll stones' on a grid, you can split the string on '#', sort, and reinsert. e.g.
Copy code
..O..O..O##..O..OOO.#.O
split
[..O..O..O][][..O..OOO.][.O]
sort
[OOO......][][OOOO.....][O.]
reinsert
OOO......##OOOO.....#O.
but tbf, doing immutable splits and transposing matrices isn't cheap, but its way shorter than my initial solution 😂
now I wish I could get a 'sublist' view from a matrix column 👁️
e
funny you mention mention it; that's basically what I'm doing in Rust, arranging the matrix so that columns are sequential, "sorting" in-place
m
Yeah, I can only get the logic to work with sort in place (with sublist) on horizontal axis. Kinda wish I had a matrix utility tool prepared
m
^ I wish Kotlin had a matrix utility tool prepared …
e
I used a mutable structure for interpretation, in the end it is always the same array changing around. I move each 'O' only once per tilt. And I tried to optimize the solution by storing only the hashcode of each array instead of an whole copy of the current one, for loop detection, but it takes twice as long. https://github.com/bayesiano/AoC-2023/blob/master/src/main/kotlin/Day14b.kt
k
@Michael de Kaste 🤝 glad to see the same idea. 😄 I solved it using this way. split by '#', sort, rejoin. also transpose() is required for N and S directions.
e
@Marcin Wisniowski it's pretty easy to construct an example where you'll "see" a loop if you're only looking at the load values, which isn't a real loop
Copy code
....#
.#...
..O..
#....
...#.
m
I'm planning a fast solution for a final refactor by creating a O(y * x) sorting algorithm for the entire matrix. currently sorting westward looks like this:
Copy code
fun Array<Array<Boolean?>>.sortWest(){
        lines@for (y in indices) {
            val width = get(y).size
            var walkPointer = 0
            var detectOPointer = 0
            while (walkPointer < width) {
                if (this[y][walkPointer] == false) { // if the current walk pointer is on a '.'
                    detectOPointer = max(walkPointer, detectOPointer) + 1
                    while (detectOPointer < width) {
                        if (this[y][detectOPointer] == true) { // if the detector detect on 'O'
                            this[y][walkPointer] = true
                            this[y][detectOPointer] = false // swap them
                            break
                        } else if (this[y][detectOPointer] == null) { //if you detect a '#'
                            walkPointer = detectOPointer    // set walker to detector position
                            break
                        } else {
                            detectOPointer++
                        }
                    }
                }
                walkPointer++
            }
        }
    }
turns
Copy code
O....#....
O.OO#....#
.....##...
OO.#O....O
.O.....O#.
O.#..O.#.#
..O..#O..O
.......O..
#....###..
#OO..#....

into

O....#....
OOO.#....#
.....##...
OO.#OO....
OO......#.
O.#O...#.#
O....#OO..
O.........
#....###..
#OO..#....

where 'O' = true, '.' = false, and '#' = null
could probably be even smarter
p
n
I still like my idea of using a queue to record possible "roll to" indices. That way, I just have to walk over a column (or row in east/west) once without backtracking.
e
not quite sure what you mean by that. I just take each run of non-
#
, count the number of 
O
, and rewrite it
p
Quite happy with this - I stuck with 
List<CharArray>
manipulation (transpose+reverse) and used 
CharArray.sort
to sort runs between 
'#'
chars in the resulting lines (so rolled right). I tried implementing it with a 
CharArray
with mutating the data directly for transpose/reverse/rolling to avoid allocations but it was only marginally faster (~25ms vs ~28ms).
Day14.kt
n
Easy peasy, though quite slow at 7s. My straightforward SetCoord data structure, improperly relying on Kotlin Sets being backed by an ordered LinkedHashSet, worked great for Part 1 but required some hackery for Part 2. Each Coord casts a ray to see if there's an empty space or a cube, and only moves if there is empty space. I'll probably refactor to MutableList eventually, or see what other clever solutions people have come up with and try to implement one of those. https://github.com/nbanman/Play2022/blob/master/src/main/kotlin/org/gristle/adventOfCode/y2023/d14/Y2023D14.kt
b
my "fast" solution is around 1s, i'll have to see what other people did to get so much speed
p
Feel free to ask any questions on my solution (currently ~30ms on part2)
b
i'm currently being distracted by actual work so i'll have to look at it a little later
m
Couldn't resist to do things a bit differently today 😃 I guess this won't work for part 2... https://github.com/fabmax/aoc-2023/blob/main/src/main/kotlin/day14/Day14Kool.kt
day14.mp4
🆒 6
🔥 5
❤️ 1
a
That's awesome!) @Max Thiele
m
Thanks! I was waiting for a puzzle that can be solved with physics for a while now 😀
t
@Jaap Beetstra I think everyone had a different cycle length (I just verified that my cycle length was 14 and required 117 tilts to occur).
n
cycle length 39, 145 tilts for me
p
77 after 160 tilts for me 😞
😮 1
rocks go brrr
e
I think it should be the same for everyone, there was only a period of 18 rotations after about the 112 rounds
m
22 after 122 for me, my regular solution gets there in about 15 ms after warmup
🙌 1
j
True there are many different cycle lengths. Still 999_999_000 has many, many divisors, so it was a good (lucky) choice.
true story 1
j
m
@Max Thiele You could still solve part 2 that way, just skipping over the repeating cycles. I think it would be awesome.
m
@Marcin Wisniowski I actually tried that 😃 The problem is that I have to use movement constraints for the spheres to only roll in the tilt direction, otherwise they wouldn't stay in their row (the movement is computed by an actual physics engine). When changing the tilt direction I also have to change the constraints but the sphere positions become more and more inaccurate after each iteration. It should be possible to fix that by re-sanitizing the sphere positions after each tilt iteration but I haven't tried that yet.
j
@Max Thiele add cube squared rocks all around the field, they make no difference for the weight
m
> I have to use movement constraints > It should be possible to fix that by re-sanitizing the sphere positions after each tilt These were exactly my thoughts before suggesting it 😄
m
Alright, by popular request, here's the Day 14 Simulator, capable of solving part 2 (theoretically 😃): https://fabmax.github.io/kool/aoc23-day14/ Thanks to kotlin-multiplatform this runs directly in the browser, but you will need a WebGL2 capable browser and a not completely terrible GPU for this.
🔥 16
❤️ 6
🆒 2
K 3
😮 4
advent of code intensifies 6
K 5
p
Wow that's awesome!
Runs even on my phone
m
Amazing! 😄 And it's Kotlin Multiplatform too! I saw people doing AoC things in Unity before but it's super cool that it's KMP.
e
it is! I've got my kotlin code compiled to JS here but I haven't put any work into visualizing… or even making it look half-decent
24 Views
Open in Slack
PreviousNext
Powered by