https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2024 day 18> (spoilers) :thread:
# advent-of-code
a
d
Blessed day, an easy one
💯 1
Copy that Dijkstra’s from 2 days ago and brute force part 2
You could binary search to find the cutoff point but you do not need to
m
Part 1
Part 2
👍 1
b
yea bin search + dij
refreshing after yesturday
m
Simple pathfinding today, nice breather
d
iteration works just fine
k
Same. Beautiful day. Just kept it simple and basic. Solution
b
oh i just assumed iteration would take too long, so i did binary search
finishes real fast
d
Yes iteration takes a couple seconds
r
Part 1 - Just Dijkstra Part 2 - Originally iteration over all points + dijkstra, changed it to a binary search after solving it. Binary search shaved of a few seconds, but iteration is completely doable.
b
my binary search only needed 12 iterations
d
Same. This was so easy I went ahead and added it.
k
Same 😂 Cuts my runtime down by 3x. Not bad
d
Screenshot 2024-12-17 at 9.43.20 PM.png
Cuts mine down like 100x lol
k
Oh wow. You're right. I was running with the sample. My actual input goes from ~700ms to ~1ms 🔥
Down from 1891 iterations to just 10
o
you could also do bfs from behind, it will consider fewer paths too since the graph will have fewer paths until it doesnt
image.png
d
Better binary search than I did above, no more tinkering
j
Solved part 2 initially with testing every point abusing the fact that for part 1 you already had an lower limit, since there it had to be reachable to get a solution and that took a while to compute, but was still faster than rewrite in binary search, now I do binary search in a nice recursive way (see the picture). Full solution: https://github.com/bulldog98/advent-of-code/blob/main/advent2024/src/main/kotlin/year2024/Day18.kt just reused my Dijkstra implementation
j
My 
solve(...)
returns the "path?", so I just store it and skip testing for all the blocks that aren't on the already found path, then repeat until no path is to be found anymore
Copy code
fun part2(input: List<Pos>): String {
    val fallen = mutableSetOf<Pos>()
    var lastPath = solve(fallen)!!.toSet()
    input.forEach { block ->
        fallen += block
        if (block in lastPath) {
            lastPath = solve(fallen)?.toSet() ?: return "${block.first},${block.second}"
        }
    }
    error("No solution found")
}
saves some time (from around 2.4s to 85ms)
👍 1
a
@Ozioma Ogbe FYI code 
.readText().split('\n')
might be simply replaces with one call 
.lines()
mind blown 1
b
mine, cleaned up
m
The binary search smart is so smart, I feel like mine is too hacky. I let an initial floodfill determine my initial searchspace. I then, per byte, remove it from this searchspace. if the 4 neighbouring spots of the now wall can't find each other within the searchspace, I floodfill again from the start to find the new searchspace.
Untitled
d
Hah that's true brute force could start at 1025 blocks
Maybe I'll see how much converting Dijkstra's to A* speeds things up 😜
Or maybe I'll write a fully abstract Dijkstra/A* that can be dropped in
j
I have a priority queue with the comparator comparing number of steps and then distance to end, not sure if it’s a dijkstra, an a-star or something completely stupid and over complicated, but it does its job
a
For part 2, just keep the distance map, iterate through the bytes in reversed order, and if the byte can be reached from one of its adjacents, update the distance and put it into the queue, and run Dijkstra again, until a path is found. I think this is generally faster than binary search.
a
yeah, while staring at it running soooo slowly, I realised I should just start with a bigger window and then stop when a path is found. my point was 2959 (out of 3450). seeing that some people got answers ~1700 ish, not necessarily obvious that starting from the end is better. so yes, will now redo using Binary search.
a
The point is that using binary search you have to run a full Dijkstra every time, but starting from the end the work needed to update the distances every time is much less.
d
a* uses an admissible heuristic in addition to cost from start for the priority of a given node. Manhattan distance to end is what you’d use here. So yes you are using A*
somehow A* is worse for my input. 3978 nodes expanded for heuristic = 0 (dijkstra), 4083 for Manhattan distance
p
I just stuck with BFS for finding the route, and for part2, stored the route, kept corrupting bytes until I found a byte in the existing best route and only then do I check for a new route. Repeat until no new route found. I should really have my 
bfsRoute
helper return null rather than throwing when no route found.
Day18.kt
d
A* can be worse against pathological (aoc) input
a
The binary search smart is so smart, I feel like mine is too hacky.
I let an initial floodfill determine my initial searchspace.
@Michael de Kaste since part 2 is really any path, flood fill from the starting point and then checking if the end point is in the same "region" seems less computationally intensive, if even if it appears like more iterations or lines-of-code. especially if you stick to just the "first" region. and the way you described a point being blocked off, it might be more lines of code but without needing to actually flood fill every time. the flood fill from the starting point is the same loop needed just to set up all the nodes in a graph, before even needing to find paths. I think that's a win.
> skip testing for all the blocks that aren't on the already found path @Jakub Gwóźdź this was a huge performance boost for my current linear approach 🎉
Copy code
#2959 (69) final: Pt(...)
ie only 69 very nice shortest path computes after 2950 iterations! especially when the graph is huge & empty, adding points just doesn't matter much.
j
yeah, but bisect still does it in 12 tests 🙂
Copy code
no optimalization: 2862 tests
test only when blocks previous: 90 tests
bisect: 12 tests
this is from my input
🆒 1
a
I was quite lazy and used for part 2 standard Kotlin's binarySearch function
Copy code
val resultIndex = (1..bytes.size)
    .map { bytes.take(it) }
    .binarySearch {
        if (isExitReachable(it.toSet()))
            -1
        else {
            val previousList = it.subList(0, it.size - 1)
            if (isExitReachable(previousList.toSet()))
                0
            else
                1
        }
    }
