Death First Search - Episode 1 - Puzzle discussion

Puzzles
#69

I feel a bit foolish, as I made this one more complex than I needed to – as a hint, realize that you are, in a sense, as fast as the AI – wherever it is, you can block it on your turn, so you don’t need to plan in advance…

#70

I got all 3 achievements and 100%… here is my findings:

Generally the agent moves “closer” to an exit but if there are several options I’m not 100% sure how it decides.
I think it might be trying to also minimize the distance from the other nodes perhaps? anyways it is clear that the agents agenda is actually not to use up all your links but to just move around in some pattern.

My algorithm did:
step 1: (using a simple Queue) calculate distance of each node from exit.
It is important that you keep updating your network as you remove nodes, and this is why you need to redo this every step.
O(n)

step 2:
My simple algorithm looked at all the nodes next to the agent and remove the link to the one with the lowest distance from any exit.
This is a simple algorithm and I don’t think this is optimal for bigger networks. But it was good enough for this problem.

2 Likes
#71

How can I see the console after I’ve submitted the code? I keep failing the fourth test after submit, and I don’t know why. In game test passes ok.

#72

Click to view the validator replay, click on the share button of the player, then open the console clicking the […]

#73

Thank you very much!

#75

What algorithm is the optimized one for the ambush achievement? I did Dijkstra’s but I suppose the algorithm to use is some kind of modified Ford-Fulkerson algo? ;D

#76

I have the same problem, triple star test isn’t working after validation, even though the replay shows the agent being blocked and unable to reach a gateway. My code was written in C#!

Also… I have 53 links remaining when the agent is stuck.

#77

58 Links left in IDE- Test still no achievement :C

#78

Amazing work.
You gave me some ideas to improve my algorithm and win that last achievement.
Thank you for the replay :slight_smile:

#79

Hi,

So graphs are not something I’ve dealt with previous to this puzzle. I understand the concepts well enough, however I’m having a hard time figuring out the correct way to set up the data structure. (I’m using C). I was thinking of setting up different structs for nodes and links but when I dive into implementing this it gets complicated fast and I feel like there must be a simpler way that I’m missing. Any advice on how to set up the data in this one would be helpful. Thanks!

#80

The simplest way is probably an adjacency matrix. If your graph has five nodes, you just make a 5x5 array. To insert an edge between two nodes a and b you set the element in the array at a,b and b,ato true, or some other value (weight).

An adjacency matrix is not very efficient if your graph contains a lot of nodes but just a few edges (called sparse).

PS: You have to be careful with the numbering of the nodes. In some games the testcases have n nodes, but the nodes are numbered arbitrary and not from 0 to n-1.

#81

My current strategy does not always save more than 50 links, but it appears to work the majority of the time.
It computes a balanced min cut on the graph.
When an opportunity arises, it will chip away at the cut, prioritizing the links that will further the agent’s distance to the nearest gateway.

There are more optimal metrics, but I find this one works quite well for me.

1 Like
#82

en fait j’ai terminé le défi avec 52 liens restants à 100% , donc normalement je devrais dévérouiller le succès embuscade et gagner +50 cp , mais voila j’ai rien gagner …

#83

I am having a problem with the game loop. At the second step it tells me that “your program did not provide an input in due time.” although my game loop always has an output no matter what. The algorithm I use is very simple :

  • If the agent is connected to a gateway, cut the link
  • Else cut a random link from the agent

Can someone help me pleas ? I am stuck. Thank you.

#84

Try inserting debug output in your code, so you can follow the execution of your code. The error stream could look something like this:

round: 0
agent at: 2
agent is not connected to a gate
random link: 2,3
cut link: 2,3

round: 1
agent at: 1
agent is connected to gate 5
cut link: 1,5

...

Also, what language are you using?

#85

The mistake was very stupid actually. I forgot the \n at the end of each console print! It works perfectly now.
I am using C++

#86

Done my work to left 50+. However, I’m still looking for better solution.

I’m just find out the shortest path of the skynet and block the front way of the skynet.

1 Like
#87

Bonjour,

Dans le test de la triple étoile, après 28 tours, le virus est stoppé sans être passé par un nœud de sortie, pourtant le challenge ‘Embuscade’ n’est pas validé alors qu’il reste 52 liens.

Est-ce que la limite des 50 liens est correcte ?

Cordialement,

Thoma

#88

The irony of the “Hardcode prevention system” is that you can hardcode a solution for the bonus trophy. The agent path and node ID’s are deterministic when validating.

#90

Did you also get the “Ambush” achievement with this approach?