Recherche d'un motif dans une grille Python [duplicate]

Question

J'ai généré au hasard une grille contenant 0 et 1:

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

Comment puis-je parcourir la grille pour trouver le plus grand cluster de 1 , qui est égal ou supérieur à 4 éléments (sur la ligne et la colonne)?

Je suppose que je dois garder un compte de chaque cluster trouvé lors de l'itération et de ses plus de 4 éléments, enregistrer et compter dans une liste, puis trouver le plus grand nombre.

Le problème est que je ne peux pas comprendre comment le faire sur les lignes et les colonnes et enregistrer le décompte. J'ai parcouru la grille mais je ne sais pas comment déplacer plus de deux lignes.

Par exemple, dans l'exemple ci-dessus, le plus grand cluster est 8. Il existe d'autres clusters dans la grille, mais ils ont 4 éléments:

AA 0 0 0 1 0 1
A A 1 0 1 1 1 1
1 0 0 0 1 0 1 1
0 0 1 0 1 0 1 1
1 1 BB 0 0 1 1
0 0 BB 1 1 1 0
0 1 0 0 1 0 1 1

Le code que j'ai essayé:

rectcount = []
for row in range(len(grid)):
    for num in range(len(grid[row])):

    # count = 0
        try:

            # if grid[row][num] == 1:
                # if grid[row][num] == grid[row][num + 1] == grid[row + 1][num] == grid[row + 1][num + 1]:
                    # count += 1

            if grid[row][num] == grid[row][num + 1]:
                if grid[row + 1][num] == grid[row][num + 1]:
                    count += 1

                # if grid[row][num] == grid[row][num + 1] and grid[row][num] == grid[row + 1][num]:
                    # count += 1
                else:
                    count = 0

            if grid[row][num] == grid[row + 1][num]:
                count += 1
        except:
            pass

Answer 1

J'ai implémenté trois algorithmes.

Le premier algorithme est Simple, en utilisant l'approche la plus simple des boucles imbriquées, il a une O(N^5) complexité temporelle (où se Ntrouve un côté de la grille d'entrée, 10dans notre cas), car nos entrées de taille 10x10temps de O(10^5)est tout à fait correcte. L'identifiant de l'algo dans le code est algo = 0. Si vous voulez juste voir cet algorithme passer à la ligne à l' ------ Simple Algorithmintérieur du code.

Le deuxième algorithme est Advanced, en utilisant l' approche de programmation dynamique , sa complexité O(N^3)est beaucoup plus rapide que le premier algorithme. L'identifiant de l'algo dans le code est algo = 1. Aller à la ligne à l' ------- Advanced Algorithmintérieur du code.

Troisième algorithme Simple-ListCompj'ai mis juste pour le plaisir, il est presque même comme Simple, même O(N^5)complexité, mais en utilisant la liste de Python au lieu de compréhensions des boucles régulières, c'est pourquoi il est plus court, aussi un peu plus lent , car ne pas utiliser certaines optimisations. L'identifiant de l'algo dans le code est algo = 2. Aller à la ligne à l' ------- Simple-ListComp Algorithmintérieur du code pour voir l'algo.

Le reste du code, outre les algorithmes, implémente la vérification de l'exactitude des résultats (double-vérification entre les algorithmes), l'impression des résultats, la production d'entrées de texte. Le code est divisé en fonction de tâche de résolution solve()et fonction de test test(). solve()function a de nombreux arguments pour permettre la configuration du comportement de la fonction.

