Clojurians Log v2

Was another quite easy day.

https://gist.github.com/RokLenarcic/5edaaa4a667217a8bf6f298163f48337

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?

I used deterministic algorythm without any heuristics

Isn’t that just dijkstra then?

No, just very tweaked Bellmann-Ford-like one

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 (#scittle 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... 🤔

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

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...

@zelark, 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!

@gabor.veres 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 🤩