Shadows of the knight I et II

Table of Contents

UCA.png

SOTK.png

1. Shadows of the knight I

1.1. Introduction Shadows of the knight I

Vous allez rechercher les otages d’un batiment donné en sautant de fenêtre en fenêtre à l’aide de votre grappin. Votre but est d’arriver sur la fenêtre de la pièce où les otages se trouvent afin de désamorcer les bombes. Malheureusement vous n’avez qu’un nombre de sauts limités avant que les bombes n’explosent…

L’indication de l’endroit de la bombe se fait avec les initiale U ; UR ; R ; DR ; D ; DL ; L ; UL pour chacune des positions possibles (U pour en haut, R pour droite, L pour gauche, D pour en bas)

1.2. Solution expliquée

Pour cette exercice il nous faut utiliser une simple recherche par dichotomie.

Je créé alors une fonction calculerMoyenne qui me renverra la moyenne entre deux points minimum et maximum suivant la direction demandé. Par exemple si le programme m’envoie ’DR’ alors la position de la bombe sera en bas à droite, donc on peut déjà noter notre position actuelle comme minimum pour l’axe des abscisse et ordonnées, puis nous allons faire la moyenne avec le maximum. et enfin déplacer le personnage. 

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

int calculerMoyenne(int pos1, int posMax)
{
    return (pos1+posMax)/2;
}

int main()
{
    // largeur du building.
    int W;
    // Hauteur du building.
    int H;
    scanf("%d%d", &W, &H);
    // nombre maximum avant la fin.
    int N;
    scanf("%d", &N);
    // position x et y du personnage
    int X0;
    int Y0;
    scanf("%d%d", &X0, &Y0);
    // valeurs max et min que peut prendre le personnage
    int MaxW=W,MaxH=H,MinW=0,MinH=0;

    // game loop
    while (1) {
        // the direction of the bombs from batman's current location (U, UR, R, DR, D, DL, L or UL)
        char bomb_dir[4];
        scanf("%s", bomb_dir);

        char *ret;

        // test du certain caractere dans le mot, puis calcule de moyenne avec le minimum et maximum actuelle dans chaque cas possibles
        ret = strstr(bomb_dir, "D");
        if (ret){
            MinH=Y0;
            Y0=calculerMoyenne(Y0,MaxH);
            }
        ret = strstr(bomb_dir, "R");
        if (ret){
            MinW=X0;
            X0=calculerMoyenne(X0,MaxW);
            }

        ret = strstr(bomb_dir, "U");
        if (ret){
            MaxH=Y0;
            Y0=calculerMoyenne(Y0,MinH);
            }

        ret = strstr(bomb_dir, "L");
        if (ret){
            MaxW=X0;
            X0=calculerMoyenne(X0,MinW);
            }

        // renvoie la position actuelle
        printf("%d %d\n",X0,Y0);
    }

    return 0;
}

1.3. Tests et exécutions

Les test sont assez basique pusiqu’ils test notre programme dans toute les directions, ils sont calibrer pour de la dichotomie car le nombre de coups possibles sont regler pile pour le nombre de coup qu’une dichotomie met pour trouver la cible.

(les jeux de test ne sont pas disponible pour cette exercice)

1.4. solutions de la communauté

Dans la solution de Klemek, il reprends le même principe que que moi, mais lorsqu’il détermine son maximum ou son minimum il fait +1 ou -1 se qui lui permet d’être un peut plus précis. ce que j’aime bien dans son code c’est qu’il est court est très compréhensible! 

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

int main()
{
    int W;
    int H;
    scanf("%d%d", &W, &H);
    int N;
    scanf("%d", &N);
    int X0;
    int Y0;
    scanf("%d%d", &X0, &Y0);

    int min_x = 0;
    int min_y = 0;
    int max_x = W;
    int max_y = H;

    while (1) {
        char bomb_dir[4];
        scanf("%s", bomb_dir);

        if (strchr(bomb_dir, 'R') != NULL) { min_x = X0 + 1; }
        if (strchr(bomb_dir, 'L') != NULL) { max_x = X0 - 1; }
        if (strchr(bomb_dir, 'D') != NULL) { min_y = Y0 + 1; }
        if (strchr(bomb_dir, 'U') != NULL) { max_y = Y0 - 1; }

        X0 = (min_x + max_x) / 2;
        Y0 = (min_y + max_y) / 2;

        printf("%d %d\n", X0, Y0);
    }
    return 0;
}

Code de Klemek

2. Shadows of the knight II

2.1. Introduction Shadows of the knight II

En raison du bouclier thermique, le détecteur ne peut plus fournir la direction des bombes : il indique uniquement si vous vous rapprochez ou vous vous éloignez des bombes.

L’indication de l’endroit de la bombe se fait ici avec le systeme de chaud, froid, pareil.

2.2. Solution expliquée

Pour cette exercice il nous faut utiliser recherche dichotomique intéligente, puisque ici on ne peut pas confirmer avec un seul saut si la bombe est devant ou derrière nous (ce saut est appelé “minijump” dans mon code). Dans ma solution j’ai séparé la tache en 2, je commence par trouver l’axe X puis l’axe Y, afin de les déterminer j’utilise une recherche par dichotomie, puis pour confirmer la position exacte de la bombe je je fait un saut en arriere puis je regarde si je me suis rapproché ou éloigné.

  • Si je me suis éloigné, alors la bombe est encore plus loin, dans la direction opposée, je peux donc renseigner le min (ou le max selon les cas), puis je continue la dichoromie.
  • Si je me suis rapproché, alors la bombe est dans la même direction, je peux renseigner le min (ou le max selon les cas), puis je continue la dichoromie.

