#shadow_of_the_night.org# 4.63 KB
Newer Older
Thomas TAMAGNAUD's avatar
Thomas TAMAGNAUD committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#+SETUPFILE: https://fniessen.github.io/org-html-themes/org/theme-readtheorg.setup
#+TITLE: Batman
#+author: Thomas Tamagnaud
#+email: tstd36@yahoo.fr
#+STARTUP: inlineimages

 # Faire un macro F3 puis F4
 # C-C C-e h o

 # pour executer le code
 # C-C C-C


 # <ce pour le c
  

* Shadow of the Night
** 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.

#+caption: Le tout n'est pas de trouver la bombe, mais aussi de la désamorcer
#+attr_html: :width 400px
[[http:64.media.tumblr.com/611aadc931770a6ca74f9534af11a2bf/tumblr_n2tokwxVpJ1qa70eyo2_r1_500.png]]

** Résolution

#+caption: Premier Cas
#+attr_html: :width 400px
[[./img/debut.png]]
   
  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 :

#+caption: Tour 0
#+attr_html: :width 400px
[[./img/et0.png]]

#+caption: Tour 1
#+attr_html: :width 400px
[[./img/et1.png]]

#+caption: Tour 2
#+attr_html: :width 400px
[[./img/et2.png]

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.

** Programme en C
   (Mon cote @Mewily sur coding game)
#+BEGIN_SRC C -n
  #include <stdio.h>

  int main()
  {
      int PosX, PosY, XMax, YMax, MaxTurn;
      scanf("%i %i %d %d %d", &XMax, &YMax, &MaxTurn, &PosX, &PosY); //Read the input
      int XMin = 0, YMin = 0;

      while (1)  // Game loop
      {
	  char BombDir[2] = "??";
	  scanf("%s", BombDir);

	  for(int i = 0; i < 2; i++) // Iterate on BombDir (for the 2 char)
	  {
	      switch(BombDir[i])
	      {
		  case 'R':   XMin = PosX;    PosX += (XMax-XMin+1) / 2;  break;
		  case 'L':   XMax = PosX;    PosX -= (XMax-XMin+1) / 2;  break;
		  case 'D':   YMin = PosY;    PosY += (YMax-YMin+1) / 2;  break;
		  case 'U':   YMax = PosY;    PosY -= (YMax-YMin+1) / 2;  break;
		  default:                                                break;
	      }
	  }
	  printf("%i %i\n", PosX, PosY);
      }
      return 0;
  }
#+END_SRC


** Comparaison avec le code d'Alain-Delpuch
   Le code d'Alain-Delpuch :
#+BEGIN_SRC C -n
#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);
    }
}
#+end_src

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