Batman

Table of Contents

1 Shadow of the Night

1.1 Introduction

Dans shadow of the Night, Batman se situe sur un immeuble qui peut être représenter par une grille. Sur cette grille, se trouve une bombe. Initialement, on connais la position de Batman et on ignore celle de la bombe. Batman dispose de N tours pour trouver la bombe, et la désarmorser. À chaque tour :

  • Batman obtient une indication par rapport à la position relative de la bombe par rapport à Batman. (Es ce que la bombe se trouve à droite/gauche/haut/bas de batman)
  • Batman indique la position (x,y) de la tuile sur laquelle il saute.

tumblr_n2tokwxVpJ1qa70eyo2_r1_500.png

Figure 1: Le tout n'est pas de trouver la bombe, mais aussi de la désamorcer

1.2 Résolution

debut.png

Figure 2: Premier Cas

Une solution pour résoudre ce problème est de déterminer une sous grille de la grille initalie dans laquel la bombe se situe. Pour celà, on note XMin, XMax, YMin et YMax les coordonnées de la sous grille dans laquelle la bombe se situe, et PosX et PosY la position de batman.

  • Si la bombe se situe vers la droite de Batman, alors il doit se déplacer vers la droite, même si on ignore de combien de case. Partant de cette conclusion, on sais que XMin = PosX, et on déplace batman de la moitier de la grille relatif, c'est à dire PosX += (XMax-XMin) / 2.
  • Si la bombe se situe vers la gauche, on peut déterminer XMax au lieu de XMin, et on déplace Batman vers la gauche.
  • Même histoire si Batman doit se déplacer en haut ou en bas, mais on utilise YMin au lieu de XMin et YMax = XMax.

Par exemple :

et0.png

Figure 3: Tour 0

et1.png

Figure 4: Tour 1

et2.png

Figure 5: Tour 2

Ici Batman sait à chaque tour que la bombe se situe en haut à droite, mais il ignore de combien de case. A chaque tour, chaque axe de la grille dans laquel la bombe se situe est divisé par 2, jusqu'à ce que Batman trouve la bombe.

1.3 Programme en C

(Mon cote @Mewily sur coding game)

 1: #include <stdio.h>
 2: 
 3: int main()
 4: {
 5:     int PosX, PosY, XMax, YMax, MaxTurn;
 6:     scanf("%i %i %d %d %d", &XMax, &YMax, &MaxTurn, &PosX, &PosY); //Read the input
 7:     int XMin = 0, YMin = 0;
 8: 
 9:     while (1)  // Game loop
10:     {
11: 	char BombDir[2] = "??";
12: 	scanf("%s", BombDir);
13: 
14: 	for(int i = 0; i < 2; i++) // Iterate on BombDir (for the 2 char)
15: 	{
16: 	    switch(BombDir[i])
17: 	    {
18: 		case 'R':   XMin = PosX;    PosX += (XMax-XMin+1) / 2;  break;
19: 		case 'L':   XMax = PosX;    PosX -= (XMax-XMin+1) / 2;  break;
20: 		case 'D':   YMin = PosY;    PosY += (YMax-YMin+1) / 2;  break;
21: 		case 'U':   YMax = PosY;    PosY -= (YMax-YMin+1) / 2;  break;
22: 		default:                                                break;
23: 	    }
24: 	}
25: 	printf("%i %i\n", PosX, PosY);
26:     }
27:     return 0;
28: }

1.4 Comparaison avec le code d'Alain-Delpuch

Le code d'Alain-Delpuch :

 1: #include <stdio.h>
 2: 
 3: int 
 4: main() {
 5:     int W; // width of the building.
 6:     int H; // height of the building.
 7:     scanf("%d%d", &W, &H);
 8: 
 9:     int N; // maximum number of turns before game over.
10:     scanf("%d", &N);
11: 
12:     int X0;
13:     int Y0;
14:     scanf("%d%d", &X0, &Y0);
15: 
16:     int xmin = 0 ; int xmax = W ;
17:     int ymin = 0 ; int ymax = H ;
18: 
19:     // game loop
20:     while (N--) {
21: 	char bombDir[4]; // the direction of the bombs from batman's current location (U, UR, R, DR, D, DL, L or UL)
22: 	scanf("%s", bombDir);
23: 	switch (bombDir[0]) {
24: 	    case 'U' : ymax = Y0 ; break ;
25: 	    case 'D' : ymin = Y0 ; break ;
26: 	    case 'R' : xmin = X0 ; break ;
27: 	    case 'L' : xmax = X0 ; break ;
28: 	}
29: 	switch (bombDir[1]) {
30: 	    case 'R' : xmin = X0 ; break ;
31: 	    case 'L' : xmax = X0 ; break ;
32: 	}
33: 
34: 	Y0 = (ymax + ymin)/2 ; 
35: 	X0 = (xmin + xmax)/2 ; 
36: 
37: 	printf("%d %d\n", X0, Y0);
38:     }
39: }

Le principe est similaire, à 2 points prêts :

  • L'utilisation de 2 switch pour les 2 caractères à la place d'une boucle et d'un switch.
  • Alain-Delpuch déplace tout le temps Batman, peut importe la direction qu'il doit suivre (ligne 34 - 35)

Voilà, Batman peut maintenant sauver la ville.

Thomas TAMAGNAUD. 05/05/2021

Author: Thomas Tamagnaud

Created: 2021-05-05 mer. 19:11

Validate