Match Multiple Patterns in 2D Array and Return (x,y) Coordinates of the highest pattern

Question

Problem Description

We are given 2 arrays: 1 array representing the image and containing the patterns to be match and another one representing the pattern. Each image is represented as an vector strings, where each element represents a line of pixels in the image, and each character represents a pixel.

The objective is to return the position (x, y) of the pattern in the image, or [-1, -1] if the pattern does not exist in the image. If the pattern appears several times in the image, return the highest position (the smallest x), in case of equality, then return the furthest left (the smallest y). The position of the pattern is determined by the (x, y) coordinates. x representing the row and y representing the column. the [0, 0] coordinates represent the top left corner.

---

Source Code

In the following code. I added 4 test cases: no pattern exists, 1 pattern exists, 2 pattern exists but at different levels or rows and 2 patterns exists at the same level or same row.

Since we might have patterns that are on the same level, I also added a vector called visited. In case of a pattern matching it will return all the pixels or points representing the location of the pattern in the image. We don't want to visit the same location multiple times.

As for the return of the coordinates. I thought that we will always want to return the first pattern in the image. Since it's the highest, so I added a check firstMatch. Always take the coordinates of the first pattern.

---

Expected Results

- Case 1: [-1, -1]
- Case 2: [2, 1]
- Case 3: [2, 1]
- Case 4: [0, 2]

---

Questions

• Is the visited logic that I added to the code, correct? Or should tag as visited all the visited cells?
• Is the logic that is used to return always the first match correct? I thought I really wanted to make it as simple as possible. I actually need to find all the patterns because I also need to know the number of matched patterns later on.

---

// Online C++ compiler to run C++ program online
#include <iostream>
#include <vector>
#include <string>
#include <utility>

struct Point{
    int x;
    int y;
};

bool isMatch(int row, int col, const std::vector<std::string> & pattern, const std::vector<std::string> & image,std::vector<Point> & visited) {
    
    int k       = 0; 
    int l       = 0;
    int tmpRow = row;
    int tmpCol = col;
    
    //Check for boundary
    if(row + pattern.size() - 1 > image.size()) { return false; }
    if(col + pattern[0].size() -1 > image[0].size()) { return false;}
    
    while(k < pattern.size()) {
        while(l < pattern[k].size()) {
            if(image[row][col] != pattern[k][l]){
                return false;
            } 
            col++;
            l++;
        }
        row++;
        k++;
    }
    
    //Pattern match. Fill visited points
    for(int i = tmpRow; i < row; ++i){
        for(int j = tmpCol; j < col; ++j){
            visited.push_back({i,j});
        }
    }
    return true;
}

bool isPointVisited(int row, int column, const std::vector<Point> & visited) {
    for(const auto& v:visited) {
        if(row == v.x && column == v.y) {
            return true;
        }
    }
    return false;
}

std::pair<int,int> patternExists(const std::vector<std::string> & image, const std::vector<std::string> & pattern){
   int firstX      = -1;
   int firstY      = -1;
   bool firstMatch = true;

   std::vector<Point> visited;

   for (int row = 0; row <  image.size(); row++) {
      for (int col = 0; col <  image[row].size(); col++) {
          if (!isPointVisited(row, col, visited) && image[row][col] == pattern[0][0]) {
              int tmpx = row;
              int tmpy = col;
              if(isMatch(row, col, pattern, image, visited)) {
                  if(firstMatch) {
                      firstX = tmpx;
                      firstY = tmpy;
                  }
                  firstMatch = false;
              } 
        }
      }
    } 
    return std::make_pair(firstX, firstY);
}

int main() {
  
  //Case 1: Pattern doesn't exist    
  std::vector<std::string> rectangle  = {"0000","0000","0000","0000","0000","0000","0000"};
  std::vector<std::string> recPattern = {"11","11"};
  
  std::pair<int, int> coordinates = patternExists(rectangle, recPattern);
  std::cout << "First X: " << coordinates.first << std::endl;
  std::cout << "First Y: " << coordinates.second << std::endl;
  
  //Case 2: Pattern exists
  rectangle  = {"0000","0000","0110","0110","0000"};
  recPattern = {"11","11"};
 
  coordinates = patternExists(rectangle, recPattern);
  std::cout << "First X: " << coordinates.first << std::endl;
  std::cout << "First Y: " << coordinates.second << std::endl;
  
  //Case 3: Multiple patterns exist at different levels
  rectangle  = {"0000","0000","0110","0110","0000","0110","0110"};
  recPattern = {"11","11"};
  
  coordinates = patternExists(rectangle, recPattern);
  std::cout << "First X: " << coordinates.first << std::endl;
  std::cout << "First Y: " << coordinates.second << std::endl;
  
  //Case 4: Multiple patterns exist at same level
  rectangle  = {"00110011","00110011"};
  recPattern = {"11","11"};
  
  coordinates = patternExists(rectangle, recPattern);
  std::cout << "First X: " << coordinates.first << std::endl;
  std::cout << "First Y: " << coordinates.second << std::endl;
    
  return 0;
}

Answer 1

Your solution is overly complicated and not very efficient. First, since we are dealing with strings, you can use std::string::find() to check if a row from pattern occurs withing a row of image. Once you have a match for the first row of pattern, you can then quickly check if the subsequent rows of image contain the subsequent rows of pattern in the same place, using std::string::compare(). If any match fails you should try the next position.

There is also no need to keep track of which points you have visited, and the way you keep track of visited points is wrong anyway. Here is a test case that your code will give the wrong answer for:

rectangle  = {"111","011"};
recPattern = {"11","11"};

The result should be 0, 1, whereas your code outputs 0, 0. Here is an example of how you can rewrite the code:

std::pair<int,int> patternExists(const std::vector<std::string> & image, const std::vector<std::string> & pattern) {
    // Loop over all rows of the image where the first row of pattern could match
    for (std::size_t row = 0; row <= image.size() - pattern.size(); ++row) {
        std::size_t col = 0;

        // Loop over all positions where the first row of the pattern matches
        while ((col = image[row].find(pattern[0], col)) != std::string::npos) {
             bool match = true;

            // Check that all subsequent rows of the pattern match as well
            for (std::size_t prow = 1; prow < pattern.size(); ++prow) {
                if (image[row + prow].compare(col, pattern[prow].size(), pattern[prow])) {
                      match = false;
                      break;
                }
            }

            // We found a match, return the coordinates
            if (match)
                return {row, col};

            // If not, find the next column with a potential match
            col++;
        }
    }

    // No matches found
    return {-1, -1};
}

Note that I used std::size_t instead of int, since the size of a vector or string might be larger than an int can represent. Ideally, the return value should also be a pair of std::size_t's. You can still use -1 as the constant to indicate that there is no match, just like std::string::npos.