return bytes[resultIndex].let { (y, x) -> Point(x, y) }
j
@Andriy that is the best approach. I like mine more only because it's mine and I like it 🙂 . but bisect is the way to go
👍 1
a
yeah, but bisect still does it in 12 tests
yes, definitely. for ~4500 inputs, that's 12 (or 13) checks, since 2 ^ 12 < 4500 < 2 ^ 13 (grid size is 71x71 = 5041)
j
@Dan Fingal-Surma I count euclidean distance (dc*dc+dr*dr) instead of manhattan, simply because it was shorter to write than all the 
.absoluteValues()
😆 it basically prefers zig-zagged diagonal, but I too noticed that for my input no heuristic is actually faster 🙂
m
@Andriy thats what I did as well in my revised solution, but you don't even need to check again and insert the 0 result
Copy code
(1..parsed.size)
    .map(parsed::take)
    .binarySearch { if(floodFill(it.toSet())) -1 else 1 }
    .let { parsed[it.absoluteValue - 1] }
since binary search return the (-wouldBeIndex - 1) result if it can't find a '0' in the result
❤️ 1
a
especially when the graph is huge & empty, adding points just doesn't matter much.
that was an incorrect assumption. it seems Mr. Wastl has carefully selected points earlier on which are on the shortest path. the re-calcs needed at the start were at a higher rate (42 in 1000) than in the middle (27 in 1500 ≈ 18 in 1000), with the extreme end being flat, (1 in 500).
😍 1
m
This is my updated code with the binary search:
Copy code
Solution for Day18: 
---------Part 1-----------
time: 939us
answer: 260
---------Part 2-----------
time: 1.100300ms
answer: (24, 48)
---------Total-----------
time: 2.039300ms
---------End-----------
Day_18_Michael.cpp
j
I like the flood fill. If you detect which edge-point of the flood fill was added last, and continue from that point you can speed it up a bit I think. My solution for part 2 takes about 190µs that way
Copy code
fun solvePart2(blocked: List<Position>, size: Int): String {
        val blockMap = blocked.mapIndexed { index, position -> position to index }.toMap()
        val bounds = ZeroBasedBounds(size, size)
        val visited = mutableSetOf<Position>()
        val edges = mutableListOf<Int>()
        var lastEdge = blocked.size
        val target = Position(size - 1, size - 1)
        var lastRemovedPosition = target
        val queue = mutableListOf(Position(0, 0))
        while (target !in queue) {
            val active = queue.removeLast()
            visited.add(active)
            for (nextPosition in active.neighbours4) {
                if (nextPosition !in visited && nextPosition in bounds) {
                    val pos = blockMap.getOrDefault(nextPosition, -1)
                    if (pos in 0..<lastEdge)
                        edges.add(pos)
                    else
                        queue.add(nextPosition)
                }
            }
            if (queue.isEmpty()) {
                lastEdge = edges.max()
                edges.remove(lastEdge)
                lastRemovedPosition = blocked[lastEdge]
                queue.add(lastRemovedPosition)
            }
        }
        return lastRemovedPosition.column.toString() + "," + lastRemovedPosition.row
    }
