Menemukan Pola dalam Kotak Python [duplikat]

Question

Saya telah membuat grid secara acak yang berisi 0 dan 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 1 0 0 1 1
0 0 1 1 1 1 1 0
0 1 1 0 0 1 0 1 1

Bagaimana saya bisa mengulang melalui grid untuk menemukan cluster 1s terbesar , yang sama atau lebih besar dari 4 item (melintasi baris dan kolom)?

Saya berasumsi saya perlu menghitung setiap cluster yang ditemukan saat melakukan iterasi dan yang lebih dari 4 item, catat dan hitung dalam daftar dan kemudian temukan nomor terbesar.

Masalahnya adalah saya tidak tahu bagaimana melakukannya di kedua baris dan kolom dan mencatat hitungannya. Saya telah mengulang melalui kisi tetapi tidak yakin bagaimana cara bergerak lebih jauh dari dua baris.

Misalnya pada contoh di atas, cluster terbesar adalah 8. Ada beberapa cluster lain dalam kisi, tetapi mereka memiliki 4 elemen:

AA 0 0 0 1 0 1
A A 1 0 1 1 1 1
1 0 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

Kode yang saya coba:

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

Saya telah menerapkan tiga algoritma.

Algoritme pertama adalah Simple, dengan menggunakan pendekatan loop bersarang yang paling mudah, ia memiliki O(N^5) kompleksitas waktu (di mana Nsalah satu sisi input grid, 10untuk kasus kami), untuk input ukuran 10x10waktu O(10^5)cukup baik-baik saja. Algo id dalam kode adalah algo = 0. Jika Anda hanya ingin melihat algoritma ini lompat ke baris ------ Simple Algorithmdi dalam kode.

Algoritma kedua Advanced, dengan pendekatan Dynamic Programming , kompleksitasnya O(N^3)jauh lebih cepat dari algoritma pertama. Algo id dalam kode adalah algo = 1. Langsung ke baris ------- Advanced Algorithmdi dalam kode.

Algoritma ketiga Simple-ListCompsaya terapkan hanya untuk bersenang-senang, itu hampir sama seperti Simple, O(N^5)kompleksitas yang sama , tetapi menggunakan pemahaman daftar Python daripada loop biasa, itulah mengapa lebih pendek, juga sedikit lebih lambat karena tidak menggunakan beberapa optimasi. Algo id dalam kode adalah algo = 2. Langsung ke baris ------- Simple-ListComp Algorithmdi dalam kode untuk melihat algo.

Kode lainnya, selain algoritme, mengimplementasikan pemeriksaan kebenaran hasil (pengecekan ganda antar algoritme), mencetak hasil, menghasilkan input teks. Kode dibagi menjadi fungsi pemecahan tugas solve()dan fungsi pengujian test(). solve()function memiliki banyak argumen untuk memungkinkan konfigurasi perilaku fungsi.

Semua baris kode utama didokumentasikan oleh komentar, membacanya untuk mempelajari cara menggunakan kode. Pada dasarnya jika svariabel berisi teks multi-baris dengan elemen grid, sama seperti dalam pertanyaan Anda, Anda hanya menjalankan solve(s, text = True)dan itu akan menyelesaikan tugas dan hasil cetak. Anda juga dapat memilih algoritma dari dua versi (0 (Sederhana) dan 1 (Lanjutan) dan 2 (Simple-ListComp)) dengan memberikan argumen berikutnya untuk menyelesaikan fungsi algo = 0, check = False(di sini 0 untuk algo 0). Lihat test()badan fungsi untuk melihat contoh penggunaan yang paling sederhana.

Algoritma output ke konsol secara default semua cluster, dari terbesar ke terkecil, terbesar ditandai dengan .simbol, sisanya oleh B, C, D, ..., Zsimbol. Anda dapat mengatur argumen show_non_max = Falsedalam fungsi penyelesaian jika Anda hanya ingin cluster pertama (terbesar) ditampilkan.

Saya akan menjelaskan algoritma sederhana:

