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.
trouver_suite(ligne, nl) qui renvoie la liste des indices des éléments recherchés formant une suite de longueur nl dans une ligne.trouver_suite([0,0,1,1,1,1,0,1], 3) → [[2, 3, 4], [3, 4, 5]]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é :
transpose_coord(coord) qui renvoie les coordonnées coord (tuple (ligne, colonne)) transposées.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.
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.decale_droite(t) qui fait la même chose vers la droite.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 :
trouver_align(tableau, nl) qui renvoie tous les alignements de nl éléments.