Toutes les principales lignes de code sont documentées par des commentaires, lisez-les pour apprendre à utiliser le code. Fondamentalement, si la svariable contient du texte multiligne avec des éléments de grille, comme dans votre question, vous venez de l'exécuter solve(s, text = True)et cela résoudra la tâche et imprimera les résultats. Vous pouvez également choisir l'algorithme parmi deux versions (0 (Simple) et 1 (Advanced) et 2 (Simple-ListComp)) en donnant les arguments suivants pour résoudre la fonction algo = 0, check = False(ici 0 pour l'algo 0). Regardez le test()corps de la fonction pour voir l'exemple le plus simple d'utilisation.

Les algorithmes de sortie à la console par défaut , tous les groupes, du plus grand au plus petit, le plus grand est signifiés par le .symbole, le reste par B, C, D, ..., Zsymboles. Vous pouvez définir l'argument show_non_max = Falsedans la fonction de résolution si vous souhaitez que seul le premier (le plus grand) cluster soit affiché.

Je vais expliquer l'algorithme simple:

1. Fondamentalement, ce que fait l'algorithme - il recherche tous les 1srectangles inclinés possibles et stocke des informations sur le maximum d'entre eux dans maun tableau 2D. Top-leftle point d'un tel rectangle est (i, j), top-right- (i, k), bottom-left- (l, j + angle_offset), bottom-right- (l, k + angle_offset), les 4 coins, c'est pourquoi nous avons tant de boucles.
2. Dans les boucles externes de deux i(lignes), j(colonnes) que nous itérons sur toute la grille, cette (i, j)position sera un top-leftpoint de 1srectangle, nous devons parcourir toute la grille car tous les 1srectangles possibles peuvent avoir top-leftà n'importe quel (row, col)point de la grille entière. Au début de la jboucle, nous vérifions que la grille à la (i, j)position doit toujours contenir 1car à l'intérieur des boucles, nous recherchons tous les rectangles avec 1sseulement.
3. kloop parcourt toutes les top-rightpositions possibles (i, k)du 1srectangle. Nous devrions sortir de la boucle si (i, k)égale à 0car il n'y a aucun intérêt à s'étendre kplus à droite car un tel rectangle contiendra toujours 0.
4. Dans les boucles précédentes, nous avons fixé top-leftet les top-rightcoins du rectangle. Nous devons maintenant rechercher deux coins inférieurs. Pour cela, nous devons étendre le rectangle vers le bas à différents angles jusqu'à ce que nous atteignions le premier 0.
5. offloop essaie d'étendre le rectangle vers le bas à tous les angles possibles ( 0(vertical droit), +1( 45degrés décalés vers la droite de haut en bas), -1( -45degrés)), offest fondamentalement un tel nombre qui grid[y][x]est "au-dessus" (correspond à par Y) grid[y + 1][x + off].
6. lessaie d'étendre le rectangle vers le bas (dans la Ydirection) à différents angles off. Il est étendu jusqu'au premier 0parce qu'il ne peut pas être étendu plus loin (car chaque rectangle de ce type contiendra déjà 0).
7. À l'intérieur de la lboucle, il y a une if grid[l][max(0, j + off * (l - i)) : min(k + 1 + off * (l - i), c)] != ones[:k - j + 1]:condition, cela ifvise essentiellement à vérifier que la dernière ligne de rectangle contient tout, 1sinon cela ifse détache de la boucle. Cette condition compare deux listtranches pour la non-égalité. La dernière ligne de rectangle s'étend du point (l, j + angle_offset)(expression max(0, j + off * (l - i)), max-limited to be 0 <= X) au point (l, k + angle_offset)(expression min(k + 1 + off * (l - i), c), min-limited to be X < c).
8. À l'intérieur de la lboucle, il y a d'autres lignes, ry, rx = l, k + off * (l - i)calcule le bottom-rightpoint du rectangle (ry, rx)qui est (l, k + angle_offset), cette (ry, rx)position est utilisée pour stocker le maximum trouvé à l'intérieur du matableau, ce tableau stocke tous les rectangles maximaux trouvés, ma[ry][rx]contient des informations sur le rectangle qui a bottom-rightau point (ry, rx).
9. rv = (l + 1 - i, k + 1 - j, off)line calcule un nouveau candidat possible pour l' ma[ry][rx]entrée du tableau, possible car ma[ry][rx]mis à jour uniquement si le nouveau candidat a une plus grande surface de 1s. Ici, la rv[0]valeur à l'intérieur du rvtuple contient un heighttel rectangle, rv[1]contient un widthtel rectangle ( widthégale à la longueur de la rangée inférieure du rectangle), rv[2]contient l'angle d'un tel rectangle.
10. La condition if rv[0] * rv[1] > ma[ry][rx][0] * ma[ry][rx][1]:et son corps vérifient simplement si la rvzone est plus grande que le maximum actuel à l'intérieur du tableau ma[ry][rx]et si elle est plus grande, cette entrée du tableau est mise à jour ( ma[ry][rx] = rv). Je rappellerai que ma[ry][rx]contient des informations (width, height, angle)sur le rectangle de zone maximale actuellement trouvé qui a un bottom-rightpoint sur (ry, rx)et qui a ces derniers width, heightet angle.
11. Terminé! Après l'exécution de l'algorithme, le tableau macontient des informations sur tous les rectangles (clusters) à angle maximal de la zone 1safin que tous les clusters puissent être restaurés et imprimés ultérieurement sur la console. Le plus grand de tous ces 1sclusters est égal à certains rv0 = ma[ry0][rx0], il suffit de parcourir une fois tous les éléments de maet de trouver un tel point (ry0, rx0)pour que ma[ry0][rx0][0] * ma[ry0][rx0][1](aire) soit maximale. Ensuite, le plus grand cluster aura un bottom-rightpoint (ry0, rx0), un bottom-leftpoint (ry0, rx0 - rv0[1] + 1), un top-rightpoint (ry0 - rv0[0] + 1, rx0 - rv0[2] * (rv0[0] - 1)), un top-leftpoint (ry0 - rv0[0] + 1, rx0 - rv0[1] + 1 - rv0[2] * (rv0[0] - 1))(ici, il rv0[2] * (rv0[0] - 1)n'y a que le décalage d'angle, c'est-à-dire le décalage de la première ligne par Xrapport à la dernière ligne du rectangle).

Essayez-le en ligne!

# ----------------- Main function solving task -----------------

def solve(
    grid, *,
    algo = 1, # Choose algorithm, 0 - Simple, 1 - Advanced, 2 - Simple-ListComp
    check = True, # If True run all algorithms and check that they produce same results, otherwise run just chosen algorithm without checking
    text = False, # If true then grid is a multi-line text (string) having grid elements separated by spaces
    print_ = True, # Print results to console
    show_non_max = True, # When printing if to show all clusters, not just largest, as B, C, D, E... (chars from "cchars")
    cchars = ['.'] + [chr(ii) for ii in range(ord('B'), ord('Z') + 1)], # Clusters-chars, these chars are used to show clusters from largest to smallest
    one = None, # Value of "one" inside grid array, e.g. if you have grid with chars then one may be equal to "1" string. Defaults to 1 (for non-text) or "1" (for text).
    offs = [0, +1, -1], # All offsets (angles) that need to be checked, "off" is such that grid[i + 1][j + off] corresponds to next row of grid[i][j]
    debug = False, # If True, extra debug info is printed
):
    # Preparing
    
    assert algo in [0, 1, 2], algo
    if text:
        grid = [l.strip().split() for l in grid.splitlines() if l.strip()]
    if one is None:
        one = 1 if not text else '1'
    r, c = len(grid), len(grid[0])
    sgrid = '\n'.join([''.join([str(grid[ii][jj]) for jj in range(c)]) for ii in range(r)])
    mas, ones = [], [one] * max(c, r)
    
    # ----------------- Simple Algorithm, O(N^5) Complexity -----------------
        
    if algo == 0 or check:
        ma = [[(0, 0, 0) for jj in range(c)] for ii in range(r)] # Array containing maximal answers, Lower-Right corners
        
        for i in range(r):
            for j in range(c):
                if grid[i][j] != one:
                    continue
                for k in range(j + 1, c): # Ensure at least 2 ones along X
                    if grid[i][k] != one:
                        break
                    for off in offs:
                        for l in range(i + 1, r): # Ensure at least 2 ones along Y
                            if grid[l][max(0, j + off * (l - i)) : min(k + 1 + off * (l - i), c)] != ones[:k - j + 1]:
                                l -= 1
                                break
                            ry, rx = l, k + off * (l - i)
                            rv = (l + 1 - i, k + 1 - j, off)
                            if rv[0] * rv[1] > ma[ry][rx][0] * ma[ry][rx][1]:
                                ma[ry][rx] = rv
                                
        mas.append(ma)
        ma = None
                    
    # ----------------- Advanced Algorithm using Dynamic Programming, O(N^3) Complexity -----------------

    if algo == 1 or check:
        ma = [[(0, 0, 0) for jj in range(c)] for ii in range(r)] # Array containing maximal answers, Lower-Right corners
        
        for off in offs:
            d = [[(0, 0, 0) for jj in range(c)] for ii in range(c)]
            for i in range(r):
                f, d_ = 0, [[(0, 0, 0) for jj in range(c)] for ii in range(c)]
                for j in range(c):
                    if grid[i][j] != one:
                        f = j + 1
                        continue
                    if f >= j:
                        # Check that we have at least 2 ones along X
                        continue
                    df = [(0, 0, 0) for ii in range(c)]
                    for k in range(j, -1, -1):
                        t0 = d[j - off][max(0, k - off)] if 0 <= j - off < c and k - off < c else (0, 0, 0)
                        if k >= f:
                            t1 = (t0[0] + 1, t0[1], off) if t0 != (0, 0, 0) else (0, 0, 0)
                            t2 = (1, j - k + 1, off)
                            t0 = t1 if t1[0] * t1[1] >= t2[0] * t2[1] else t2
                            
                            # Ensure that we have at least 2 ones along Y
                            t3 = t1 if t1[0] > 1 else (0, 0, 0)
                            if k < j and t3[0] * t3[1] < df[k + 1][0] * df[k + 1][1]:
                                t3 = df[k + 1]
                            df[k] = t3
                        else:
                            t0 = d_[j][k + 1]
                        if k < j and t0[0] * t0[1] < d_[j][k + 1][0] * d_[j][k + 1][1]:
                            t0 = d_[j][k + 1]
                        d_[j][k] = t0
                    if ma[i][j][0] * ma[i][j][1] < df[f][0] * df[f][1]:
                        ma[i][j] = df[f]
                d = d_
                
        mas.append(ma)
        ma = None
        
    # ----------------- Simple-ListComp Algorithm using List Comprehension, O(N^5) Complexity -----------------
        
    if algo == 2 or check:
        ma = [
            [
                max([(0, 0, 0)] + [
                    (h, w, off)
                    for h in range(2, i + 2)
                        for w in range(2, j + 2)
                            for off in offs
                    if all(
                        cr[
                            max(0, j + 1 - w - off * (h - 1 - icr)) :
                            max(0, j + 1 - off * (h - 1 - icr))
                        ] == ones[:w]
                        for icr, cr in enumerate(grid[max(0, i + 1 - h) : i + 1])
                    )
                ], key = lambda e: e[0] * e[1])
                for j in range(c)
            ]
            for i in range(r)
        ]
        mas.append(ma)
        ma = None
    
    # ----------------- Checking Correctness and Printing Results -----------------

    if check:
        # Check that we have same answers for all algorithms
        masx = [[[cma[ii][jj][0] * cma[ii][jj][1] for jj in range(c)] for ii in range(r)] for cma in mas]
        assert all([masx[0] == e for e in masx[1:]]), 'Maximums of algorithms differ!\n\n' + sgrid + '\n\n' + (
            '\n\n'.join(['\n'.join([' '.join([str(e1).rjust(2) for e1 in e0]) for e0 in cma]) for cma in masx])
        )

    ma = mas[0 if not check else algo]

    if print_:
        cchars = ['.'] + [chr(ii) for ii in range(ord('B'), ord('Z') + 1)] # These chars are used to show clusters from largest to smallest
        res = [[grid[ii][jj] for jj in range(c)] for ii in range(r)]
        mac = [[ma[ii][jj] for jj in range(c)] for ii in range(r)]
        processed = set()
        sid = 0
        for it in range(r * c):
            sma = sorted(
                [(mac[ii][jj] or (0, 0, 0)) + (ii, jj) for ii in range(r) for jj in range(c) if (ii, jj) not in processed],
                key = lambda e: e[0] * e[1], reverse = True
            )
            if len(sma) == 0 or sma[0][0] * sma[0][1] <= 0:
                break
            maxv = sma[0]
            if it == 0:
                maxvf = maxv
            processed.add((maxv[3], maxv[4]))
            show = True
            for trial in [True, False]:
                for i in range(maxv[3] - maxv[0] + 1, maxv[3] + 1):
                    for j in range(maxv[4] - maxv[1] + 1 - (maxv[3] - i) * maxv[2], maxv[4] + 1 - (maxv[3] - i) * maxv[2]):
                        if trial:
                            if mac[i][j] is None:
                                show = False
                                break
                        elif show:
                            res[i][j] = cchars[sid]
                            mac[i][j] = None
            if show:
                sid += 1
            if not show_non_max and it == 0:
                break
        res = '\n'.join([''.join([str(res[ii][jj]) for jj in range(c)]) for ii in range(r)])
        print(
            'Max:\nArea: ', maxvf[0] * maxvf[1], '\nSize Row,Col: ', (maxvf[0], maxvf[1]),
            '\nLowerRight Row,Col: ', (maxvf[3], maxvf[4]), '\nAngle: ', ("-1", " 0", "+1")[maxvf[2] + 1], '\n', sep = ''
        )
        print(res)
        if debug:
            # Print all computed maximums, for debug purposes
            for cma in [ma, mac]:
                print('\n' + '\n'.join([' '.join([f'({e0[0]}, {e0[1]}, {("-1", " 0", "+1")[e0[2] + 1]})' for e0_ in e for e0 in (e0_ or ('-', '-', 0),)]) for e in cma]))
        print(end = '-' * 28 + '\n')
    
    return ma

# ----------------- Testing -----------------

def test():
    # Iterating over text inputs or other ways of producing inputs
    for s in [
        """
        1 1 0 0 0 1 0 1
        1 1 1 0 1 1 1 1
        1 0 0 0 1 0 1 1
        0 0 1 0 1 0 1 1
        1 1 1 1 0 0 1 1
        0 0 1 1 1 1 1 0
        0 1 0 0 1 0 1 1
        """,
        """
        1 0 1 1 0 1 0 0
        0 1 1 0 1 0 0 1
        1 1 0 0 0 0 0 1
        0 1 1 1 0 1 0 1
        0 1 1 1 1 0 1 1
        1 1 0 0 0 1 0 0
        0 1 1 1 0 1 0 1
        """,
        """
        0 1 1 0 1 0 1 1
        0 0 1 1 0 0 0 1
        0 0 0 1 1 0 1 0
        1 1 0 0 1 1 1 0
        0 1 1 0 0 1 1 0
        0 0 1 0 1 0 1 1
        1 0 0 1 0 0 0 0
        0 1 1 0 1 1 0 0
        """
    ]:
        solve(s, text = True)

if __name__ == '__main__':
    test()

Production:

Max:
Area: 8
Size Row,Col: (4, 2)
LowerRight Row,Col: (4, 7)
Angle:  0

CC000101
CC1011..
100010..
001010..
1BBB00..
00BBBDD0
010010DD
----------------------------
Max:
Area: 6
Size Row,Col: (3, 2)
LowerRight Row,Col: (2, 1)
Angle: -1

10..0100
0..01001
..000001
0BBB0101
0BBB1011
CC000100
0CC10101
----------------------------
Max:
Area: 12
Size Row,Col: (6, 2)
LowerRight Row,Col: (5, 7)
Angle: +1

0..01011
00..0001
000..010
BB00..10
0BB00..0
001010..
10010000
01101100
----------------------------