Databases
StackOverflow2013
Postsdbo
POHow to match ASCII art segments within ASCII art?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow to match ASCII art segments within ASCII art?
    primarykey
    data
    text
    <p>I am practising for a programming competition in which I will have the choice for each problem whether to use Python or C++, so I am open to a solution in either language – whatever language is best suited to this problem.</p> <p>The URL to the past problem I am stuck on is <a href="http://progconz.elena.aut.ac.nz/attachments/article/74/10%20points%20Problem%20Set%202012.pdf" rel="nofollow">http://progconz.elena.aut.ac.nz/attachments/article/74/10%20points%20Problem%20Set%202012.pdf</a>, problem F ("Maps").</p> <p>Basically it involves matching occurrences of a small piece of ASCII art within a big one. In C++ I can make a vector for each piece of ASCII art. The problem is how to match it when the smaller piece is multi-line.</p> <p>I have no idea how to go about it. I don't want all the code written for me, just an idea of the logic needed for the problem.</p> <p>Thanks for any help.</p> <p>Here's what I've got so far:</p> <pre><code>#include &lt;cstdlib&gt; #include &lt;iostream&gt; #include &lt;string&gt; #include &lt;algorithm&gt; #include &lt;vector&gt; using namespace std; int main( int argc, char** argv ) { int nScenarios, areaWidth, areaHeight, patternWidth, patternHeight; cin &gt;&gt; nScenarios; for( int a = 0; a &lt; nScenarios; a++ ) { //get the pattern info and make a vector cin &gt;&gt; patternHeight &gt;&gt; patternWidth; vector&lt; vector&lt; bool &gt; &gt; patternIsBuilding( patternHeight, vector&lt;bool&gt;( patternWidth, false ) ); //populate data for( int i = 0; i &lt; patternHeight; i++ ) { string temp; cin &gt;&gt; temp; for( int j = 0; j &lt; patternWidth; j++ ) { patternIsBuilding.at( i ).at( j ) = ( temp[ j ] == 'X' ); } } //get the area info and make a vector cin &gt;&gt; areaHeight &gt;&gt; areaWidth; vector&lt; vector&lt; bool &gt; &gt; areaIsBuilding( areaHeight, vector&lt;bool&gt;( areaWidth, false ) ); //populate data for( int i = 0; i &lt; areaHeight; i++ ) { string temp; cin &gt;&gt; temp; for( int j = 0; j &lt; 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; } </code></pre> <p>EDIT: From the comments below I've got a solution in Python from <code>J.F. Sebastian</code>. It works but I don't understand it all. I've commented what I could but need help understanding the <code>return</code> statement in the <code>count_pattern</code> function.</p> <pre><code>#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() ) </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow to match ASCII art segments within ASCII art?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POHow to match ASCII art segments within ASCII art?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POHow to match ASCII art segments within ASCII art?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COAs a starting point, I'd suggest that you define both the large part and the small part as 2D arrays, potentially of booleans where `true` indicates a building and `false` indicates snow. Then, you'd need to use some loop-fu to find each occurrence the small matrix within the large matrix.
      singulars
      1. POHow to match ASCII art segments within ASCII art?
      1. USVulcan
    2. CO@Vulcan thanks, that seems like it'd work. I'll have a go at it. Maybe add it as an answer so I can accept it :)
      singulars
      1. POHow to match ASCII art segments within ASCII art?
      1. This table or related slice is empty.
    3. COI'm not satisfied with my comment as an answer (which is why it's a comment), but I might take a shot at writing an actual matrix-within-matrix location algorithm. I'm not terribly familiar with either C++ or Python, so it'll be a nice exercise for me, but don't forget that you can always answer your own question with the code too!
      singulars
      1. POHow to match ASCII art segments within ASCII art?
      1. USVulcan
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload