https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2023 day 23> :thread:
# advent-of-code
a
j
I'm still stuck on part1 with lots of out of heap space errors kodee sad
s
my part 2 is running (simple single-thread dfs) for 30min now 😞 and the current max is still not the correct solution... anyone got an idea for a LIFO with coroutines?
m
The idea for part 2 is too prefilter your graph to only care about the points on junctions. You only really can walk towards a junction
m
I did that, and it's looking (through the graph) for the last 20 minutes. Clearly I did something wrong. 😄
m
but I have a classical "it works on the test input, but not on the real one" problem
Are you keeping track of all the inbetween points, or just the distance? At the end I'm left up with a graph of 36 points at least, its solveable with that
m
Just the distance
My graph has 120 points though 🤔
j
Man I'm still stuck on part1, first tried modified dijkstra and a few other graph algorithms, I must be missing something
m
That's not the right answer; your answer is too high. Curiously, it's the right answer for someone else; you might be logged in to the wrong account or just unlucky.
I must be close though lol
m
I hate that I have a solution that works for the test input, because now I dont know what I should debug xD
m
Yeah mine works for the test input too, and then either never finishes or if I try other things, gives the wrong answer. Both of which work for the test input.
m
at first, I thought there could be multiple startnodes going to the same endnode, but with a longer path, but that wasn't it
j
today DeepRecursiveFunction shines, but mine is still not shining enough, 16 seconds for part 2 - clearly the approach is not the correct one. I’ll polish it later, now it’s the time for shopping before xmas 🙂
@Marcin Wisniowski “you might be logged in to the wrong account or just unlucky.” - wow I never ever seen this message. I’d say you’re lucky 🙂
m
alright, I figured out why I was stupid 😂 . Thats 1.5 hours of debugging down the drain.
apparantly, you cant just return 0 on your dfs if you can't travel further. Because you will walk into a corner of the map, and that so happens to be longer than finding the endpoint. So it was a matter of changing my function from Int to Int? and work with it accordingly blob nervous
m
Finally got it
j
Oh man I solved part 1 the overcomplicated way with splitting on intersections, made part 2 easy
@Marcin Wisniowski what was the problem in your code?
m
I made it harder for myself because I made the slopes be the nodes of my graph, which made it much bigger, plus I had to take into account that you might double step while passing the junction so had to check for that. I changed to the now obvious approach of just having the junctions between the slopes be the graph nodes. Then I switched BFS to DFS and just let it run for a while until it stopped getting better solutions.
j
hm interesting, I searched for splits and computed the distance between the splits and then computed out of that the total distances. Uncleaned code: https://github.com/bulldog98/advent-of-code/blob/main/advent2023/src/main/kotlin/year2023/Day23.kt
t
After 3 hours I did both parts 😊 Part 1 was just normal BFS so it went quick for me, but part 2 was much harder 😮‍💨 Spoiler for part 2: I constructed a graph (from start point, end point, and all junctions), pre-calculated lengths between all neighbors, and then did a BFS on the graph (discarding paths whose length was significantly smaller than the longest to the given point).
e
https://github.com/ephemient/aoc2023/blob/main/kt/aoc2023-lib/src/commonMain/kotlin/com/github/ephemient/aoc2023/Day23.kt I simplified the graph to only the junctions for part 2 (I had a hard time reasoning about how to do that with the directionality in part 1). still takes 15 seconds on beefy hardware with all the cores in parallel, though.
p
@ephemient I took the same approach - but did so for part1 so part2 was just mitigating the navigability flag I had - ~13.4s thought for part2 makes me sad.
e
Copy code
$ ./gradlew :aoc2023-exe:install && time aoc2023-exe/build/install/aoc2023-exe/bin/aoc2023-exe 23
# M1 Max
real    0m15.850s
user    1m9.606s
sys     0m7.762s
# i5-1235U
real    0m28.414s
user    3m16.550s
sys     0m10.988s
sad panda
p
Copy code
year 2023 day 23 part 1
	 Optimized took 102.772901ms (1.00x): 2366
	 Default took 136.125899ms (1.32x): 2366
year 2023 day 23 part 2
	 Optimized took 4.997177600s (1.00x): 6682
	 Default took 13.586675400s (2.72x): 6682
getting there
j
1m 15s for part 2. Nothing super obvious left to optimize. Ran out of heap space when trying to solve naively
p
Copy code
year 2023 day 23 part 1
	 OptimizedWIP took 22.193766ms (1.00x): 2366
year 2023 day 23 part 2
	 OptimizedWIP took 1.595661433s (1.00x): 6682
