Rapport sur Lumen
Table of Contents
1. Présentation du problème
Brainfuck est un puzzle présent sur le site codingame. On dispose d’une grille composé de ’X’ et de ’C’, Les ’C’ représentes les positions de bougie disposé sur la grille et les ’X’ sont les zones ou il n’y en a pas. On doit créer une nouvelle grille qui sera composé des valeurs de l’intensité de la lumière qu’emet la bougie. On nous donne la valeur initiale comprise entre 0 et 10 puis il faut diminuer cette valeur dès qu’on s’éloigne de la bougie, par exemple si la valeur initiale est 5, alors toute les cases qui sont autour prendront la valeur 4 et à chaque fois qu’on s’écarte on diminue de 1. Le but étant de donné le nombre de case non éclairée, autrement dit le nombre de case dont la valeur est 0.
2. Méthode de résolution
2.1. détail algorithmique
2.2. code de résolution
voici le code de résolution de lumen, il n’y a pas de fonctions, seulement le programme principal. On instancie d’abord les variables puis on crée la grille remplie de 0 hormis au endroit ou se trouve les bougies qui sont initialiser a la valeur de L c’est-à-dire la valeur de l’intensité de la lumière. on crée ensuite la triple boucle qui permet de parcourir la grille, la première sert pour chaque valeur d’intensité, qui va de 0 à L-1. La deuxième sert a parcourir chaque lignes de la grille, et enfin la troisième sert a regarder chaque éléments de chaque lignes. A l’intérieur de cette triple boucle on retrouve les conditions qui regardent les 8 cases autour de la case actuelle, et applique les changement s’il le faut. Enfin, après avoir rempli la grille avec les bonnes valeurs, on fait la somme des 0 qu’il reste dans la grille et on l’affiche
#include <stdlib.h> #include <stdio.h> #include <string.h> #include <stdbool.h> int main() { int N; scanf("%d", &N); int L; scanf("%d", &L); char grille[256][256]; int somme; //on crée la grille remplie de 0 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { char cell[4]; scanf("%s", cell); grille[i][j]= cell[0]=='X' ? '0' : (char)L+'0'; } } //on parcours le tableau pour chaques valeurs d'intensité for (int k=0; k<L ;k++){ //on parcours chaques lignes de la grille for (int i=0; i<N;i++){ //on parcours chaques éléments for (int j=0; j<N;j++){ char valeur=(char)L-k+'0'; if (grille[i][j]==valeur){ //on regarde chaque case autour de la case actuelle et on change la valeurs si nécéssaire if (grille[i-1][j-1]<valeur){ grille[i-1][j-1]=valeur-1; } if (grille[i-1][j]<valeur){ grille[i-1][j]=valeur-1; } if (grille[i-1][j+1]<valeur){ grille[i-1][j+1]=valeur-1; } if (grille[i][j+1]<valeur){ grille[i][j+1]=valeur-1; } if (grille[i+1][j+1]<valeur){ grille[i+1][j+1]=valeur-1; } if (grille[i+1][j]<valeur){ grille[i+1][j]=valeur-1; } if (grille[i+1][j-1]<valeur){ grille[i+1][j-1]=valeur-1; } if (grille[i][j-1]<valeur){ grille[i][j-1]=valeur-1; } } } } } //on fait la somme des 0 qu'il reste for (int i = 0; i<N; i++){ for (int j=0; j<N;j++){ somme+=grille[i][j]=='0' ? 1 : 0; } } //on affiche le résultat printf("%d\n",somme); return 0; }
2.3. tests
2.3.1. premier test
avec seulement une bougie d’intensité 3 sur une zone de 5 x 5 cases
5 3 X X X X X X C X X X X X X X X X X X X X X X X X X
cela donne:
9
si on compare le résultat au résultat attendu:
9
on voit que le code renvoie bien le bon résultat
2.3.2. deuxième test
avec une grille de 20 x 20 et et plusieurs bougies d’intensité 3
20 3 X X X C X C X X X X X X X X X X X X X X X C X X X C X X X X C X X X X C X X X X X X X X X X X X X X X X X C C X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X C X X X X X X X X C X X X X X X X C X X X X X X X X C X X X X X X X X C X X X X C X X X X X X C X X C C C X X X X X X X X X C X X X X X X X X C X X X C X X X X X X X X X C X X C X X X X X X X X X C X X X X X X X X X X X C X C X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X C X X X X X X X X X X C X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X C C X X X X C X X X X X X X X X X X X X X X X C C C X X X X X X X X X X X X X C X X X X X X X C C X X X X X C X X X X X X X X X X X X X C X X X X X X X C X X X X X X X X X C X X X X X C X C X X X X X X X X X X X X X X X X
cela donne:
34
si on compare le résultat au résultat attendu:
34
on voit que le code renvoie bien le bon résultat
3. solutions de la comunauté
J’ai choisi de présenter la solution de Alain-Delpuch qui utilise la récursivité pour résoudre ce problème, ce type de solution était ma première idée pour résoudre ce problème mais je n’ai pas reussi a la mettre en place.
// ------------------------------------------------------------------ // Lumen // ------------------------------------------------------------------ #include <stdio.h> // ------------------------------------------------------------------ int map[25][25]; int N,L; // ------------------------------------------------------------------ void F(unsigned int i, unsigned int j, int l){ if ( i >= N || j >= N || l < map[i][j] ) return; map[i][j] = l--; F( i-1 , j-1 , l) ; F( i-1 , j , l) ; F( i-1 , j+1 , l) ; F( i , j-1 , l) ; ; F( i , j+1 , l) ; F( i+1 , j-1 , l) ; F( i+1 , j , l) ; F( i+1 , j+1 , l) ; } // ------------------------------------------------------------------ main() { scanf("%d %d\n", &N, &L); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { char buf[2]; scanf("%s",buf); F( i , j , *buf=='X' ? 0 : L); } } int result = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { result += map[i][j] == 0; } } printf("%d",result); }
Il initialise la fonction F qui est la fonction récursive qui renverra la répartition des intensités de lumières pour chaque cases. Il met ensuite dans son main la double boucle for qui appellera la fonction F qui modifiera les valeurs des cases. Il met ensuite en place une autre double boucle for pour compter le nombre de 0 qu’il reste dans la grille complète et renvoie le résultat.
4. lien
Vous pouvez retrouver ce rapport sur ma page web