Des chemins dans une grille )D;éfi Turing, problème 23)

Bonjour,

Je me suis inscrit sur le site Défi Turing et je suis confronté à un problème. Étant donné ma cécité, je ne peux pas toujours tout percevoir d’un problème.

Par exemple, dans le problème 23, il semble y avoir une erreur dans l’énoncé. Voici cet énoncé:

Problème 23 Des chemins dans une grille À partir du coin supérieur gauche d’une grille 2x2, il y a 6 chemins jusqu’au coin inférieur droit, en se déplaçant uniquement vers la droite ou vers lebas. Combien y a-t-il de tels chemins dans une grille 30x20 ?

Voici le lien vers cet énoncé:

Des chemins dans une grille.

Selon moi, une grille 2 x 2 ne contient que 2 chemins possibles, pas 6.

1 2
3 4

Soient 1 > 2 > 4 ou 1 > 3 > 4.

Les chemins 1 > 2 > 3 > 4 et 1 > 3 > 2 > 4 sont interdits suivant la règle.

Ce problème se résout facilement par programmation dynamique. En effet, on place des 1 sur la dernière ligne et la dernière colonne car il n’y a qu’une façon de se déplacer pour ces positions. La dernière case en bas à droite pourrait contenir n’importe quoi.

En partant de l’avant dernière ligne et l’avant dernière colonne, on fait la somme de la position sur la ligne suivante et la colonne suivante. On remonte ainsi jusqu’au début en haut haut à gauche. La solution se trouve sur la case du coin en haut et à gauche.

Voici une illustration pour une grille 4 x 4:

 0  0  0  1         0  0  0  1         0  0  0  1        20 10  4  1
 0  0  0  1         0  0  0  1        10  6  3  1        10  6  3  1
 0  0  0  1         4  3  2  1         4  3  2  1         4  3  2  1
 1  1  1  0         1  1  1  0         1  1  1  0         1  1  1  0

Puisqu’on n’utilise plus les lignes précédentes, on peut tout accumuler sur une seule ligne (ou une seule colonne).

Voici le code que j’ai soumis et qui a été refusé par Défi Turing:

nl, nc = 20, 30
lignes = [1] * nc
for l in range(nl-2, -1, -1):
    for c in range(nc-2, -1, -1):
        lignes[c] += lignes[c+1]
print(lignes[0])

Je ne peux pas rejoindre l’auteur du site Défi Turing.

Quelqu’un a une idée du problème?

Merci pour toute aide.

Merci Adri1.

Je viens de l’essayer et j’ai obtenu le bon résultat avec 21 x 31 arêtes.

Comme quoi il faut bien lire la question, et surtout savoir l’interpréter.

Le site Défi Turing nous donne souvent ce genre de colle.

Effectivement, j’avais remarqué que les termes ressemblaient aux coefficients du binome (a+b)**2 mais je n’en étais pas certain.

Je ne me rappelais pas de la fonction math.comb(). J’utilise ma propre fonction récursive qui est sans doute moins rapide. En voici un exemple:

>>> C = lambda n, k: 1 if k <= 0 else n * C(n-1, k-1) // k 
>>> C(6,3)
20
>>> C(4,2)
6
>>> C(21+31, (21+31)//2)
495918532948104
>>> 

C’est la même valeur que mon programme a trouvé.

Euh… Ta définition de C est correcte, mais C(21+31, (21+31)//2) n’est pas la réponse attendue (et dépasse d’un ordre de grandeur!). C(20 + 30, 20) est la réponse attendue ici, et est bien la valeur donnée par ton programme précédent qui construit le triangle de Pascal.

Voici ce que donne le problème 23 du site Défi Turing:

Vous avez déjà donné la bonne réponse : 47129212243960

Je vois que je n’avais pas les bons paramètres.

Justement, j’ai retrouvé le code pour générer les lignes du triangle de Pascal:

P = []
for n in range(1, 10):
    P.append(1)
    for j in range(n-1, 0, -1):
        P[j] += P[j-1]
    print(*P)

Ici, je prend le terme précédent au lieu du suivant. C’est sans doute ce qui m’a induit en erreur pour le problème 23.

Voici ce que ça donne:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

En regardant mon résultat, je m’aperçois qu’il ne s’agit pas de (a+b)**2 mais de (a+b)**n.

Le second terme donne la puissance en question (0 pour la première ligne).