How to match segments of ASCII art in ASCII art?

Question

I am participating in a programming competition in which I will have a choice for each problem: whether to use Python or C ++, therefore I am open to solving in any language - any language is best suited for this problem.

The URL of the previous problem I'm stuck with is http://progconz.elena.aut.ac.nz/attachments/article/74/10%20points%20Problem%20Set%202012.pdf , Problem F ("Maps" )

This is mainly due to the coincidence of occurrences of a small part of ASCII art in a large one. In C ++, I can make a vector for every piece of ASCII art. The problem is how to match it when the smaller part is multi-line.

I have no idea how to do this. I don't need all the code written for me, just the idea of ​​the logic needed for the problem.

Thanks for any help.

Here is what I have so far:

#include <cstdlib> #include <iostream> #include <string> #include <algorithm> #include <vector> using namespace std; int main( int argc, char** argv ) { int nScenarios, areaWidth, areaHeight, patternWidth, patternHeight; cin >> nScenarios; for( int a = 0; a < nScenarios; a++ ) { //get the pattern info and make a vector cin >> patternHeight >> patternWidth; vector< vector< bool > > patternIsBuilding( patternHeight, vector<bool>( patternWidth, false ) ); //populate data for( int i = 0; i < patternHeight; i++ ) { string temp; cin >> temp; for( int j = 0; j < patternWidth; j++ ) { patternIsBuilding.at( i ).at( j ) = ( temp[ j ] == 'X' ); } } //get the area info and make a vector cin >> areaHeight >> areaWidth; vector< vector< bool > > areaIsBuilding( areaHeight, vector<bool>( areaWidth, false ) ); //populate data for( int i = 0; i < areaHeight; i++ ) { string temp; cin >> temp; for( int j = 0; j < areaWidth; j++ ) { areaIsBuilding.at( i ).at( j ) = ( temp[ j ] == 'X' ); } } //now the vectors contain a `true` for a building and a `false` for snow //need to find the matches for patternIsBuilding inside areaIsBuilding //how? } return 0; } 

EDIT: from the comments below, I have a solution in Python from JF Sebastian . It works, but I do not understand all this. I commented everything I could, but I need help understanding the return in count_pattern .

 #function to read a matrix from stdin def read_matrix(): #get the width and height for this matrix nrows, ncols = map( int, raw_input().split() ) #get the matrix from input matrix = [ raw_input() for _ in xrange( nrows ) ] #make sure that it all matches up assert all(len(row) == ncols for row in matrix) #return the matrix return matrix #perform the check, given the pattern and area map def count_pattern( pattern, area ): #get the number of rows, and the number of columns in the first row (cause it the same for all of them) nrows = len( pattern ) ncols = len( pattern[0] ) #how does this work? return sum( pattern == [ row[ j:j + ncols ] for row in area[ i:i + nrows ] ] for i in xrange( len( area ) - nrows + 1 ) for j in xrange( len( area[i] ) - ncols + 1 ) ) #get a number of scenarios, and that many times, operate on the two inputted matrices, pattern and area for _ in xrange( int( raw_input() ) ): print count_pattern( read_matrix(), read_matrix() ) 

Answer 1

 #how does this work? return sum( pattern == [ row[ j:j + ncols ] for row in area[ i:i + nrows ] ] for i in xrange( len( area ) - nrows + 1 ) for j in xrange( len( area[i] ) - ncols + 1 ) ) 

The generator expression can be rewritten using explicit for-loop blocks:

 count = 0 for i in xrange( len( area ) - nrows + 1 ): for j in xrange( len( area[i] ) - ncols + 1 ): count += (pattern == [ row[ j:j + ncols ] for row in area[ i:i + nrows ] ]) return count 

Comparison ( pattern == .. ) returns True / False equal to 1/0 in Python.

Understanding the list that creates submatrices for comparison with a template can be optimized to return earlier:

 count += all(pattern_row == row[j:j + ncols] for pattern_row, row in zip(pattern, area[i:i + nrows])) 

Or using explicit blocks for the loop:

 for pattern_row, row in zip(pattern, area[i:i + nrows]): if pattern_row != row[j:j + ncols]: break # no match (the count stays the same) else: # matched (no break) count += 1 # all rows are equal 

Answer 2

Do not think about lines. Read the entire page in a line and process the end of line character just like any other.

(You might think this is a cryptic hint, but you only asked for an “idea” on how to do this.)

EDIT: since you know the overall size of the image, you can count the characters ahead from the first line of the pattern you are trying to match to fit the second line, etc. for subsequent lines.

Answer 3

 #include <iostream> #include <vector> using namespace std; int main(){ int numOfRounds; cin >> numOfRounds; for(int round = 0; round < numOfRounds; round++){ int out = 0; int linesToMatch; cin >> linesToMatch; int sizeToMatch; cin >> sizeToMatch; vector <string> v; string t; for (int i = 0; i < linesToMatch; i++){ cin >> t; v.push_back(t); } string s = ""; int rows; cin >> rows; int columns; cin >> columns; for (int j = 0; j < rows; j++){ //map->string cin >> t; s += t; } // main part of implementation // it mainly basic algebra and index tracking for (int m = 0; m <= rows - linesToMatch; m++){ for (int n = 0; n <= columns - sizeToMatch; n++){ int x; for (x = 0; x < linesToMatch; x++){ int index = (m + x) * columns + n; string newTemp(s.begin() + index, s.begin() + index + sizeToMatch); if (newTemp != v.at(x)) break; } if (x == linesToMatch) out++; } } cout << out << endl; } }