Alignements

L’objectif de l’exercice est de trouver tous les alignements de \(n\) éléments dans un tableau de dimension \(nl\) lignes par \(nc\) colonnes.

Résoudre un tel problème est notamment très utile pour évaluer l’état d’une grille dans des jeux tels que le morpion, ou puissance 4.

Exemple sur une grille de Puissance 4 :

Dans la suite, nous décidons de rechercher les alignements de \(1\) dans un tableau de \(0\).

 

Implémentation du tableau

Pour implémenter un tableau, on utilise une liste de listes. En python, cela donne :

T = [[0, 1, 0, 1],
[0, 1, 1, 0],
[0, 1, 0, 1],
[0, 0, 0, 0],
]

 

Recherche d’alignements horizontaux

Rechercher un alignement horizontal dans un tableau revient à rechercher un alignement dans chacune de ses lignes.

Écrire une fonction trouver_suite(ligne, nl) qui renvoie la liste des indices des éléments recherchés formant une suite de longueur nl dans une ligne.
exemple : trouver_suite([0,0,1,1,1,1,0,1], 3)[[2, 3, 4], [3, 4, 5]]
Utiliser cette fonction pour écrire une fonction trouver_align_H(tableau, nl) qui renvoie la liste des coordonnées dans un tableau (tuple (ligne, colonne)) des éléments recherchés formant des alignements horizontaux de longueur nl .

exemple :

T = [[0, 1, 1, 1],
[0, 1, 1, 0],
[0, 1, 0, 1],
[1, 1, 1, 0]]
→ [[(0, 1), (0, 2), (0, 3)], [(3, 0), (3, 1), (3, 2)]]

 

 

Recherches dans les autres directions

Direction verticale

Rechercher un alignement dans la direction verticale d’un tableau
revient à rechercher un alignement horizontal dans son transposé :

Écrire une fonction transpose_coord(coord) qui renvoie les coordonnées coord (tuple (ligne, colonne)) transposées.
Écrire une fonction transpose(t) qui renvoie la version transposée d’un tableau t.

 

Directions diagonales

Rechercher un alignement dans une direction diagonale d’un tableau
revient à rechercher un alignement vertical dans un tableau dont les lignes sont décalées :

Remarque : on « comble » les extrémités des lignes avec des zéros.

Écrire une fonction decale_gauche(t) qui renvoie un tableau dont chaque ligne est décalée vers la gauche d’autant de colonnes que son rang dans le tableau t.
Écrire la fonction decale_droite(t) qui fait la même chose vers la droite.
Écrire deux fonctions decale_gauche_coord(coord, nl) et decale_gauche_coord(coord, nl) qui renvoie les coordonnées « réelles » d’une case d’un tableau de nl lignes à partir des coordonnées « décalées ».

 

Assemblage des fonctions pour obtenir l’ensemble des alignements :

Écrire une fonction trouver_align(tableau, nl) qui renvoie tous les alignements de nl éléments.

 


 

Vous aimerez aussi...

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

*

code