Trovare un pattern in una griglia Python [duplicato]

Question

Ho una griglia generata casualmente contenente 0 e 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

Come posso scorrere la griglia per trovare il cluster più grande di 1 , che è uguale o maggiore di 4 elementi (su riga e colonna)?

Presumo di dover tenere un conteggio di ogni cluster trovato durante l'iterazione e quelli sono più di 4 elementi, registrare e contare in un elenco e quindi trovare il numero più grande.

Il problema è che non riesco a capire come farlo su righe e colonne e registrare il conteggio. Ho ripetuto la griglia ma non sono sicuro di come muovermi oltre due righe.

Ad esempio, nell'esempio precedente, il cluster più grande è 8. Ci sono altri cluster nella griglia, ma hanno 4 elementi:

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

Il codice che ho provato:

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

Ho implementato tre algoritmi.

Il primo algoritmo è Simple, utilizzando l'approccio più semplice di cicli annidati, ha una O(N^5) complessità temporale (dove Nè un lato della griglia di input, nel 10nostro caso), perché i nostri input di dimensione 10x10time of O(10^5)sono abbastanza buoni. L'ID algoritmo nel codice è algo = 0. Se vuoi solo vedere questo algoritmo, salta alla riga ------ Simple Algorithmall'interno del codice.

Il secondo algoritmo è Advanced, utilizzando l' approccio della programmazione dinamica , la sua complessità O(N^3)è molto più veloce del primo algoritmo. L'ID algoritmo nel codice è algo = 1. Passa alla riga ------- Advanced Algorithmall'interno del codice.

Terzo algoritmo che Simple-ListCompho implementato solo per divertimento, è quasi uguale Simple, stessa O(N^5)complessità, ma usando le comprensioni delle liste di Python invece dei cicli regolari, ecco perché è più breve, anche un po 'più lento perché non utilizza alcune ottimizzazioni. L'ID algoritmo nel codice è algo = 2. Passa alla riga ------- Simple-ListComp Algorithmall'interno del codice per visualizzare l'algo.

Il resto del codice, oltre agli algoritmi, implementa il controllo della correttezza dei risultati (doppio controllo tra algoritmi), la stampa dei risultati, la produzione di input di testo. Il codice è suddiviso in funzione di attività di risoluzione solve()e funzione di test test(). solve()funzione ha molti argomenti per consentire la configurazione del comportamento della funzione.

Tutte le linee di codice principali sono documentate da commenti, leggili per imparare a usare il codice. Fondamentalmente se la svariabile contiene testo su più righe con elementi della griglia, come nella tua domanda, corri solve(s, text = True)e risolverà l'attività e stamperà i risultati. Inoltre puoi scegliere l'algoritmo tra due versioni (0 (Semplice) e 1 (Avanzata) e 2 (Simple-ListComp)) fornendo gli argomenti successivi per risolvere la funzione algo = 0, check = False(qui 0 per algo 0). Guarda il test()corpo della funzione per vedere il più semplice esempio di utilizzo.

Algoritmi di uscita per console di default tutti i cluster, dal più grande al più piccolo, più grande è significata dal .simbolo, il resto da B, C, D, ..., Zsimboli. È possibile impostare l'argomento show_non_max = Falsenella funzione di risoluzione se si desidera visualizzare solo il primo cluster (più grande).

Spiegherò l'algoritmo semplice:

