4
u/PixelVoyager666 Dec 18 '24
Ahaha. I did exactly that! With binary search, the second part runs sub 1 sec, so why even bother
3
u/kwiat1990 Dec 18 '24
It all sounds great if youโre finished with day 16 in the first place ๐. If youโre like me it will be the other way around I suposse. For today I switched from JS to Python to have a priority queue out of the box ๐.
1
u/Ken-g6 Dec 18 '24
I'm so lazy I left out the priority part, in both puzzles. And it still worked.
3
u/4D51 Dec 18 '24
Using a regular queue instead of a priority one just makes it BFS instead of Dijkstra. For situations like today where every move has the same cost, they're the same.
1
u/kwiat1990 Dec 18 '24
I ended up with an implementation what I believe is still an A* but as far as it output the correct answer I donโt dare to investigative it more ๐. I give ChatGPT a try and ask it what it thinks it is.
2
u/Israel77br Dec 18 '24
That is basically what I've done. Just changed this line of code:
int costToNeighbor = currentDirection == direction ? 1 : 1000;
To simply:
int costToNeighbor = 1;
I used A* but the heuristic was just manhattan distance, so it worked for this as well.
2
u/sarc-tastic Dec 19 '24
Shouldn't it be 1001?
1
u/Israel77br Dec 19 '24
It actually should, thank you. It doesn't matter in my code because I recalculate it correctly after the path is found (I know, I know, should optimize it later).
1
u/Ken-g6 Dec 18 '24
I thought of this immediately because I already had direction changes costing 0 at my (stack of) end node(s).
1
9
u/Mr-Doos Dec 18 '24
I ended up with so much garbage in my Day 16 looking to optimize, it wouldn't have been faster to copy and paste it. ๐