HackerRank The Grid Search Solution

Hello Programmers, In this post, you will know how to solve the HackerRank The Grid Search Solution. This problem is a part of the HackerRank Algorithms Series.

Ezoicreport this adHackerRank The Grid Search Solution
HackerRank The Grid Search Solution

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Hackerrank by yourself. If you find any difficulty after trying several times, then you can look for solutions.

HackerRank The Grid Search Solution

Ezoicreport this adTask

Given an array of strings of digits, try to find the occurrence of a given pattern of digits. In the grid and pattern arrays, each string represents a row in the grid. For example, consider the following grid:

1234567890  
0987654321  
1111111111  
1111111111  
2222222222  

The pattern array is:

876543  
111111  
111111

The pattern begins at the second row and the third column of the grid and continues in the following two rows. The pattern is said to be present in the grid. The return value should be YES or NO, depending on whether the pattern is found. In this case, return YES.

Function Description

Complete the gridSearch function in the editor below. It should return YES if the pattern exists in the grid, or NO otherwise.

gridSearch has the following parameter(s):

  • string G[R]: the grid to search
  • string P[r]: the pattern to search for

Input Format

The first line contains an integer t, the number of test cases.

Each of the t test cases is represented as follows:
The first line contains two spaceseparated integers R and C, the number of rows in the search grid G and the length of each row string.
This is followed by R lines, each with a string of C digits that represent the grid G.
The following line contains two space-separated integers, r and c, the number of rows in the pattern grid P and the length of each pattern row string.
This is followed by r lines, each with a string of c digits that represent the pattern grid P.

Returns

  • string: either YES or NO

Constraints

  • 1 <= t <= 5
  • 1 <= RrCc <= 1000
  • 1 <= r <= R
  • 1 <= c <= C

Sample Input

2
10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530
15 15
400453592126560
114213133098692
474386082879648
522356951189169
887109450487496
252802633388782
502771484966748
075975207693780
511799789562806
404007454272504
549043809916080
962410809534811
445893523733475
768705303214174
650629270887160
2 2
99
99

Sample Output

YES
NO

Explanation

The first test in the input file is:

10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530

The pattern is present in the larger grid as marked in bold below.

7283455864  
6731158619  
8988242643  
3830589324  
2229505813  
5633845374  
6473530293  
7053106601  
0834282956  
4607924137  

The second test in the input file is:

15 15
400453592126560
114213133098692
474386082879648
522356951189169
887109450487496
252802633388782
502771484966748
075975207693780
511799789562806
404007454272504
549043809916080
962410809534811
445893523733475
768705303214174
650629270887160
2 2
99
99

The search pattern is:

99
99

This pattern is not found in the larger grid.

HackerRank The Grid Search Solution

The Grid Search Solution in C

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
static void print_grid(char **grid, int R, int C) {
  for (int i = 1; i <= R; ++i) {
    fprintf(stderr, "%s\n", grid[i]);
  }
}
static char **get_grid(int R, int C) {
  char **grid = malloc((R+1)*sizeof(*grid));
  for (int i = 1; i <= R; ++i) {
    grid[i] = malloc((C+2)*sizeof(*grid[i]));
    scanf("%s", grid[i]);
  }
  return grid;
}
static void free_grid(char **grid, int R, int C) {
  for (int i = 1; i <= R; ++i) {
    free(grid[i]);
  }
  free(grid);
}
int main() {
  int num_tests = 0;
  scanf("%d", &num_tests);
  for (int i = 0; i < num_tests; ++i) {
    int R, C;
    scanf("%d %d", &R, &C);
    char **grid = get_grid(R, C);
    //print_grid(grid, R, C);
    int r, c;
    scanf("%d %d", &r, &c);
    char **pattern = get_grid(r, c);
    //print_grid(pattern, r, c);
    int found = 0;
    for (int i = 1; i <= R-r+1; ++i) {
      for (int j = 0; j <= C-c; ++j) {
        found = 1;
        int abort = 0;
        for (int a = 0; a < r; ++a) {
          if (abort) break;
          for (int b = 0; b < c; ++b) {
            if (grid[i+a][j+b] != pattern[a+1][b]) {
              abort = 1;
              found = 0;
              break;
            }
          }
        }
        if (found) break;
      }
      if (found) break;
    }
    printf("%s\n", found ? "YES" : "NO");
    free_grid(grid, R, C);
    free_grid(pattern, r, c);
  }
  return 0;
}