1. Pada dasarnya apa yang dilakukan algoritma - ia mencari melalui semua kemungkinan 1spersegi panjang bersudut dan menyimpan info tentang maksimalnya ke dalam maarray 2D. Top-leftTitik persegi panjang tersebut adalah (i, j), top-right- (i, k), bottom-left- (l, j + angle_offset), bottom-right- (l, k + angle_offset), keempat sudut, itulah sebabnya kami memiliki banyak loop.
2. Dalam dua loop i(baris), j(kolom) terluar yang kita iterasi ke seluruh grid, (i, j)posisi ini akan menjadi top-lefttitik 1spersegi panjang, kita perlu mengulang seluruh grid karena semua 1spersegi panjang yang mungkin ada top-leftdi (row, col)titik mana pun dari keseluruhan grid. Pada awal jperulangan kami memeriksa bahwa kisi pada (i, j)posisi harus selalu berisi 1karena di dalam loop kami mencari semua persegi panjang 1shanya dengan .
3. klingkaran iterates melalui semua kemungkinan top-rightposisi (i, k)dari 1spersegi panjang. Kita harus keluar dari loop jika (i, k)sama dengan 0karena tidak ada gunanya memperpanjang klebih jauh ke kanan karena persegi panjang seperti itu akan selalu berisi 0.
4. Di loop sebelumnya kami memperbaiki top-leftdan top-rightsudut persegi panjang. Sekarang kita perlu mencari dua sudut bawah. Untuk itu kita perlu memanjangkan persegi panjang ke bawah pada sudut yang berbeda hingga mencapai yang pertama 0.
5. offloop mencoba memanjangkan persegi panjang ke bawah pada semua sudut yang memungkinkan ( 0(lurus vertikal), +1( 45derajat bergeser ke kanan dari atas ke bawah), -1( -45derajat)), offpada dasarnya adalah angka yang grid[y][x]"di atas" (sesuai dengan Y) grid[y + 1][x + off].
6. lmencoba memanjangkan persegi panjang ke bawah ( Ysearah) pada sudut yang berbeda off. Itu diperpanjang sampai pertama 0karena tidak dapat diperpanjang lebih jauh (karena setiap persegi panjang seperti itu sudah berisi 0).
7. Di dalam lloop ada if grid[l][max(0, j + off * (l - i)) : min(k + 1 + off * (l - i), c)] != ones[:k - j + 1]:kondisi, pada dasarnya ini ifdimaksudkan untuk memeriksa bahwa baris terakhir persegi panjang berisi semua 1jika tidak ini ifkeluar dari loop. Kondisi ini membandingkan dua listirisan untuk non-kesetaraan. Baris terakhir persegi panjang terbentang dari titik (l, j + angle_offset)(ekspresi max(0, j + off * (l - i)), maks-terbatas menjadi 0 <= X) ke titik (l, k + angle_offset)(ekspresi min(k + 1 + off * (l - i), c), min-terbatas menjadi X < c).
8. Di dalam lloop terdapat baris lain, ry, rx = l, k + off * (l - i)menghitung bottom-righttitik persegi panjang (ry, rx)yaitu (l, k + angle_offset), (ry, rx)posisi ini digunakan untuk menyimpan maarray dalam maksimum yang ditemukan , array ini menyimpan semua persegi panjang yang ditemukan maksimal, ma[ry][rx]berisi info tentang persegi panjang yang ada bottom-rightdi titik (ry, rx).
9. rv = (l + 1 - i, k + 1 - j, off)baris menghitung kandidat baru yang mungkin untuk ma[ry][rx]entri array, mungkin karena ma[ry][rx]diperbarui hanya jika kandidat baru memiliki area yang lebih luas 1s. Disini rv[0]nilai di dalam rvtupel berisi heightpersegi panjang tersebut, rv[1]berisi widthpersegi panjang tersebut ( widthsama dengan panjang baris bawah persegi panjang), rv[2]berisi sudut persegi panjang tersebut.
10. Kondisi if rv[0] * rv[1] > ma[ry][rx][0] * ma[ry][rx][1]:dan badannya hanya memeriksa apakah rvarea lebih besar dari maksimum saat ini di dalam larik ma[ry][rx]dan jika lebih besar maka entri larik ini diperbarui ( ma[ry][rx] = rv). Saya akan mengingatkan bahwa ma[ry][rx]berisi info (width, height, angle)tentang persegi panjang area maksimal yang ditemukan saat ini yang memiliki bottom-righttitik (ry, rx)dan yang memiliki ini width, heightdan angle.
11. Selesai! Setelah algoritma run array maberisi informasi tentang semua persegi panjang bersudut area maksimal (cluster) 1ssehingga semua cluster dapat dipulihkan dan dicetak nanti ke konsol. 1sCluster terbesar dari semua cluster sama dengan beberapa rv0 = ma[ry0][rx0], cukup lakukan iterasi sekali melalui semua elemen madan temukan titik tersebut (ry0, rx0)sehingga ma[ry0][rx0][0] * ma[ry0][rx0][1](area) maksimal. Kemudian cluster terbesar akan memiliki bottom-righttitik (ry0, rx0), bottom-lefttitik (ry0, rx0 - rv0[1] + 1), top-righttitik (ry0 - rv0[0] + 1, rx0 - rv0[2] * (rv0[0] - 1)), top-lefttitik (ry0 - rv0[0] + 1, rx0 - rv0[1] + 1 - rv0[2] * (rv0[0] - 1))(di sini rv0[2] * (rv0[0] - 1)hanya offset sudut, yaitu berapa banyak yang bergeser pada baris pertama Xdibandingkan dengan baris persegi panjang terakhir).

Cobalah secara 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()

Keluaran:

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