For part 1 there actually is a non-brute force algorithm, since it is a directed acyclic graph (DAG) and for those you can find the longest path by topological sorting your graph and then loop through the sorted list and remember the highest costs. In real life that algorithm is used in job scheduling to find the next job while respecting all previous dependencies to run in an efficient manner. Part 2 was indeed brute-forcing for me as well since now the graph contains cycles.
This has been really helpful, thank you. It's lead me down paths for a lots of additional reading/learnings, such as DAG and topological sorting. Annoyingly my part 2 actual result is too high, while the test is fine. I predict lots of staring at the screen in my future.
First of all, thank you for your fantastic videos on AoC! For me I started doing edge contraction in part 2 (did not know the name for it before though) but my simple brute force recursive search function in c++ solved it in about a minute so I didn't finish my code!
I solved it using brute force too. Was quite unhappy about the slow running time. But now I know what's the problem with longest path. Didn't think about that before.
Sorry, I don't understand what the seen set is doing in the dfs function. I see that you add a point, find all paths from that point, then remove the point. But seen set doesn't seem to be used otherwise? at least not as part of some conditional. Unless I'm (probably) missing something.
You said initializing max = 0 'would probably work'. I don't understand why initializing it to 0, -1, or -infinity seems to return three different values. Any insight?
@@chicomferreira No. I messed around for a bit and picking different numbers and some range in like -350 or so made it 'work' correctly and I had to move on to something else and never came back to investigate further. Are you unable to use -Infinity (or equivalent)?
I had the same problem with getting different results and this was in part because I was testing for 'end' incorrectly. When I fixed this and initialized max to int.MinValue (C#) the answer was revealed. Note, part 1 tolerates max starting at 0 with no 'end' validation checking. Part 2 does not... GPT answered for me why the max must start at a wildly improbable number: When you initialize max to 0, the algorithm behaves differently in the scenario where a path does not exist or when the recursive calls do not find a valid path from the current point to the endPoint. Here’s why: 1. Initialization to int.MinValue: This ensures that any valid path found (even if it has a negative distance) will be larger than int.MinValue. This way, if no valid path is found, max remains int.MinValue, which is a clear indication that no path exists. 2. Initialization to 0: This assumes that the minimum possible distance is zero. If no valid path is found, max remains 0, which is interpreted as a valid distance. This can cause incorrect results because 0 might not be the correct maximum distance if no path exists.
Dijkstra relies on that you found the shortest path up until the point where you are in the search. When you visit a new node you know that there is no shorter path to this node. For longest path the premise does not hold. There could be another way of reaching that node in a longer path using the still unexplored part of the grid.
You can use a default python list as a queue. Just do pop(0) to get the first element and then just append to the end as usual. It makes it very quick to switch between bfs and dfs 🎉
For part 1 there actually is a non-brute force algorithm, since it is a directed acyclic graph (DAG) and for those you can find the longest path by topological sorting your graph and then loop through the sorted list and remember the highest costs. In real life that algorithm is used in job scheduling to find the next job while respecting all previous dependencies to run in an efficient manner. Part 2 was indeed brute-forcing for me as well since now the graph contains cycles.
This has been really helpful, thank you. It's lead me down paths for a lots of additional reading/learnings, such as DAG and topological sorting.
Annoyingly my part 2 actual result is too high, while the test is fine. I predict lots of staring at the screen in my future.
First of all, thank you for your fantastic videos on AoC! For me I started doing edge contraction in part 2 (did not know the name for it before though) but my simple brute force recursive search function in c++ solved it in about a minute so I didn't finish my code!
This was a great video. Helped clarify the types of things I need to learn more about!
I solved it using brute force too. Was quite unhappy about the slow running time. But now I know what's the problem with longest path. Didn't think about that before.
Wonderful explanations every time! Could you tell me what the whiteboard software/website is that you use?
It's a website called Excalidraw
Sorry, I don't understand what the seen set is doing in the dfs function. I see that you add a point, find all paths from that point, then remove the point. But seen set doesn't seem to be used otherwise? at least not as part of some conditional. Unless I'm (probably) missing something.
woops just didnt watch long enough lol
You said initializing max = 0 'would probably work'. I don't understand why initializing it to 0, -1, or -infinity seems to return three different values. Any insight?
have you found the reason? i am dealing with the same strange behavior
@@chicomferreira No. I messed around for a bit and picking different numbers and some range in like -350 or so made it 'work' correctly and I had to move on to something else and never came back to investigate further. Are you unable to use -Infinity (or equivalent)?
I had the same problem with getting different results and this was in part because I was testing for 'end' incorrectly. When I fixed this and initialized max to int.MinValue (C#) the answer was revealed.
Note, part 1 tolerates max starting at 0 with no 'end' validation checking. Part 2 does not...
GPT answered for me why the max must start at a wildly improbable number:
When you initialize max to 0, the algorithm behaves differently in the scenario where a path does not exist or when the recursive calls do not find a valid path from the current point to the endPoint. Here’s why:
1. Initialization to int.MinValue: This ensures that any valid path found (even if it has a negative distance) will be larger than int.MinValue. This way, if no valid path is found, max remains int.MinValue, which is a clear indication that no path exists.
2. Initialization to 0: This assumes that the minimum possible distance is zero. If no valid path is found, max remains 0, which is interpreted as a valid distance. This can cause incorrect results because 0 might not be the correct maximum distance if no path exists.
hey, can someone explain why dijkstra doesn't work for this problem?
we could simply use negative numbers to still find the minimum as dijkstra needs.
I too am very interested why this won’t work.
Dijkstra's is for shortest
Dijkstra relies on that you found the shortest path up until the point where you are in the search. When you visit a new node you know that there is no shorter path to this node. For longest path the premise does not hold. There could be another way of reaching that node in a longer path using the still unexplored part of the grid.
You can use a default python list as a queue. Just do pop(0) to get the first element and then just append to the end as usual. It makes it very quick to switch between bfs and dfs 🎉
👍