The Grid Search Solution in Cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
typedef unsigned int LL;
struct MatHash {
    typedef unsigned int LL;
    #define MAXN 1001
    #define MAXM 1001
    #define TIME 2
    static LL P[TIME], Q[TIME], MOD[TIME];
    static LL powerP[TIME][MAXN], powerQ[TIME][MAXM];
    int n, m;
    int mat[MAXN][MAXM];
    LL h[TIME][MAXN][MAXM];//???hash?
    static void init(int id) {
        powerP[id][0] = 1;
        for (int i = 1; i < MAXN; i++) {
            powerP[id][i] = (powerP[id][i - 1] * P[id]);
        }
        powerQ[id][0] = 1;
        for (int i = 1; i < MAXM; i++) {
            powerQ[id][i] = (powerQ[id][i - 1] * Q[id]);
        }
    }
    void inithash(int id) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                h[id][i][j] = (mat[i][j] + 3) * powerP[id][n - 1 - i] * powerQ[id][m - 1 - j];
                if (i) h[id][i][j] = (h[id][i][j] + h[id][i - 1][j]);
                if (j) h[id][i][j] = (h[id][i][j] + h[id][i][j - 1]);
                if (i && j) h[id][i][j] = (h[id][i][j] - h[id][i - 1][j - 1]);
            }
        }
    }
    LL gethash(int x1, int y1, int x2, int y2, int id) {
        LL ret = h[id][x2][y2];
        if (x1) ret = (ret - h[id][x1 - 1][y2]);
        if (y1) ret = (ret - h[id][x2][y1 - 1]);
        if (x1 && y1) ret = (ret + h[id][x1 - 1][y1 - 1]);
        ret = (ret * powerP[id][x1]);
        ret = (ret * powerQ[id][y1]);
        return ret;
    }
    LL resize(int x1, int y1, int x2, int y2, int id, int _n, int _m) {
        LL ret = gethash(x1, y1, x2, y2, id);
        ret = ret * powerP[id][_n - n] * powerQ[id][_m - m];
        return ret;
    }
    void input() {
        for (int i = 0; i < n; i++) {
            getchar();
            for (int j = 0; j < m; j++) {
                mat[i][j] = getchar() - '0';
            }
        }
    }
}A, B;
LL MatHash::P[TIME], MatHash::Q[TIME], MatHash::MOD[TIME];
LL MatHash::powerP[TIME][MAXN], MatHash::powerQ[TIME][MAXM];
int main() {
    MatHash::P[0] = 393241, MatHash::Q[0] = 784633, MatHash::MOD[0] = 805306457;
    MatHash::P[1] = 784633, MatHash::Q[1] = 111117, MatHash::MOD[1] = 402653189;
    for (int i = 0; i < TIME; i++) {
        MatHash::init(i);
    }
    int cases;
    scanf("%d", &cases);
    for (int T = 0; T < cases; T++) {
        scanf("%d %d", &A.n, &A.m);
        A.input();
        for (int i = 0; i < TIME; i++) {
            A.inithash(i);
        }
        scanf("%d %d", &B.n, &B.m);
        B.input();
        for (int i = 0; i < TIME; i++) {
            B.inithash(i);
        }
        bool yes = false;
        for (int id = 0; id < TIME; id++) {
            B.inithash(id);
            LL val = B.resize(0, 0, B.n - 1, B.m - 1, id, A.n, A.m);
            for (int i = B.n - 1; i < A.n; i++) {
                for (int j = B.m - 1; j < A.m; j++) {
                    if (A.gethash(i - B.n + 1, j - B.m + 1, i, j, id) == val) {
                        yes = true;
                        break;
                    }
                }
                if (yes) break;
            }
        }
        puts(yes ? "YES" : "NO");
    }
}

The Grid Search Solution in Java

import java.util.*;
public class Solution {
  public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);
    
    int T = cin.nextInt();
    for (int set = 0; set < T; set++) {
      int R = cin.nextInt();
      int C = cin.nextInt();
      cin.nextLine(); //Skip end-of-line character to get to the grid
      
      String[] grid = new String[R];
      for (int i = 0; i < R; i++)
        grid[i] = cin.nextLine();
      
      int r = cin.nextInt();
      int c = cin.nextInt();
      cin.nextLine();
      String[] subgrid = new String[r];
      for (int i = 0; i < r; i++)
        subgrid[i] = cin.nextLine();
      
      boolean found = false;
      for (int i = 0; !found && i < R-r + 1; i++) { //iterates over "top rows" for the subgrid.
        for (int j = 0; !found && j < C-c + 1; j++) { //iterates over "left-cols" for the subgrid.
         // System.err.println("Now checking "+ grid[i].substring(j, j+c));
          if (subgrid[0].equals(grid[i].substring(j, j+c))) { //We've found a first row!  so, let's check all the rows below
            System.err.println("We found a substring at row=" + i + ", col=" + j);
            found = true;
            for (int k = i+1; found && k < r + i; k++) {
              System.err.println("  The substring = " + grid[k].substring(j, j+c));
              found &= subgrid[k-i].equals(grid[k].substring(j, j+c));
            }
          }
        }
      }
      
      System.out.println(found ? "YES" : "NO");
      
    }
  }
}
Ezoicreport this ad

The Grid Search Solution in Python

def find_all(string, substring):
    index = []
    L = len(string)
    l = len(substring)
    for i in xrange(L-l+1):
        if string[i:i+l] == substring:
            index.append(i)
    return index
def find_pattern(grid, pattern):
    R, C = len(grid), len(grid[0])
    r, c = len(pattern), len(pattern[0])
    for i in xrange(R-r+1):
        indeces = find_all(grid[i], pattern[0])        
        if indeces:
            for idx in indeces:
                for j in xrange(i+1, i+r):
                    if pattern[j-i] != grid[j][idx:idx+c]:
                        break
                else:
                    print 'YES'
                    return
    print 'NO'
    return
 