I'm going to leave it there for now.
j
Today, applying "heavy tools before brain" approach I came across 
DeepRecursiveFunction
that did the trick for "super naive" approach to part 1. It was not good enough for part 2, but still I learnt something 🤷‍♂️. My part 2 on simplified graph still takes ca 45s which does not meet the AoC "every problem has a solution that completes in at most 15 seconds on ten-year-old hardware" rule, however, it's still under a minute, so good enough for me 😇
p
https://github.com/tKe/aoc/blob/main/kt/src/main/kotlin/year2023/Day23.kt#L139-L169 - unfortunately my Ultimate license expired so I have no profiler to work with
j
consider this path: whenever - during the search - there is a node that we cannot come back (red on the drawing), maybe we could skip further DFS on such branch? Probably wouldn’t work for all possible graphs, but should work for the ones like in our input files?
m
Same approach as everybody else: https://github.com/fabmax/aoc-2023/blob/main/src/main/kotlin/day23/Day23.kt
discarding paths whose length was significantly smaller than the longest to the given point
Added this to my code (threshold = 0.3). Feels a little unsafe but reduced runtime for part 2 from 10 secs to 2
j
@Jakub Gwóźdź ...there is a node that we cannot come back (red on the drawing), maybe we could skip further DFS on such branch
Adding this actually (even with added BFS each time and no cache) brought my time from 45s to 25s i.e. to half
very nice 1
I've also discovered (by accident when "beautifying") that 
val visited = (blocked + from).toMutableSet()
makes my code much slower than 
val visited = blocked.toMutableSet().also { it.add(from) }
(32s vs. 25s)
m
well yeah. the first line is double allocation, the 2nd line is just single.
j
Sure, I understand why that is, just did not think that it would have THAT much impact. So much for optimizing code for readability 🤷‍♂️
m
I agree. I usually just start of writing my code as very 'functional' and immutable. Then later optimize it away. Mutability is so good for performance 👀, especially when you do small little things a lot of times
p
I prefer to encapsulate and hide mutability behind functions where possible. It finds a nice balance usually.
j
I like Roman's take on this https://elizarov.medium.com/immutability-we-can-afford-10c0dcb8351d And tend to agree in most cases I do not care if it's a fee ms slower, I care more that about correctness
p
Exactly. Where it matters you can encapsulate the mutability into a unit that can be readily reasoned about and maintain that correctness and clarity in its usage.
m
my DFS for part 2 goes from 10.54s to 2.15s. I'd say that is pretty huge
its recursive, creating a new set at every iteration to check against. If I make the initial set mutable and do something like
Copy code
if(visited.add(point)){
    val toReturn = recursiveSolve(...)
    visited.remove(point)
    return toReturn
}
that is way faster
r
for part 2, by using a DeepRecursiveFunction and a BitSet for maintaining visited state, I got it to about 5 seconds, and now, with the above tip by @Michael de Kaste , by reusing the same BitSet, setting before and clearing after calling the recursive function, I got it down to 2 seconds... good enough 🙂 👍
w
I managed to get to the correct solution without any help eventually. However I tried the approach of a shortest path (Dijkstra) with just inverted (negative) weights to get the longest path. Apparently that does not work. Maybe that only works for strictly directed graphs? Hard to reason about that.
m
I believe finding the longest path is considerably more difficult than finding the shortest path: For shortest path your result path will consist of the shortest path to each and every node in you path. I.e. whenever you find a shorter path to an intermediate node in your graph, that one will also result in a shorter result path. For longest path however, choosing a longer path to an intermediate node might block later nodes off of even longer paths. So it's often beneficial to choose a shorter path to an intermediate node to get a longer path as end result. That's probably why Dijkstra with inverted weights does not work.
m
@Werner Altewischer Think about this graph: Start -> End = 1000 Start -> A = 750 A -> End = 750 Clearly taking the 'direct' longest path doesn't work.
there are some graphs where you can reason in, in a smart way, but in this case I think its purely about pruning your graph correctly. If this was a 'cactus' graph, the solution is as simple as find shortest path and then explicitly NOT taking that path for instance.
t
That one was fun. I knocked part 1 out quickly and then took my dog for A Long Walk (a fitting title for the puzzle today) and had time to think about how I wanted to do part 2. Basically find the interesting nodes in the maze and record the distance between directly connected nodes and run a DFS on that instead of the full graph. I rewrote part 1 to use DFS as well, but my implementation of that is perhaps a bit messy. It's still a bit slow but I'm satisfied with the speed of it for a puzzle. • Code • Blog
m
Copy code
Benchmark                       Mode  Cnt    Score   Error  Units
Day23Benchmark.part1            avgt    5    1.385 ± 0.011  ms/op
Day23Benchmark.part2Exhaustive  avgt    5  467.248 ± 2.539  ms/op
Day23Benchmark.part2Fast        avgt    5   80.669 ± 1.731  ms/op
That should do
n
I definitely put the cart before the horse on this one. I thought the old* trick of reducing the graph to junctions would be insufficient. So then, not knowing squat about Graph theory I jumped down the rabbit hole of learning about the limitations of undirected graphs, cycle detection algorithms, schemes to have state track visited locations without scarfing up too much memory, etc. Then I decided I might as well reduce the graph to junctions anyway and voila it worked the first time. * That's how I made the graph in 2019 D20 manageable.
j
Did any of the inputs actually have a ^ ?
j
mine had neither < nor ^
p
n
Does anyone have any tips on how to parallelize the DFS in Day 23? My naive approach of doing recursive calls in an async/await ballooned my time from <1s to 17s. My code is here, but it is some of the ugliest code I've written this year. Mostly because I added a bunch of edge pruning stuff in a kludgy way, and haven't bothered to clean it up. The recursive DFS part is pretty clean though, lines 57-77.
m
I remember trying some parallelization as well but removed it because their wasn't mush speed gain. I got a little though. If I remember correctly I spawned new coroutines on each branch with but used an atomic counter to limit the number of launched tasks to something like 128. As soon as the limit was reached no new coroutines were spawned and each task proceeded with regular recursive DFS. However, it wasn't pretty, added quite a bit of complexity and the benefit was small so I removed it again.
👍 1
15 Views
Open in Slack
PreviousNext
Powered by