Death First Search - Episode 1 - Puzzle discussion

Puzzles
#347

I don’t understand i complete all the IDE exemple but the submit didn’t work can you help me understand what i do wrong. My code is on python

type or paste code here
n, l, e = [int(i) for i in input().split()]
NOEUD=[]
PASS=[]
N=[]
Coeur=0
cont=0
for i in range(l):
    # n1: N1 and N2 defines a link between these nodes
    n1, n2 = [int(j) for j in input().split()]
    N=[n1,n2]
    NOEUD.append(N)
for i in range(e):
    ei = int(input())  # the index of a gateway node
    PASS.append(ei)
print(n, file=sys.stderr, flush=True)

# game loop
while True:
    si = int(input())  # The index of the node on which the Bobnet agent is positioned this turn
    for i in range(l):
        for j in range(len(PASS)):
            if PASS[j]<si:
                Noeud=[PASS[j],si]
            elif PASS[j]>si:
                Noeud=[si,PASS[j]]
            print(Noeud,NOEUD[i], file=sys.stderr, flush=True)
            if Noeud==NOEUD[i]:
                print(Noeud,si, file=sys.stderr, flush=True)
                x=Noeud[0]
                y=Noeud[1]
                print(x,y)
                cont=1
    if cont==0:
        if si-1<0:
            print(si,si+1)
        elif si+1>l:
            print(si-1,si)
        else:
            add=mt.ceil(si/2)
            print(add,add+1)
    cont=0```
#348

Take a look at the Validator 1 replay. There are only two links and your algorithm is choosing the wrong link to break. I would start there. I’ll bet what you find after getting your algorithm to properly choose the correct link in Validator 1 will help you with the tougher validators.

#349

I did this puzzle a year ago and I never even thought to try to satisfy achievement #3, so I’ll do this with you now - well, tomorrow anyway. Here’s my first thought. The Bobnet agent is 2 moves away from any gateway at the start, so the first link we cut is kind of a “free move”. Since we have a ton of options for our free move, I’m betting that some options are more powerful than others.

#350

My hints for the third achievement:

  • i find the nearest vulnerable gateway.
  • i select all links from the botnet location to the nearest vulnerable gateway (from the shortest path)
  • i simulate to cut all of theses links
  • i retain the better link analysing theses conditions
    - if i can fully protect the nearest gateway, it’s better
    - if i can fully protect more gateways, it’s even better
    - after all, i will select the nearest link from the botnet
#351

It still helps.
But it fills like cheat now :face_with_thermometer:

#353

Does anyone here know how to display the inputs so that I can get a better sense of what data is actually being inputted?

I can’t seem to access any of the data defined in the for loops that are used to initialize the function in the main while loop.

I have no idea how I’m supposed to figure out which connection to cut if I can’t even see which connections already exist.

#354

The default code shows you how to display the inputs, or any other info you want for debugging (using cerr in C++ for example).

1 Like
#355

:wave: Hi to all and thanks for this Puzzle !
→ the third achievement is harder than i could imagine …
But with a better analysis of my “failing” replays, i could build and try different strategies …
=> Today i found a good one :smiley: … so happy :+1: !
Bye, have :sun_with_face: sun, :dark_sunglasses: fun and :keyboard: CodinGames :handshake: …

#357

I don’t know how to make it faster?

I tried to make a prestorage of the link but I don’t know how I could have it writen before the main?

[mod edit: please avoid posting code on the forum]

#358

There are only a few nodes in the second test. Your issue isn’t that your code isn’t fast enough. Your code times out because it doesn’t output anything before the next round starts. You’ll see that if you add several “cerr” statements at various points in your code.

1 Like
#359

Hello Coders,

I am really enjoying the time spent here. But at this puzzle I think there should be limitations for the solution. Because I could solve it without the real solution of the deep problems inside it. (For example without deleting any edges in my graph…) I can show you some tests which I think should be solved with better algorithms but are not tested. Maybe there should be a possibility to check the test cases manually and without any visualization the agent could choose one of the shortest path to go.

This is a situation where you have to cut the edge which leads to a node which has 2 target neighbours.
8 7 4
0 1
0 2
1 6
1 7
2 3
3 4
3 5
4
5
6
7

SI : 0 // agent starts from node 0.

// Other case where the agent can choose from at least 2 equally long paths but there could be cut off 4 edges to separate all possible targets.

19 34 2
0 1
0 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
5 11
5 12
6 13
6 14
7 15
7 16
8 15
8 16
9 15
9 16
10 15
10 16
11 15
11 16
12 15
12 16
13 15
13 16
14 15
14 16
15 17
15 18
16 17
16 18
17
18

SI: 0 // agent start at node 0
#361

Hello,
I encounter a problem that seems to be a bug, I built my graph structure, but when I test using the “simple test”, I realise that one of the link is “0 0” which doesn’t make sense.
After debugging a bit, I found that it’s actually the input that doesn’t work correctly :
For some reason, I can’t upload image, but basically, I displayed n1 and n2 for the first edge, and its both 0 while it should be 0 1,
Does anyone knows why is that ?
Thank in advance

#362

Could you please copy and paste here:
(a) the contents of the console, and
(b) the code where you read and print the debug statements (just that part, no full code)?

#363

Nevermind, I just realise where the problem was, sorry for the inconvenience, I did write it before the cin command,

1 Like
#365

Hi.
Just solved it, leaving a little feedback

I feel like I have learned about bfs on the way but I do not feel like I have applied it because my solution wraps around it completely. I got stuck, sad, and then found a loophole. At the end, only thing I used is adjacency list and I think I got away with the fact that it was not directional graph.

Now going through other coders’ solutions to see how they did it to understand concept better and looking forward for next levels.
Graphics are great for the puzzle!

#366

Hi All,
nice puzzle… M.Dijsktra is my (your?) friend :wink: