Gridception - Round 2, Google Codejam 2018

gridception.py

# Codejam 2018, Round 2: Gridception

def largest_connected_component(grid):
    """Find largest connected component of 1s on a grid."""

    def traverse_component(i, j):
        """Returns number of unseen valid elements connected to grid[i][j]."""
        seen[i][j] = True
        result = 1

        # Check all four neighbours
        if i > 0 and grid[i-1][j] and not seen[i-1][j]:
            result += traverse_component(i-1, j)
        if j > 0 and grid[i][j-1] and not seen[i][j-1]:
            result += traverse_component(i, j-1)
        if i < len(grid)-1 and grid[i+1][j] and not seen[i+1][j]:
            result += traverse_component(i+1, j)
        if j < len(grid[0])-1 and grid[i][j+1] and not seen[i][j+1]:
            result += traverse_component(i, j+1)
        return result

    nrows, ncols = len(grid), len(grid[0])
    seen = [[False] * ncols for _ in range(nrows)]

    # Tracks size of largest connected component found
    component_size = 0

    for i in range(nrows):
        for j in range(ncols):
            if grid[i][j] and not seen[i][j]:
                temp = traverse_component(i, j)
                if temp > component_size:
                    component_size = temp

    return component_size

def find_quad_patterns(nrows, ncols, grid):
    """Find all quadrant patterns present in grid."""
    patterns = set()

    for i in range(nrows):
        for j in range(ncols):
            D = grid[i][j]
            patterns.add((D, D,
                          D, D))
            if i > 0:
                B = grid[i-1][j]
                patterns.add((B, B,
                              D, D))
            if j > 0:
                C = grid[i][j-1]
                patterns.add((C, D, 
                              C, D))
            if i > 0 and j > 0:
                A = grid[i-1][j-1]
                patterns.add((A, B,
                              C, D))
    return patterns

def check_pattern(nrows, ncols, grid, pattern, r, c):
    """Check pattern on grid. Quadrants intersect at (r, c)."""
    A, B, C, D = pattern

    # Generate template based on pattern
    temp = [[grid[i][j] == A if j < c else grid[i][j] == B 
            for j in range(ncols)] if i < r else 
            [grid[i][j] == C if j < c else grid[i][j] == D
            for j in range(ncols)] for i in range(nrows)]

    return largest_connected_component(temp)

def largest_pattern(nrows, ncols, grid):
    """Find largest pattern that meets specifications."""

    # Get set of patterns that exist in original grid
    patterns = find_quad_patterns(nrows, ncols, grid)

    result = 0
    for pattern in patterns:
        A, B, C, D = pattern
        if A == B == C == D:
            temp = check_pattern(nrows, ncols, grid, pattern, 0, 0)
            if temp > result:
                result = temp
        elif A == B and C == D:
            for i in range(nrows):
                temp = check_pattern(nrows, ncols, grid, pattern, i, 0)
                if temp > result:
                    result = temp
        elif A == C and B == D:
            for j in range(ncols):
                temp = check_pattern(nrows, ncols, grid, pattern, 0, j)
                if temp > result:
                    result = temp
        else:
            for i in range(nrows):
                for j in range(ncols):
                    temp = check_pattern(nrows, ncols, grid, pattern, i, j)
                    if temp > result:
                        result = temp
    return result

# I/O Code
num_cases = int(input())

for case in range(1, num_cases + 1):
    nrows, ncols = map(int, input().split())
    grid = []
    for _ in range(nrows):
        grid.append([int(c == 'W') for c in input().strip()])

    pattern_size = largest_pattern(nrows, ncols, grid)
    print('Case #{}: {}'.format(case, pattern_size))