Come abbinare i segmenti artistici ASCII all'interno dell'arte ASCII?

Question

Mi sto esercitando per un concorso di programmazione in cui avrò la possibilità di scegliere se utilizzare Python o C++, quindi sono aperto a una soluzione in entrambe le lingue, qualunque sia la lingua più adatta a questo problema.

L'URL del problema passato su cui sono bloccato è http://progconz.elena.aut.ac.nz/attachments/article/74/10%20points%20Problem%20Set%202012.pdf, problema F ("Mappe").

Fondamentalmente si tratta di corrispondenze occorrenze di un piccolo pezzo di arte ASCII all'interno di una grande. In C++ posso creare un vettore per ogni pezzo di arte ASCII. Il problema è come abbinarlo quando il pezzo più piccolo è multilinea.

Non ho idea di come procedere. Non voglio che tutto il codice sia scritto per me, solo un'idea della logica necessaria per il problema.

Grazie per qualsiasi aiuto.

Ecco quello che ho finora:

#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: Dai commenti qui sotto ho una soluzione in Python da J.F. Sebastian. Funziona ma non capisco tutto. Ho commentato quello che potevo, ma ho bisogno di aiuto per comprendere l'istruzione return nella funzione 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's 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) 
) 

L'espressione generatore potrebbe essere riscritto utilizzando blocchi esplicite per-loop:

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 

Il confronto (pattern == ..) restituisce Vero/Falso, che sono pari a 1/0 in Python.

La lista di comprensione che costruisce submatrixes da confrontare con il modello può essere ottimizzato per tornare in precedenza:

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

o utilizzando esplicite per-loop blocchi:

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

Non pensare in termini di linee. Leggi l'intera pagina in una stringa e tratta i caratteri di fine riga come qualsiasi altro.

(Si potrebbe pensare che questo è un suggerimento criptico, ma ha chiesto solo "un'idea" come farlo.)

EDIT: Dal momento che si conoscono le dimensioni complessive della foto, è possibile contare caratteri in avanti dalla prima riga del pattern che stai cercando di abbinare per abbinare la seconda linea, e così via per le linee successive.

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's 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; 

    } 

}