Rapport shadow of the knight
Table of Contents
1. Episode 1
1.1. Présentation du problème
Shadow of the knight est un puzzle du site codingame, qui consiste à aider batman a trouver la bombe dans un batiment piégé, il faut trouver les otages en sautant de fenêtre en fenêtre pour trouver la bombe et donc les otages, tout cela en un nombre de saut limités. Dans cette épisode, a chaque saut il nous est préciser ou se trouve la bombe par rapport à notre position, si elle est en haut, à droite ou les deux…
1.2. Méthode de résolution
Pour réussir ce code on nous donne plusieurs entrées d’initialisations, W et H qui sont les dimensions du tableau, la largeur et la hauteur, ensuite il y a N qui est le nombre de saut maximum que batman peut faire avant que la bombe n’explose, enfin X0 et Y0 qui sont les coordonées initiales de batman. On nous donne aussi, après chaque saut, la variable bombdir qui nous donne la direction vers laquelle se trouve la bombe qui peuvent avoir comme valeur: “U”,“UR”,“R”,“DR”,“D”,“DL”,“L”,“UL”.
1.2.1. Code de résolution
#include <stdlib.h> #include <stdio.h> #include <string.h> #include <stdbool.h> int main(){ //hauteur et largeur int W; int H; scanf("%d%d", &W, &H); //nombres de saut int N; scanf("%d", &N); //position initiale int X0; int Y0; scanf("%d%d", &X0, &Y0); //variables définissant la zone qu'il reste a analyser int xmin=0,xmax=W,ymin=0,ymax=H; while (1) { //direction vers laquelle est la bombe char bomb_dir[4]; scanf("%s", bomb_dir); //switch qui analyse bomb_dir et change les valeurs de xmax,ymax,xmin, //et ymin en fonctions de la direction de la bombe switch (bomb_dir[0]+bomb_dir[1]) { case 'U'+'R': xmin=X0,ymax=Y0; break; case 'U': ymax=Y0; break; case 'R': xmin=X0; break; case 'D'+'R': xmin=X0,ymin=Y0; break; case 'D': ymin=Y0; break; case 'D'+'L': xmax=X0,ymin=Y0; break; case 'L': xmax=X0; break; case 'U'+'L': xmax=X0,ymax=Y0; break; default: break; } //on met batman au milieu de la zone qu'il reste a analyser X0=(xmin+xmax)/2; Y0=(ymin+ymax)/2; //on affiche les coordonées printf("%d %d\n",X0,Y0); } return 0; }
Après avoir reçu les entrées d’initialisations, on regarde ensuite la valeur de bombdir grace a un switch et en fonction de sa valeur, on modifie les valeurs de xmax,xmin,ymax,ymin. On deplace ensuite batman au milieu de la zone définie par ces 4 variables puis on affiche ses coordonées.
1.3. Présentation de tests
Le code a passer plusieurs tests, entre autre ce test la:
en entrée:
4 5
40
2 3
et en sortie:
3 7
ou encore ce test la:
en entrée:
25 33
49
2 29
et en sortie:
24 2
1.4. Présentation de la méthode de quelqu’un d’autre
Voici le code de delegateStack
#include <stdlib.h> #include <stdio.h> #include <string.h> int main() { int W, H,X0,Y0, N;char bombDir[4]; scanf("%d%d%d%d%d", &W, &H, &N, &X0, &Y0); int x1=0,y1=0; while (1) { scanf("%s", bombDir); if(strstr(bombDir,"R")!=NULL)x1=X0; if(strstr(bombDir,"L")!=NULL)W=X0; if(strstr(bombDir,"D")!=NULL)y1=Y0; if(strstr(bombDir,"U")!=NULL)H=Y0; X0=(W+x1)/2; Y0=(H+y1)/2; printf("%i %i\n",X0,Y0); } return 0; }
J’ai choisi ce code car il l’a réduit au maximum pour qu’il soit lisible et court, il n’utilise pas la même méthode que moi, c’est-à-dire qu’il utilise la fonction strstr qui permet de savoir si par exemple “R” est dans bombdir alors que moi je regarde ce que vaut réellement bombdir ce qui lui permet de modifier une valeur pour une lettre.
2. Episode 2
2.1. Présentation du problème
Le problème est a peut prêt le même que pour l’épisode 1, il faut toujours trouver la bombe et sauver les otages en sautant de fenêtre en fenêtre en un nombre de sauts limités. Cependant dans cet épisode on ne nous dit plus dans quelle direction allez pour trouver la bombe, cette fois-ci on nous dit juste si on s’en rapproche ou si on s’en éloigne.
2.2. Méthode de résolution
On définie les mêmes variables d’initialisation que pour l’episode 1 mais on change les valeurs de bombdir qui sont maintenant: “UNKNOWN”,“WARMER”,“SAME” et “COLDER”.
2.2.1. code personnel
N’ayant pas réussi par moi même… Je me suis inspiré de la méthode d’Alain-Delpuch qui ressemblait le plus a la méthode que j’ai essayé mais sans succès. Cela donne ce code:
#include <stdlib.h> #include <stdio.h> #include <string.h> #include <stdbool.h> //définition de X et Y int X,Y; //définition de la fonction move qui renvoie une valeur entière en fonction de bomb_dir int move(int x, int y) { X = x; Y = y; printf("%d %d\n",x,y); char bombDir[11]; scanf("%s", bombDir); switch (bombDir[0]) { case 'W' : //WARMER return 1; break; case 'C' : //COLDER return -1; break; case 'S' : //SAME return 0; break; default : return 2; } } //définition de la fonction miroir qui renvoie le nombre "miroir" //c'est-à-dire le nombre symétrique par rapport au milieu de la zone int miroir(int mini, int maxi, int point, int n) { int next ; // on change next pour son symetrique par rapport au milieu de //la plage qu'il reste a regarder next = mini + maxi - point ; //si next ne peut pas exister dans la zone on renvoie -1 if ((mini == maxi) || (next<0) || (next>=n)){ return -1 ; } return next; } int main() { //on définie les variables d'initialisation, W, H, N, int W; int H; scanf("%d%d", &W, &H); int N; scanf("%d", &N); scanf("%d%d", &X, &Y); int xmin = 0 ; int xmax = W-1 ; int ymin = 0 ; int ymax = H-1 ; //on ignore le bomb_dir qui vaut "UNKNOWN" char bombDir[11]; scanf("%s", bombDir); while (N--) { int next; //on coupe horizontalement next = miroir(xmin, xmax, X, W); if (next != -1) { int est_paire; int m = (X + next) / 2; int temp = move(next, Y); if ((X+next)%2==0){ est_paire=0; }else{ est_paire=1; } if (temp>0) { // Warmer if (m < next ) { xmin = m+1; }else{ xmax = m-est_paire; } } else if (temp<0) { // Colder if (m < next ) { xmax = m-est_paire; } else{ xmin = m+1; } } else { // same xmin = xmax = m; } continue; } //on modifie verticalement, si ce n'est pas modifier horizontalement next = miroir(ymin, ymax, Y, H); if (next != -1) { int est_paire; int m = ( Y + next ) / 2; int temp = move(X, next); if ((Y+next)%2==0){ est_paire=0; }else{ est_paire=1; } if (temp>0) { // Warmer if (m < next ) { ymin = m+1; } else{ ymax = m-est_paire; } } else if (temp<0) { // Colder if (m < next ) { ymax = m-est_paire; } else{ ymin = m+1; } } else { // same ymin = ymax = m; } continue; } //si on ne peut pas couper en 2, on coupe en 3 int x; int y; if (xmin<(W-xmax)){ x=xmin+2*xmax; }else{ x=2*xmin+xmax; } if (ymin<(H-ymax)){ y=ymin+2*ymax; }else{ y=2*ymin+ymax; } int dontcare = move ( x/3 , y/3 ); } return 0; }
Au début on définie la fonction move qui renvoie une valeur entière en fonction de la valeur de bombdir. On définie ensuite la fonction miroir qui renvoie la position miroir, si il existe, de X ou Y tout dépend l’argument. Ensuite on commence a faire sauter batman, on fait d’abord en sorte d’avoir la colonne précise sur laquelle se trouve la bombe, puis on définie la ligne.
2.3. Présentation des tests
Le code a passé plusieurs test, il a notamment passer ce test:
en entrée:
5 16
80
1 5
et en sortie:
4 10
il a aussi passé ce test:
32 18
44
17 31
et en sortie:
2 1
2.4. Présentation de la méthode d’un autre dévellopeur
Voici le code de DaNinja:
#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 choisi de présenter ce code car il utilise une notion que nous n’avons pas encore vu en cours de C, les structure de données, et car il a aussi creer un code assez court pour résoudre ce problème. Il définie d’abord la fonction found qui renvoie la nouvelle position si on n’y est pas encore allez, il définie ensuite la fonction get qui définie la nouvelle zone a observer. Dans le main il définie les variables dont il a besoin pour ensuite appliquer les fonctions définie plus haut en fonction de la valeur de dir.
vous pouvez retrouver ce rapport en ligne ici