[Algorithmie] Descends les escaliers mais ne remonte jamais.

[Kiwazaru]

Énoncé:
On vous donne un tableau 2D X*Y dans lequel s'y trouve des 0 et des 1 qui ont les propriétés suivantes:
1 = Chemin
0 = Mur

Vous n'aurez le droit de parcourir le tableau dans 2 sens différents:
→ Vers la droite.
↓ Vers le bas.

On vous donne le tableau 2D suivant:

1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1

Combien de chemins existent-ils pour ce tableau ?

Solution:

La solution que j'ai utilisé a été la résolution par récursivité.
Le principe est simple, parcourir le tableau et vérifier successivement l'état des coordonnés [X+1;Y+1].
Dans le cas d'un double état positif (X+1 = 1 && Y+1 = 1) on appelle récursivement la fonction en lui passant comme paramètre la coordonnés suivante à suivre; Dans un premier temps X+1 puis au retour de cette fonction Y+1.

Code C :


/*

DEFINIR STRUCTURE = var_array
    TABLEAU (Multidimensionnel): LIGNE(S) = 8, COLONNE(S) = 11
        X/Y 0 1 2 3 4 5 6 7 8 9 10
        0   1 1 1 1 1 1 1 1 1 1 1
        1    1 1 1 0 1 1 1 0 1 1 1
        2    1 1 1 1 1 1 1 1 1 1 1
        3    1 0 1 1 0 1 1 1 1 1 1
        4    1 1 1 1 1 1 1 1 1 1 1
        5    1 1 0 1 1 1 0 1 1 1 1
        6    1 1 1 1 1 1 1 1 1 1 1
        7    1 1 1 0 1 1 1 1 1 1 1
   
    ENTIER row_count = 0, line_count = 0, ret = 0
FIN STRUCTURE

DECLARER FONCTION = findArray => ARGUMENT(S) = ENTIER x, ENTIER y, POINTEUR STRUCTURE var_array -> struct_array

PROGRAMME PRINCIPAL
    APPELLER findArray => ARGUMENT(S) = ENTIER 0, ENTIER 0, ADRESSE STRUCTURE struct_array
    AFFICHER "Nombre de possibilités: [ENTIER ret]\n"
FIN PROGRAMME PRINCIPAL

FONCTION = findArray => ARGUMENT(S) = ENTIER x, ENTIER y, POINTEUR STRUCTURE struct_array
    TANT QUE ( y EST INFERIEUR A line_count ) => INCREMENTER y
        TANT QUE ( x EST INFERIEUR A row_count ) => INCREMENTER x
           
            SI ( x EST EGAL A row_count-1 ) ET ( y EST EGAL A line_count-1 ) ALORS
                INCREMENTER ret
                RETOURNER
            FIN SI
           
            SI ( array[y+1][x] EST EGAL A 1 ) ET ( array[y][x+1] EST EGAL A 1 ) ALORS
                APPELLER findArray => ARGUMENT(S) = ENTIER x+1, ENTIER y, STRUCTURE struct_array
                APPELLER findArray => ARGUMENT(S) = ENTIER x, ENTIER y+1, STRUCTURE struct_array
                RETOURNER
            FIN SI
           
            SI ( array[y+1][x] EST EGAL A 0 ) ET ( array[y][x+1] EST EGAL A 0 ) ALORS
                RETOURNER
            FIN SI
           
            SI ( y EST EGAL A line_count-1 ) ET ( array[y][x+1] EST EGAL A 0 ) ALORS
                RETOURNER
            FIN SI
           
            SI ( ( array[y][x+1] EST EGAL A 1 ) OU ( x EST EGAL A 6 ) ) ET ( array[y+1][x] EST EGAL A 1 ) ALORS
                INCREMENTER y
            FIN SI
        FIN TANT QUE
    FIN TANT QUE
FIN FONCTION
*/

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

typedef struct var_array var_array;
struct var_array
{
    char array[1024][1024]; // 1024 Bytes max for all dimensions (MAX: 1024*1024 table size)
    int column_count, line_count, ret; // limits
};

int findArray ( int x, int y, var_array* struct_array );
               
int main() {
    var_array struct_array = { {  { 1,1,1,1,1,1,1,1,1,1,1 },
                                  { 1,1,1,0,1,1,1,0,1,1,1 },
                                  { 1,1,1,1,1,1,1,1,1,1,1 },
                                  { 1,0,1,1,0,1,1,1,1,1,1 },
                                  { 1,1,1,1,1,1,1,1,1,1,1 },
                                  { 1,1,0,1,1,1,0,1,1,1,1 },
                                  { 1,1,1,1,1,1,1,1,1,1,1 },
                                  { 1,1,1,0,1,1,1,1,1,1,1 } },
                                  11, // 11 columns
                                  8, // 8 lines
                                  0 // 0 possibilities
                             }; // Define values of structure
    findArray ( 0,0,&struct_array ); // call the first findArray();
    printf("P = %d\n", struct_array.ret); // print result
    return (0);    // end
   
}

