• 1

• 145.5k
• 22
• 190
• 478

• 1.7k
• 15
• 24

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)