Skip to content
  • Home
  • Contact Us
  • About Us
  • Privacy Policy
  • DMCA
  • Linkedin
  • Pinterest
  • Facebook
thecscience

TheCScience

TheCScience is a blog that publishes daily tutorials and guides on engineering subjects and everything that related to computer science and technology

  • Home
  • Human values
  • Microprocessor
  • Digital communication
  • Linux
  • outsystems guide
  • Toggle search form
HackerRank The Grid Search Problem Solution

HackerRank The Grid Search Problem Solution

Posted on April 19, 2023April 19, 2023 By Yashwant Parihar No Comments on HackerRank The Grid Search Problem Solution

In this post, we will solve HackerRank The Grid Search Problem Solution.

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 space-separated 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, 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

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 Problem Solution
HackerRank The Grid Search Problem Solution

Table of Contents

  • The Grid Search C Solution
  • The Grid Search C++ Solution
  • The Grid Search C Sharp Solution
  • The Grid Search Java Solution
  • The Grid Search Javascript Solution
  • The Grid Search Python Solution

The Grid Search C Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

#define MAX_GRID_SIZE           1000

int PatternExists
    (
    short rows_g,
    short cols_g,
    short rows_p,
    short cols_p,
    char g[MAX_GRID_SIZE][MAX_GRID_SIZE+1],
    char p[MAX_GRID_SIZE][MAX_GRID_SIZE+1]
    )
{
    long hash_g, hash_p, i, j, k, l, result, count = 0;

    for (i = 0, hash_p = 0; i < cols_p; i++)
        hash_p += p[0][i] - '0';

    for (i = 0, result = 0; i < (rows_g - (rows_p - 1)); i++)
    {
        for (j = 0, hash_g = 0; j < cols_g; j++)
        {
            hash_g += g[i][j] - '0';
            if (j >= (cols_p - 1))
            {
                if (j > (cols_p - 1))
                    hash_g -= g[i][j - cols_p] - '0';
                if (hash_g == hash_p)
                {
                    for (k = 0; k < rows_p; k++)
                    {
                        for (l = 0; l < cols_p; l++)
                        {
                            if (g[i + k][j - (cols_p - 1) + l] == p[k][l])
                                result = 1;
                            else
                            {
                                result = 0;
                                break;
                            }
                        }
                        if (!result)
                            break;
                    }
                    if (result)
                        return 1;
                }
            }
        }
    }
    return 0;
}