Enfin si l’indicateur m’indique same, alors cela signifie que nous avons trouver la bonne abscisse, on passe donc aux ordonnées.

A noter: Cette solution fonctionne mais est très lente puisque l’on double son coût en utilisant le “minijump” ce qui rends cette solution obselète sur des test plus important 

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


int main()
{
    // width of the building.
    int W;
    // height of the building.
    int H;
    scanf("%d%d", &W, &H);
    // maximum number of turns before game over.
    int N;
    scanf("%d", &N);
    int X0;
    int Y0;
    //variable pour la direction a suivre
    int DirX=0,DirY=0;
    // borne de la dichotomie
    int MaxH=H,MinH=0,MaxW=W,MinW=0;

    scanf("%d%d", &X0, &Y0);

    // initialisation du premier saut et du Minijump
    int firstJump=0;
    int MiniJump=0;
    
    // game loop
    while (1) {
        // Current distance to the bomb compared to previous distance (COLDER, WARMER, SAME or UNKNOWN)
        char bomb_dir[11];
        scanf("%s", bomb_dir);

        if (strcmp(bomb_dir,"UNKNOWN") == 0)
        {
            //je renseigne une direction initial a suivre suivant ou l'on se trouve sur le terrain
            firstJump=0;
            if(X0<W-1)
            {
                X0=X0+1;
                DirX=1;
            }
            else if(X0>1)
            {
                X0=X0-1;
                DirX=-1;
            }
        }
        
        else if (strcmp(bomb_dir,"WARMER") == 0)
        {
            //je test chaques cas et j'utilise la dichotomie dans le sens de la direction
            MiniJump++;
            firstJump++;
            if(MiniJump<2)
            {
            if(DirX==1)
            {
                X0=(X0+MaxW)/2;
            }
            if(DirX==-1)
            {
                X0=(X0+MinW)/2;
            }
            if(DirY==1)
            {
                Y0=(Y0+MaxH)/2;
            }
            if(DirY==-1)
            {
                Y0=(Y0+MinH)/2;
            }
            }
            //ici un tour sur deux je viens faire un saut de taille -1 afin de determiner la bonne direction à suivre lors du prochain saut
            else if(MiniJump<3)
            {
            if(DirX!=0)
            {
                DirX*=-1;
                X0+=DirX;
            }
            if(DirY!=0)
            {
                DirY*=-1;
                Y0+=DirY;
            }
            }
            else
            {
                if(DirX==1)
            {
                MinW=X0;
                X0=(X0+MaxW)/2;
                
            }
            if(DirX==-1)
            {
                MaxW=X0;
                X0=(X0+MinW)/2;
            }
            if(DirY==1)
            {
                
                MinH=Y0;
                Y0=(Y0+MaxH)/2;
            }
            if(DirY==-1)
            {
                
                MaxH=Y0;
                Y0=(Y0+MinH)/2;
            }
            MiniJump=0;
            }

        }
        else if (strcmp(bomb_dir,"COLDER") == 0)
        {
            //je test chaques cas et j'utilise la dichotomie dans le sens de la direction
            MiniJump++;
             fprintf(stderr, "COLDER\n");
             firstJump++;

            if(MiniJump<2)
            {

            if(DirX==1)
            {
                X0=(X0+MinW)/2;
            }
            if(DirX==-1)
            {
                X0=(X0+MaxW)/2;
            }
            if(DirY==1)
            {
                Y0=(Y0+MinH)/2;
            }
            if(DirY==-1)
            {
                Y0=(Y0+MaxH)/2;
            }
            }
            //ici un tour sur deux je viens faire un saut de taille -1 afin de determiner la bonne direction à suivre lors du prochain saut
            else if (MiniJump<3)
            {
            if(DirX!=0)
            {
                DirX*=-1;
                X0+=DirX;
            }
            if(DirY!=0)
            {
                DirY*=-1;
                Y0+=DirY;
            }
            }
            else
            {
                if(DirX==1)
            {
                
                MaxW=X0;
                X0=(X0+MinW)/2;
            }
            if(DirX==-1)
            {
                
                MinW=X0;
                X0=(X0+MaxW)/2;
            }
            if(DirY==1)
            {
                
                MaxH=Y0;
                
                Y0=(Y0+MinH)/2;
            }
            if(DirY==-1)
            {
                
                MinH=Y0;
                
                Y0=(Y0+MaxH)/2;
            }
            MiniJump=0;
            }
        }
        else if (strcmp(bomb_dir,"SAME") == 0)
        {
            //ici je change l'axe sur lequel je fait ma recherche
            DirX=0;
            firstJump=0;
            if(DirY==0)
            {
                if(Y0<W-1)
                {
                Y0=Y0+1;
                DirY=1;
                }
                else if(Y0>1)
                {
                Y0=Y0-1;
                DirY=-1;
                }
            }
            
        }

        printf("%d %d\n",X0,Y0);
    }

    return 0;
}

2.3. Tests et exécutions

Les test sont intéligents puisque ils nous font tester tous les cas possibles ce qui rends cette exercice assez dificile !

(les jeux de test ne sont pas disponible pour cette exercice)

2.4. Solutions de la communauté

Dans la solution de DaNinja, il sépare son code en 2 fonctions la premiere found() qui va permettre une fois appelé de changer d’axe de recherche. Et une fonction get() qui va instaurer les bornes de la recherche. 

#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);
    }
}

Code de DaNinja

retour au Hub

Date: 2024-04-01

Author: CyprienJULLIEN

Created: 2024-05-01 mer. 12:28