Rapport Lumen

Table des matières

1. Introduction
2. Méthode de résolution
- 2.1. Implémentation complète
3. Tests
4. Solution de la communauté
5. Conclusion

1. Introduction

1.1. Déroulement du jeu / Objectif

Url du challenge : https://www.codingame.com/ide/puzzle/lumen

Mise en situation: vous êtes placé au milieu d’une pièce sombre éclairée par des bougies. La pièce est rectangulaire et les bougies sont placées au sol. Chaque bougie éclaire une zone de la pièce. L’objectif est trouvé les zones de la pièce qui ne sont pas éclairées par aucune bougie.

1.2. Données fournies

On reçoit en entrée la taille du côté de la pièce `N` et l’intensité de chaque bougie `L`. Exemple :

5
3

Ce qui donne une pièce de 5x5 et une intensité de 3 pour chaque bougie.

On nous donne ensuite la position de chaque bougie dans la pièce. La pièce est représentée par une matrice de caractères. Les caractères sont soit :

’X’ : la zone est vide
’C’ : la zone est occupée par une bougie

Exemple de matrice :

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

Dans cet exemple la bougie est en position (1,1) et l’intensité est de 3. Ce qui donne une zone éclairée de 3x3 autour de la bougie, que l’on peut voir sur la figure ci-dessous.

2	2	2	1
2	3	2	1
2	2	2	1
1	1	1	1
0	0	0	0

1.3. Données à fournir

Le résultat à fournir est un nombre entier qui représente le nombre de zones non éclairées. Dans l’exemple ci-dessus le résultat est 9.

1.4. Contraintes

’N’ est compris entre : 0 < N <= 25
’L’ est compris entre : 0 < L < 10
Il n’y a pas de temps limite pour le calcul.

2. Méthode de résolution

On définit une structure qui représente une coordonnée dans la pièce. Elle contient deux entiers `x` et `y`.

typedef struct {
    int x;
    int y;
} coord;

On commence par récupérer les données d’entrée.

int N; // taille de la pièce
scanf("%d", &N);

int L; // intensité des bougies
scanf("%d", &L);

On crée ensuite une matrice de taille N*N qui représente la pièce avec malloc. Elle contiendra la position des bougies.

coord *tab_light = malloc(N * N * sizeof *tab_light);
int next_pos = 0;

On parcourt ensuite la matrice de la pièce et on stocke les coordonnées des bougies dans la matrice `tab_ light`.

int x, y;
char cell[2];
for (x = 0; x < N; x++)
{
    for (y = 0; y < N; y++)
    {
        scanf("%s", cell);

        if (cell[0] == 'C')
        {
            tab_light[next_pos].x = x;
            tab_light[next_pos].y = y;
            next_pos++;
        }
    }
}

On crée ensuite une fonction qui calcule la distance entre deux coordonnées.

int distance(coord cell, coord light)
{
    int dist_x = abs(cell.x - light.x);
    int dist_y = abs(cell.y - light.y);

    if (dist_x > dist_y)
    {
        return dist_x;
    }
    else
    {
        return dist_y;
    }
}

Ensuite, on parcourt chaque case de la pièce et on vérifie si elle est éclairée par au moins une bougie. Si oui la case est éclairée. Sinon on vient de trouver une case non éclairée, on incrémente le compteur de case non éclairée.

int dark_spot = 0;
for (x = 0; x < N; x++)
{
    for (y = 0; y < N; y++)
    {
        int flag = 0;

        for (int k = 0; k < next_pos; k++)
        {
            if (L - distance((coord){x, y}, tab_light[k]) > 0)
            {
                flag = 1;
                break;
            }
        }

        if (flag == 0)
        {
            dark_spot++;
        }
    }
}

Enfin, on libère la mémoire allouée avec malloc et on affiche le résultat.

free(tab_light);
printf("%d", dark_spot);

2.1. Implémentation complète

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

typedef struct {
    int x;
    int y;
} coord;

int distance(coord cell, coord light)
{
    int dist_x = abs(cell.x - light.x);
    int dist_y = abs(cell.y - light.y);

    if (dist_x > dist_y)
    {
        return dist_x;
    }
    else
    {
        return dist_y;
    }
}

int main()
{
    int N; // taille de la pièce
    scanf("%d", &N);
    
    int L; // intensité des bougies
    scanf("%d", &L);

    coord *tab_light = malloc(N * N * sizeof *tab_light);
    int next_pos = 0;

    int x, y;
    char cell[2];
    for (x = 0; x < N; x++)
    {
        for (y = 0; y < N; y++)
        {
            scanf("%s", cell);
    
            if (cell[0] == 'C')
            {
                tab_light[next_pos].x = x;
                tab_light[next_pos].y = y;
                next_pos++;
            }
        }
    }

    int dark_spot = 0;
    for (x = 0; x < N; x++)
    {
        for (y = 0; y < N; y++)
        {
            int flag = 0;
    
            for (int k = 0; k < next_pos; k++)
            {
                if (L - distance((coord){x, y}, tab_light[k]) > 0)
                {
                    flag = 1;
                    break;
                }
            }
    
            if (flag == 0)
            {
                dark_spot++;
            }
        }
    }

    free(tab_light);
    printf("%d", dark_spot);

    return 0;
}

