The Paranoid Android – solution CodinGame en C
On mémorise, pour chaque étage, la colonne que les clones doivent atteindre : la position de l'ascenseur à chaque étage et celle de la sortie à l'étage de sortie. Chaque tour, on ne regarde que le clone de tête : s'il marche vers la gauche alors que sa cible est à sa droite, ou vers la droite alors qu'elle est à sa gauche, on répond BLOCK ; dans tous les autres cas, y compris quand il n'y a aucun clone (étage -1), on répond WAIT.
L'énoncé
Des clones sortent d'un générateur à l'étage du bas l'un après l'autre et marchent en ligne droite, ne faisant demi-tour que lorsqu'ils rencontrent un clone bloqué. Chaque étage possède un ascenseur qui monte un clone à l'étage supérieur, et la sortie se trouve au dernier étage. On connaît le nombre d'étages, la largeur de la zone, le nombre de tours, la position de la sortie, le nombre de clones disponibles et la position de chaque ascenseur.
Chaque tour, on reçoit l'étage, la position et la direction du clone de tête (ou -1 -1 NONE s'il n'y en a aucun) et on répond WAIT ou BLOCK. Un clone bloqué reste sur place comme un mur qui renvoie les autres. Il faut amener au moins un clone à la sortie avant d'épuiser les tours ou les clones.
La démarche, étape par étape
- Lire toute la ligne d'initialisationLa première ligne contient huit entiers ; seuls le nombre d'étages, l'étage de sortie et la position de la sortie comptent pour cet épisode. On lit ensuite une ligne par ascenseur et on stocke sa position indexée par étage.
- Définir une cible par étagetarget[f] est la colonne de l'ascenseur à l'étage f, et target[exitFloor] celle de la sortie. Avec ce tableau, chaque étage devient le même sous-problème : atteindre une colonne connue.
- Décider uniquement sur le clone de têteSi le clone va vers LEFT avec pos < target, ou vers RIGHT avec pos > target, il s'éloigne de son but : on le bloque. Le clone suivant viendra buter contre lui et repartira dans la bonne direction.
- Attendre dans tous les autres casQuand le clone se dirige déjà vers sa cible, se trouve dessus, ou quand il n'y a pas de clone de tête (étage -1), on répond WAIT. On ne bloque jamais un clone situé sur sa colonne cible : il est sur le point de prendre l'ascenseur.
Complexité
O(1) per turnO(F)Après une préparation en O(F) pour les cibles par étage, chaque tour se réduit à une comparaison. F est le nombre d'étages.
Code de la solution
The Paranoid Android – C
#include <stdio.h>
int main(void) {
int nbFloors, width, nbRounds, exitFloor, exitPos, nbClones, nbAddElevators, nbElevators;
scanf("%d %d %d %d %d %d %d %d", &nbFloors, &width, &nbRounds, &exitFloor,
&exitPos, &nbClones, &nbAddElevators, &nbElevators);
/* target[f] = column the leading clone must reach on floor f */
int target[nbFloors];
target[exitFloor] = exitPos;
for (int i = 0; i < nbElevators; i++) {
int f, pos;
scanf("%d %d", &f, &pos);
target[f] = pos;
}
while (1) {
int floor, pos;
char dir[11];
scanf("%d %d %10s", &floor, &pos, dir);
/* block only a clone that walks away from its target */
if (floor >= 0 && ((dir[0] == 'L' && pos < target[floor]) ||
(dir[0] == 'R' && pos > target[floor])))
printf("BLOCK\n");
else
printf("WAIT\n");
fflush(stdout);
}
return 0;
}
Erreurs fréquentes
- Bloquer quand il n'y a aucun cloneQuand aucun clone n'est en jeu, on reçoit l'étage -1. Indexer le tableau des cibles avec -1 lit n'importe quoi, et envoyer BLOCK dans ce cas est invalide ; il suffit de répondre WAIT.
- Oublier l'étage de sortieIl n'y a pas d'ascenseur à l'étage de sortie, donc un tableau de cibles rempli uniquement à partir de la liste des ascenseurs laisse cet étage indéfini. Il faut insérer la position de la sortie à exitFloor avant la boucle de jeu.
- Bloquer le clone qui vient de faire demi-tourCertaines solutions tentent de suivre les clones déjà bloqués et finissent par bloquer aussi le leader suivant. Aucune mémoire n'est nécessaire : le nouveau leader est réévalué avec la même règle et, après avoir rebondi, il marche déjà dans le bon sens.
- Mal orienter la comparaison stricteBloquer quand pos <= target pour un clone allant à gauche bloque aussi un clone qui se tient sur son ascenseur. Cela gaspille un clone et peut condamner la colonne de l'ascenseur pour de bon.
Pour aller plus loin
Une seule comparaison suffit parce que tous les clones quittent le générateur dans la même direction et la conservent quand ils prennent un ascenseur. Chaque étage n'est donc abordé qu'une fois par le clone de tête, et au plus un BLOCK par étage est nécessaire : soit le clone arrive face à sa cible et y va tout droit, soit il arrive dos à elle et un seul sacrifice retourne tous ceux qui le suivent. On obtient ainsi une borne d'un clone sacrifié par étage, ce qui explique que cette règle gloutonne tienne dans le budget de clones des tests. La suite difficile, « The Paranoid Android - One step further », casse cette propriété : certains étages ont plusieurs ascenseurs ou aucun, et il faut en construire, si bien que le problème devient une recherche de plus court chemin sur des états (étage, position, direction).
Questions fréquentes
Pourquoi ne regarder que le clone de tête ?
Les clones qui suivent le leader empruntent le même chemin quelques cases plus tard. Ce qu'on fait au leader (le laisser passer ou le bloquer) décide de la direction de tout le groupe à cet étage.
Que signifie la direction NONE ?
Elle accompagne l'étage -1 et la position -1 quand aucun clone ne marche, typiquement au départ ou juste après un blocage. On répond WAIT et le clone suivant apparaît.
Quelle différence avec « One step further » ?
Dans la suite, on peut construire des ascenseurs supplémentaires et certains étages en ont plusieurs ou aucun : la règle gloutonne « bloquer s'il s'éloigne » ne suffit plus et il faut une recherche dans un graphe.