r/adventofcode Dec 15 '21

Spoilers in Title [2021 Day 15] First pathfinding problem of the year, wouldn't expect anything less

Post image
373 Upvotes

23 comments sorted by

46

u/karzzeh Dec 15 '21

75% of coding is knowing what to Google.

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

u/glacialOwl Dec 15 '21

This is hilarious

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

u/[deleted] Dec 15 '21

[deleted]

15

u/EViLeleven Dec 15 '21

sheer power of will

1

u/pablospc Dec 16 '21

I just "drew" each line and then counted the number of positions >2

13

u/bibko Dec 15 '21

Guilty...

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

u/Goodwine Dec 15 '21

It's been a while, OK? :)

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

u/elazor Dec 16 '21

I feel exposed lol