การค้นหารูปแบบใน Grid Python [ซ้ำกัน]

Question

ฉันได้สร้างตารางแบบสุ่มที่มี 0 และ 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 0 0 1 1
0 0 1 1 1 1 1 0
0 1 0 0 1 0 1 1

ฉันจะวนซ้ำผ่านตารางเพื่อค้นหาคลัสเตอร์ที่ใหญ่ที่สุดของ 1sที่มีค่าเท่ากันหรือมากกว่า 4 รายการ (ข้ามแถวและคอลัมน์) ได้อย่างไร

ฉันคิดว่าฉันจำเป็นต้องนับคลัสเตอร์ที่พบแต่ละรายการในขณะที่ทำซ้ำและมีมากกว่า 4 รายการบันทึกและนับในรายการจากนั้นค้นหาจำนวนที่มากที่สุด

ปัญหาคือฉันไม่สามารถหาวิธีทำได้ทั้งแถวและคอลัมน์และบันทึกจำนวน ฉันได้วนซ้ำไปตามเส้นตาราง แต่ไม่แน่ใจว่าจะเลื่อนได้ไกลกว่าสองแถวอย่างไร

ตัวอย่างเช่นในตัวอย่างข้างต้นคลัสเตอร์ที่ใหญ่ที่สุดคือ 8 มีคลัสเตอร์อื่น ๆ ในกริด แต่มี 4 องค์ประกอบ:

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 1 BB 0 0 1 1
0 0 BB 1 1 1 0
0 1 0 0 1 0 1 1

รหัสที่ฉันลอง:

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

ฉันใช้อัลกอริทึมสามแบบ

อัลกอริทึมแรกคือการSimpleใช้วิธีที่ง่ายที่สุดของการวนซ้ำแบบซ้อนมันมีO(N^5) ความซับซ้อนของเวลา (โดยที่Nด้านหนึ่งของกริดอินพุตอยู่10สำหรับกรณีของเรา) สำหรับอินพุตขนาด10x10เวลาของO(10^5)เราค่อนข้างโอเค algo = 0รหัสอัลโกในรหัสคือ หากคุณต้องการเพียงแค่เห็นอัลกอริทึมนี้ข้ามไปยังบรรทัด------ Simple Algorithmภายในโค้ด

อัลกอริทึมที่สองคือการAdvancedใช้วิธีการเขียนโปรแกรมแบบไดนามิกความซับซ้อนจะO(N^3)เร็วกว่าอัลกอริทึมแรกมาก algo = 1รหัสอัลโกในรหัสคือ ข้ามไปที่บรรทัด------- Advanced Algorithmภายในรหัส

อัลกอริทึมที่สามที่Simple-ListCompฉันใช้เพื่อความสนุกสนานมันเกือบจะเหมือนSimpleกันมีO(N^5)ความซับซ้อนเหมือนกันแต่ใช้การเข้าใจรายการของ Python แทนการวนซ้ำปกตินั่นเป็นสาเหตุที่สั้นกว่าและช้ากว่าเล็กน้อยเนื่องจากไม่ได้ใช้การเพิ่มประสิทธิภาพบางอย่าง algo = 2รหัสอัลโกในรหัสคือ ข้ามไปที่บรรทัด------- Simple-ListComp Algorithmภายในรหัสเพื่อดู algo

ส่วนที่เหลือของโค้ดนอกเหนือจากอัลกอริทึมแล้วยังดำเนินการตรวจสอบความถูกต้องของผลลัพธ์ (การตรวจสอบซ้ำระหว่างอัลกอริทึม) ผลการพิมพ์การป้อนข้อความ รหัสคือแยกออกเป็นฟังก์ชั่นการแก้งานและฟังก์ชั่นการทดสอบsolve() ฟังก์ชันมีอาร์กิวเมนต์มากมายที่อนุญาตให้กำหนดลักษณะการทำงานของฟังก์ชันtest()solve()

บรรทัดรหัสหลักทั้งหมดได้รับการบันทึกโดยความคิดเห็นอ่านเพื่อเรียนรู้วิธีใช้โค้ด โดยทั่วไปหากsตัวแปรมีข้อความหลายบรรทัดพร้อมองค์ประกอบตารางเช่นเดียวกับในคำถามของคุณคุณเพียงแค่เรียกใช้solve(s, text = True)และมันจะแก้ปัญหางานและผลการพิมพ์ นอกจากนี้คุณสามารถเลือกอัลกอริทึมจากสองเวอร์ชัน (0 (Simple) และ 1 (ขั้นสูง) และ 2 (Simple-ListComp)) โดยให้อาร์กิวเมนต์ถัดไปเพื่อแก้ฟังก์ชันalgo = 0, check = False(ที่นี่ 0 สำหรับ algo 0) ดูที่test()ตัวฟังก์ชันเพื่อดูตัวอย่างการใช้งานที่ง่ายที่สุด