3. Tests

3.1. Compilation

Compilation avec gcc :

✅ Compilation sans erreur/warning OK

3.2. Test de Codingame

3.2.1. Test 1 : THEY only have one candle

Input:

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

Expected output:

Actual output:

Run test:

Test 1: THEY only have one candle
✅ Test passed

3.2.2. Test 2 : THEY are doing a ritual

Input:

5
3
C X X X C
X X X X X
X X X X X
X X X X X
C X X X C

Expected output:

Actual output:

Run test:

Test 2: THEY are doing a ritual
✅ Test passed

3.2.3. Test 3 : THEY have a large pit

Input:

5
3
X X X X X
X C X X X
X X X X X
X X X C X
X X X X X

Expected output:

Actual output:

Run test:

Test 3: THEY have a large pit
✅ Test passed

3.2.4. Test 4 : THEY have a small cellar

Input:

6
3
X X 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 X
X X X X X X

Expected output:

Actual output:

Run test:

Test 4: THEY have a small cellar
✅ Test passed

3.2.5. Test 5 : THEY have a medium cellar

Input:

15
3
X X 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 C 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 C X X X X X X X X X X
C X X X X X X X C X X C X X X
X X X X X C 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 C X C 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 X X X X X X X
X X C X C X X X X X X X X X C
X X X X X X C X X X C 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

Expected output:

Actual output:

Run test:

Test 5: THEY have a medium cellar
✅ Test passed

3.2.6. Test 6 : THEY have a large cellar

Input:

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

Expected output:

Actual output:

Run test:

Test 6: THEY have a large cellar
✅ Test passed

3.2.7. Test 7 : THEY are not very smart

Input:

3
3
X X X
X X X
X X X

Expected output:

Actual output:

Run test:

Test 7: THEY are not very smart
✅ Test passed

3.2.8. Test 8 : THEY have a great hall

Input:

25
2
X X C C C C X X X X C C X X X C X X X X X C X X X
C 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 X X X X X X X X X X X C X X X X C X X X C C X X
C 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 C X X X X X X X X X C X X C X X X C X X X
X X X X X C X X X X X X X C X C X X X X X X X X X
C X X X X C C X X X X X X X X X C X X X X X X C X
C X C C X X C X X C X X C C 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 C X X X X X C 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
C X X X X X X C X C X X X X C X X X X X C X X X X
X C X X C X X X X X X X X X C 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 C X C X X X X X C X X X X X X C C X X X C X C
C X C C X X X X X X X X X X C X X X X X C X X X X
C X X C X C X X C C X X X C C X X X X X X X C C X
C 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 X X C X X X X X X C X X X X X X X C X X
X C X C X X C X X X X X C X X X X X X X C C X C X
X X X C X X C C C X X C X X X X X C X X X X X X X
X C X 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 C C X X C X C X X X X X X X X X C C X X X X
X X C X X X X C X C C X X X X X C X X X X C C X X
X X X X C X X X X X C X X X X X C X X X C X X C X
X X X C X X C X X X X X X X X X X X C X X X X X X

Expected output:

Actual output:

Run test:

Test 8: THEY have a great hall
✅ Test passed

3.2.9. Test 9 : Not Euclidean

Input:

5
4
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

Expected output:

Actual output:

Run test:

Test 9: Not Euclidean
✅ Test passed

✅ Test 1 : THEY only have one candle passed
✅ Test 2 : THEY are doing a ritual passed
✅ Test 3 : THEY have a large pit passed
✅ Test 4 : THEY have a small cellar passed
✅ Test 5 : THEY have a medium cellar passed
✅ Test 6 : THEY have a large cellar passed
✅ Test 7 : THEY are not very smart passed
✅ Test 8 : THEY have a great hall passed
✅ Test 9 : Not Euclidean passed
Passed: 9 (100.0%)
Failed: 0 (0.0%)

3.3. Test Valgrind

✅ Valgrind check

4. Solution de la communauté

Solution de Alain-Delpuch :

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

Pour résoudre le problème, l’utilisateur a décidé de créer une fonction récursive qui prend en argument les coordonnées d’une case et l’intensité lumineuse. La fonction se rapelle tant que la luminosité est différente de 1, en baissant la luminosité de 1 et se propage aux cases voisines.

On peut aussi noter que l’utilisateur utilise des variables avec des types non signés pour optimiser l’usage de la mémoire, mais utilise à l’inverse un tableau à deux dimensions de traille maximale au lieu d’utiliser une allocation dynamique.

5. Conclusion

Lors de cet exercice, j’ai mis en pratique l’utilisation de ’malloc’ et le parcours de tableaux a deux dimensions. Cet exercice m’a aussi permis de mettre en place un template pour automatiser le téléchargement, l’exécution et la vérification de tests.

Retour vers ma page Web personnelle

Crédits :

Template : github