Shadow Knight

Table of Contents

Retour vers le site

1. Shadows of the Knight 1

1.1. Présentation du problème

Le but de ce problème est de trouver la position d’une bombe dans un immeuble. L’immeuble est assimilé à un tableau à 2 dimensions. A chaque tour, on indique les coordonées d’une fenêtre au programme et il nous insique si la direction de la bombe.

direction.png

1.2. Stratégie

La stratégie est simplement de réaliser une dicotomie en \(x\) et ne \(y\) sur l’immeuble.

1.2.1. Dichotomie

Pour rappel, le principe de la recherche dichotomique est de trouver un elem dans un tableau trié. Pour cela, on compare l’élément recherché avec l’élément du milieu de l’interval de recherche.

  • Si l’élément recherché est plus grand, on abaisse la valeur haute de l’interval de recherche à celle de l’élément.
  • Dans le cas inverse, on élève la valeur basse de l’inteval de recherche.

1.3. Code

1.3.1. Explications

Tout d’abord, je défini les bornes de mon interval en \(x\) et \(y\) : 

int min_x = 0, max_x = width - 1;
int min_y = 0, max_y = height - 1;

Maintenant, tant que l’on a pas atteind le nombre de coups maximal :

  • On regarde chaque lettre du message renvoyé par codingame:
    • Si celui-ci comporte un R, on rehausse le \(min\) en \(x\) en le mettant à \(x+1\) la valeur du milieu de l’interval en excluant la case visitée
    • Si celui-ci comporte un D, on rehausse le \(min\) en \(y\) en le mettant à \(y-1\) la valeur du milieu de l’interval en excluant la case visitée
    • Si celui-ci comporte un L, on rabaisse le \(max\) en \(x\) en le mettant à \(x+1\) la valeur du milieu de l’interval en excluant la case visitée
    • Si celui-ci comporte un U, on rabaisse le \(max\) en \(y\) en le mettant à \(y-1\) la valeur du milieu de l’interval en excluant la case visitée
  • On affiche les nouvelles coo à tester soit le milieu du nouvel interval.
  • On enlève 1 aux nombres de coup.

1.3.2. Programme principale

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

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/

int main() {
  // width of the building.
  int width, height;
  int max_turn;
  int x, y;
  int i;
  int max_y, min_y = 0;
  int max_x, min_x = 0;
  // height of the building.
  // maximum number of turns before game over.
  scanf("%d%d", &width, &height);
  scanf("%d", &max_turn);
  scanf("%d%d", &x, &y);

  max_y = height - 1;
  max_x = width - 1;
  // game loop
  while (max_turn) {
    // the direction of the bombs from batman's current location (U, UR, R, DR,
    // D, DL, L or UL)
    i = 0;
    char bomb_dir[3];
    scanf("%s", bomb_dir);
    // printf("%d %d, %d %d:\n", min_x, max_x, min_y, max_y);
    while (bomb_dir[i] != '\0') {
      switch (bomb_dir[i]) {
      case 'U':
        max_y = y - 1;
        break;
      case 'D':
        min_y = y + 1;
        break;
      case 'R':
        min_x = x + 1;
        break;
      case 'L':
        max_x = x - 1;
        break;
      default:
        return 1;
      }
      ++i;
    }

    y = (min_y + max_y) / 2;
    x = (min_x + max_x) / 2;
    // Write an action using printf(). DON'T FORGET THE TRAILING \n
    // To debug: fprintf(stderr, "Debug messages...\n");

    // the location of the next window Batman should jump to.
    printf("%d %d\n", x, y);
    --max_turn;
  }

  return 0;
}

1.4. Solution de la communauté

Encore une fois les solutions d’Alain-Delpuch force le respect. Ce qui est plaisant dans sa solution c’est la petitesse de son code. Le code comprend très peu de ligne mais reste pour autant très lisible. De manière générale la mise en plage de ses code participe à la lecture.

1.4.1. Code

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

2. Shadown of the Night 2

2.1. Présentation du problème

A l’instar du premier problème, le but est de trouver une bombe dans un immeuble en un temps de coup limité. Seulement cette fois-ci, on ne nous indique la directnio de la bombe à chaque tour mais plus s’il on se trouve plus près ou non par rapport au tour précédent. Ce léger détails complexifie pas mal la tâche.

2.1.1. Input initiale

W H
N
X0 Y0

Avec :

  • W la longueur de l’immeuble
  • H la hauteur de l’immeuble
  • N le nombre de coup autorisé
  • (X0, Y0) Les coordonées initiale de Batman

2.2. Stratégie

2.2.1. Précision

D’emblée, je précise que ma solution ne fonctionne pas. Elle marche pour quelqes test (les 2 premiers en l’occurence). Ma solution n’est pas assez optimisée pour réussir des tests plsu exigents.

