Databases
StackOverflow2013
Postsdbo
POFast two-dimensional pattern matching
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POFast two-dimensional pattern matching
    primarykey
    data
    text
    <p>Consider a two-dimensional grid (the usual lattice in the plane). For my purposes, a <em>pattern</em> or <em>arrangement</em> is an assignment of the numbers 1 and 2 to some connected subset of the grid points. For example, the following shows three separate arrangements:</p> <pre><code>.......1.....1.... .222...2.....12... .111...2.....2.... .222...22...12211. .......1....11.1.. </code></pre> <p>I say that a small pattern matches a large one if the small one can be rotated or reflected such that all of its numbers are smaller than the numbers in the larger one. For example, consider this pattern:</p> <pre><code>...... .1212. ....2. ...... </code></pre> <p>It does NOT match the leftmost arrangement above because it can't be rotated or reflected to fit in a 3x3 square. It DOES match the middle arrangement because it can be rotated and reflected to fit underneath. It does NOT, however, match the rightmost arrangement because however it is rotated or reflected to fit in the rightmost arrangement, the numbers are larger in the small pattern than the large arrangement. (If any of my examples are unclear or you need more information, just ask away in the comments area. Some clarifications in advance: the pattern can't be stretched, and it can't be rotated so it's diagonal with respect to the grid. That means there are four rotations and four reflections total, each of which can be translated.)</p> <p>I am wondering about the following questions:</p> <ol> <li><p>How can I quickly test if a small pattern matches a large arrangement?</p></li> <li><p>Suppose I have a lot of small patterns. Can I pre-process them somehow to quickly tell if <em>at least one</em> of them matches an arrangement?</p></li> </ol> <p>I suppose it'd be cool if a solution solves a more general problem (like arbitrary numbers -- not just 1 and 2 -- or allowing disconnected shapes), but I really only care about the case above. Thanks.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USA. Rex
    1. USA. Rex
    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
    1. VO
      singulars
      1. POFast two-dimensional pattern matching
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POFast two-dimensional pattern matching
      1. USergosys
      1. VTFavorite
    3. VO
      singulars
      1. POFast two-dimensional pattern matching
      1. USA. Rex
      1. VTFavorite
    1. COWell you can check if none match by summing up the points in the arrangements. If the sum of a pattern is greater than the sum of the greatest arrangement there definitely isn't a match. I know this isn't what you asked, just throwing it out there.
      singulars
      1. POFast two-dimensional pattern matching
      1. USRedDeckWins
    2. COThat's true and a good observation. (You can also count the number of 2s.) In my cases, I think that would settle very few of my pattern-matching queries.
      singulars
      1. POFast two-dimensional pattern matching
      1. USA. Rex
 

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