Suchen eines Musters in einem Grid Python [Duplikat]

Question

Ich habe zufällig ein Raster mit 0 und 1 generiert:

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

Wie kann ich durch das Raster iterieren, um den größten Cluster von Einsen zu finden, der gleich oder größer als 4 Elemente ist (über Zeile und Spalte hinweg)?

Ich gehe davon aus, dass ich während der Iteration eine Zählung jedes gefundenen Clusters und seiner mehr als 4 Elemente durchführen, in einer Liste aufzeichnen und zählen und dann die größte Anzahl finden muss.

Das Problem ist, dass ich nicht herausfinden kann, wie dies sowohl in Zeilen als auch in Spalten geschehen soll, und die Anzahl aufzeichnen kann. Ich habe das Raster durchlaufen, bin mir aber nicht sicher, wie ich mich weiter als zwei Zeilen bewegen soll.

Im obigen Beispiel ist der größte Cluster beispielsweise 8. Es gibt einige andere Cluster im Raster, die jedoch 4 Elemente enthalten:

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

Der Code, den ich ausprobiert habe:

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

Ich habe drei Algorithmen implementiert.

Der erste Algorithmus ist Simple, dass er unter Verwendung des einfachsten Ansatzes verschachtelter Schleifen eine O(N^5) zeitliche Komplexität aufweist (in unserem Fall Neine Seite des Eingabegitters 10), da unsere Eingaben der Größenzeit 10x10von O(10^5)in Ordnung sind. Algo ID im Code ist algo = 0. Wenn Sie diesen Algorithmus nur sehen möchten, springen Sie zur Zeile ------ Simple Algorithmim Code.

Der zweite Algorithmus ist Advancedunter Verwendung des Ansatzes der dynamischen ProgrammierungO(N^3) viel komplexer als der erste Algorithmus. Algo ID im Code ist algo = 1. Zur Zeile ------- Advanced Algorithminnerhalb des Codes springen .

Der dritte Algorithmus, den Simple-ListCompich nur zum Spaß implementiert habe, ist fast gleich Simple, genauso O(N^5)komplex, aber wenn man Pythons Listenverständnis anstelle von regulären Schleifen verwendet, ist er kürzer und auch etwas langsamer, da einige Optimierungen nicht verwendet werden. Algo ID im Code ist algo = 2. Springe zur Zeile ------- Simple-ListComp Algorithmim Code, um Algo zu sehen.

Der Rest des Codes implementiert neben Algorithmen die Überprüfung der Richtigkeit der Ergebnisse (doppelte Überprüfung zwischen den Algorithmen), das Drucken der Ergebnisse und die Erstellung von Texteingaben. Der Code ist in Funktionen zum Lösen von Aufgaben solve()und Testen unterteilt test(). solve()Funktion hat viele Argumente, um das Verhalten der Funktion zu konfigurieren.

Alle Hauptcodezeilen werden durch Kommentare dokumentiert. Lesen Sie diese, um zu erfahren, wie Sie Code verwenden. Wenn eine sVariable mehrzeiligen Text mit Rasterelementen enthält, wie in Ihrer Frage, führen Sie sie einfach aus solve(s, text = True)und lösen Aufgaben- und Druckergebnisse. Sie können auch einen Algorithmus aus zwei Versionen (0 (Einfach) und 1 (Erweitert) und 2 (Einfach-ListComp)) auswählen, indem Sie die nächsten Argumente zur Lösung der Funktion angeben algo = 0, check = False(hier 0 für algo 0). Schauen Sie sich den test()Funktionskörper an, um das einfachste Anwendungsbeispiel zu sehen.

Algorithmen auf der Konsole standardmäßig alle Cluster, vom größten bis zum kleinsten, größten bezeichnet wird durch .Symbol, der Rest durch B, C, D, ..., ZSymbole. Sie können ein Argument show_non_max = Falsein der Lösungsfunktion festlegen , wenn nur der erste (größte) Cluster angezeigt werden soll.

Ich werde den einfachen Algorithmus erklären:

