Rapport Shadows of the Knight - Episode 2

1. Présentation du puzzle
2. Présentation de ma méthode de résolution
- 2.1. Description
- 2.2. Code
3. Apprentissage

1. Présentation du puzzle

L’objectif de ce puzzle est d’encore aider batman à retrouver la bombe. Cependant à chaque batman dispose de moins d’informations que l’épisode 1. Les informations possibles sont :

COLDER Pour dire que l’on est plus loin de la bombe en distance que l’essai précédent
WARMER Pour dire que l’on est plus proche de la bombe en distance que l’essai précédent
SAME Pour dire que l’on est à la même distance que l’essai précédent
UNKNOWN Pour dire le premier saut car le saut 0 n’existe pas

2. Présentation de ma méthode de résolution

2.1. Description

Pour trouver la position de la bombe . Je n’ai que des informations par rapport au coup précédent. Mon objectif est de faire une dichotomie sur les colonnes pour trouver la bonne colonne de la bombe. Je fais ensuite une dichotomie sur les lignes de la grille pour trouver la bonne ligne. Une fois cela j’obtiendrais donc la bonne ligne et la bonne colonne c’est à dire la position de la bombe. Pour faire cette dichotomie sur les colonnes, je place batman au centre de la ou la bombe peut se placer et je regarde si je suis plus proche ou plus loin. Si je suis plus proche alors je vais placer batman au centre l’autre moitié. Ensuite je supprime l’ancienne moitié ou la bombe était plus loin. Je recommence ceci jusqu’à ne contenir qu’une seule colonne , ce qui signifie etre dans la bonne colonne. Pour les lignes j’effectue le même processus. Lors des tests ce programme ne passe que la moitié des ceux-ci. J’ai cependant pensé mais pas réussi à coder la dichotomie verticale et horizontale en même temps, grâce à cette méthode j’aurais pu gagner quelques coups précieux pour la réalisation de puzzle.

2.2. Code

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

int main()
{
    int W; /*Variable pour la largeur de la grille*/
    int H; /*Variable pour la hauteur de la grille*/
    int N; /*nombre de tours maximal*/
    int X0;
    int Y0; /*variable pour les coordonnées de batman*/
    scanf("%d%d%d%d%d", &W, &H, &N, &X0, &Y0);
    int Yd; /*différence de valeur de Y0 avec le précédent*/
    int X0b = 0;
    int Y0b = 0;  /*coordonnées de départ de la grille où se trouve la bombe*/
    int X1b = W-1;
    int Y1b = H-1; /*coordonnées de fin de la grille où se trouve la bombe*/

    while (N--) { /*boucle sur le nombre de tours*/
        char bomb_dir[11]; /*création d'un tableau de caractères qui contient les informations à chaque tours*/
        scanf("%s", bomb_dir);

        if (bomb_dir[0]=='U'){  /*Si Unknown alors on est au premier coup*/
            Xd = (W/2) - X0;
            Yd = (H/2) - Y0;
            X0=(W/2);
            Y0=(H/2); /*place batman au centre de la grille*/
        }
        else{
            if (bomb_dir[0]=='W'){ /*si on se rapproche de la bombe*/
                if (Xd>0){          /*Si l'on est à droite*/
                    X0b=X0;
                    Xd = (X0b+X1b)/2 - X0;
                    Yd = 0;
                }
                else if (Xd<0){/*Si l'on est à gauche*/
                    X1b=X0;
                    Xd = (X0b+X1b)/2 - X0;
                    Yd = 0;
                }
                else if (Yd<0){/*Si l'on est au dessus*/
                    Y1b=Y0;
                    Yd = (Y0b+Y1b)/2 - Y0;
                    Xd = 0;
                }
                else if (Yd>0){/*Si l'on est en dessous*/
                    Y0b=Y0;
                    Yd = (Y0b+Y1b)/2 - Y0;
                    Xd = 0;
                }
            }
            else if(bomb_dir[0]=='C'){/*si on s'éloigne*/
                if (Xd>0){
                    X1b=X0-1;
                    Xd = (X0b+X1b)/2 - X0;
                    Yd = 0;
                }
                else if (Xd<0){ /*de la meme facon que si on se rapproche à gauche*/
                    X0b=X0;
                    Xd = (X0b+X1b)/2 - X0;
                    Yd = 0;
                }
                else if (Yd>0){

                    Y1b=Y0-1;
                    Yd = (Y0b+Y1b)/2 - Y0;
                    Xd = 0;
                }
                else if (Yd<0){
                    Y0b=Y0-1;
                    Yd = (Y0b+Y1b)/2 - Y0;
                    Xd = 0;
                }
            }
            else if(bomb_dir[0]=='S'){/*si l'on est a égal distance*/


                if (Xd>0){
                    Xd = 0;
                    Y0=(Y0b+Y1b)/2;
                    Yd = (Y0b+Y1b)/2 - Y0;
                }
                else if (Xd<0){
                    Xd = 0;
                    Y0=(Y0b+Y1b)/2;
                    Yd = (Y0b+Y1b)/2 - Y0;
                }
                else if (Yd>0){

                    Yd = 0;
                    X0=(X0b+X1b)/2;
                    Xd = (X0b+X1b)/2 - X0;
                }
                else if (Yd<0){

                    Yd = 0;
                    X0=(X0b+X1b)/2;
                    Xd = (X0b+X1b)/2 - X0;
                }
                else if (Xd==0){
                    Xd = 0;
                    Y0=Y0/2;
                    Yd = Y0/2 - Y0;
                }
                else if (Yd==0){
                    Yd = 0;
                    X0=X0/2;
                    Xd = X0/2 - X0;
                }
            }
            if(bomb_dir[0]!='S'){/*si l'on n'est pas à égal distance on regarde la parité*/
                if ((X0b+X1b)/2<1){
                    X0=0;
                }
                else if ((X0b+X1b)%2!=0){
                    X0=((X0b+X1b)/2)+1;
                }
                else{
                    X0=((X0b+X1b)/2);
                }
                if ((Y0b+Y1b)/2<1){
                    Y0=0;
                }
                else if ((Y0b+Y1b)%2!=0){
                    Y0=((Y0b+Y1b)/2)+1;
                }
                else{
                    Y0=(Y0b+Y1b)/2;
                }

            }
        }
        printf("%d %d\n",X0,Y0);/*affiche la nouvelle position de batman*/
    }
    return 0;
}

3. Apprentissage

J’ai trouvé cet épisode bien plus dur que le premier, trouver un algorithme qui fonctionnait à été bien plus long à trouver. Cependant ce n’était pas le meilleurs algorithme. Je pense que si j’avais réussi à coder mes deux dichotomie en même temps mes tests aurait pu fonctionner à 100%