การส่งออกไปยังคอนโซลอัลกอริทึมโดยค่าเริ่มต้นกลุ่มทั้งหมดจากที่ใหญ่ที่สุดไปหาน้อยที่สุดใหญ่ที่สุดคือความหมายโดย.สัญลักษณ์ที่เหลือโดยB, C, D, ... , Zสัญลักษณ์ คุณสามารถตั้งค่าอาร์กิวเมนต์show_non_max = Falseในฟังก์ชันแก้ได้หากคุณต้องการให้แสดงเฉพาะคลัสเตอร์แรก (ใหญ่ที่สุด) เท่านั้น

ฉันจะอธิบายอัลกอริทึมอย่างง่าย:

1. โดยพื้นฐานแล้วอัลกอริทึมทำหน้าที่อะไร - จะค้นหา1sรูปสี่เหลี่ยมมุมที่เป็นไปได้ทั้งหมดและจัดเก็บข้อมูลเกี่ยวกับจำนวนสูงสุดในmaอาร์เรย์ 2D Top-leftจุดสี่เหลี่ยมดังกล่าวเป็น(i, j), top-right- (i, k), bottom-left- (l, j + angle_offset), bottom-right- (l, k + angle_offset)ทั้งหมด 4 มุมที่ว่าทำไมเรามีลูปจำนวนมากดังนั้น
2. ในสองi(แถว) ด้านนอก(แถว) j(คอลัมน์) เราวนซ้ำบนเส้นตารางทั้งหมด(i, j)ตำแหน่งนี้จะเป็นtop-leftจุดของ1sสี่เหลี่ยมผืนผ้าเราจำเป็นต้องวนซ้ำทั้งตารางเนื่องจาก1sสี่เหลี่ยมที่เป็นไปได้ทั้งหมดอาจtop-leftอยู่ที่(row, col)จุดใดก็ได้ของเส้นตารางทั้งหมด เมื่อเริ่มjลูปเราตรวจสอบว่ากริดที่(i, j)ตำแหน่งควรมีเสมอ1เพราะในลูปเราค้นหาสี่เหลี่ยมผืนผ้าทั้งหมดที่มี1sเพียง
3. kวนซ้ำผ่านtop-rightตำแหน่งที่เป็นไปได้ทั้งหมด(i, k)ของ1sสี่เหลี่ยมผืนผ้า เราควรจะแยกออกจากห่วงถ้า(i, k)เท่ากับ0เพราะมีจุดที่จะขยายไม่ไปทางขวาเพราะสี่เหลี่ยมดังกล่าวจะประกอบด้วยk0
4. ในลูปก่อนหน้านี้เราแก้ไขtop-leftและtop-rightมุมของสี่เหลี่ยมผืนผ้า ตอนนี้เราต้องค้นหาสองมุมล่าง 0เพื่อที่เราต้องการที่จะขยายลงสี่เหลี่ยมผืนผ้าในมุมที่แตกต่างกันจนเราไปถึงครั้งแรก
5. offห่วงพยายามขยายลงสี่เหลี่ยมผืนผ้าในมุมที่เป็นไปได้ทั้งหมด ( 0(แนวตั้งตรง), +1( 45องศาขยับตัวไปทางขวาจากบนลงล่าง) -1( -45องศา)) offโดยทั่วไปเป็นจำนวนดังกล่าวว่าgrid[y][x]เป็น "เหนือ" (โดยสอดคล้องกับการ)Ygrid[y + 1][x + off]
6. lพยายามขยายรูปสี่เหลี่ยมผืนผ้าลงด้านล่าง (ในYทิศทาง) ที่มุมoffต่างๆ มันถูกขยายออกไปก่อน0เพราะมันไม่สามารถขยายออกไปได้อีกแล้ว (เพราะแต่ละสี่เหลี่ยมผืนผ้าจะมีอยู่แล้ว0)
7. ภายในlลูปมีif grid[l][max(0, j + off * (l - i)) : min(k + 1 + off * (l - i), c)] != ones[:k - j + 1]:เงื่อนไขโดยทั่วไปนี่ifมีไว้เพื่อตรวจสอบว่าแถวสุดท้ายของสี่เหลี่ยมผืนผ้ามีทั้งหมด1ถ้าไม่ifแตกออกจากลูป เงื่อนไขนี้เปรียบเทียบสองlistชิ้นสำหรับความไม่เท่ากัน แถวสุดท้ายของสี่เหลี่ยมผืนผ้ามีระยะตั้งแต่จุด(l, j + angle_offset)(นิพจน์max(0, j + off * (l - i))จำกัด สูงสุดที่จะเป็น0 <= X) ถึงจุด(l, k + angle_offset)(นิพจน์min(k + 1 + off * (l - i), c)จำกัด ต่ำสุดเป็นX < c)
8. ภายในlวงมีสายอื่น ๆry, rx = l, k + off * (l - i)คำนวณbottom-rightจุดสี่เหลี่ยม(ry, rx)ซึ่งเป็น(l, k + angle_offset)นี้(ry, rx)ตำแหน่งที่ถูกนำมาใช้ในการจัดเก็บสูงสุดพบภายในmaอาร์เรย์ร้านค้าอาร์เรย์นี้สูงสุดทั้งหมดที่พบสี่เหลี่ยมma[ry][rx]มีข้อมูลเกี่ยวกับรูปสี่เหลี่ยมผืนผ้าที่มีที่จุดbottom-right(ry, rx)
9. rv = (l + 1 - i, k + 1 - j, off)บรรทัดคำนวณผู้สมัครที่เป็นไปได้ใหม่สำหรับma[ry][rx]รายการอาร์เรย์ไปได้เพราะมีการปรับปรุงเฉพาะในกรณีที่ผู้สมัครใหม่ที่มีพื้นที่ขนาดใหญ่ของma[ry][rx] 1sที่นี่rv[0]คุ้มค่าภายในrvtuple มีheightของสี่เหลี่ยมดังกล่าวrv[1]มีwidthของสี่เหลี่ยมเช่น ( widthเท่ากับความยาวของแถวด้านล่างของรูปสี่เหลี่ยมผืนผ้า) rv[2]มีมุมของสี่เหลี่ยมดังกล่าว
10. เงื่อนไขif rv[0] * rv[1] > ma[ry][rx][0] * ma[ry][rx][1]:และเนื้อความจะตรวจสอบว่าrvพื้นที่มีขนาดใหญ่กว่าอาร์เรย์สูงสุดในปัจจุบันหรือไม่ma[ry][rx]และหากมีขนาดใหญ่กว่ารายการอาร์เรย์นี้จะถูกอัปเดต ( ma[ry][rx] = rv) ฉันจะเตือนว่าma[ry][rx]มีข้อมูล(width, height, angle)เกี่ยวกับการค้นพบในปัจจุบันสูงสุดพื้นที่สี่เหลี่ยมที่มีbottom-rightจุด(ry, rx)และที่มีเหล่านี้width, และheightangle
11. เสร็จแล้ว! หลังจากรันอัลกอริทึมอาร์เรย์maมีข้อมูลเกี่ยวกับรูปสี่เหลี่ยมมุมพื้นที่สูงสุด (คลัสเตอร์) ทั้งหมด1sเพื่อให้สามารถกู้คืนและพิมพ์คลัสเตอร์ทั้งหมดในภายหลังไปยังคอนโซลได้ ที่ใหญ่ที่สุดของ1s-clusters ทั้งหมดนั้นเท่ากับบางส่วนrv0 = ma[ry0][rx0]เพียงวนซ้ำหนึ่งครั้งผ่านองค์ประกอบทั้งหมดของmaและค้นหาจุดดังกล่าว(ry0, rx0)เพื่อให้ma[ry0][rx0][0] * ma[ry0][rx0][1](พื้นที่) มีค่าสูงสุด จากนั้นคลัสเตอร์ที่ใหญ่ที่สุดจะมีbottom-rightจุด(ry0, rx0), bottom-leftจุด(ry0, rx0 - rv0[1] + 1), top-rightจุด(ry0 - rv0[0] + 1, rx0 - rv0[2] * (rv0[0] - 1)), top-leftจุด(ry0 - rv0[0] + 1, rx0 - rv0[1] + 1 - rv0[2] * (rv0[0] - 1))(ที่นี่rv0[2] * (rv0[0] - 1)เป็นเพียงมุมชดเชยคือวิธีการขยับมากเป็นแถวแรกพร้อมXเมื่อเทียบกับแถวสุดท้ายของสี่เหลี่ยม)

ลองออนไลน์!

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

เอาท์พุต:

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