Fork me on GitHub
#adventofcode
<
2023-12-17
>
roklenarcic07:12:07

Day 17 - Solutions

roklenarcic07:12:18

Was another quite easy day.

😁 2
norman13:12:55

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

gabor.veres15:12:58

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

alekszelark15:12:03

@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

👍 1
alekszelark17:12:29

Forgot I have my g2/plus function for adding delta. Now it is a bit faster 6.2 secs for part 2 :star-struck:

Ivana17:12:17

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 😊

roklenarcic19:12:21

If you used A*, what was your heuristic for max path length to goal?

Ivana21:12:23

I used deterministic algorythm without any heuristics

roklenarcic21:12:55

Isn’t that just dijkstra then?

Ivana21:12:27

No, just very tweaked Bellmann-Ford-like one

jurjanpaul12:12:42

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

roklenarcic12:12:41

manhattan distance is wrong heuristic

roklenarcic12:12:46

Consider field 0,0 -> 10, 10, you are on part 2, and your current position is 9,9. What is the maximum remaining path?

jurjanpaul12:12:11

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:

roklenarcic12:12:34

doesn’t need one…

roklenarcic12:12:07

I see that I got my idea about A* backwards

roklenarcic12:12:30

the heuristic function has to return less or equal to the real shortest path

roklenarcic12:12:42

I thought it was more or equal

jurjanpaul13:12:08

Interestingly, indeed simply estimating the remaining cost to be 0, turns out to not be significantly slower in this case.

roklenarcic13:12:30

yeah because the rules take you all over the place

roklenarcic13:12:51

hard make a good heuristic

roklenarcic13:12:25

My guess is that it would have to do something with coordinates and mod 3 or something to be better