Death First Search - Episode 2 - Puzzle discussion

Puzzles
#125

I really can’t figure out why only validator 4 isn’t working.

Basically, my code works like this (Javascript):
create array, push N1, N2 onto array.

Cycle through array, push onto graph.
Besides BFS, I have another BFS method in my class called shortestForcedpath (which checks for all paths where each one is connected to a gateway, to avoid all scenarios with forced moves leading up to a double gateway)

I am filtering out undefined, I just can’t figure out why my graph is adding things that didn’t exist.

Any ideas why validator 4 is so different?

Edit: Besides Validator 4, all other validators pass without issue.
Inside the graph, I am using an adjacency graph which just pushes items like

this.adj(u) = v

It’s just causing me to obsess because I can’t figure out what kind of inputs could cause my code to malfunction

#126

I think that Donotalo’s walkthrough: (A Depth-First Search Algorithm to Outmaneuver Skynet Robots – CodinGame Blog) should not be linked on the puzzle main page or only with a warning that it’s here for more advanced users who already solved the puzzle to compare notes because as a noob trying to level up in more advanced algorithms and get past the last hard test cases, you’ll restart from scratch trying to follow it in full, thinking that doing so will introduce you to BFS, DFS and the correct ways to use them for this particular puzzle, but this walkthrough absolutely doesn’t do that. The explanations are pretty messy and even lackadaisical when it comes to the details of the implementations of the algorithms, and it’s extremely frustrating to realize that once you finally get to the very end that the last DFS algorithm is returning some absolute gibberish because some important part is missing from the explanation about it or my implantation is just wrong because I misunderstood what it was supposed to be doing. It’s far from being a tutorial about DFS or BFS.

1 Like
#127

this is my algorithm :

  1. First check if bobnet is one step away from the gateway
    1. if true break that link
    2. else
      • Check if there is a node that has links with multiple gateways

        1. if exist :

          • you need to find the best node of that type where you will do that by using the DFS to simulate the path that bobnet will pass throw
          • of course you need to create a new graph since you will break some links
          • inside the DFS find the minimal path between the current node and a gateway
            (use Dijkstra to find that path)
          • sort the child node based on the length of the path
          • when you find that node (that shared links with multiple nodes) break one of these links

        2. else
          break any link exist

#128

is there a bug with validation test 1 and 4?

#129

Probably not, as more than 6000 players have solved the puzzle.

Do the validator replays show any buggy behaviour? If so, you may share the replay links here.

#130

For some reason my code does not pass validation test #5, even though none of it is hard-coded. I also can’t see what my program is outputting, so I literally don’t know what’s causing the validation output to differ from the test output :confused:

#131

If you click RESULTS (to the left of the puzzle statement), then DETAILS under MY REPORT, you can find the replays of the validators. You may then study what went wrong by watching the replays.

#132

I can see that it’s doing something wrong, and I have a faint idea of what that something is, but I can’t see what my program is outputting because the replay doesn’t output debug info. It’s the same shape graph as the one in the test case, just with the nodes having different names, so it has to be some sort of weird bug with my program (or unlikely, but still possibly, with the validation case itself).

There’s two nodes with two gateways connected with them in #5. In the test case, it correctly severs one of the edges of the bottom one:

But in the validation case, it goes for the top one instead:

#133

You may try deducing the inputs from the replay (for the entire case, or for relevant turn(s) only), and then running your code offline using those inputs to see what your program outputs.

#134

I did just that and got the correct output. I can privately send you the code to verify.

#135

Okay, so I managed to fix the issue with the help of @5DN1L (thanks a lot!). It turns out that, at least with the algorithm I had, the order of the input of edges changed the output of the algorithm for reasons I am still not entirely sure of.

My algorithm worked like this:
When the agent is not on a vertex next to a gateway – if it’s next to a gateway then the edge linking them would have to be cut, obviously – my algorithm would look at all of the vertices with more than one gateway. If there is only one than its edges take priority, because if the agent reaches that vertex, it’s game over. For the case with more than one such vertex, BFS was used to determine the shortest path for each of them (you could use Dijkstra but there’s really no point since the graph is unweighted). My algorithm then used the # of vertices that aren’t attached in a gateway (“free” vertices) to determine which of the shortest paths was the most “dangerous” (the lower the # the more edges are attached to gateways, thus forcing more moves and making the path more “dangerous”).

For one of the validators a peculiar bug appeared, dependent on the ordering of the edges, as mentioned above. As shown in a post above, the test case worked, but the validation of it didn’t. I found it strange, because the shapes of both graphs were identical, just with the vertices relabelled; no part of my solution was hard-coded, either. This was especially weird when I put the graph into my IDE and it picked the correct first edge to sever, whereas with the validator case it didn’t.

It turns out that the validation case turned was one of ~5% of cases where the edges of that graph inserted in a particular order caused my algorithm to pick the incorrect first edge to cut. This was because for those cases, one of the shortest paths went through a gateway, causing the # of “free” vertices of that path to go above that of the other one (gateways aren’t connected to other gateways, so it would count as a free vertex). My algorithm would thus determine that the path to the other vertex with multiple gateways was more dangerous, and cut one of the edges of that vertex instead.

The solution to such a seemingly perplexing issue was, when building the path, to check if the next vertex of the path was a gateway. This fixed the bug I experienced, which in the end, turned out to be caused by an oversight in the pathfinding algorithm I had not considered before. I suspect that this might be the issue for some of the other people who posted on this thread about failing the validation checks.

Moral of the story: if it seems like something is wrong with the validator, it might just be a hidden bug in your code that you overlooked. Just debug (print the output of various parts your program to see if something is going wrong) and test until you fix it.

1 Like
#136

PS: Who knows, maybe the issue with the 5% of cases might be another unforseen bug in my code XD

It kind of reminds me of this story, where a strange problem seemed to just randomly come out of nowhere, but ended up having a straightforward reason of occuring and subsequent fix.