The Grid Search

Question

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"

Please provide any tips from efficiency to readability.

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

int main () {
    int testCases;
    cin >> testCases;

    // Iterate through each test case
    for (int i = 0; i < testCases; i++) {
        /* MAIN GRID */
        // Iterate through each row of the main grid and store it in 'grid' a vector of strings
        int rows, cols;        
        cin >> rows >> cols;
        vector<string> grid(rows);
        for (int j = 0; j < rows; j++) {
           cin >> grid[j];
        }

        /* PATTERN GRID */
        // Iterate through each row of the pattern grid and store it in 'pattern' a vector of strings
        int patternRows, patternCols;
        cin >> patternRows >> patternCols;
        vector<string> pattern(patternRows);
        for (int j = 0; j < patternRows; j++) {
           cin >> pattern[j];
        }

        /* GRID INSPECTION */
        bool found = false; // To know when to leave the loop and what answer to return
        // Iterate through each row until the pattern would extend off the grid
        for (int j = 0; j <= (rows - patternRows); j++) {
            // Iterate through each column until the pattern would extend off the grid
            for (int k = 0; k <= (cols - patternCols); k++) {
                // Check if there is a number in the grid equal to the first number in the pattern
                if (grid[j][k] == pattern[0][0]) {
                    bool wrong = false; // To break out if wrong is false at the end of checking the lines
                    // Begin cross checking each row with the pattern, until you hit the amount of pattern rows
                    for (int l = 0; l < patternRows; l++) {
                        // Set wrong to true and break out if the pattern row is not the same as the grid row --
                        // stripped at the correct spot to be the same length as the pattern row.
                        // E.g. if the pattern row was '9729' and the grid row was '209729142' get the substring --
                        // that is the same length as the pattern row (4) and starting at the correct place found --
                        // out by the checking of the first number in the pattern to this number in the row -- 
                        // then go downwards.
                        if (pattern[l] != grid[l + j].substr(k, patternCols)) { 
                            wrong = true;
                            break;
                        }
                    }
                    // If the whole test passed without any inconsistencies set found to true and begin the break chain 
                    if (!wrong) {
                        found = true;
                        break;
                    }
                }
            }
            // If found is false continue breaking
            if (found) {
                break;
            }
        }

        /* ANSWER RETURN */
        if (found == true) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }

    return 0;
}

theosza · Accepted Answer · 2016-01-18 09:35:25Z

For readability I'd suggest breaking the algorithm up into a number of functions. Any time you find you need to write "heading" comments, it suggests that the code under that heading could go into a separate function. Breaking the code up into functions like this makes the code easier to reason about and, in my experience, easier to test and debug.

Your main() could look like this:

int main () {
  int testCases;
  std::cin >> testCases;
  for (int i = 0; i < testCases; ++i) {
    std::vector<std::string> mainGrid = ReadGrid(std::cin);
    std::vector<std::string> pattern = ReadGrid(std::cin);
    if (IsPatternInGrid(mainGrid, pattern)) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
  }
}

While the function ReadGrid would be simple enough, the new IsPatternInGrid function would still be quite complex and could possibly also benefit from factoring out some its code into yet another function.

Other things that I changed in the block of code above aren't as important for readability but are common for coding standards:

No using namespace std; - use std:: where needed.
Prefer '\n' over std::endl except when flushing the output buffer is explicitly needed.
No need for a return 0 as it is the default return value for int main.

Naming standards vary greatly. My preference is for boolean functions to have names that are like questions, e.g. I prefer IsEmpty() rather than Empty() though std containers prefer the latter. — theosza
– theosza, Commented Jan 18, 2016 at 10:20
isEmpty is a member function, so it readsnaturally as "if collection is empty" But your function is free over it's arguments. The English word order is "if pattern is in grid", so I prefer the code to read the same: "if (patternIsInGrid(pattern, grid))". — kevin cline
– kevin cline, Commented Jan 19, 2016 at 2:39

Caridorc · Accepted Answer · 2016-01-17 21:38:09Z

Write a function to read in the matrix

These two blocks of code are too similar:

    int rows, cols;        
    cin >> rows >> cols;
    vector<string> grid(rows);
    for (int j = 0; j < rows; j++) {
       cin >> grid[j];
    }

And:

    int patternRows, patternCols;
    cin >> patternRows >> patternCols;
    vector<string> pattern(patternRows);
    for (int j = 0; j < patternRows; j++) {
       cin >> pattern[j];
    }

You should write a function to read in a matrix from the input and use it twice to reduce code duplication.

Stack Exchange Network

The Grid Search

2 Answers 2

You must log in to answer this question.

Linked

Hot Network Questions

The Grid Search

2 Answers 2

You must log in to answer this question.

Linked

Related

Hot Network Questions