Markov Ants

Page web ISIMA
Fichier .org source
Défi de programmation - Markov Ants

1. Introduction

Le problème consiste en compter le nombre moyen de secondes qu’une fourmi met à sortir d’une fourmilère, en connaissant sa vitesse de déplacement et la taille de la fourmilière. La fourmi se déplace dans une direction aléatoire à chaque pas.

2. Approche utilisée

2.1. Description synoptique

Mon approche est de compter en combien de temps une seule fourmi sort de la fourmilère puis de répéter ceci un grand nombre de fois afin d’en faire une moyenne.

2.2. Algorithme

M : Constante définissant le nombre de simulations sur lesquelles faire la moyenne
Fonction leave :
Prend en entrée une position pos (x, y), un entier step la taille du pas de la fourmi et la taille de la grille (w, h) et renvoie le nombre de seconde que la fourmi met pour sortir de la grille.
Si la pos n’est pas dans la grille :

Renvoyer 0

direction = entier aléatoire compris entre 0 et 3 (inclus)
mise à jour de pos en fonction de direction et step
Renvoyer 1 + valeur de retour de leave avec la nouvelle position pos

Fonction principale :
pos : la position (x, y) de la fourmi
w, h : respectivement la largeur et hauteur de la grille
step : la taille du pas de la fourmi
Somme = 0
Boucle allant de 0 à M:

Somme = Somme + leave(pos, step, w, h)

Fin boucle
average = Somme / M
Afficher average

3. Résolution

3.1. Programme

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

#define M 1000000

// Fonction renvoyant 1 si la position donnée est en dehors de la grille de taille (w, h)
int isOutside(int pos[2], int w, int h) {
    return pos[0]<=0 || pos[0]>=w-1 || pos[1]<=0 || pos[1]>=h-1;
}

// Fonction récursive comptant le nombre de seconde pour sortir de la grille
int leave(int pos[2], int step, int w, int h) {
    if (isOutside(pos, w, h)) {
        return 0;
    }
    int offX[4] = {0, 1, 0, -1};
    int offY[4] = {-1, 0, 1, 0};
    int dir = rand()%4;
    pos[0] += offX[dir] * step;
    pos[1] += offY[dir] * step;
    return 1 + leave(pos, step, w, h);
}

int main()
{
    srand(0);
    int step;
    scanf("%d", &step);
    int w;
    int h;
    int pos[2]; // x, y
    scanf("%d%d", &w, &h); fgetc(stdin);
    for (int i = 0; i < h; i++) {
        char row[32];
        scanf("%[^\n]", row); fgetc(stdin);
        for (int j=0; j<32; ++j) {
            // Récupère la position de la fourmi
            if (row[j] == 'A') {
                pos[0] = j; pos[1] = i;
            }
        }
    }

    // Moyenne sur un grand nombre de test
    int sum = 0;
    for (int i = 0; i<M; ++i) {
        int tmp[2] = {pos[0], pos[1]};
        sum += leave(tmp, step, w, h);
    }

    float avg = (float) sum / M;
    printf("%0.1f\n", avg);

    return 0;
}

3.2. Test

A partir du test suivant (markovAnts.txt) :

1
9 5
+-------+
|.......|
|....A..|
|.......|
+-------+

Le programme fait une moyenne du temps de sortie de la colonie et affiche :

6.9

4. Comparaison avec une autre solution

A partir de cette solution externe :

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

#define BEFORE(__time)  while((double)clock()<__time*CLOCKS_PER_SEC)

int n,m;
int sx=-1,sy;
int step;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
int walk(int x,int y){
    int t=0;
    while(x>0&&x+1<n&&y>0&&y+1<m){
        int d=rand()%4;
        x+=dx[d]*step;
        y+=dy[d]*step;
        ++t;
    }
    return t;
}
int main()
{
    srand(time(0));
    scanf("%d", &step);
    scanf("%d%d", &m, &n); fgetc(stdin);
    for (int i = 0; i < n; i++) {
        char a[32];
        scanf("%[^\n]", a); fgetc(stdin);
        if(sx==-1)for(int j=0;j<m;++j)if(a[j]=='A'){
            sx=i;
            sy=j;
        }
    }
    int t_s=0;
    int k;
    BEFORE(0.499){
        t_s+=walk(sx,sy);
        ++k;
    }
    fprintf(stderr,"%d %d %d %d\n",sx,sy,t_s,k);
    printf("%.1f",(double)t_s/k);
    return 0;
}

Cette solution propose elle aussi un calcul de moyenne, mais utilise une boucle while pour déplacer la fourmi.
Cette solution calcule la moyenne en un temps constant et n’utilise pas un nombre de simulation déjà fixé.

5. Bilan

Après avoir analyser le problème, je l’ai trouvé plutôt simple à résoudre et je n’ai pas rencontré de difficultés.