Rapport Shadow Of the Knight ep1/2
Table of Contents
Episode 1
Présentation du problème
Shadow of the knight est un problème tiré du site Codingame inspiré de Batman. C’est un problème de recherche dichotomique où Batman doit sauver des otages dans un batiment. Le but est de localiser les otages qui se trouvent dans une des nombreuses fenêtres d’un immeuble avant que la bombe qui se trouve dans la même pièce que les otages explose. En réalité la bombe est là pour que l’on ai un nombre d’essai limité afin de trouver la bonne fenêtre. Le but du problème est donc de trouver un couple de coordonnée par recherche dichotomique dans un rectangle de dimensions données. On considère que la fenêtre en haut à gauche a pour coordonnées (0,0). Pour trouver la bonne fenêtre, à chaque proposition de coordonnée, le site Codingame nous donne des indications sur la position de la bombe par rapport à Batman. Il va renvoyer une ou deux lettres spécifiques pour indiquer l’emplacement de la bombe.
- ’U’: la bombe est au dessus de Batman
- ’D’: la bombe est en dessous de Batman
- ’L’: la bombe est à gauche de Batman
- ’R’: la bombe est à droite de Batman
- ’UR’: la bombe est au dessus et à droite de Batman
- ’UL’: la bombe est au dessus et à gauche de Batman
- ’DL’: la bombe est en dessous et à gauche de Batman
- ’DR’: la bombe est en dessous et à droite de Batman
Afin de résoudre ce problème on dispose églament d’autres données.
- ’H’: la hauteur de l’immeuble
- ’W’: la longueur de l’immeuble
- (X0,Y0): les coordonées de départ de Batman
- ’N’: le nombre d’essai afin de trouver la bombe
Métode de résolution
Description de la stratégie
Pour résoudre ce problème j’ai travaillé sur la zone de recherche des bombes. Pour cela, j’ai d’abord réduit la zone de recherche à chaque essai, en fonction de la réponse envoyée par le site. Ensuite, j’ai fais se déplacer Batman au milieu de la zone de recherche afin de pouvoir considérablement la réduire à chaque tour de boucle. En effet, en utilisant cette méthode, j’étais sûr de supprimer au moins la moitié de la zone de recherche restante à chaque tour de boucle, et donc de trouver assez rapidement l’emplacement de la bombe.
Détail algorithmique de la méthode
Pour pouvoir appliquer ma stratégie de réduction de la zone de recherche, il me fallait d’abord initialiser 4 variables (un x et un y pour chaque extremité de ma zone de recherche). Puis, j’ai utilisé un switch afin de différencier les 8 possibilitées d’emplacement de la bombe par rapport à Batman. Pour mieux comprendre comment fonctionne le découpage des zones, voici un schéma explicatif.
Dans ce schéma, la case rouge représente Batman, et les cases bleues représentent la zone de recherche encore active. On voit bien que dans le premier cas, lorsque la bombe se trouve en bas à droite de Batman, on peut éliminer une grande zone de recherche. Et ce, encore plus dans le cas 2 où la bombe se trouve au dessus de Batman. Elle peut se trouver uniquement sur un fragment de ligne ce qui rend la recherche très simple.
Code commenté ayant résolu le problème
Voici ci dessous le code m’ayant permis de résoudre le problème.
#include <stdlib.h> #include <stdio.h> #include <string.h> #include <stdbool.h> int main() { int W; // Longueur de l'immeuble int H; // Hauteur de l'immeuble scanf("%d%d", &W, &H); int N; // Nombre de tentatives scanf("%d", &N); int X0; // Abscisse de batman int Y0; // Ordonnée de batman scanf("%d%d", &X0, &Y0); int xmin=0; // Abscisse minimum int ymin=0; // Ordonnée minimum int xmax=W; // Abscisse maximale int ymax=H; // Ordonnée maximale // Boucle principale while (1) { char bomb_dir[4]; scanf("%s", bomb_dir); // Direction dans laquelle se situe la bombe switch(bomb_dir[0]+bomb_dir[1]){ case 'U':ymax=Y0; // Si la bombe est au dessus de batman, alors la zone de recherche est coupé en dessous de batman break; case 'U'+'R':ymax=Y0,xmin=X0; // Si la bombe est au dessus à droite de batman, alors la zone de recherche est réduite break; case 'R':xmin=X0; // Si la bombe est à droite de batman, alors la zone de recherche est coupé à gauche de batman break; case 'D'+'R':ymin=Y0,xmin=X0; // Si la bombe est en dessous à droite de batman, alors la zone de recherche est réduite break; case 'D':ymin=Y0; // Si la bombe est en dessous de batman, alors la zone de recherche est coupé au dessus de batman break; case 'D'+'L':ymin=Y0,xmax=X0; // Si la bombe est en dessous à gauche de batman, alors la zone de recherche est réduite break; case 'L':xmax=X0; // Si la bombe est à gauche de batman, alors la zone de recherche est coupé à droite de batman break; case 'U'+'L':ymax=Y0,xmax=X0; // Si la bombe est au dessus à gauche de batman, alors la zone de recherche est réduite break; } X0=(xmin+xmax)/2; // L'abscisse de batman est le milieu entre l'abscisse minimale et maximale de la zone de recherche Y0=(ymin+ymax)/2; // L'ordonnée de batman est le milieu entre l'ordonnée minimale et maximale de la zone de recherche printf("%d %d\n",X0,Y0); // Affichage de la nouvelle position de batman } return 0; }
Présentation des tests
Afin de coder ce programme et de le valider, il a fallut passer plusieurs tests. Alors voici ci dessous quelques tests qui m’ont permi de résoudre ce problème.
- Premier test
Entrées du tour 1:
H, W: 8, 4
X0, Y0: 2, 33
N: 40
Direction: ’DR’
Sortie dernier tour:
X0, Y0: 3, 7
Ce test permet de comprendre le problème, mais il ne faut pas forcément s’y fier. En effet, comme il est assez simple, il ne permet pas de tester l’efficacité du programme.
- Second test
Entrées du tour 1:
H, W: 80, 1
X0, Y0: 0, 10
N: 6
Direction: ’D’
Sortie dernier tour:
X0, Y0: 0, 36
Ce test est un cas particulier puisque l’immeuble ne comporte qu’une colonne. Il permet donc de voir si le programme est assez géneral pour passer tout les tests.
- Troisième test
Entrées du tour 1:
H, W: 9999, 9999
X0, Y0: 54, 77
N: 14
Direction: ’DR’
Sortie dernier tour:
X0, Y0: 9753, 2531
Ce test est le test ultime. C’est le plus long et il y a peu de tentatives comparé à la grandeur des dimensions. Il permet de tester si le programme est efficace.
Description d’une autre solution au problème
J’ai décidé de présenter la solution au problème Shadow of the knight épisode 1 de l’utilisateur delegateStack car elle est particulièrement efficace et compact. En effet, comparé à ma solution, le programme est beaucoup plus court et traite moins de cas, ce qui le rend bien meilleur. Malgré cela, il le même principe que ma solution. A chaque tour, on réduit la zone de recherche de la bombe, et on se place au milieu de cette dernière. La différence réside dans le fait qu’il test si une lettre apparait dans l’indication de direction, snas se soucier des combinaisons. En effet, avec ce code il peut modifier la zone de recherche en fonction de chaque lettre, et il n’a pas besoin d’écrire des lignes spéciales pour les combinaisons. De plus, au niveau de l’écriture, il a fait un code extrèmement compact, en inscrivant un maximum d’instruction sur une même ligne.
Voici ci dessous le code commenté de l’utilisateur 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); // Récupération des entrées de l'énoncé int x1=0,y1=0; // Initialisation // Boucle principale while (1) { scanf("%s", bombDir); if(strstr(bombDir,"R")!=NULL)x1=X0; // Si la bombe est à droite de Batman, alors on réduit la zone de recherche if(strstr(bombDir,"L")!=NULL)W=X0; // Si la bombe est à gauche de Batman, alors on réduit la zone de recherche if(strstr(bombDir,"D")!=NULL)y1=Y0; // Si la bombe est au dessus de Batman, alors on réduit la zone de recherche if(strstr(bombDir,"U")!=NULL)H=Y0; // Si la bombe est en dessous de Batman, alors on réduit la zone de recherche X0=(W+x1)/2; // On se place au milieu de la zone de recherche en abscisse Y0=(H+y1)/2; // On se place au milieu de la zone de recherche en ordonnée printf("%i %i\n",X0,Y0); // On affiche le résultat } return 0; }
Bilan de ce travail
Ce travail m’a permis de mieux prendre en main la fonction switch, qui m’a été très utile afin de coder ma solution. De plus, il m’a permis de mieux comprendre comment fonctionne une méthode dichotomique, ce qui en fait une bonne base avant de coder la solution de l’épisode 2.
Episode 2
Présentation du problème
Shadow of the knight épisode 2 est un problème tiré du site Codingame inspiré de Batman. Il s’inscrit dans la logique de l’épisode 1, et a un énoncé assez similaire. C’est un problème de recherche dichotomique où Batman doit sauver des otages dans un batiment. Le but est de retrouver les otages qui se trouvent derrière une des nombreuses fenêtres d’un immeuble avant que la bombe qui se trouve dans la même pièce que les otages explose. En réalité la bombe est là pour que l’on ai un nombre d’essai limité afin de trouver la bonne fenêtre. Le but du problème est donc de trouver un couple de coordonnée par recherche dichotomique dans un rectangle de dimensions données. On considère que la fenêtre en haut à gauche a pour coordonnée (0,0). Afin trouver la bonne fenêtre, à chaque proposition de coordonnée, le site Codingame nous donne des indications sur la position de la bombe par rapport à Batman. Mais contrairement à l’épisode 1, celles ci sont beaucoup moins précises. En effet le site nous indiquera seulement si on se rapproche ou si on s’éloigne de la bombe, sans nous indiquer aucune direction. Le site Codingame calcul la distance avec la bombe grace à la formule de la distance euclidienne:
\begin{equation*} AB=\sqrt{{({x}_{b}-{x}_{a})}^{2}+{({y}_{b}-{y}_{a})}^{2}} \end{equation*}Afin de résoudre ce problème on dispose de différentes données.
- ’H’: la hauteur de l’immeuble
- ’W’: la longueur de l’immeuble
- (X0,Y0): les coordonnées de départ de Batman
- ’N’: le nombre d’essai afin de trouver la bombe
- bomb dir: qui indique la position de la bombe par rapport à nous, elle pourra prendre 3 valeurs:
- ’COLDER’: si on s’éloigne de la bombe
- ’WARMER’: si on se rapproche de la bombe
- ’SAME’: si on est à la même distance de la bombe que précedemment
Métode de résolution
Description de la stratégie
Afin de résoudre ce problème, ma stratégie est la suivante. Il faut d’abord s’intéresser à une coordonnée, puis lorsqu’on a trouvé la bonne, s’intéresser à la seconde. Cela revient à effectuer deux dichotomies sur un axe. Et en fonction de si on s’éloigne, ou si on se rapproche, il faudra réduire la zone de recherche sur l’axe, comme réalisé pour l’épisode 1. Il faudra alors rajouter des conditions permettant de changer d’axe si une des deux coordonnées est trouvée. Pour simplifier les choses, on commencera forcement par calculer l’abscisse de la bombe avant de s’intéresser à l’ordonnée.
Détail algorithmique de la méthode
Pour débuter notre programme, on va commencer par définir un certain nombre de variables qui vont nous permettre de stocker des résultats et des valeurs durant tout le programme. Une variable va être particulièrement importante, la variable numphase qui va définir la coordonée que l’on étudie. En effet, on va commencer la boucle principale de notre programme par la vérification de la coordonnée que l’on étudie. Si il n’y a qu’une seule colonne sur l’immeuble, on s’intéressera directement à l’ordonnée. Et si l’abscisse a été trouvé, on changera également d’axe d’étude. C’est cette variable qui va permettre l’échange de l’axe d’étude. On distinguera alors plusieurs cas dans la boucle principale.
- Si la distance entre les deux derniers déplacements est la même, il suffira de prendre la valeur du milieu entre les deux derniers déplacements.
- Si on se rapproche de la bombe, alors on va supprimer une partie de la zone de recherche, en fonction de si on est vers la gauche, ou vers la droite de l’immeuble. Ou en fonction de si on est en haut ou en bas de l’immeuble.
- Si on s’éloigne de la bombe, alors on va supprimer une partie de la zone de recherche, en fonction de si on est vers la gauche, ou vers la droite de l’immeuble. Ou en fonction de si on est en haut ou en bas de l’immeuble.
Une fois cela fait, on va calculer les coordonnées possibles pour le futur déplacement, et vérifier si elles corrspondent à des coordonnées vraissemblables (si elles rentrent dans les dimensions de l’immeuble).
Afin de mieux comprendre la dichotomie axiale, voici un schéma explicatif de ce principe.
Dans ce schéma, la bombe est symbolisé par un cercle rouge, la position actuelle de Batman par un cercle bleu. Et l’ancienne position de Batman, par un cercle gris. On observe qu’à l’étape 1 Batman est assez proche de la bombe. Il s’en éloigne à l’étape 2 puisqu’il se place au mileu entre le début de l’axe, et son ancienne position. Il va alors se placer au niveau de la bombe à l’étape 3, car l’enplacement de la bombe correspond au centre de la zone de recherche restante. Il a alors trouvé la bombe. C’est ce principe qui est utilisé tout au long du programme.
La boucle principale du programme nécessite elle aussi quelques explications supplémetaires afin de mieux la comprendre. Voici donc ci dessous, un schéma réalisé avec SketchViz expliquant le déroulement de la boucle.
Cliquez ici pour agrandir
Dans ce schéma, on distingue bien les deux parties du programme. Avec des couleurs plutot brunes et orangées on voit le mécanisme de recherche de l’abscisse, et avec des couleurs bleutées on retrouve le mécanisme de recherche de l’ordonnée. Les cases les plus importantes ressortent en rose, avec nottament la case de début, de fin, et la case qui fournit l’information sur la position. Les cases signalant que l’on a trouvé la coordonnée recherchée sont également en rose. Enfin, en blanc on retrouve les deux cases représentant chacune un processus, la première, la recherche en abscisse, et la seconde, la recherche en ordonnée.
Code commenté ayant résolu le problème
Voici ci dessous le code m’ayant permis de résoudre le problème.
#include <stdlib.h> #include <stdio.h> #include <string.h> #include <stdbool.h> int main() { int W; // Largeur du batiment int H; // Hauteur du batiment scanf("%d%d", &W, &H); int N; // Nombre d'essai scanf("%d", &N); int X0; // Position initiale en abscisse int Y0; // Position initiale en ordonnée scanf("%d%d", &X0, &Y0); int num_phase = -1; int pos_preced[2] = {X0, Y0}; // Position précedente de batman int pos_suivante[2] = {X0, Y0}; // Position suivante de batman int position_min[2] = {0}; // Abscisse et ordonnée minimum de la zone de recherche int position_max[2] = {W - 1, H - 1}; // Abscisse et ordonnée maximum de la zone de recherche int dimension[2] = {W - 1, H - 1}; // Dimentions de l'immeuble int ancien; // Variable qui contient la dernière coordonée modifiée int nouveau; // Variable qui contient la coordonnée qui va être modifiée int parite; // stock la parité de la distance ancien/nouveau int centre; // Milieu des coordonnées "ancien" et "nouveau" int tentative; // Future abscisse ou ordonnée possible int i; // Boucle principale while (1) { char bomb_dir[11]; scanf("%s", bomb_dir); // Récupération de l'information sur la position de batman par rapport à la bombe if (num_phase < 0) { // Si on ne recherche pas l'ordonnée de la bombe if (num_phase == -1 && W >= 2){ // Si la longueur de l'immeuble est différente de 1 num_phase = 0; // Alors on cherche l'abscisse de la bombe } else { num_phase = 1; // Sinon on cherche l'ordonnée de la bombe } pos_suivante[num_phase] = position_max[num_phase] + position_min[num_phase] - pos_preced[num_phase]; // Calcul de la position suivante de batman par défaut } else { ancien = pos_preced[num_phase]; // Récupération de la dernière coordonnée qui a été modifiée nouveau = pos_suivante[num_phase]; // Récupération de la future coordonnée qui va être modifié parite = (ancien + nouveau)%2; // test la parité de la distance ancien/nouveau centre = (ancien + nouveau)/2; // Milieu entre ancien et nouveau pos_preced[num_phase] = nouveau; // Initialise la position précedente if (bomb_dir[0] == 'S'){ // Si batman n'a pas changé de distance par rapport à la bombe pos_suivante[num_phase] = centre; // Alors la prochaine coordonnée modifiée vaudra le milieu entre la position précedente de batman et sa position actuelle if (num_phase == 0){ // Si on cherche l'abscisse de la bombe num_phase = -2; } } else { if (bomb_dir[0] == 'W'){ // Si batman s'est rapproché de la bombe if (ancien < nouveau){ // Si batman est monté ou est allé à droite lors de son dernier déplacement if (position_min[num_phase] < centre + 1){ // Si la zone de recherche s'étend trop vers la gauche ou vers le bas position_min[num_phase] = centre + 1; // Alors on met à jour la zone de recherche avec les nouvelles informations } } else if (ancien > nouveau){ // Si batman est descendu ou est allé à gauche lors de son dernier déplacement if (position_max[num_phase] > centre - 1 * (parite == 0)){ // Si la zone de recherche est trop étendue à droite ou vers le haut position_max[num_phase] = centre - 1 * (parite == 0); // Alors on met à jour la zone de recherche avec les nouvelles informations } } } else if (bomb_dir[0] == 'C'){ // Si batman s'est éloigné de la bombe if (ancien > nouveau){ // Si batman est descendu ou est allé à gauche lors de son dernier déplacement if (position_min[num_phase] < centre + 1){ // Si la zone de recherche s'étend trop vers la gauche ou vers le bas position_min[num_phase] = centre + 1; // Alors on met à jour la zone de recherche avec les nouvelles informations } } else if (ancien < nouveau){ // Si batman est monté ou est allé à droite lors de son dernier déplacement if (position_max[num_phase] > centre - 1 * (parite == 0)){ // Si la zone de recherche est trop étendue à droite ou vers le haut position_max[num_phase] = centre - 1 * (parite == 0); // Alors on met à jour la zone de recherche avec les nouvelles informations } } } if (position_min[num_phase] == position_max[num_phase]){ // Si les longueur minimales et maximales sont confondues, ou que les hauteur minimales et maximales sont confondues pos_suivante[num_phase] = position_min[num_phase]; // Alors le prochain déplacement est le point où elles sont confondues if (num_phase == 0){ // Si on recherchait l'abscisse de la bombe num_phase = 1; // Alors on recherche l'ordonnée de la bombe } } tentative = position_max[num_phase] + position_min[num_phase] - nouveau; // Mise à jour de la possible future coordonnée if (tentative < 0 || tentative > dimension[num_phase]){ // Si la future coordonée ne rentre pas dans le cadre de l'immeuble tentative = (position_min[num_phase] + position_max[num_phase])/2; // Alors la fuure coordonnée possible est le milieu de la zone de recherche } if (tentative == nouveau || tentative == ancien || position_max[num_phase] - position_min[num_phase] <= 2){ // Si la possible future coordonnée a déja été essayé ou que l'axe sur lequel on cherche n'a qu'une seule case for (i=position_min[num_phase];i<position_max[num_phase]+1;i++){ // Pour i se trouvant dans la zone de recherche if (i != nouveau && i != ancien){ // Si i est une position qui n'a pas était testé tentative = i; // la possible future coordonnée vaut i break; } } } pos_suivante[num_phase] = tentative; // La valeur de tentative est assignée à la coordonnée suivante } } printf("%d %d\n", pos_suivante[0], pos_suivante[1]); // Affiche les possibles coordonnées de la bombe } return 0; }
Présentation des tests
Afin de coder ce programme et de le valider, il a fallu passer plusieurs tests. Alors voici ci dessous quelques tests qui m’ont permi de résoudre ce problème.
- Premier test
Entrées du tour 1:
H, W: 16, 5
X0, Y0: 1, 5
N: 80
Entrée du tour 2:
Indication: ’WARMER’
Sortie dernier tour:
X0, Y0: 4, 10
Ce test permet de comprendre le problème, mais il ne faut pas forcément s’y fier. En effet, comme il est assez simple, il ne permet pas de tester l’efficacité du programme mais seulement si il fonctionne correctement.
- Second test
Entrées du tour 1:
H, W: 100, 1
X0, Y0: 0, 98
N: 12
Entrée du tour 2:
Indication: ’COLDER’
Sortie dernier tour:
X0, Y0: 0, 65
Ce test est un cas particulier puisque l’immeuble ne comporte qu’une colonne. Il permet donc de voir si le programme est assez géneral pour passer tout les tests. Il a donc permis de coder une des premières conditions de la boucle while, qui dit qu’on cherche en abscisse seulement si la longueur est au minimum de 2.
- Troisième test
Entrées du tour 1:
H, W: 8000, 8000
X0, Y0: 3200, 2100
N: 31
Entrée du tour 2:
Indication: ’COLDER’
Sortie dernier tour:
X0, Y0: 0, 3
Ce test est le dernier test. C’est le plus long et il y a peu de tentatives comparé aux dimensions de l’immeuble. Il permet de tester si le programme est efficace et si il fonctionne réellement bien. Le fait que la bombe soit située sur une extrémité oblige le programme à fonctionner de manière optimale.
Description d’une autre solution au problème
J’ai décidé de m’intérresser à la solution de Vry trouvée sur le site Codingame. En effet, bien que cette solution ai été créé il y a longtemps, et qu’elle utilise une syntaxe plus ancienne, elle reste très intéressante dans le principe. Elle utilise le principe de recherche sur chaque axe mais son squelette est bien plus intelligent et compréhensible que le mien. En effet, au lieu de mettre toutes ses instructions dans la fonction main, l’utilisateur a créé une multitude de fonctions s’appelant entre elles, ce qui fait que son programme principal ne comporte que 4 instructions. Son programme en général est donc plus facile à interpréter et à étudier. Il fonctionne de la façon suivante. Le programme va d’abord faire intervenir une fonction permettant d’initialiser les variables et de récupérer les valeurs données par le site. Puis il va rentrer dans la boucle principale, composée de 3 instructions. La première est une fonction qui initialisera les variables qui doivent être modifiées à chaque tour de boucle. La seconde est la fonction la plus importante, c’est celle qui va calculer les prochaines coordonnées de Batman en fonction des cas. La fonction play appelle elle même d’autres fonction, dont une particulièrement importante. C’est elle qui va permettre de calculer la valeur de la coordonnée que l’on modifie. Tout cela rend sa proposition très intelligente et bien conçue.
Voici ci dessous le code commenté de l’utilisateur Vry.
#include <stdlib.h> #include <stdint.h> #include <stdio.h> #include <string.h> #define MAX_TURN 256 typedef struct _turn_ { int x; int y; char bombDir[10+1]; // Distance actuelle par rapport à la bombe comparé à l'ancienne distance (COLDER, WARMER, SAME ou UNKNOWN) int d; // Défini notre axe de recherche } TURN; typedef struct _game_ { int w; // Longueur de l'immeuble int h; // Hauteur de l'immeuble int n; // Nombre d'essai TURN t_turn[MAX_TURN]; // Défini un type TURN int c_turn; int sx; int sy; int ex; int ey; } GAME; GAME g = {}; // Initialisation des différentes fonction void initGame(void); void initLoop(void); void play(void); void updateBound(int* s, int f, int t, int* e); int getNext(int v, int s, int e, int max); // Boncle principale utilisant toutes les fonctions ci dessous int main() { initGame(); // game loop while (1) { initLoop(); play(); printf("%d %d\n", g.t_turn[g.c_turn].x, g.t_turn[g.c_turn].y); // Affichage de la solution } return 0; } void initGame(void) // Fonction qui permet d'initialiser les variables et récupérer les informations du site { scanf("%d%d", &(g.w), &(g.h)); fprintf(stderr, "%d %d\n", g.w, g.h); scanf("%d", &(g.n)); fprintf(stderr, "%d\n", g.n); scanf("%d%d", &(g.t_turn[0].x), &(g.t_turn[0].y)); fprintf(stderr, "%d %d\n", g.t_turn[0].x, g.t_turn[0].y); g.sx = 0; g.sy = 0; g.ex = g.w-1; g.ey = g.h-1; } void initLoop(void) // Fonction qui permet d'initialiser les variables à chaque tour de boucle { g.t_turn[g.c_turn].bombDir[0] = '\0'; scanf("%s", g.t_turn[g.c_turn].bombDir); fprintf(stderr, "%s\n", g.t_turn[g.c_turn].bombDir); if (g.t_turn[g.c_turn].bombDir[0] == '\0') { fprintf(stderr, "No more input!\n"); exit(0); } } void play(void) // Fonction principale qui va permettre de trouver les prochaines coordonnées de Batman en fonction // des informations renvoyées pa rle site et des différents cas { TURN* ppt = NULL; TURN* pt = NULL; TURN* nt = NULL; if (g.c_turn > 0) ppt = g.t_turn + (g.c_turn-1); pt = g.t_turn + g.c_turn; g.c_turn++; nt = g.t_turn + g.c_turn; nt->x = pt->x; nt->y = pt->y; if ( (g.sx == g.ex) && (g.sx != pt->x) ) { nt->x = g.sx; return; } if ( (g.sy == g.ey) && (g.sy != pt->y) ) { nt->y = g.sy; return; } // Action en fonction des différents cas if (strcmp(pt->bombDir, "SAME") == 0) { if (pt->x != ppt->x) { g.sx = (pt->x + ppt->x) / 2; g.ex = g.sx; } else { g.sy = (pt->y + ppt->y) / 2; g.ey = g.sy; } } else if (strcmp(pt->bombDir, "WARMER") == 0) { if (ppt->x != pt->x) updateBound(&(g.sx), ppt->x, pt->x, &(g.ex)); else updateBound(&(g.sy), ppt->y, pt->y, &(g.ey)); } else if (strcmp(pt->bombDir, "COLDER") == 0) { if (ppt->x != pt->x) updateBound(&(g.sx), pt->x, ppt->x, &(g.ex)); else updateBound(&(g.sy), pt->y, ppt->y, &(g.ey)); } if (g.ex > g.sx) nt->x = getNext(pt->x, g.sx, g.ex, g.w-1); else nt->y = getNext(pt->y, g.sy, g.ey, g.h-1); } void updateBound(int* s, int f, int t, int* e) // Fonction utilisée dans la fonction play qui va permettre de modifier // les valeurs des prochaines coordonnées en fonction de son résultat de sortie { fprintf(stderr, "[%d .. %d] %d => %d", *s, *e, f, t); //if (t > f) (*s) = (f+t) / 2; //else (*e) = (f+t) / 2; fprintf(stderr, " [%d .. %d]\n", *s, *e); while (abs(*s-t) >= abs(*s-f)) (*s)++; while (abs(*e-t) >= abs(*e-f)) (*e)--; } int getNext(int v, int s, int e, int max) // Fonction qui va permettre de calculer les prochaines coordonnées de Batman { int r = s + e - v; if (v == r) r++; if (r < 0) r = 0; else if (r > max) r = max; if ( (v == 0) || (v == max) ) { if (g.w > 1000) r = (double)(r+v) / 2.5; else r = (r+v) / 2; if (r == 0) r = 1; else if (r == max) r--; } return r; }
Bilan de ce travail
Ce travail m’a permi d’approfondir le raisonnement par dichotomie. Il m’a également permi d’apprendre à découper un problème en plusieurs sous parties, ce qui a été d’autant plus le cas lorsque je me suis intéresser à la solution de Vry. De plus, le fait de devoir expliquer la boucle principale de mon programme m’a permi d’approfondir mes compétences sur l’outil Sketchviz.