https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2021 day 15> :thread:
# advent-of-code
a
d
e
Phew, that was stressful. Iā€™ve implemented a naive O(N^2) Djikstra for Part 1 and then ran it for Part 2. It did not finish in a few seconds, so Iā€™ve started to fret about the prospect of having to implement O(N*log N) version. However, while I was contemplating on how to approach this implementation (whether to write binary heap from scratch or find and reuse some of my older code) it did actually complete with an answer.
šŸ‘ 2
d
I was considering killing it and adding a 
println(unvisited.size)
to the top of the loop to make sure it was going to make progress, but then it finished. Going back and doing this now I can see it making steady, if slow, progress
When I started I reached for 
java.util.PriorityQueue
but then decided nah, letā€™s go with 
minByOrNull
e
Iā€™ve almost killed it! It was pure luck that Iā€™ve, instead, copied the source of it and started to stare at the copy, trying to force myself into writing an implementation with binary heap, and the same time frantically trying to remember why on earth 
PriorityQueue
is of no help ā€” you cannot efficiently decrease the key of an arbitrary element in there.
k
I first used a 
Deque
(breath first), took 5 seconds for part 2. Switched to a 
PriorityQueue()
and only took 2 seconds. I am not CS trained so I don't know which algorithm I am using. My solution: https://github.com/knthmn/AdventOfCode-Kotlin/blob/main/src/y21/day15.kt
d
Oh wow the PQ version completes sub-second it seems like
Updated my code
You just insert the same element again after updating its distance
Donā€™t worry about the one thatā€™s in there with the wrong distance ā€” it will come off the queue eventually and be a no-op
m
https://github.com/mdekaste/AdventOfCode2021/blob/main/src/main/kotlin/year2021/day15/Day15.kt for now, just a dijkstras, runtime is 0.34 seconds for part2 so I'm totally fine with it
e
@Dan Fingal-Surma Cool. Itā€™ll work, indeed, for this specific problem because there are few neightbours and distances are short. Iā€™ll try to remember this trick
m
PQ shaves my time from 0.34 to 0.32
d
And actually, you can remove the vertex first, which is O(N) in the size of the queue, but the queue never gets very big in this case so the runtime difference is slight.
Copy code
queue.remove(it)
queue.add(it)
(since the queue contains just the frontier)
e
@Dan Fingal-Surma Great observation, too. In this problem the frontier is always relatively small, so you can actually keep it in any collection. Even without PQ itā€™ll be relatively fast.
d
Ah, good point
@*knthmn* Dijkstraā€™s algorithm
šŸ‘šŸ¼ 1
d
Ohhhh 
PriorityQueue
! I created a 
data class Chiton(val point: Pair<Int,Int>, val risk: Int)
then a 
val chitons = mutableListOf<Chiton>()
for each iteration adding possible steps, and then 
chitons.sortBy { it.risk }
.
m
sorting after every addition can get very expensive, but you got the logic down šŸ™‚
šŸ‘ 2
e
It does not really matter here. Resorting ā€œalmost sortedā€ list is O(N), so it is still the same asymptotic if you werenā€™t sorting it, but just taking 
minBy
every time.
šŸ‘ 1
m
yeah I think I meant saying that using unsorted data structures can get very expensive. Adding and getting = o(1 + n) vs. sorted adding and getting = o(log n + log n)
d
Yes indeed, a HashSet with minByOrNull works just the same for this case
Right, but the size of the queue is O(sqrt(n)) where n is the number of vertexes in a grid (specifically for a grid graph)
m
oh thats very interesting, I was looking for the maximum size for the PQ to initialize the capacity with
Mhh that doesn't seem to be the case. I still reach my breakpoint on the "grow" function of PQ
d
thatā€™s just an order šŸ™‚
the frontier is a line through the grid
that may curve or wander
blue vertexes:

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#/media/File:Dijkstras_progress_animation.gifā–¾

Iā€™d guess 2 * sqrt(n) would be enough to avoid a resize
e
d
BTW, what was the point of part 2? Was there a possible naĆÆve solution to part 1?
m
possibly to stop brute force methods that revisit tiles?
e
my original part 1 solution wouldn't re-visit the same path, but would re-visit the same _node_; that did not work at all for part 2
šŸ‘ 2
also had an accidental "copy the entire world" mistakes in my original Haskell solutionā€¦ fixing that brought the runtime from 7 minutes to 100ms
I'm using Java's PriorityQueue on JVM, but since I'm also targeting JS/native, I had to write my own binary heap. https://github.com/ephemient/aoc2021/blob/main/kt/src/nonJvmMain/kotlin/com/github/ephemient/aoc2021/PriorityQueue.kt
m
I feel like in that case, couldn't you just use sortedSet?
e
also not multiplatform
m
Nothing fancy but works.
d
There's that 
getAdjacentSides
again. I definitely thought of you as I toiled away with my four separate checks.
d
As discussed above you don't need a heap for this problem because the frontier stays sufficiently small
What I did originally was check the entire list of vertexes for the minimum one on each loop, which is pretty slow because there are 250k of them. As long as vertexes that have been updated go into the frontier set/list/whatever and then come out as they get processed, runtime is very short even for part 2
Marcin that looks like A* search since you added Manhattan distance as a heuristic šŸ˜
When I first saw this problem I looked up the A* algorithm but then decided to try Dijkstra's first
A* with a 0 heuristic function
Oddly, for my code on part 2 plain Dijkstraā€™s takes ~900ms whereas A* takes ~1100ms. Checking why, for part 2 Dijkstraā€™s explores all 250,000 nodes before dequeuing the target vertex, whereas A* dequeues 249,998 nodes. So the cost of the heuristic dominates. This is a pretty pathological graph!
@Michael de Kaste I checked, the max size of the frontier for part 2 is 901 which is indeed < 2 * sqrt(250,000) = 1000
p
d
Out of curiosity, in the animation that @Dan Fingal-Surma posted, what's the best way to handle an obstacle like that? Would it work just to pre-initialize the visited list with the exterior points of the shape?

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#/media/File:Dijkstras_progress_animation.gifā–¾