1. Fondamentalmente ciò che fa l'algoritmo: cerca in tutti i possibili 1srettangoli angolati e memorizza le informazioni sul loro massimo in un maarray 2D. Top-leftpunto di tale rettangolo è (i, j), top-right- (i, k), bottom-left- (l, j + angle_offset), bottom-right- (l, k + angle_offset), tutti e 4 gli angoli, ecco perché abbiamo così tanti loop.
2. Nei due cicli esterni i(riga), j(colonna) iteriamo su tutta la griglia, questa (i, j)posizione sarà il top-leftpunto del 1srettangolo, dobbiamo iterare l'intera griglia perché tutti i possibili 1srettangoli possono avere top-leftin qualsiasi (row, col)punto dell'intera griglia. All'inizio del jciclo controlliamo che la griglia in (i, j)posizione debba sempre contenere 1perché all'interno dei cicli cerchiamo tutto il rettangolo con 1ssolo.
3. kloop itera attraverso tutte le possibili top-rightposizioni (i, k)del 1srettangolo. Dovremmo interrompere il ciclo se è (i, k)uguale a 0perché non ha senso estendersi kulteriormente a destra perché tale rettangolo conterrà sempre 0.
4. Nei cicli precedenti abbiamo fissato top-lefte gli top-rightangoli del rettangolo. Ora dobbiamo cercare due angoli inferiori. Per questo dobbiamo estendere il rettangolo verso il basso con angoli diversi fino a raggiungere il primo 0.
5. offloop cerca di estendere il rettangolo verso il basso a tutti gli angoli possibili ( 0(verticale diritta), +1( 45gradi spostati a destra dall'alto verso il basso), -1( -45gradi)), offfondamentalmente è tale numero che grid[y][x]è "sopra" (corrisponde a da Y) grid[y + 1][x + off].
6. lcerca di estendere il rettangolo verso il basso (in Ydirezione) con angoli diversi off. Viene esteso fino all'inizio 0perché non può essere esteso ulteriormente (perché ogni rettangolo di questo tipo conterrà già 0).
7. All'interno del lciclo c'è la if grid[l][max(0, j + off * (l - i)) : min(k + 1 + off * (l - i), c)] != ones[:k - j + 1]:condizione, fondamentalmente questo ha lo ifscopo di controllare che l'ultima riga del rettangolo contenga tutto 1se non questo si ifinterrompe dal ciclo. Questa condizione confronta due listsezioni per non uguaglianza. L'ultima riga del rettangolo si estende da un punto (l, j + angle_offset)(espressione max(0, j + off * (l - i)), max-limited to be 0 <= X) al punto (l, k + angle_offset)(espressione min(k + 1 + off * (l - i), c), min-limited to be X < c).
8. All'interno del lciclo ci sono altre linee, ry, rx = l, k + off * (l - i)calcola il bottom-rightpunto del rettangolo (ry, rx)che è (l, k + angle_offset), questa (ry, rx)posizione viene utilizzata per memorizzare il massimo trovato all'interno madell'array, questo array memorizza tutti i massimi rettangoli trovati, ma[ry][rx]contiene informazioni sul rettangolo che ha un bottom-rightpunto (ry, rx).
9. rv = (l + 1 - i, k + 1 - j, off)riga calcola un nuovo possibile candidato per l' ma[ry][rx]inserimento dell'array, possibile perché ma[ry][rx]viene aggiornato solo se il nuovo candidato ha un'area maggiore di 1s. Qui il rv[0]valore all'interno della rvtupla contiene heightdi tale rettangolo, rv[1]contiene widthdi tale rettangolo ( widthuguale alla lunghezza della riga inferiore del rettangolo), rv[2]contiene l'angolo di tale rettangolo.
10. Condizione if rv[0] * rv[1] > ma[ry][rx][0] * ma[ry][rx][1]:e il suo corpo controllano solo se l' rvarea è più grande del massimo corrente all'interno dell'array ma[ry][rx]e se è più grande, questa voce dell'array viene aggiornata ( ma[ry][rx] = rv). Ricorderò che ma[ry][rx]contiene informazioni (width, height, angle)sul rettangolo di area massima trovato corrente che ha bottom-rightpunto a (ry, rx)e che ha questi width, heighte angle.
11. Fatto! Dopo l'esecuzione dell'algoritmo, l'array macontiene informazioni su tutti i rettangoli angolati (cluster) di area massima in 1smodo che tutti i cluster possano essere ripristinati e stampati successivamente sulla console. Il più grande di tutti questi 1scluster è uguale ad alcuni rv0 = ma[ry0][rx0], basta iterare una volta su tutti gli elementi di mae trovare tale punto in (ry0, rx0)modo che ma[ry0][rx0][0] * ma[ry0][rx0][1](area) sia massima. Quindi il cluster più grande avrà bottom-rightpunto (ry0, rx0), bottom-leftpunto (ry0, rx0 - rv0[1] + 1), top-rightpunto (ry0 - rv0[0] + 1, rx0 - rv0[2] * (rv0[0] - 1)), top-leftpunto (ry0 - rv0[0] + 1, rx0 - rv0[1] + 1 - rv0[2] * (rv0[0] - 1))(qui rv0[2] * (rv0[0] - 1)è solo l'offset dell'angolo, cioè quanto spostato è la prima riga Xrispetto all'ultima riga del rettangolo).

Provalo online!

# ----------------- 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()

Produzione:

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
----------------------------