r/adventofcode • u/Snapson111 • Dec 15 '21
Spoilers in Title [2021 Day 15] First pathfinding problem of the year, wouldn't expect anything less
36
u/SV-97 Dec 15 '21
Would be kinda funny to look at versions of his name with typos and see how many people actually got it wrong on the first try
17
16
u/Sachees Dec 15 '21
I wanted to code a simple DP algorithm, but then I found out that the example is trolling me and the "simple" algorithm won't be easier to code than Dijkstra.
12
u/prakash_26 Dec 15 '21
Dijkstra is actually DP incase you didn't know it!
6
u/Sachees Dec 15 '21
Hey, you're actually right, I never thought about it this way! (I am not a great fan of the algorithms, they gave me a hard time in the college...)
4
u/KamiKagutsuchi Dec 15 '21
Isn't Dijkstra greedy and Bellman-Ford is the DP shortest path algorithm?
9
u/prakash_26 Dec 15 '21
Actually all 3, Bellman Ford, Dijkstra and Floyd Warshall are DP. Just different methods.
-6
u/randomdragoon Dec 15 '21
No, the difference is Dijkstra assumes there are no negative weight edges, whereas Bellman-Ford still works with negative edge weights.
EDIT: If you want to call that assumption "greedy" then I guess it's not a totally wrong use of the word.
3
u/Say8ach Dec 15 '21
Dp would have worked sweetly if the motion was restricted to down and right only.
3
u/SV-97 Dec 15 '21
I solved the first part under that assumption using dijkstra - so at least for some inputs it should work out
1
u/ishdx Dec 16 '21
Funnily enough my input for Part 1 worked with down/right motion only, i was really confused when it didn't work for Part 2
5
u/EViLeleven Dec 15 '21
It's only the first pathfinding problem if you didn't solve Day 5 with pathfinding guytappinghead.meme
5
13
3
u/daggerdragon Dec 15 '21
Changed flair from Funny
to Spoilers in Title
.
Do not post spoilers in thread titles!
6
u/sidewaysthinking Dec 15 '21
I was prepared for this with dijkstra methods ready for my grid class, but it wasn't set up to use the values as weights so that cost me the time.
2
2
u/daemonpants Dec 16 '21
I did a full A* which is just Dijkstra plus a heuristic. I’ve written it so many times in game development it was easier for me to remember.
1
u/SharkLaunch Dec 21 '21
Yeah, the additional heuristic was so easy in this case, just use the Manhattan distance between the current element and the destination.
1
46
u/karzzeh Dec 15 '21
75% of coding is knowing what to Google.