d
A* search

https://en.wikipedia.org/wiki/A*_search_algorithm#/media/File:Astar_progress_animation.gifā–¾

m
probably also the reason why I couldn't get A* to work faster than my Dijkstra. I've seen some visualisations of peoples A* and it basically looked like they visited almost all nodes anyways. And A* needed extra overhead.
e
Started with Dijkstra, worked for part 1, but way too slow for part 2. Switched to A*, 3 seconds for the whole thing. I don't quite understand why Dijkstra was so slow, since it's working fine for others seemingly. Took a few seconds to get through a thousand nodes in the queue. But in the end - whatever. I hate graphs. Even though I used a graph yesterday. https://github.com/edgars-supe/advent-of-code/blob/master/src/main/kotlin/lv/esupe/aoc/year2021/Day15.kt
e
tracking the path in a map is definitely a source of overhead. it shouldn't be necessary
p
Certainly an overhead when all we need is the total risk/cost of the route.
d
@Edgars try updating h to always return 0 and see how fast it runs ā€” thatā€™s Dijkstra
Actually I think this is the issue:
Copy code
if (neighbor !in openSet) {
    openSet.add(neighbor)
}
The neighbor may already be in the open set, but at a lower priority. You want to update its priority with the new value of 
fScore[neighbor]
. Simply modifying the 
fScore
map doesnā€™t move it to the correct place in the PQ
So you can either remove-then-add, or just add since multiple dequeues of the same point are no-ops
Additionally, 
!in openSet
is the same complexity as 
remove
, so you arenā€™t paying more
p
I originally had removals before adding neighbours back in, but I found it was doubling my runtime. Not sure PriorityQueue is very efficient at removing arbitrary values...
d
Yeah itā€™s O(N) in the size of the PQ
Anyhow dequeueing in strict priority order ensures that each node dequeues at most once, whereas violating that may result in nodes getting added back multiple times
p
I'll be honest though, it was a difference between 250ms and 90ms. Neither are particularly overwhelming giving the usecase of providing an answer.
t
I wrote mine a few different ways but ended up using a priority queue and keeping track of visited spots. I donā€™t expand the cave in part two, we can calculate the risk level without needing to do that. It wasnā€™t really any faster to expand the cave or to read cached values, it turns out. Finishes in ~1s or so. ā€¢ Code ā€¢ Blog
d
Nice
t
I really enjoy reading those blog posts, great job @todd.ginsberg and thank you šŸ™‡
t
Thanks @Todor Grudev! šŸ™‚
e
@Dan Fingal-Surma Changing 
h()
to return 0 improved it by 100ms (from 2600ms). Doing 
openSet.add(neighbor)
without checking if it's in shaved off another 350ms. Removing 
fScore
altogether - another 200ms.
šŸ‘ 1
Still kinda slow, tho. šŸ˜„
@ephemient @phldavies How would you get the path/risks then?
d
Mine is about 900, I store the cost (and risk) in the vertex itself so thereā€™s no map access. also no need to track 
cameFrom
, in your code you can just get 
gScore[end]
at the end
p
I was just going to suggest by the looks of it it'll be gscore[end] as that's where you're building up the distance/risk for the route.
e
exactly, all you need is the best cost at each point during the search, and the final cost at the end of the search just pops out for free
p
once the shortest route in the frontier is your end point, you're done.
e
Aha, makes sense! Yeah, sorry, probably should've realized on my own, but graph puzzles aren't much fun for me. Now it's down to 1850ms. I think I'll leave it at that. Thanks for the tips and knowledge! šŸ™‚
m
Proud of having solved it brute-force not knowing Dijkstraā€™s algorithm ā€¦ not so proud of not knowing the algorithm šŸ™‚ https://github.com/MikeEnRegalia/AdventOfCode2021/blob/main/kotlin/src/main/kotlin/Day15.kt
K 1
14 Views
Open in Slack
PreviousNext
Powered by