1. Grundsätzlich funktioniert der Algorithmus - er durchsucht alle möglichen abgewinkelten 1sRechtecke und speichert Informationen über das Maximum davon in einem ma2D-Array. Top-leftPunkt eines solchen Rechtecks ​​ist (i, j), top-right- (i, k), bottom-left- (l, j + angle_offset), bottom-right- (l, k + angle_offset), alle 4 Ecken, deshalb haben wir so viele Schleifen.
2. In den äußeren zwei i(Zeilen-) j(Spalten-) Schleifen iterieren wir über das gesamte Gitter. Diese (i, j)Position ist der top-leftPunkt des 1sRechtecks. Wir müssen das gesamte Gitter iterieren, da alle möglichen 1sRechtecke top-leftan jedem (row, col)Punkt des gesamten Gitters vorhanden sein können. Zu Beginn der jSchleife prüfen wir, ob das Gitter an der (i, j)Position immer enthalten sollte, 1da wir innerhalb der Schleifen 1snur nach allen Rechtecken suchen .
3. kDie Schleife durchläuft alle möglichen top-rightPositionen (i, k)des 1sRechtecks. Wir sollten aus der Schleife ausbrechen, wenn dies (i, k)gleich ist, 0weil es keinen Punkt gibt, sich kweiter nach rechts zu erstrecken , weil ein solches Rechteck immer enthält 0.
4. In vorherigen Schleifen haben wir top-leftund top-rightEcken des Rechtecks fixiert . Jetzt müssen wir nach zwei unteren Ecken suchen. Dazu müssen wir das Rechteck in verschiedenen Winkeln nach unten verlängern, bis wir zuerst erreichen 0.
5. offDie Schleife versucht, das Rechteck in allen möglichen Winkeln nach unten zu erweitern ( 0(gerade vertikal) +1( 45Grad von oben nach unten nach rechts verschoben) -1( -45Grad)). offDies ist im Grunde eine solche Zahl, grid[y][x]die "über" liegt (entspricht durch Y) grid[y + 1][x + off].
6. lversucht, das Rechteck in Yverschiedenen Winkeln nach unten (in Richtung) zu verlängern off. Es wird bis zum ersten Mal erweitert, 0da es dann nicht weiter erweitert werden kann (da jedes dieser Rechtecke bereits enthalten ist 0).
7. Innerhalb der lSchleife gibt es eine if grid[l][max(0, j + off * (l - i)) : min(k + 1 + off * (l - i), c)] != ones[:k - j + 1]:Bedingung, im Grunde ifsoll damit überprüft werden, ob die letzte Reihe des Rechtecks ​​alle enthält, 1wenn dies nicht ifaus der Schleife herausbricht. Diese Bedingung vergleicht zwei listSchichten auf Ungleichheit. Die letzte Reihe des Rechtecks ​​erstreckt sich von Punkt (l, j + angle_offset)(Ausdruck max(0, j + off * (l - i)), maximal begrenzt zu sein 0 <= X) bis Punkt (l, k + angle_offset)(Ausdruck min(k + 1 + off * (l - i), c), minimal begrenzt zu sein X < c).
8. Innere lSchleife gibt es andere Linien, ry, rx = l, k + off * (l - i)berechnet bottom-rightRechteck Punkt von (ry, rx)dem ist (l, k + angle_offset), diese (ry, rx)Position zu speichern verwendet wird maximales Innen gefunden maArray dieser Array speichert all maximal gefundenen Rechtecken, ma[ry][rx]enthält Informationen über das Rechteck hat bottom-rightam Punkt (ry, rx).
9. rv = (l + 1 - i, k + 1 - j, off)line berechnet einen neuen möglichen Kandidaten für den ma[ry][rx]Array-Eintrag, der möglich ma[ry][rx]ist , weil er nur aktualisiert wird, wenn der neue Kandidat eine größere Fläche von hat 1s. Hier enthält der rv[0]Wert innerhalb des rvTupels ein heightsolches Rechteck, rv[1]enthält ein widthsolches Rechteck ( widthentspricht der Länge der unteren Reihe des Rechtecks), rv[2]enthält den Winkel eines solchen Rechtecks.
10. Die Bedingung if rv[0] * rv[1] > ma[ry][rx][0] * ma[ry][rx][1]:und ihr Körper prüfen nur, ob die rvFläche innerhalb des Arrays größer als das aktuelle Maximum ist. ma[ry][rx]Wenn sie größer ist, wird dieser Array-Eintrag aktualisiert ( ma[ry][rx] = rv). Ich werde daran erinnern, dass ma[ry][rx]Informationen (width, height, angle)über das aktuell gefundene Rechteck mit maximaler Fläche enthalten sind, auf das bottom-rightPunkt zeigt (ry, rx)und das diese hat width, heightund angle.
11. Erledigt! Nach dem Ausführen des Algorithmus maenthält das Array Informationen zu allen rechtwinkligen Rechtecken (Clustern) mit maximaler Fläche, 1ssodass alle Cluster wiederhergestellt und später auf der Konsole gedruckt werden können. Der größte aller solcher 1sCluster ist gleich einigen rv0 = ma[ry0][rx0], iteriere nur einmal durch alle Elemente von maund finde einen solchen Punkt, (ry0, rx0)so dass ma[ry0][rx0][0] * ma[ry0][rx0][1](Fläche) maximal ist. Dann hat der größte Cluster bottom-rightPunkt (ry0, rx0), bottom-leftPunkt (ry0, rx0 - rv0[1] + 1), top-rightPunkt (ry0 - rv0[0] + 1, rx0 - rv0[2] * (rv0[0] - 1)), top-leftPunkt (ry0 - rv0[0] + 1, rx0 - rv0[1] + 1 - rv0[2] * (rv0[0] - 1))(hier rv0[2] * (rv0[0] - 1)ist nur der Winkelversatz, dh wie stark die erste Reihe im XVergleich zur letzten Reihe des Rechtecks verschoben ist ).

Probieren Sie es online aus!

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

Ausgabe:

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