HackerRank - The Grid Search

Question

Was playing around tonight and thought this problem was interesting enough to post here.

Given a 2D array of digits, try to find the location of a given 2D pattern of digits.

Input Format

The first line contains an integer, T, which is the number of test cases.

T test cases follow, each having a structure as described below:
The first line contains two space-separated integers, R and C, indicating the number of rows and columns in the grid G, respectively.

This is followed by R lines, each with a string of C digits, which represent the grid G.

The following line contains two space-separated integers, r and c, indicating the number of rows and columns in the pattern grid P.

This is followed by r lines, each with a string of c digits, which represent the pattern P.

Output Format

Display YES or NO, depending on whether (or not) you find that the larger grid G contains the rectangular pattern P. The evaluation will be case sensitive.

Taken from HackerRank challenge "The Grid Search." Much more detailed explanation there. I borrowed this writeup from a similar question.

Any feedback appreciated - this passes all the tests. I did not really try to optimize beyond passing the test cases and making it fairly simple in order to do that.

Specifically am curious about:

• Ability to streamline the nested if statements and loops
• All the match/find stuff seems clunky
• I don't like all the break statements and my cont boolean, is there a better way to early exit this?

Anything else would be appreciated too. the initial chunk is all system input stuff which I did not change but pasted here in case anyone wants to run it on HackerRank.

#!/bin/python3

import sys


t = int(input().strip())
for a0 in range(t):
    R,C = input().strip().split(' ')
    R,C = [int(R),int(C)]
    G = []
    G_i = 0
    for G_i in range(R):
       G_t = str(input().strip())
       G.append(G_t)
    r,c = input().strip().split(' ')
    r,c = [int(r),int(c)]
    P = []
    P_i = 0
    for P_i in range(r):
       P_t = str(input().strip())
       P.append(P_t)

    # everything above here is auto generated by the site for parsing input

    result = 'NO'

    # search each potential matching row
    for y in range(R - r + 1):
        match_index = -1
        cont = True

        # search vertically for every time that the first row in the search matrix matches
        while cont:
            match_index = G[y].find(P[0], match_index + 1)
            if match_index < 0:
                cont = False

            # check to ensure row in outcome matches input
            for y_p in range(r):
                G_sub = str(G[y + y_p][match_index : match_index + c])
                P_sub = str(P[y_p])
                if G_sub != P_sub:
                    break

                if y_p == r - 1:
                    result = 'YES'
                    break

    print(result)  

Answer 1

Being given some generated code doesn't mean you can't criticize it. Unused imports, unused variables, meaningless variable names, unpythonic constructs… To organize things a bit more, you should also

Use functions

This is to separate the parsing of the input from the core of the computation. It can help you further test your logic without rellying on the input being fed through stdin. A basic layout could be:

def find_pattern_in_grid(grid, pattern, pattern_height=None, pattern_width=None):
    if pattern_height is None or pattern_width is None:
        pattern_height = len(pattern)
        pattern_width = len(pattern[0])

    return False  # Placeholder

def run_test_case():
    grid_height = int(input().split()[0])  # Dropping grid width, we don't use it
    grid = [input() for _ in range(grid_height)]
    pattern_height, pattern_width = map(int, input().split())
    pattern = [input() for _ in range(pattern_height)]

    return find_pattern_in_grid(grid, pattern, pattern_height, pattern_width)

def main():
    test_cases = int(input())
    for _ in range(test_cases):
        if run_test_case():
            print('YES')
        else:
            print('NO')


if __name__ == '__main__':
    main()

A few things to note here:

• input() does not return the end-of-line character, so there is no need to strip() it;
• even if it didn't, split() without argument have special logic to remove extraneous whitespace around words;
• when building the grid or pattern you don't need to split since there is no whitespace in the rows. Even if it had, working with strings and sub-strings can be more efficient as you already do;
• find_pattern_in_grid accept optional pattern_height and pattern_width so you can easily drop into an interactive session, import your file and feed this function with any pre-formatted input you want without having to bother computing the number of rows and columns beforehand;
• dropping in an interactive session like that is the reason why it's a good habit to have an if __name__ == '__main__' clause that wraps all your top-level code.

As a bonus, having functions will let you return early so you might be able to remove flag variables.

Iterate over rows

Python makes it easy to iterate over content rather than using indexes to access the content. It is both faster and more pythonic. In case you need the indexes too, use enumerate:

def find_pattern_in_grid(grid, pattern, pattern_height, pattern_width):
    # search each potential matching row
    for y, row in enumerate(grid[:1-pattern_height]):  # [:-pattern_height+1]
        reduced_grid = grid[y:]  # Keep only the remaining row for further comparison

        # search vertically for every time that the first row in the search matrix matches
        match_index = row.find(pattern[0])
        while match_index != -1:
            # check to ensure row in outcome matches input
            for pattern_row, grid_row in zip(pattern, reduced_grid):
                grid_sub = grid_row[match_index:match_index+pattern_width]
                if grid_sub != pattern_row:
                    break
            else:
                return True

            # We didn't find the pattern, try another match
            match_index = row.find(pattern[0], match_index + 1)

    # Remaining of the grid turned out to be less than the pattern height
    return False

Here I used:

• slicing (grid[y:]) and zip to iterate over both the remaining rows of the grid and the rows of the pattern at the same time;
• for .. else to execute the else clause if (and only if) no break were reached within the for loop. Meaning no mismatch were found between the grid and the pattern.

I also incorporated the "match" condition directly within the while loop. But it lead to somewhat duplicated find as you can see, so not that ideal. And I removed the call to str since slicing a string already returns a string.