HackerRank ‘The Grid Search’ Solution | MartinKysel.com

HackerRank 'The Grid Search' Solution | MartinKysel.com
Given a 2D array of digits, try to find the location of a given 2D pattern of digits
https://www.hackerrank.com/challenges/the-grid-search
Good solution:
https://github.com/jiayuanmark/hackerrank/blob/master/hackrank-back-school/grid-search.cpp
int R, C, r, c;
string grid[1005], pat[1005];
int hist[1005][1005];

bool solve(const int& sum) {
for (int i = 0; i+r-1 < R; ++i) {
for (int j = 0; j+c-1 < C; ++j) {
int bot = i+r-1, rht = j+c-1;
int check = hist[bot][rht];
if (i >= 1) {
check -= hist[i-1][rht];
}
if (j >= 1) {
check -= hist[bot][j-1];
}
if (i >= 1 && j >= 1) {
check += hist[i-1][j-1];
}

if (check == sum) {
bool match = true;
for (int k = 0; k < r; ++k) {
for (int l = 0; l < c; ++l) {
if (grid[i+k][j+l] != pat[k][l]) {
match = false;
break;
}
}
if (!match) break;
}
if (match) return true;
}
}
}
return false;
}

int main() {
int t; cin >> t;
while (t--) {
memset(hist, 0, sizeof(hist));

// Grid
cin >> R >> C;
for (int i = 0; i < R; ++i) {
cin >> grid[i];
for (int j = 0; j < C; ++j) {
hist[i][j] += (grid[i][j] - '0');
if (i >= 1) {
hist[i][j] += hist[i-1][j];
}
if (j >= 1) {
hist[i][j] += hist[i][j-1];
}
if (i >= 1 && j >= 1) {
hist[i][j] -= hist[i-1][j-1];
}
}
}


// Pattern
int sum = 0;
cin >> r >> c;
for (int i = 0; i < r; ++i) {
cin >> pat[i];
for (int j = 0; j < c; ++j) {
sum += (pat[i][j] - '0');
}
}

// Solve
bool res = solve(sum);
if (res) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
return 0;
}

SubArray-Check reduction techniques:

• keep the sum of the sub-array in a separate grid, check only if sum matches the pattern
• Rabin-Karp string searching algorithm on each line to fast forward

def matchSubArray(arr, pat, x, y, pat_y, pat_x):

    for running_y in xrange(pat_y):

        for running_x in xrange(pat_x):

            if arr[running_y+y][running_x+x] != pat[running_y][running_x]:

                return False

     

    return True

             

             

def solveBruteForce(arr, pat, arr_y, arr_x, pat_y, pat_x):

    for y in xrange(arr_y-pat_y+1):

        for x in xrange(arr_x-pat_x+1):

            if matchSubArray(arr, pat, x, y, pat_y, pat_x):

                return True

     

    return False

     

if __name__ == '__main__':

    t = int(raw_input())

    for _ in xrange(t):

        arr_y, arr_x = map(int, raw_input().split())

        arr = [0] * arr_y

        for y in xrange(arr_y):

            arr[y] = list(raw_input())

         

        pat_y, pat_x = map(int, raw_input().split())

        pat = [0] * pat_y

        for y in xrange(pat_y):

            pat[y] = list(raw_input())

         

        if solveBruteForce(arr, pat, arr_y, arr_x, pat_y, pat_x):

            print "YES"

        else:

            print "NO"

http://codereview.stackexchange.com/questions/86275/hackerrank-grid-search-challenge#
Read full article from HackerRank 'The Grid Search' Solution | MartinKysel.com