Death First Search - Episode 1 - Puzzle discussion

Puzzles
#23

You are right. The problem was, that in the validation tests, there is no link between nodes 0 and 1 (while in the tests, there are), and the program prints an error, if i select a link, that does not exist in the original graph. The description does not say, that the output must be an existing link, so i did not think of that. I modified the code to select a valid link, and it works now.
Thanks for the help.

2 Likes
#24

Solved it with little cute pathfinding recursion, so proud of myself right now :slight_smile:

Just remember: to cut an agent, you must think like an agent. Look for closest path to the gateway and cut it mercilessly. Repeat until done.

5 Likes
#25

My approach here was dead simple. At each step, I compute Skynet’s neighbour nodes. If any of these nodes is an exit, I cut that link. Otherwise, I just cut a random link next to Skynet. The amount of code needed was also ridiculously small - my main function is only 12 lines long. Perhaps this challenge should be moved to the easy problem section


6 Likes
#26

Yeah, I agree that if you don’t try and find a solution that might be acceptable for the second level, this exercise is pretty simple

#27

J’ai rĂ©ussi tous les tests, mais lorsque que je fais envoyer le code je n’obtiens pas les points pour â€œĂ©toile” et “triple Ă©toile”. Mon code est vraiment simple, il consiste Ă  regarder s’il existe un lien entre l’agent et une passerelle, s’il y en a un il le coupe, sinon il affiche (“0 1”), ce qui ne fait rien bugger mĂȘme si ce lien 0 - 1 a dĂ©jĂ  Ă©tĂ© coupé  Donc les tests fonctionnent trĂšs bien avant de les envoyer, mais aprĂšs les avoir envoyĂ©s les deux derniers ne dĂ©marrent mĂȘme pas. Merci de m’aider ça ne m’est jamais arrivĂ© ^^.

edit : J’ai remplacĂ© le print(“0 1”) par print(N1,N2) qui est en fait le dernier noeud donnĂ© en entrĂ©e
 Je ne vois vraiment pas ce que ça change mais en tout cas ça fonctionne, si quelqu’un a une explication rationnelle je suis preneur x).

#29

je crois me souvenir que si le lien X-Y n’existe pas, cela fait planter le programme.

Dans les tests, le lien 0-1 doit exister, mais pas dans les corrections qui sont légÚrement différentes.

#30

Bonjour a tous un petit soucis sur ce puzzle, les gateways (porte de sortie) ne sortent pas correctement.
Le plus souvent, SI=EI a l’initialisation(dans les chiffres pas a l’écran). Du coup dur dur de gagner.

Je code en C++, si quelqu’un a dĂ©jĂ  rencontre ce problĂšme


PS je viens de lire vos solutions, qui sont en effet trùs simples, personnellement je voulais recoder dijkstra, du coup
 c’est bien plus long xD

#31

dijkstra tu en auras besoin pour ‘skynet strikes back’, et plein d’autre puzzle, donc ce sera pas perdu.

Peut tu ĂȘtre plus prĂ©cis au niveau de ta question? Quel code a tu utiliser pour parser l’input? Le code par dĂ©faut marche trĂšs bien.

#32

Merci pour cette réponse, pour le moins rapide !

Effectivement c’est un problùme d’input, j’utilise l’input sans le parser.
Si tu te souviens “SI” indique la position du “mĂ©chant” et la liste des “EI” retourne ses portes de sortie.
Le problĂšme c’est que je ne rĂ©cupĂšre pas les bonnes portes de sorties. Puisque “EI” ne correspond jamais a la position de la porte de sortie a l’écran


Attends je viens d’avoir une idee. Il est possible que j’ai inverse l’ordre de des cin >>
Je vérifie ça et je te dis.

#33

Bon c’est bien ça !

Un malencontreux Crt-K Crt-Y. Donc ça peut paraĂźtre Ă©vident, mais l’ordre des “cin>>” compte.
Du coup, si vous avez un problĂšme d’input checkez en prioritĂ© l’ordre de vos “cin>>” avec la version initiale !
Merci CvxFous, bizarrement ton post m’a menĂ© a la solution.

#alwaysblameyourself

#34

Even I followed the similar approach but this ways you won’t score 100%, tricky part comes when you have to restrict the agent with more than 50 links left in the 4th test case. That was not easy I think

#35

The 50 links left trophy is a bonus trophy, you don’t have to do it to get 100%.

#36

Yup!! my bad. I mean to say that bonus trophy, I’m stuck there, any help is appreciated.

#37

try isolating the biggest star whenever you can :wink:

#38

hi
seems legit
 i implemented that, but I’ve got only one try

all other moves are forced as when the agent get on a star, he turns around, then go another star (which are linked) and I always have to cut the link to the gateway

1 Like
#39

How many people have earned the 50 links left trophy?

#40

Heys, not sure if this is where I should report for a possible bug.

The thing is, I did mine with javascript, managed to pass all the tests but after validation, it shows I’ve only completed 75%. Any advice? :smile:

#42

Same here. After first move the bot manage to always stay next to a gateway => no choice to cut anything else that the link to this gateway. It ends up with less 50 links up in the end.

The bot has not the same IA during final validation tests.
I had to reverse my graph loops to achieve the 50 links bonus during those tests while it was ok in the local tests (it changes the first move of skynet and eventually IA make less clever move afterwards)

When I look into the issue, I think a good skynet IA should be able to never let us isolate it with more than 50 links still open.

Interesting though.

1 Like
#43

It’s the other way around, the IA bot cannot prevent you from ending up with 50+ links if YOUR IA is optimized.

1 Like
#44

I finished last test case with 52 steps left and i cant get the final achievement, any ideas why ??!!