I ended up just coding up an a* library in common lisp that is generic (handles arbitrary graphs) and then just imported it.
I’m sure python likely just has pip install astar :slightly_smiling_face:
@badkins - pinging you here since I think your post (re: graph module) in #general was intended to be here?
No, it was a general question, and I haven’t implemented part 2 yet, so I didn’t want to see any spoilers. Although, if the graph module can’t handle the new size, I’ll have to think of something else :)
It was fast enough for 100x100, but I’m not 100% sure it will be for 500x500 since it’s computing all shortest paths from the source i.e. 250K of them :)
I hand coded A*, but also decided that while I was doing it I might as well package it up nicely for generic use in the future. It ends up taking ~7s to run on the large data set. Coming up with a better H(x,y) function other than a simple sum-of-distances would likely produce faster results.
The only thing about part 2 that’s “tricky” other than the size is how the tiling is done (and wrapping of numbers). That tripped me up a bit.
I got my part 2 down from 5s to about 300ms by changing the sorting function in my heap. Rather than storing pairs of (position, cost) and having the function extract the cost from the pair, I used < and packed the cost and position into a fixnum, with the cost shifted 32 bits to the left.
<https://github.com/benknoble/advent2021/blob/main/day15/solution.rkt> Building the graph for part2 took me a while to get right. I… did not write an A*, and just use graph’s dijkstra :slightly_smiling_face: 240s, of which 75s is building the graph, for part2 (998000 edges is a lot).
<https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2021/solutions/day15/day15.rkt|Day 15> - rather slow for part 2 using dijkstra from graph, but it got it done :)
Okay… I’ve finished spending way too much time on this one. But, I’ve come to the conclusion that it’s a bad puzzle (IMO). All that’s being measured is whether or not you can actually code Dijkstra (or know to use a library) and the performance of your language.
Basically it’s a pathological setup that can’t be optimized:
• There are no obstacles/impassable nodes • There are no diagonal moves allows (meaning any heuristic needs to be Manhattan) • The start and goal nodes are at corners Basically at every step you are guaranteeing that you’ll improve your position exactly the same amount (heuristically) regardless of which choice is made. The only difference is in the cost per node.
So, regardless of path chosen, eventually you’ll run into a situation where your priority queue of nodes to search will be to go back near the beginning and try the other way. Except that most of the time, you aren’t improving anything.
If you attempt to modify the heuristic to value being closer to the goal more (a wise thing to do), you end up overestimating the value of the path you’re searching and never backtrack to find the optimal path.
For my part 2, if I run it with no heuristic (read: dijkstra) or manhattan, I end up with essentially the same results and the correct optimal cost:
#<ASTAR::PATH of length 998 with cost 2846>
249996 The second value is the total number of nodes searched (so 99.99%). And it takes 1.4s to do.
If I instead use a better heuristic overvaluing being closer to the end goal, the search space is reduced considerably (0.04s), but I don’t get the optimal path:
#<ASTAR::PATH of length 998 with cost 3100>
7734 So, anyway, unlike most every other “large problem space” puzzle AOC has done in the past, this one was unoptimizable. :disappointed:
If anyone happens to know of a heuristic function they’d like me to try out, though, I’m more than happy to.
~36~ (Edit: sorry, cat on the keyboard …)
I would have used a bunch more emoticons in that reaction, but Slack doesnt have all the meow- emoji that Discord does :)
I coded up a <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2021/solutions/day15/day15-conspicio.rkt|concise & fast version> using ideas I gleaned from a few different solutions. Takes about 375 ms for part 2.
A 2,000 x 2,000 grid takes less than 6 seconds.
Day 16 spoilers
Padding tripped me up so much today lol
@badkins - using the code code you posted and having it load my real data, part 2 takes 5 seconds to run. Are you sure? The code looks exactly the same as dijkstra: add distance from start + cost of next space onto sorted list, pop next best, repeat until goal.
I also added a nodes-searched counter that’s incremented each iteration of the loop and it searched 249,998 nodes (on my data), which is 99.999% of the grid.
This was one day I was really happy for Common Lisp. Using ldb made this one an absolute breeze to do.
That’s neat. I decided to treat it as a string parsing problem early on and that probably made it harder for me than necessary.
One thing that has struck me doing AOC the past few years is that whatever first idea comes to my mind when I dive in either makes or breaks me.
I’ve also discovered that my threshold for giving up on an idea and starting fresh is probably higher than it should be. It makes me wonder if that threshold is the same - or lower (or maybe even higher?) - at work when discussing solutions w/ teammates. I’d like to think it’s lower and I can be convinced to give up/listen to other ideas.
I think I’ll ask about that w/ some blunt co-workers tomorrow. :wink:
Day 8 this year was definitely like that for me. I think it was 3am before I finally decided it was time to stop, go to sleep, etc. Woke up, took a different approach, and was done in 20 minutes.
I know what you mean. Compared to work, though, I think the competitive factor plays a big role here in how much I dig into my first approach, because it’s a sunk cost. Even though I know it’s pointless for me to try and get a high score (these get posted at 7am my time, which is about when I get up), I still pressure myself to do them quickly.
@popa.bogdanp Just looking at your code… Could your data just be defined as (format "~b" (string->number (read-line) 16)) ?
instead of all the manual conversion from hex -> binary?
I tried that initially and something was wrong with the result so I just changed it without investigating
I’ll probably clean it up later today :D
everything else is neat to look at. love seeing different solutions
> something was wrong with the result My guess is that - since you were dealing with strings (as opposed to actual bits/numbers) - you would have been missing leading 0’s in the MSB positions. Your string conversion handles that.
That must’ve been it.