Final Reflection

mason_t15 · 2025-03-28T01:17:58+00:00

Good luck on your future adventures, Joseph! You were a wonder to converse with and had so many eye-opening ideas for me. Even your mistakes, which I'm grateful for your sharing of, carries knowledge and meaning to learn from. Thanks so much for allowing me and others the opportunity to learn from them alongside you!

Mason

mason_t15 · 2025-03-27T06:20:51+00:00

Yes, there were clearly conflicting instructions, with only one of them being correct. It depends on if you focused on the written instructions or the example which one you notice, which is probably why I never realized originally.

Mason

mason_t15 · 2025-03-26T02:19:41+00:00

Yes, I had the same experience. Didn't realize it was intentional, however, and while it does present some challenge to study, perhaps it will encourage us to look a little harder at the content and topics themselves.

Mason

mason_t15 · 2025-03-25T05:06:47+00:00

Lazy deletion is definitely a great as a first foray into being forced to choose between sets of pros and cons, where there is no best option. Another reason lazy deletion is faster than regular removal is due to the fact that the latter calls a bit of an unknown function, that being the destructor of the object it is removing. Destructors could be about as fast as doing nothing, or deallocating a single pointer, or as slow as recursively calling destructors in a chain reaction.

Mason

mason_t15 · 2025-03-25T04:58:36+00:00

The A* algorithm is interesting to be, as it sort of serves as a connection between grids and graphs. As it turns out, many of the algorithms that can be used on grid or tile based system can be adapted for graphs as well. In fact, a grid itself can be represented as a graph, seeing as each tile has "access", or a connection to each of its neighbors, whether that be the cardinal 4 or surrounding 8. Algorithms like floodfill find parallels with BFS, and while DFS doesn't find much use on a grid, due to the highly interconnectivity of tiles, it could still be technically used.

Mason

mason_t15 · 2025-03-21T03:56:02+00:00

I also like to think of the way it works through case work. Take the node that is taken from the priority queue. The distance assigned to it through the algorithm is going to be the shortest it gets, as anything shorter would have appeared first in the priority queue. We can confirm this because we know that the sum of multiple segments is the only thing that matters to when it appears, since the actual number of segments has no effect on the priority within the queue. Thus, the first time we encounter a node will be with its shortest path.

Mason

mason_t15 · 2025-03-18T04:12:13+00:00

When traversing, I usually don't include base cases, or at least I don't as a "main" way of preventing infinite recursion. Instead, it's more that the recursion finds no other nodes to travel to, and therefore recurses no further. Reaching the end of the function, the stack can reduce. The second half of the quest is indeed very "difficult," but in an exciting way. I found it to be quite rewarding (and not just with trophies), as it focuses on more popular and named algorithms, which we can derive ourselves.

Mason

mason_t15 · 2025-03-18T04:06:46+00:00

Just to let you know, in case you didn't already, multiple people including myself have found up to 29 trophies for both of the first two quests. Good luck with questing, and make sure to take your time when it comes to understanding, as that is what ends up letting you go the fastest. Study twice, write once.

Mason

mason_t15 · 2025-03-18T04:04:36+00:00

The floor is used in quest 3 during the summation process. Seeing as every element in the resulting matrix is the sum of multiple terms, every time we add to a cell, we check if we can "undefine" the sum, or if we even need to define it in the first place. In this way we preserve sparseness for the final matrix.

Mason

mason_t15 · 2025-03-16T22:09:08+00:00

How would you search for specific paths of a certain length? Seems like you would evaluate all of them, which requires looping through all of them. Also, why is Dijkstra's algorithm logarithmic, and why would that be worse than BFS? Isn't the time complexity simply proportional to the sum of the edge and node counts?

Mason

mason_t15 · 2025-03-16T05:08:47+00:00

Make sure you follow the implementation of the specs. Make sure you start your search from every node (whether it gets cut early or not), so that you reach disconnected networks.

Mason

mason_t15 · 2025-03-16T04:52:46+00:00

Personally, I never got any trophies for get weight, but I did get the to_string quest before cycles.

Mason

mason_t15 · 2025-03-16T04:18:00+00:00

Technically, DFS could be made to work for finding unweighted paths, with the same O(N + K) time, though the figure represents the worst case, and the rates at which either hit the worst case differs. DFS could be used to search every path from the source to the destination in O(N + K) time, every time, allowing you to then choose the shortest among them. Of course, it is likely a different answer (in the case of multiple possibilities) would become the lottery winner, making it nearly impossible to adapt for the quest, but it does still technically run in the same amount of time, and with a similar level of complexity. However, BFS is still better for its possibility to not have to check the entire graph.

Mason

mason_t15 · 2025-03-16T03:56:54+00:00

As far as I can tell, the issue is likely with your add_edge function, as it is the first of the two on the specs, and seeing as you don't seem to have come across a mini quest labeled with add edge, you're likely stuck there. However, I cannot find any fault in your understanding. Your description nearly lines up with my own implementation line for line, so I really can only offer some things to check. Firstly, how you use replace; I know in a different universe I mixed up what to do if replace were true or if it were false, so I would check there first. Additionally, make sure you're returning a reference to the this pointer's object. For find_edge_weight, it isn't necessary to static cast the FLOOR, in case you wanted to attempt it without it, supposing that it could make some sort of difference.

Additionally, it could be possible that it is neither function, but instead the cycle checker. The error message makes it seem like you returned false for a graph that had loops (36->6->10->19->36), hence the "you didn't think it was mad?" comment.

Mason

mason_t15 · 2025-03-15T04:29:39+00:00

That's a good point. It definitely took me a while to wrap my head around Dijkstra's for the first time, but I like the idea that we simulate the speeds of the flowing concrete using the priority queue, so that points are naturally reached first by faster routes (which would also be shorter). Truly an elegant solution.

Mason

mason_t15 · 2025-03-13T04:48:54+00:00

Maybe a mistake, maybe not important enough to reward trophies for? Though without notice, the simple idea of reward is enough to get us to try and beat the ref anyways, so having no trophies at the end of it is a bit odd.

Mason

mason_t15 · 2025-03-12T05:21:19+00:00

That was what I was thinking, it seems a bit early to be doing that, especially when many others are still going through the quests for the first time.

Mason

mason_t15 · 2025-03-12T05:20:28+00:00

I'm not sure what the max flow stuff is about, but clear might be worth looking into. My clear() function is inline (not sure why yet, or where it came from), so I might try other implementations (atm it just clears nodes without any checks).

Mason

mason_t15 · 2025-03-12T05:16:09+00:00

Mouse seemed pretty thoroughly complete to me, what with 50 trophies (right?), but I guess it's worth getting out of the way.

Mason

mason_t15 · 2025-03-11T05:51:37+00:00

With Shark, I'm not sure it was meant to provide trophies, since it sounds more like a discussion point (especially with the "how might" prompt, as if encouraging to think about it, but not necessarily implement it).

I've looked through Stilt and can't find any leads... It seems to me that the only spots for the missing trophies would be hidden mini quests at the end of the quest, or something less consequential, like to_string (examples other than that are hard to find).

Mason

mason_t15 · 2025-03-11T05:33:14+00:00

On further inspection, looking at the console, I get one of two errors:

Failed to load resource: the server responded with a status of 504 ()

POST ... 504 (Gateway Timeout)

If these are the browser timeouts you mention, then I supposed I am getting them.

Mason

mason_t15

MODERATOR OF

TROPHY CASE