h
Thankfully, I had taken the time to learn about Dijkstra during the Reindeer Maze from a couple of days ago... so I repurposed that for Part 1. For Part 2, I (eventually)[1] just started from Byte 1025, removing the locations from the node graph and rerunning Dijkstra iteratively... obviously not as efficient as some of the solutions here, but it only takes a second or 2. For someone who started learning Kotlin a little over a month ago, I've been having fun with these Advent puzzles 🙂 (except maybe yesterdays!) [1] we won't talk about my initial Part 2 solve that recreated the full maze, the full node graph and then ran Dijkstra for Every. Single. New. Byte. :P
👍 3
🎉 2
e
Day18.kt my part 2 is currently skipping past any obstacles that aren't on the last found path (since clearly they won't impact it) and re-running search. but there's certainly some graph theory solution involving cuts…
m
Day18.kt - Binary search is a nice optimization, part 2 went down from ~1300 ms to ~6 ms!
j
Ok so I found another interesting solution to P2 (or rather, my wife inspired me, when I was talking to her about today's AoC and how fun it was to decide between Dijkstra and A* 🙂 ) Instead of finding paths many times on different timestamps (no matter if it's bisect or step after step), just drop (in one run) all the bricks one after another and see at which point you can find a wall completely blocking 
S
from 
E
. So I came back to keyboard and implemented something for it: Basically I'm dropping the bricks and either creating a new set of borders(together with diagonal) for each one, or if the new brick belongs to borders of one or more existing sets, add it to this set instead (merging sets when necessary). A merged (continuous) set of bricks is considered as blocking the path if it had a brick on (top or right) grid line and another brick on (bottom or left) And that approach is to be honest pretty darn quick!
Part2 new approach.cpp
very nice 1
d
Oh hey it's union find
j
yes kinda sorta, but also no 🙂
d
Ah I read it closer, no
j
I mean, union-find seems way faster and more complicated 🙂 But yes, I'm solving the same problem as union-find, just in a worse way. I'm trying now to implement U-F and... ah it's too late and I'm tired, I prefer to do something more rewarding, like an java/awt visualization or... idk, maybe I'll simply play some apex legends instead 😛
🤣 2
d
Yeah it's also more complicated because you're trying to track aggregate properties of the unioned sets
j
wooohoooo Union-Find is a monster!
Copy code
Parsing took 188.25us
Part 1 took 389.208us, result is 226
Part 2 took 306.459us, result is 60,46
And the code is actually pretty ok, after cleanup.
And here's the visualization for my "no path searches for part 2" approach :)
Screen Recording 2024-12-19 at 11.09.44.mov
K 1
🥶 1
p
I’ve built this one. I found a binarySearch in the stdlib but couldn’t really utilize it. Is there something in the stdlib for this? https://github.com/PaulWoitaschek/AdventOfCode/blob/main/2024/src/main/kotlin/aoc/year2024/Day18.kt
binarySearchHighestMatching.kt
p
@Paul Woitaschek hard to beat Elizarov's take on binarySearch https://elizarov.medium.com/programming-binary-search-6e999783ba5d
🙏 1
p
Thank you! Super good read 👌
13 Views
Open in Slack
PreviousNext
Powered by