int findArray ( int x, int y, var_array* struct_array ) {
   
    for ( y; y < struct_array->line_count; y++ ) { // travel all abscissa values
        for ( x; x < struct_array->column_count; x++ ) { // travel all ordinate values
           
            /*
                1  1
                1 (N)
            */
            if ( x == ( struct_array->column_count-1 ) && y == ( struct_array->line_count-1 ) ) {
                struct_array->ret++;
                return;
            }
           
            /*
                (1) 1
                 1  0
            */
            if ( struct_array->array[y+1][x] && struct_array->array[y][x+1] ) {
                findArray ( x+1,y,struct_array );
                findArray ( x,y+1,struct_array );
                return;    
            }
           
            /*
                (1) 0
                 0  1
            */
            if ( !struct_array->array[y+1][x] && !struct_array->array[y][x+1] ) {
                return;
            }
           
            /*
                (1) 0 1 1 1
                -----------
            */
            if ( y == ( struct_array->line_count-1 ) && !struct_array->array[y][x+1] ) {
                return;    
            }
           
            /*
                1 1 (1) |
                0 1  1  |
            */
            if ( ( !struct_array->array[y][x+1] || x == ( struct_array->column_count-1 ) ) && struct_array->array[y+1][x] ) {
                y++;
            }
           
        }
    }
   
}
 

Sortie:

Code :

P = 1218
Process returned 0 (0x0)   execution time : 0.020 s

[b0fh]

Chouettos !

Cela dit, on peut faire mieux: voici comment.

Cet algorithme marche sur tous les chemins possibles, puis incrémente un compteur a la fin de chaque chemin. Tu fais donc un nombre d'appels de fonction proportionnel au nombre de chemins multiplié par la longueur du chemin (qui est la même partout.) Pour une grille de taille NxN, il y a de l'ordre de C(2n,n) chemins, tu fais donc de l'ordre de N! appels de fonction.

Mais, une grande partie du travail est redondant. Quand tu explores le point (x,y), tu commences par marcher sur (x+1,y). Cette marche te conduit à marcher, d'abord sur tous les chemins partants de (x+2,y), ensuite ceux partant de (x+1,y+1). Ensuite, tu remontes, et tu explores (x,y+1), qui te conduit d'abord en (x+1,y+1), puis en (x,y+2). Mais, tu as déja exploré (x+1,y+1) dans la passe précédente ! Il suffirait de mémoizer le nombre intermédiaires de chemins, et il n'y aurait plus q'un appel de fonction par point, de l'ordre de N^2.

La différence n'est pas flagrante sur une aussi petite carte, mais elle deviendra vite colossale.

Aussi, je te propose l'algorithme suivant:

- Initialiser un tableau des comptes.
- Pour x de 0 à dernier_x, et pour y de 0 à dernier_y:
-- si x = 0 et y = 0: compte[x][y] = 1 et suivant
-- si (x,y) contient un mur: compte[x][y] = 0 et suivant
-- compte_horizontal = 0 si x == 0, cout[x-1][y] sinon;
-- compte_vertical = 0 si y == 0, cout[x][y-1] sinon;
-- compte[x][y] = compte_horizontal + compte_vertical;
- retourner compte[dernier_x][dernier_y]

Voici une implémentation vite faite en Haskell:

Code :

import Data.Array
import Data.Set

dimensions = ((1,1),(11,8))

murs = fromList [
    (4,2), (8,2),
    (2,4), (5,4),
    (3,6), (7,6),
    (4,8) ]


tableCouts = array dimensions [ ((x,y), cout (x-1) y + cout x (y-1)) | (x,y) <- range dimensions ]

cout 1 1 = 1
cout 0 _ = 0
cout _ 0 = 0
cout x y | (x,y) `member` murs = 0
         | otherwise = tableCouts ! (x,y)

et le résultat (il va falloir comprendre pourquoi ça diverge.. le problème est mal défini, mais je suppose que par "chemin" tu entends un chemin qui commence au coin supérieur gauche et finit au coin inférieur droit ?):

Code :

*Main> cout 11 8
3239

EDIT: j'ai trouvé un bug dans ton code.

Lorsqu'en un point, le seul chemin possible est en bas, la dernière condition de ta boucle (celle qui fait y++) se déclenche; mais immédiatement après, le x++ de la boucle interne se déclenche, ce qui fait
que tu prends un pas en diagonale au lieu de suivre le chemin vers le bas.

Lorsque je change le y++ en y++;x--; (hack dégeulasse, nous en conviendront), j'obtiens le même résultat avec les deux algos.

[Kiwazaru]

J'me disais bien qu'il y avait un problème avec le y++, thanks