This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
Day 17 - Solutions
My part 1 runs 2.5 secs, and part 2 runs 7.5 secs
https://github.com/zelark/AoC/blob/master/src/zelark/aoc_2023/day_17.clj
https://gitlab.com/maximoburrito/advent2023/-/blob/main/src/day17/main.clj?ref_type=heads I've been out sick for a bit and have quite a few days to catch up on. I feel a bit rusty as I had to finish this in the morning despite being a relatively straightforward search problem...
@U067R559Q, can you push your zelark.aoc.core
with the astar
implementation you are using at https://github.com/zelark/AoC/blob/7c0ba284618adecec81aa9631e180ad516a193d1/src/zelark/aoc_2023/day_17.clj#L37? Very nice aoc specific library btw, but this function is missing in the repo. I'm curious! Thanks!
@U4XJNL67P thanks. Somehow I forgot to push it. In a nutshell it’s a copy of astar-search implementation with a few improvements. Here we go https://github.com/zelark/AoC/blob/6d8ae4bb8d33efc47758076c2ed47875cde8ae2c/src/zelark/aoc/core.clj#L190
Forgot I have my g2/plus
function for adding delta. Now it is a bit faster 6.2 secs for part 2 :star-struck:
This was challenging task for me, thought on it during 3 days and only today created usable algorythm, although working for both parts. Thanks to author of AOC, this task for me was times harder than all other ones for now 😊
If you used A*, what was your heuristic for max path length to goal?
Isn’t that just dijkstra then?
Intuitively implemented 'shortest path' search with Manhattan distance heuristic, but didn't get the prioritization quite right at first, causing the code to take prohibitively long on my platform of choice (#C034FQN490E on my iPhone 8; no clojure.data.priority-map or more advanced libs). Studied A* again and learned how to use sorted-set
properly. Part 1 now finishes within 30s and I am happy to accept that. 🙂
manhattan distance is wrong heuristic
Consider field 0,0 -> 10, 10, you are on part 2, and your current position is 9,9. What is the maximum remaining path?
Manhattan only for the lower bound: 1 + 1 = 2 in your example. But yes, a more realistic lower bound, if computable, would converge faster. I only just read part 2. Your solution seems to work without an explicit heuristic for the cheapest path to the goal... :thinking_face:
doesn’t need one…
I see that I got my idea about A* backwards
the heuristic function has to return less or equal to the real shortest path
I thought it was more or equal
Interestingly, indeed simply estimating the remaining cost to be 0, turns out to not be significantly slower in this case.
yeah because the rules take you all over the place
hard make a good heuristic
My guess is that it would have to do something with coordinates and mod 3 or something to be better