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.
The first line contains an integer,
T, which is the number of test cases.
Ttest cases follow, each having a structure as described below:
The first line contains two space-separated integers,
C, indicating the number of rows and columns in the grid
This is followed by
Rlines, each with a string of
Cdigits, which represent the grid
The following line contains two space-separated integers,
c, indicating the number of rows and columns in the pattern grid
This is followed by
rlines, each with a string of
cdigits, which represent the pattern
NO, depending on whether (or not) you find that the larger grid
Gcontains 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
breakstatements 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, 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)