Death First Search - Episode 1 – solution CodinGame en Java
Chaque tour, on lance un parcours en largeur depuis l'agent Skynet pour trouver la passerelle la plus proche, puis on coupe le premier lien de ce plus court chemin. Si l'agent est voisin d'une passerelle, c'est exactement ce lien qu'on coupe ; sinon, on retire un lien sur sa meilleure route. Dans l'Episode 1, chaque nœud touche au plus une passerelle, donc cette règle gloutonne ne perd jamais.
L'énoncé
Un réseau de N nœuds est relié par L liens non orientés, et E de ces nœuds sont des passerelles. Un agent viral part d'un nœud et avance d'un lien par tour vers une passerelle. Avant chacun de ses déplacements, on supprime un lien, et on gagne si l'agent ne peut plus jamais atteindre une passerelle.
Les premières lignes décrivent le graphe et listent les passerelles ; puis chaque tour, on reçoit le nœud courant de l'agent et on affiche les deux indices de nœuds dont on coupe le lien. Ce puzzle s'appelait auparavant Skynet: the Virus, puis Skynet Revolution - Episode 1 sur CodinGame.
La démarche, étape par étape
- Construire une liste d'adjacenceOn stocke les voisins de chaque nœud pour pouvoir retirer un lien de ses deux extrémités quand on le coupe. On garde un ensemble ou un drapeau pour les nœuds passerelles.
- Trouver la passerelle la plus proche par BFSOn lance un BFS depuis le nœud de l'agent et on s'arrête à la première passerelle défilée : comme le BFS explore par distance croissante, c'est la plus proche. On mémorise le prédécesseur de chaque nœud pour reconstruire le chemin.
- Couper le premier lien du cheminOn remonte de la passerelle vers l'agent et on coupe le lien entre l'agent et le nœud suivant sur ce chemin. Quand l'agent est voisin d'une passerelle, c'est le lien qui ferait perdre la partie immédiatement.
- Mettre à jour le graphe et recommencerOn retire le lien des deux listes d'adjacence, on l'affiche et on attend la nouvelle position de l'agent. On recalcule le BFS à chaque tour, car la route de l'agent change après chaque coupe.
Complexité
O(E·(N + L)) per turnO(N + L)Ce code lance un BFS par passerelle, chacun linéaire en la taille du graphe. Un seul BFS depuis l'agent qui s'arrête à la première passerelle donne la même réponse en O(N + L).
Code de la solution
Death First Search - Episode 1 – Java
Un objet Path est construit par BFS depuis l'agent vers chaque passerelle, et le plus court chemin non vide est coupé à son premier lien. Node conserve une liste chaînée de voisins, si bien que retirer un lien revient à une suppression dans la liste à chaque extrémité.
import java.util.*;
/**
* <b> Node is the class representing a node of the network. </b> Each node as :
* <ul>
* <li> a unique id, constant
* <li> a list of neighbour nodes
* </ul>
*/
class Node {
private final int n;
private LinkedList<Node> neighb;
public Node(int n) {
this.n = n;
neighb = new LinkedList<Node>();
}
public void addNeighb(Node m) {
neighb.add(m);
}
public void removeNeighb(Node m) {
neighb.remove(m);
}
public Node[] neighb() {
return neighb.toArray(new Node[neighb.size()]);
}
public int n() {
return n;
}
}
/**
* <b> Path is the class representing a path in the network, by a list of nodes </b>
*/
class Path {
private LinkedList<Node> p;
public Node getNode(int i) {
return p.get(i);
}
public int length() {
return p.size();
}
public void addFirst(Node n) {
p.addFirst(n);
}
public Path() {
p = new LinkedList<Node>();
}
/** This constructor builds a shortest path in the network described by
* nodes, between begin and end
*/
public Path (Node begin, Node end, Node[] nodes) {
p = new LinkedList<Node>();
int N = nodes.length;
/* For each node is kept a boolean equal to true if it has been visited
and an int equal to the node it has been visited from (initially = -1) */
boolean[] explored = new boolean[N];
for (int i=0; i < N ;i++)
explored[i] = false;
explored[begin.n()] = true;
int[] prec = new int[N];
for (int i=0; i < N; i++)
prec[i] = -1;
/* A BFS is performed, starting from node begin
and until finding the node end.*/
LinkedList<Node> q = new LinkedList<Node>();
q.add(begin);
Node n = null;
while((q.size() != 0) && (n = q.remove()) != end) {
for (Node m : n.neighb()) {
if(!explored[m.n()]) {
explored[m.n()] = true;
prec[m.n()] = n.n();
q.add(m);
}
}
}
/* if the queue is empty before finding the node end then
there is no path, the new path stays empty.
Else, a shortest path is identified by backtracing.*/
if (n == end) {
while(n != begin) {
this.addFirst(n);
n = nodes[prec[n.n()]];
}
this.addFirst(n);
}
}
}
class Player {
public static void cut(Node n1, Node n2){
n1.removeNeighb(n2);
n2.removeNeighb(n1);
System.out.println(n1.n() + " " + n2.n());
}
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
// Scanning number of nodes, links, and exits
int N = in.nextInt();
int L = in.nextInt();
int E = in.nextInt();
// Initializing an array of non-linked nodes
Node[] nodes = new Node[N];
for (int i = 0 ; i < N ; i++)
nodes[i] = new Node(i);
// Linking nodes
for (int i = 0; i < L; i++) {
int N1 = in.nextInt();
int N2 = in.nextInt();
nodes[N1].addNeighb(nodes[N2]);
nodes[N2].addNeighb(nodes[N1]);
}
// Initializing an array of exit nodes
Node[] exits = new Node[E];
for (int i = 0; i < E; i++)
exits[i] = nodes[in.nextInt()];
while (true) {
// Skynet agent position
int SI = in.nextInt();
/* Simple strategy : identify one shortest paths from Skynet
agent to each exit node, thanks to a Breadth First Searches
Then cutting the shortest, as close as possible to Skynet agent */
Path[] shortestPaths = new Path[E];
int minLength = Integer.MAX_VALUE;
Path pathToCut = null;
for (int i = 0 ; i < E ; i++) {
shortestPaths[i] = new Path(nodes[SI], exits[i], nodes);
int length = shortestPaths[i].length();
if ((length != 0) && (length < minLength)) {
minLength = length;
pathToCut = shortestPaths[i];
}
}
cut(pathToCut.getNode(0), pathToCut.getNode(1));
}
}
}
Death First Search - Episode 1 – Python
Même algorithme que la version Java. La file est une liste où les nouveaux nœuds sont insérés en tête et retirés en queue, ce qui est bien FIFO mais coûte O(n) par insertion ; collections.deque la rendrait en O(1).
import sys, math
class Node(object):
'''Class representing a node of the network, each node as :
a unique id, constant
a list of neighbour nodes'''
def __init__(self, n =0):
self.n = n
self.neighb = []
def addNeighb(self, m):
self.neighb.append(m)
def removeNeighb(self, m):
self.neighb.remove(m)
class Path(object):
'''class representing a path in the network, by a list of node'''
def __init__(self, begin, end, nodes):
'''This constructor builds a shortest path in the network described by
nodes, between begin and end'''
self.p = []
N = len(nodes)
# explored[i] is True <=> node i has been visited
# prec[i] = j <=> node i has been visited coming from node j
explored, prec = [], []
for i in range(N):
explored.append(False)
prec.append(-1)
explored[begin.n] = True
# A BFS is performed starting from node begin, until finding node end
q, n = [], None
q.append(begin)
while len(q) != 0:
n = q.pop()
if n == end:
break
else:
for m in n.neighb:
if not explored[m.n]:
explored[m.n] = True
prec[m.n] = n
q[0:0] = [m]
# if the queue is empty before finding end, there is no path
# else a shortest path is identified by backtracking
if n == end:
while n != begin:
self.p[0:0] = [n]
n = prec[n.n]
self.p[0:0] = [n]
def length(self):
return len(self.p)
def addFirst(self, n):
self.p[0:0] = [n]
def getNode(self, i):
return self.p[i]
def cut(n1, n2):
'''removes the edge between node n1 and n2'''
n1.removeNeighb(n2)
n2.removeNeighb(n1)
print("{} {}".format(n1.n, n2.n))
# number of nodes, links and exits
N, L, E = [int(i) for i in input().split()]
# initializing the array of nodes and linking them
nodes = []
for i in range(N):
nodes.append(Node(i))
for i in range(L):
N1, N2 = [int(j) for j in input().split()]
nodes[N1].addNeighb(nodes[N2])
nodes[N2].addNeighb(nodes[N1])
# initializing the array of exits
exits = []
for i in range(E):
exits.append(nodes[int(input())])
while 1:
# each turn, identifies one of the shortest paths from Skynet Agent
# to each exit node (by a Breadth First Search), then cuts the shortest
SI = int(input())
shortestPaths = []
minLength = 9999999
pathToCut = None
for i in range(E):
shortestPaths.append(Path(nodes[SI], exits[i], nodes))
length = shortestPaths[i].length()
if (length != 0) and (length < minLength):
minLength = length
pathToCut = shortestPaths[i]
cut(pathToCut.getNode(0), pathToCut.getNode(1))
Erreurs fréquentes
- Couper un lien de passerelle au hasardRetirer n'importe quel lien rattaché à une passerelle marche sur de minuscules graphes mais échoue quand l'agent est sur le point d'entrer dans une autre passerelle. Il faut toujours réagir à la position réelle de l'agent.
- Afficher un lien qui n'existe plusSi l'on oublie de retirer un lien coupé du graphe, le BFS suivant peut le choisir à nouveau et on perd un tour à afficher un lien déjà sectionné.
- Retirer le lien d'un seul côtéLes liens sont non orientés, donc il faut supprimer le voisin dans les deux sens. Sinon, le BFS continue de l'emprunter depuis l'autre extrémité.
- Utiliser un DFS pour trouver le cheminUn chemin en profondeur vers une passerelle n'est pas forcément le plus court : on risque de couper un lien lointain pendant que l'agent entre dans une passerelle voisine.
Pour aller plus loin
Pourquoi la règle gloutonne est-elle sûre dans l'Episode 1 ? Grâce à une garantie dans la conception des tests : aucun nœud n'est relié à deux passerelles. La seule situation dangereuse est un agent voisin d'une passerelle, et il y a alors exactement un lien dangereux, celui que la règle du BFS coupe. Quand l'agent n'est voisin d'aucune passerelle, il n'y a pas de menace immédiate et n'importe quelle coupe sur son plus court chemin convient. L'Episode 2 supprime cette garantie : des nœuds peuvent toucher deux passerelles, et l'agent peut créer une double menace impossible à parer en une seule coupe. Il faut alors couper à l'avance les liens des nœuds reliés à plusieurs passerelles, en priorisant ceux que l'agent peut atteindre sans passer par des déplacements « gratuits », ce qui explique qu'une simple coupe sur le plus court chemin ne se transpose pas.
Questions fréquentes
Faut-il un BFS par passerelle ?
Non. Un seul BFS depuis l'agent, arrêté à la première passerelle atteinte, trouve directement la plus proche et coûte E fois moins.
Dans quel ordre afficher les deux nœuds ?
Peu importe : le lien est non orienté et l'arbitre accepte « a b » comme « b a ».
Quelle différence avec l'Episode 2 ?
Dans l'Episode 2, un nœud peut être relié à deux passerelles : il faut anticiper les doubles menaces au lieu de réagir seulement à la passerelle la plus proche.