Rapport Shadows of the night EP 2
Table des matières
1. Introduction
Explication et résolution du problème Shadows of the night épisode 2, que vous pouvez trouver ici. Cet épisode est le deuxième d’une série : épisode 1.
1.1. Déroulement du jeu
Dans l’épisode 2 de Shadows of the night, nous jouons toujours le rôle de Batman. Celui a, une fois de plus pour mission de sauver des otages situés dans un immeuble, où se situe une bombe. Pour cela Batman peut toujours se déplacer de fenêtre en fenêtre pour trouver la bombe.
Cependant dans cet épisode Batman possède un détecteur de bombe, qui peut seulement lui indiquer si il s’est rapproché de la bombe ou non depuis son dernier saut.
Le détecteur fourni les infos suivantes:
- UNKNOW : avant le premier saut
- WARMER : le point d’arrivée du saut est plus proche de la bombe que le point de départ (Batman se rapproche de la bombe)
- COLDER : le point de départ du saut est plus proche de la bombe que point d’arrivée (Batman s’éloigne de la bombe)
- SAME : Les points de départ et d’arrivée sont à la même distance de la bombe (Batman est la même distance de la bombe)
1.2. Données fournies
Pour résoudre ce problème on nous donne les données suivantes :
- W : le nombre de fenêtres en largeur du bâtiment
- H : le nombre de fenêtres de haut du bâtiment
- N : le nombre de saut possible avant l’explosion de la bombe
- X0 : la position en X de Batman au début du jeu
- Y0 : la position en Y de Batman au début du jeu
A chaque tour après avoir donné les coordonnées ou l’on souhaite déplacer Batman le programme nous fournira la nouvelle indication (WARMER, COLDER, SAME).
2. Méthode de résolution
2.1. Raisonnment
Dans un premier temps, on cherche à définir la coordonnée X de la bombe. Dans un second temps, on cherche à trouver la coordonnée Y de la bombe. Comme ces deux actions sont très similaires, pour éviter d’écrire deux fois la même chose on va écrire une fonction qui prendra en argument la position de Batman, la taille de l’immeuble et enfin si on cherche la coordonnée X ou Y.
Pour expliquer la fonction, on va prendre le cas de recherche de la coordonnée X, mais c’est similaire pour la coordonnée Y.
On commence par définir une zone de recherche composée de deux valeurs min et max qui définissent les bornes de la zone de recherche. Au début de la fonction les bornes sont égales à 0 pour min et la largeur du bâtiment pour max.
L’objectif est de diviser la zone de recherche en deux à chaque coup. Pour pouvoir y arriver, il faut donc placer Batman en symétrie par rapport au milieu de la zone de recherche.
Cependant il arrive qu’il soit nécessaire de placer Batman en dehors du bâtiment pour pouvoir couper la zone de recherche en deux. Puisque c’est impossible on place donc Batman au bord du bâtiment de ces cas là. L’inconvénient de placer Batman au bord c’est que le coup suivant n’apporte souvent aucune information. Pour résoudre ce problème, lorsque Batman sort du bâtiment, on le replace toujours au bord. Mais cette fois au tour suivant, on déplace Batman intentionnellement au milieu de la zone de recherche. Cela permet de rendre le coup encore suivant plus rentables si la bombe est au bord du bâtiment et permet ainsi de rééquilibrer les probabilités de la dichotomie.
2.2. Le programme
#include <stdlib.h> #include <stdio.h> struct Result { int x; // position de batman en x int y; // position de batman en y int result; // la colonne ou la ligne ou la bombe se retrouve }; struct Result dichotomie(int limite, int x, int y, int search_x) { /* limite: la taille de la grille (nombre de colonne ou de ligne) * x: position de batman en x au tour precedent * y: position de batman en y au tour precedent * search_x: 1 si on cherche la colonne, 0 si on cherche la ligne */ int min = 0; // le minimum de la zone de recherche int max = limite; // le maximum de la zone de recherche int value; // la prochaine poisition de batman int coupe; // la position de la coupe int coupe_juste; // 1 si la coupe est juste (la coupe est entre deux colonnes ou deux lignes) // 0 si la coupe n'est pas juste (la coupe est sur une colonne ou une ligne) int precedent; // la position de batman au tour precedent int sortie_min = 0; // 1 : batman est sorti de la zone de recherche a gauche/en haut au tour precedent et est a été remis au bord int sortie_max = 0; // 1 : batman est sorti de la zone de recherche a droite/en bas au tour precedent et est a été remis au bord fprintf(stderr, "dichotomie: min 0, max %d, x %d, y %d, search_x %d, \n", max, x, y, search_x); // si la zone de recherche fait deja une colonne ou une ligne, on retourne la position de batman if (min == max) { return (struct Result){x, y, min}; } // on determine la position de batman au tour precedent en fonction des parametres passes a la fonction if (search_x) { precedent = x; } else { precedent = y; } // tant que la zone de recherche n'est pas reduite a une colonne ou une ligne while (min != max) { // debug fprintf(stderr, "Zone de recherche: min: %d, max: %d, \n", min, max); if (sortie_max && max - min > 1) { // batman est sorti de la zone de recherche a droite/en bas au tour precedent et est a été remis au bord // on joue le prochain coup au centre de la zone de recherche value = (min + max) / 2; sortie_max = 0; } else if (sortie_min && max - min > 1) { // batman est sorti de la zone de recherche a gauche/en haut au tour precedent et est a été remis au bord // on joue le prochain coup au centre de la zone de recherche sortie_min = 0; value = (min + max) / 2; } else if (max - min >= 2 && (max - min) % 2 == 0) { // nombre impaire de colonnes/lignes coupe = (max + min) / 2; fprintf(stderr, "coupe sur: %d\n", coupe); if (precedent < coupe) { // batman était à gauche de la coupe, on le place à droite à la meme distance value = coupe + (coupe - precedent); } else if (precedent > coupe) { // batman était à droite de la coupe, on le place à gauche à la meme distance value = coupe - (precedent - coupe); } else { // batman était sur la coupe, on le place à droite // cela revient à couper entre deux colonnes value = coupe + 1; } } else if (max - min >= 1) { // nombre de colonnes/lignes pair coupe = (max + min) / 2; // 0.5 fprintf(stderr, "coupe entre %d et %d\n", coupe, coupe + 1); if (precedent <= coupe) { // batman était à gauche de la coupe, on le place à droite à la meme distance value = coupe + (coupe - precedent) + 1; } else { // batman était à droite de la coupe, on le place à gauche à la meme distance value = coupe - ((precedent - coupe) - 1); } } // si batman sort de la zone de recherche, on le replace au bord de la zone de recherche // et on active le flag de sortie if (value < 0) { // batman sort a gauche fprintf(stderr, "batman est en dessous du 0: %d\n", value); value = 0; sortie_min = 1; } else if (value > limite) { // batman sort a droite fprintf(stderr, "batman est dessus du max (%d) : %d \n", max, value); value = limite; sortie_max = 1; } // on calcule la position de la coupe pour le prochain tour coupe = (value + precedent) / 2; // on active le flag coupe_juste si la coupe est entre deux colonnes ou deux lignes coupe_juste = (value + precedent) % 2 == 1; // on joue le coup, en modifiant x ou y en fonction de ce qu'on cherche (search_x) if (search_x) { printf("%d %d\n", value, y); } else { printf("%d %d\n", x, value); } // Distance actuelle de la bombe par rapport à la distance précédente (COLDER, WARMER, SAME or UNKNOWN) char bombe_dir[11]; scanf("%s", bombe_dir); fprintf(stderr, "bombe direction: %s\n", bombe_dir); // on met à jour la zone de recherche if (bombe_dir[0] == 'S') // SAME { max = coupe; min = coupe; } else if (bombe_dir[0] == 'W') // WARMER { if (coupe_juste) // coupe entre colonnes/lignes { if (value <= coupe) { // batman est à gauche de la coupe if (coupe < max) { fprintf(stderr, "batman est à gauche de la coupe\n"); max = coupe; } } else { // batman est à droite de la coupe if (coupe + 1 > min) { fprintf(stderr, "batman est à droite de la coupe\n"); min = coupe + 1; } } } else // coupe sur une colonne { if (value < coupe) { // batman est à gauche de la coupe if (coupe - 1 < max) { fprintf(stderr, "batman est à gauche de la coupe\n"); max = coupe - 1; } } else { // batman est à droite de la coupe if (coupe + 1 > min) { fprintf(stderr, "batman est à droite de la coupe\n"); min = coupe + 1; } } } } else if (bombe_dir[0] == 'C') // COLDER { if (coupe_juste) { if (value <= coupe) { // batman est à gauche de la coupe if (coupe + 1 > min) { fprintf(stderr, "batman est à gauche de la coupe\n"); min = coupe + 1; } } else { // batman est à droite de la coupe if (coupe < max) { fprintf(stderr, "batman est à droite de la coupe\n"); max = coupe; } } } else { if (value < coupe) { // batman est à gauche de la coupe if (coupe + 1 > min) { fprintf(stderr, "batman est à gauche de la coupe\n"); min = coupe + 1; } } else { // batman est à droite de la coupe if (coupe - 1 < max) { fprintf(stderr, "batman est à droite de la coupe\n"); max = coupe - 1; } } } } // si la zone de recherche ne fait plus qu'une ligne/colonne, on a trouvé la ligne/colonne de la bombe if (min == max) { fprintf(stderr, "Bombe trouve en ligne/colonne : %d\n", min); // on renvoie la position de batman et la ligne/colonne de la bombe if (search_x) { return (struct Result){value, y, min}; } else { return (struct Result){x, value, min}; } } // on met à jour l'ancienne position de batman pour le prochain tour precedent = value; } } int main() { // hauteur de la tour int hauteur; // largeur de la tour int largeur; scanf("%d%d", &largeur, &hauteur); // nombre de tours avant la fin de la partie (inutile) int tentative; scanf("%d", &tentative); // position de départ de batman int X0; int Y0; scanf("%d%d", &X0, &Y0); // on lit maintenant les directions UNKNOW (inutile) char bombe_dir[11]; scanf("%s", bombe_dir); // on lance la recherche en x struct Result result_x = dichotomie(largeur - 1, X0, Y0, 1); X0 = result_x.x; Y0 = result_x.y; // on lance la recherche en y struct Result result_y = dichotomie(hauteur - 1, X0, Y0, 0); printf("%d %d\n", result_x.result, result_y.result); return 0; }
3. Analyse et tests
Le code fonctionnement parfaitement bien et passe tous les tests proposés par codingame sans erreur.
4. La solution de la communauté
Analyse du code de DaNinja : lien
#include <stdlib.h> #include <stdio.h> #include <string.h> #include <stdbool.h> struct {int lo,hi;} warm, cold; int W, H, N, x, y, px, py, lo, hi; int found_x = 0, outside = 0; int found(){ if (found_x) y=(lo+hi) / 2; // found y else { found_x = 1; x=(lo+hi) / 2; // found x, start search for y lo=0; hi=H-1; warm.lo = 0; warm.hi = hi; cold.lo = 0; cold.hi = hi; } return x==px && y==py; // calc next pos if already output } int get(int value, int limit){ int res = lo + hi - value; if (outside){ // take halfway point if was outside if (value==0) res = res / 2; if (value==limit) res = (limit+res) / 2; outside = 0; } if (res==value) res++; if (res<0) outside=1, res=0; if (res>limit) outside=1, res=limit; int l2 = (res+value-1)>>1, h2 = (res+value+1)>>1; if (res>value) warm.lo = h2, warm.hi = hi, cold.lo = lo, cold.hi = l2; else warm.lo = lo, warm.hi = l2, cold.lo = h2, cold.hi = hi; return res; } int main(){ scanf("%d%d", &W, &H); scanf("%d", &N); scanf("%d%d", &x, &y); lo = 0, hi = W; warm.lo = 0; warm.hi = hi; cold.lo = 0; cold.hi = hi; while (1) { px = x; py = y; char dir[11]; scanf("%s", dir); if (dir[0]=='W') lo=warm.lo, hi=warm.hi; if (dir[0]=='C') lo=cold.lo, hi=cold.hi; if ((dir[0]=='S' || lo>=hi) && !found()){} else { if (found_x) y=get(y,H-1); else x=get(x,W-1); } printf("%d %d\n", x,y); } }
J’ai choisie de code car il est extrement conci. De plus l’utilisateur utilise des structs pour c’est données. Ensuite, le code est beaucoup plus performant puisque au lieu de rechercher les coordonnées x puis y de la bombe. Ce code cherche simultanement les deux coordonées de manieres beaucoup plus efficace. On peu cependant un peu critiquer le code puisque de nombreuses lignes contiennent plusieurs opérations rendant le code moins facilement lisible et compréhensible.
5. Conclusion
Ce projet m’a permis de découvrir les `struct` qui permettent, par exemple de renvoyer plusieurs valeur pour une fonction.