int main() {
    short num_test_cases, R, C, r, c, i, j;
    char grid[MAX_GRID_SIZE][MAX_GRID_SIZE+1];
    char pattern[MAX_GRID_SIZE][MAX_GRID_SIZE+1];
    scanf("%hi", &num_test_cases);

    for (i = 0; i < num_test_cases; i++)
    {
        scanf("%hi %hi", &R, &C);
        for (j = 0; j < R; j++)
            scanf("%s", grid[j]);
        scanf("%hi %hi", &r, &c);
        for (j = 0; j < r; j++)
            scanf("%s", pattern[j]);
        if (PatternExists(R, C, r, c, grid, pattern))
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

The Grid Search C++ Solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void test(vector<string>& grid, vector<string>& ptrn, int rg, int cg, int rp, int cp) {
    const int kmax = rg - rp;
    const int jmax = cg - cp;
    for (int k = 0; k <= kmax; ++k) {
        for (int j = 0; j <= jmax; ++j) {
            bool mismatch = false;
            for (int ik = 0; ik < rp; ++ik) {
                for (int ij = 0; ij < cp; ++ij) {
                    if (grid[ik + k][ij + j] != ptrn[ik][ij]) {
                        mismatch = true;
                        break;
                    }
                }
                if (mismatch == true)
                    break;
            }
            if (mismatch == false) {
                cout << "YES" << endl;
                return;
            }
        }
    }
    cout << "NO" << endl;
    return;    
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int t; cin >> t;
    
    for (int i = 0; i < t; ++i) {
        
        int rg; cin >> rg;
        int cg; cin >> cg;
        vector<string> grid(rg);
        for (int j = 0; j < rg; ++j) {
            cin >> grid[j];
            //cerr << grid[j] << endl;
        }
        //cerr << endl;
        
        int rp; cin >> rp;
        int cp; cin >> cp;
        vector<string> ptrn(rp);
        for (int j = 0; j < rp; ++j) {
            cin >> ptrn[j];
            //cerr << ptrn[j] << endl;
        }
        //cerr << endl;
        
        test(grid, ptrn, rg, cg, rp, cp);
    }
    return 0;
}

The Grid Search C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
    static void Main(String[] args) {
        int T = int.Parse(Console.ReadLine());
        string[] vals;
        for(int t=0; t<T; ++t){
            vals = Console.ReadLine().Split(' ');
            int R = int.Parse(vals[0]);
            int C = int.Parse(vals[1]);
            string[] G = new string[R];
            for(int i=0; i<R; ++i)
                G[i] = Console.ReadLine().Substring(0, C);
            
            vals = Console.ReadLine().Split(' ');
            int r = int.Parse(vals[0]);
            int c = int.Parse(vals[1]);
            string[] P = new string[r];
            for(int i=0; i<r; ++i)
                P[i] = Console.ReadLine().Substring(0, c);
            
            int j = 0;
            int offset = 0;
            bool b = false;
            while(j<=R-r && !b){
                int idx = G[j].IndexOf(P[0], offset);
                
                if (idx >= 0){
                    bool found = true;
                   for(int k=1; k<r; ++k)
                       if(G[j+k].IndexOf(P[k], offset) != idx){
                           found = false;
                           break;
                       }
                    if (found){
                        Console.WriteLine("YES");
                        b = true;
                    }
                    else offset =idx+1;
                }
                else {++j; offset = 0;}             
            }
            if (!b)
                Console.WriteLine("NO");
        }
    }
}

The Grid Search Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'gridSearch' function below.
     *
     * The function is expected to return a STRING.
     * The function accepts following parameters:
     *  1. STRING_ARRAY G
     *  2. STRING_ARRAY P
     */

    public static String gridSearch(List<String> G, List<String> P) {
        return solve(G, P, 0) ? "YES" : "NO";
    }

    private static boolean solve(List<String> G, List<String> P, int rowNum) {

        if (G.size() - rowNum < P.size()) return false;

        String row = G.get(rowNum);
        int len = row.length();

        boolean found = false;
        for (int i=0; i<len && !found; i++) {

            boolean hasInit = getInitPosition(row, P.get(0), i);

            if (hasInit) {
                // System.out.println(String.format("init: (%d,%d)", rowNum, i));
                found = check(rowNum, i, G, P);
            }
        }
        if (found) return true;
        else return solve( G, P, rowNum+1);
    }


    private static boolean getInitPosition(String gRow, String firstRowPattern, int colNum) {

        if (gRow.length() - colNum < firstRowPattern.length()) return false;
        if (gRow.charAt(colNum) == firstRowPattern.charAt(0)) return true;
        else return false;
    }

    private static boolean check(int rowNum, int colNum, List<String> G, List<String> P) {

        int s=0;
        for (int w=rowNum; w<P.size()+rowNum; w++) {

            int a=0;
            for (int q=colNum; q<P.get(0).length()+colNum; q++) {

                char g = G.get(w).charAt(q);
                char p = P.get(s).charAt(a);
                if (g != p) {
                    return false;
                }
                a++;
            }
            s++;
        }

        return true;
    }


}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = Integer.parseInt(bufferedReader.readLine().trim());

        IntStream.range(0, t).forEach(tItr -> {
            try {
                String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

                int R = Integer.parseInt(firstMultipleInput[0]);

                int C = Integer.parseInt(firstMultipleInput[1]);

                List<String> G = IntStream.range(0, R).mapToObj(i -> {
                    try {
                        return bufferedReader.readLine();
                    } catch (IOException ex) {
                        throw new RuntimeException(ex);
                    }
                })
                    .collect(toList());

                String[] secondMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

                int r = Integer.parseInt(secondMultipleInput[0]);

                int c = Integer.parseInt(secondMultipleInput[1]);

                List<String> P = IntStream.range(0, r).mapToObj(i -> {
                    try {
                        return bufferedReader.readLine();
                    } catch (IOException ex) {
                        throw new RuntimeException(ex);
                    }
                })
                    .collect(toList());

                String result = Result.gridSearch(G, P);

                bufferedWriter.write(result);
                bufferedWriter.newLine();
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        bufferedReader.close();
        bufferedWriter.close();
    }
}

The Grid Search Javascript Solution

function processData(input) {
    const lines = input.split('\n'),
          T = parseInt(lines.shift(), 10);
    
    for (var i = 0; i < T; i++) {
        var RC = lines.shift().split(' ').map(Number),
            R = RC[0],
            C = RC[1],
            search = lines.splice(0, R),
            rc = lines.shift().split(' ').map(Number),
            r = rc[0],
            c = rc[1],
            pattern = lines.splice(0, r);
        
        //console.log(R,C,search,r,c,pattern);
        
        console.log(gridSearch(search, pattern, R, C, r, c) ? 'YES' : 'NO');
    }
}

function gridSearch(search, pattern, R, C, r, c) {
    var found = false;
    for (var i=0; i <= (R-r); i++) {
        var row = search[i],
            match = row.indexOf(pattern[0]);
        //console.log(row, match, R-r, pattern[0]);
        if (match !== -1) {
            found = pattern.every(function(str, j) {
                if (j==0) return true;
                var line = search[i + j];
                if (!line || (c-match) > str.length) return false;
                //console.log(line.substr(match, c), str);
                return (line.substr(match, c) === str);
            });
            if (found) {
                break;
            }
        }
    }
    return found;
}

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 Python Solution

t = int(input())

for _ in range(t):
    R, C = (int(x) for x in input().split())
    G = [input() for _ in range(R)]

    r, c = (int(x) for x in input().split())
    P = [input() for _ in range(r)]
    
    for row in range(R - r + 1):
        index = 0
        found = False
        while index < C - c + 1:
            x = G[row].find(P[0], index)
            if x >= 0:
                y = 1
                found = True
                while y < r:
                    if G[row+y][x:x+c] != P[y]:
                        found = False
                        break
                    y += 1
                if found: break
            else:
                break
            index = x + 1
        if found: break

    if found:
        print("YES")
    else:
        print("NO")

Other Solutions

  • HackerRank Happy Ladybugs Problem Solution
  • HackerRank Strange Counter Problem Solution
c, C#, C++, HackerRank Solutions, java, javascript, python Tags:C, cpp, CSharp, Hackerrank Solutions, java, javascript, python

Post navigation

Previous Post: HackerRank Manasa and Stones Problem Solution
Next Post: HackerRank Happy Ladybugs Problem Solution

Related Posts

HackerRank Insertion Sort - Part 2 Problem Solution HackerRank Insertion Sort – Part 2 Solution c
HackerRank Minimum MST Graph Problem Solution HackerRank Minimum MST Graph Solution c
HackerRank Task Scheduling Problem Solution HackerRank Task Scheduling Problem Solution c
HackerRank Brick Tiling Problem Solution HackerRank Brick Tiling Problem Solution c
HackerRank Substring Diff Problem Solution HackerRank Substring Diff Problem Solution c
HackerRank Pairs Problem Solution HackerRank Pairs Problem Solution c

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Pick Your Subject
Human Values

Copyright © 2023 TheCScience.

Powered by PressBook Grid Blogs theme