2.2.2. Approche

Mon approche est la suivante :

  • On commence par faire une dichotomie classique horizontale.
  • Tant que l’on chauffe, on continue.
  • Si l’on refroidit, on change de domaine de recherche, on passe à la verticale.
  • On continue ainsi de suite jusqu’à se retrouver sur ka case de la bombe.

2.3. Code

2.3.1. Programme principale

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

void move_warmer(int *prec, int *coo, int *search_zone, int i_axes) {
  if (prec[i_axes] > coo[i_axes]) {
    search_zone[1] = (coo[i_axes] + prec[i_axes]) / 2;
    prec[i_axes] = coo[i_axes];
    coo[i_axes] = search_zone[1];
  } else {
    search_zone[0] = (coo[i_axes] + prec[i_axes] + 1) / 2;
    prec[i_axes] = coo[i_axes];
    coo[i_axes] = search_zone[0];
  }
}

int move_cooler(int prec[], int coo[], int search_zone[][2], int i_axes) {
  if (prec[i_axes] < coo[i_axes]) {
    search_zone[i_axes][1] = (coo[i_axes] + prec[i_axes]) / 2;
  } else {
    search_zone[i_axes][0] = (coo[i_axes] + prec[i_axes] + 1) / 2;
  }
  prec[i_axes] = coo[i_axes];
  i_axes = (i_axes + 1) % 2;
  coo[i_axes] = search_zone[i_axes][1] - coo[i_axes] <
                        (search_zone[i_axes][1] - search_zone[i_axes][0]) / 2
                    ? search_zone[i_axes][0]
                    : search_zone[i_axes][1];

  return i_axes;
}

int main() {
  // width of the building.
  int width;
  // height of the building.
  int height;
  scanf("%d%d", &width, &height);
  // maximum number of turns before game over.
  int N;
  scanf("%d", &N);
  int coo[2];
  int warmest[2];
  int prec[2];
  int i_axes = 0;
  int search_zone[2][2] = {{0, width - 1}, {0, height - 1}};
  scanf("%d%d", &coo[0], &coo[1]);
  prec[0] = coo[0], prec[1] = coo[1];

  // game loop
  while (N) {
    // Current distance to the bomb compared to previous distance (COLDER,
    // WARMER, SAME or UNKNOWN)
    char bomb_dir[11];
    scanf("%s", bomb_dir);
    fprintf(stderr, "x: %d %d\ny: %d %d\n", search_zone[0][0],
            search_zone[0][1], search_zone[1][0], search_zone[1][1]);
    fprintf(stderr, "prec: %d %d\n", prec[0], prec[1]);
    fprintf(stderr, "coo: %d %d\n", coo[0], coo[1]);
    fprintf(stderr, "i_axes: %d", i_axes);
    switch (bomb_dir[0]) {
    case 'U':
      coo[0] = search_zone[0][1] - coo[0] < width / 2 ? 0 : width - 1;
      break;
    case 'W':
      move_warmer(prec, coo, search_zone[i_axes], i_axes);
      break;
    case 'C':
      if (search_zone[(i_axes + 1) % 2][0] !=
          search_zone[(i_axes + 1) % 2][1]) {
        fprintf(stderr, "test");
        i_axes = move_cooler(prec, coo, search_zone, i_axes);
      } else {
        move_warmer(coo, prec, search_zone[i_axes], i_axes);
      }
      break;
    case 'S':
      if (search_zone[i_axes][0] == search_zone[i_axes][1]) {
        i_axes = (i_axes + 1) % 2;
        coo[i_axes] =
            search_zone[i_axes][1] - coo[i_axes] <
                    (search_zone[i_axes][1] - search_zone[i_axes][0]) / 2
                ? search_zone[i_axes][0]
                : search_zone[i_axes][1];
      } else {
        coo[i_axes] = (prec[i_axes] + coo[i_axes] + 1) / 2;
        search_zone[i_axes][0] = coo[i_axes];
        search_zone[i_axes][1] = coo[i_axes];
      }
      break;
    }
    // Write an action using printf(). DON'T FORGET THE TRAILING \n
    // To debug: fprintf(stderr, "Debug messages...\n");

    printf("%d %d\n", coo[0], coo[1]);
    --N;
  }

  return 0;
}

3. Conclusion

N’ayant pas réussie à trouver la solution du deuxième Codingame, je ne peux vous présenter de solutions de la communauté. Néanmoins, ces 2 exercices sont très untéressant d’un point de vue accadémique. En effet, on y voit une approche de la dichotomie plus ludique et plus challengeante.

Author: Arthur Barraux

Created: 2024-05-01 mer. 01:06