Rapport Shadows of the night EP 1
Table des matières
1. Introduction
Explication et résolution du problème Shadows of the night que vous pouvez trouver ici
1.1. Déroulement du jeu
Dans l’épisode 1 de shadows of the night, nous jouons le rôle de Batman. Celui a pour mission de sauver les otages situés dans un immeuble d’une bombe. Pour cela Batman peut se déplacer de fenêtre en fenêtre pour trouver la bombe. Mais Batman a un nombre limité de sauts avant que la bombe explose, il doit donc faire vite et bien pour trouver la bombe.
Pour aider Batman à trouver la bombe celui-ci possède avec un détecteur qui nous permet avant chaque vers une nouvelle fenêtre de savoir dans quelle direction se trouve la bombe. Le détecteur fourni les indices suivant:
- U : la bombe se trouve au-dessus de sa position
- R : la bombe se trouve à droite de sa position
- D : la bombe se trouve en dessous de sa position
- L : la bombe se trouve à droite de sa position
- UR : la bombe se trouve au-dessus à droite de sa position
- UL : la bombe se trouve au-dessus à gauche de sa position
- DR : la bombe se trouve en dessous à droite de sa position
- DL : la bombe se trouve en dessous à gauche de sa position
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 batiment
- H : le nombre de fenetres de haut du batiment
- 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 tours après avoir donné les coordonnées ou l’on souhaite déplacer Batman, le programme nous fournira la nouvelle indication quand à la direction de la bombe.
2. Méthode de résolution
2.1. Raisonnement
Au début du jeu on définit la zone de recherche qui pourrait potentiellement contenir la bombe aux dimensions maximales du bâtiment. Puis à chaque tour en réduit la zone de recherche en fonction de l’indication qui nous est fournie sur à la direction de la bombe. On déplace ensuite Batman au centre de la zone de recherche pour diviser la zone de recherche le plus équitablement possible. On effectue donc une dichotomie à la fois verticale et horizontale en même temps en utilisant Batman comme pivot en le plaçant au centre de la zone de recherche.
2.2. Le programme
#include <stdlib.h> #include <stdio.h> int main() { // width of the building. int W; // height of the building. int H; scanf("%d%d", &W, &H); // maximum number of turns before game over. int N; scanf("%d", &N); int X0; int Y0; scanf("%d%d", &X0, &Y0); // debug fprintf(stderr, "W: %d, H: %d, N: %d, X0: %d, Y0: %d \r ", W, H, N, X0, Y0); int top_left_coner_x = 0; int top_left_coner_y = 0; int bottom_right_coner_x = W - 1; int bottom_right_coner_y = H - 1; // game loop while (1) { // the direction of the bombs from batman's current location (U, UR, R, DR, D, DL, L or UL) char bomb_dir[4]; scanf("%s", bomb_dir); // debug fprintf(stderr, "bomb_dir: %s \r ", bomb_dir); // Write an action using printf(). DON'T FORGET THE TRAILING \n // To debug: fprintf(stderr, "Debug messages...\n"); if (bomb_dir[0]=='U' && bomb_dir[1]=='\0') { top_left_coner_x = X0; bottom_right_coner_y = Y0 - 1; bottom_right_coner_x = X0; } else if (bomb_dir[0]=='U' && bomb_dir[1]=='R') { top_left_coner_x = X0 + 1; bottom_right_coner_y = Y0 - 1; } else if (bomb_dir[0]=='R' && bomb_dir[1]=='\0') { top_left_coner_x = X0 + 1; top_left_coner_y = Y0; bottom_right_coner_y = Y0; } else if (bomb_dir[0]=='D' && bomb_dir[1]=='R') { top_left_coner_x = X0 + 1; top_left_coner_y = Y0 + 1; } else if (bomb_dir[0]=='D' && bomb_dir[1]=='\0') { top_left_coner_x = X0; top_left_coner_y = Y0 + 1; bottom_right_coner_x = X0; } else if (bomb_dir[0]=='D' && bomb_dir[1]=='L') { bottom_right_coner_x = X0 - 1; top_left_coner_y = Y0 + 1; } else if (bomb_dir[0]=='L' && bomb_dir[1]=='\0') { top_left_coner_x = X0; bottom_right_coner_x = X0 - 1; bottom_right_coner_y = Y0; } else if (bomb_dir[0]=='U' && bomb_dir[1]=='L') { bottom_right_coner_x = X0 - 1; bottom_right_coner_y = Y0 - 1; } X0 = (top_left_coner_x + bottom_right_coner_x) / 2; Y0 = (top_left_coner_y + bottom_right_coner_y) / 2; // debug fprintf(stderr, "Rect %d %d - %d %d\n", top_left_coner_x, top_left_coner_y, bottom_right_coner_x, bottom_right_coner_y); // the location of the next window Batman should jump to. printf("%d %d \n", X0, Y0); } 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é
Solution de Alain-Delpuch : lien
#include <stdio.h> int main() { int W; // width of the building. int H; // height of the building. scanf("%d%d", &W, &H); int N; // maximum number of turns before game over. scanf("%d", &N); int X0; int Y0; scanf("%d%d", &X0, &Y0); int xmin = 0 ; int xmax = W ; int ymin = 0 ; int ymax = H ; // game loop while (N--) { char bombDir[4]; // the direction of the bombs from batman's current location (U, UR, R, DR, D, DL, L or UL) scanf("%s", bombDir); switch (bombDir[0]) { case 'U' : ymax = Y0 ; break ; case 'D' : ymin = Y0 ; break ; case 'R' : xmin = X0 ; break ; case 'L' : xmax = X0 ; break ; } switch (bombDir[1]) { case 'R' : xmin = X0 ; break ; case 'L' : xmax = X0 ; break ; } Y0 = (ymax + ymin)/2 ; X0 = (xmin + xmax)/2 ; printf("%d %d\n", X0, Y0); } }
J’ai choisi ce code car il utilise l’instruction `switch` qui permet de remplacer la longue suite de if/else if que contenait mon programme. Cela rend le code plus rapide et plus facile à lire. Par ailleurs le code est plus optimisé car il sépare les directions en deux parties U, D, R, L d’un côté et l’info secondaire R, L qui complémente la première information. Cela permet de retirer 2 cas de vérification.