def main():
    T = input()
    for i in xrange(T):
        R, C = map(int, raw_input().strip().split())
        N = R * C
        grid = []
        for k in xrange(R):
            grid.append(raw_input().strip())
        r, c = map(int, raw_input().strip().split())
        pattern = []
        for k in xrange(r):
            pattern.append(raw_input().strip())
        find_pattern(grid, pattern)
if __name__ == '__main__':
    main()

The Grid Search Solution using JavaScript

function cint (str) {
    return parseInt(str);
}
function processData(input) {
    var cases = [], lines = input.trim().split('\n'), lineNo = 1, dims, haystack, needle;
    for (var i = 0; i < parseInt(lines[0]); i++) {
        dims = lines[lineNo++].split(' ').map(cint);
        haystack = [];
        needle = [];
        for (var j = 0; j < dims[0]; j++) {
            haystack.push(lines[lineNo++].split('').map(cint));
        }
        dims = lines[lineNo++].split(' ').map(cint);
        for (var j = 0; j < dims[0]; j++) {
            needle.push(lines[lineNo++].split('').map(cint));
        }
        cases.push({haystack: haystack, needle: needle});
    }
    
    process.stdout.write(cases.map(processCase).join('\n'));
}
function processCase(c) {
    var jumpAmt = {
        0: [1, 1],
        1: [1, 1],
        2: [1, 1],
        3: [1, 1],
        4: [1, 1],
        5: [1, 1],
        6: [1, 1],
        7: [1, 1],
        8: [1, 1],
        9: [1, 1]},
        H = c.haystack.length,
        W = c.haystack[0].length,
        h = c.needle.length,
        w = c.needle[0].length,
        searchElem = c.needle[h - 1][w - 1],
        minVertJump, jump,
        i, j, k, l, m, n;
    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            jump = jumpAmt[c.needle[i][j]];
            jumpAmt[c.needle[i][j]] = [Math.min(jump[0], h - i), Math.min(jump[1], w - j)];
        }
    }
    
    for (i = H - 1; i >= h - 1; i -= minVertJump) {
        minVertJump = 1;
        cell: for (j = W - 1; j >= w - 1; j -= jump[1]) {
            if (c.haystack[i][j] === searchElem) {
                for (k = 0, m = i - h + 1; m <= i; k++, m++) {
                    for (l = 0, n = j - w + 1; n <= j; l++, n++) {
                        // console.dir({i: i, j: j, k: k, l: l, m: m, n: n});
                        if (c.haystack[m][n] !== c.needle[k][l]) {
                            continue cell;
                        }
                    }
                }
                return 'YES';
            }
            jump = jumpAmt[c.haystack[i][j]];
            minVertJump = Math.min(minVertJump, jump[0]);
        }
    }
    
    return 'NO';
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});
process.stdin.on("end", function () {
   processData(_input);
});

The Grid Search Solution in Scala

object Solution {
    def main(args: Array[String]) {
        val t = readInt()
        for (_ <- 0 until t) {
            val Array(r, c) = readLine().split(" ").map(_.toInt)
            val big = (0 until r).map(_ => readLine())
            val Array(rr, cc) = readLine().split(" ").map(_.toInt)
            val small = (0 until rr).map(_ => readLine())
            val isOk = (0 to r - rr).exists(i => {
                val j = big(i).indexOf(small(0))
                if (j < 0) {
                    false
                } else {
                    val end = j + cc
                    (1 until rr).forall(k => big(i + k).substring(j, end) == small(k))
                }
            })
            println(if (isOk) "YES" else "NO")
        }
    }
}

The Grid Search Solution in Pascal

var t, rr, cc, r, c: word;
    p, s: array [1..1000, 1..1000] of char;
    i, j, i0, j0: word;
    ok, br: boolean;
begin
  readln(t);
  while (t>0) do begin
    readln(rr, cc);
    for i:= 1 to rr do begin
      for j:= 1 to cc do begin
        read(p[i, j]);
      end;
      readln;
    end;
    readln(r, c);
    for i:= 1 to r do begin
      for j:= 1 to c do begin
        read(s[i, j]);
      end;
      readln;
    end;
    ok:= false;
    for i0:= 1 to rr-r+1 do begin
      for j0:= 1 to cc-c+1 do begin
        br:= false;
        for i:= 1 to r do begin
          for j:= 1 to c do begin
            if s[i, j]<>p[i0+i-1,j0+j-1] then begin
              br:= true;
              break;
            end;  
          end;
          if br then break;
        end;
        if not br then begin
          ok:= true;
          break;
        end;  
      end;
      if ok then break;
    end;
    if ok then writeln('YES')
          else writeln('NO'); 
    dec(t);      
  end;
end.

Disclaimer: This problem (The Grid Search) is generated by HackerRank but the Solution is Provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.

Next: HackerRank Encryption Solution

Sharing Is Caring

Leave a Comment

Ezoicreport this ad