Language Design: 2-D Pattern Matching

Question

This is Fortnightly Challenge #6. Theme: Language Design

There's a chatroom for this challenge. Come and join us if you want to discuss ideas!

And now for something completely different...

This fortnight, we want to experiment with a new type of challenge. In this challenge, you will be designing a language! Pattern matching is a very common problem in programming, and often very useful for code golf. Regular expressions, for example, can be used to detect a pattern in a line of text. There are not, however, any established methods to describe and detect two-dimensional patterns.

The Challenge

You're to design a pattern-matching language, which allows the description of two-dimensional patterns in blocks of text. The mode of operation of your language will be similar to regular expressions (although your language doesn't have to have anything in common with regex otherwise):

• As input, you will receive a rectangular block of text. You may assume that the text consists only of printable ASCII characters (0x20 to 0x7E) as well as newlines (0x0A) to separate the rows of the grid.
• If a match, according to the pattern description, can be found as any subset of this block of text, this match should be returned or printed. If the match can be non-rectangular, it should be padded to a rectangular area with some reserved character. If there are several valid matches, you may decide how the returned match is chosen (largest, smallest, first, etc.).

For some applications it might be useful if your implementation can return the position of a match instead of the match itself, but this is not a requirement.

At the very least, your language should be able to match a pattern as a contiguous, rectangular subregion of its input.

Your answer should contain:

• A description of the language.
• A working implementation. This can be a program, or a set of functions/classes in a language of your choice.
• You should demonstrate your language by showing how it can be used to solve the examples provided below. Your language does not have to be capable of matching all of them, but you must be able to match at least 8 of these. If your language can do something fancy we didn't think of, feel free to include it as well.

If your answer builds on existing ideas, that is fine, but please give credit where it's due.

Extensions

The above describes the minimum that a valid submission has to satisfy. However, several generalisations could make such a pattern matching language even more useful, including but not limited to:

• Being able to anchor the pattern to one or more edges, so that one can check if the entire input region has a certain pattern.
• Producing all matches instead of just one. You may choose the semantics of overlapping matches.
• Taking non-rectangular text as input.
• Allowing patterns to specify non-rectangular matches. In such a case, the output should be padded to a rectangle with some reserved character.
• Allowing patterns to specify matches with holes.
• Allowing non-contiguous matches, like two characters appearing with a certain offset.
• Easy specification of rotations and reflections.
• Optionally treat the input cyclically as a cylinder or a torus, such that opposite edges are considered adjacent.

Scoring

The primary goal of this challenge is to produce an effective 2D pattern-matching language which could potentially be used in the future. As such, a scoring system like "shortest combined length to solve the examples" would lead to hard-coding of certain functionality at the expense of general usability. Therefore, we have decided that this challenge is best run as a popularity contest. The submission with the most net votes wins. While we can't force how people vote, here are a few guidelines for what voters should ideally look for:

• Expressiveness. Can the language solve a variety of problems, even beyond the examples presented in this question? Does it support any of the suggested extensions?
• Readability. How intuitive is the notation (at least to people who know the basic syntax)?
• Golfitude. This is still CodeGolf.SE. For the purposes of this site, it would of course be nice to have a matching language that needs very little code to describe a pattern.

Example Problems

The following Stack Snippet shows 16 example problems which a 2-D pattern matching language could be able to deal with. Each example contains a short problem description and is then usually followed by one input example where a match can be found and one example where no match can be found (if applicable).

As stated above, your language only needs to be able to solve 8 of these problems. Everything on top of that is optional, but should of course increase the number of votes you get.

body{font-family:'Helvetica Neue',Arial,sans-serif;color:#444;font-size:13px;width:500px;line-height:1.3}h3{font-size:16px!important;line-height:1.2em!important;margin-bottom:1.2em}code{white-space:pre-wrap;padding:1px 5px;font-family:'Droid Sans Mono',Consolas,Menlo,Monaco,Lucida Console,Liberation Mono,DejaVu Sans Mono,Bitstream Vera Sans Mono,Courier New,monospace,serif;color:#222;background:#eee}p code{padding:1px 5px}pre{overflow:auto;width:auto;width:480px !ie7;max-height:600px;font-family:'Droid Sans Mono',Consolas,Menlo,Monaco,Lucida Console,Liberation Mono,DejaVu Sans Mono,Bitstream Vera Sans Mono,Courier New,monospace,serif;margin-bottom:10px;padding:5px;background:#eee;border-left:2px dotted #ccc;font-size:12px}pre code{white-space:inherit;padding:0;background:0 0}

<h3>Problem 1 - Finding Chessboards</h3><p>Match any rectangular subregion, at least 3 columns wide and 3 rows tall, which consists of alternating <code>#</code> and <code>_</code>. The top left corner may be either of those two characters.</p><p><strong>Match</strong></p><pre><code>~______~&#10;~##_#_#~&#10;~#_#_##~&#10;~##_#_#~&#10;~______~&#10;</code></pre><p>(There's an alternating 4x3 region in the centre. The match could be either that or either of its two 3x3 subregions.)</p><p><strong>No match</strong></p><pre><code>#_##&#10;_#_#&#10;__#_&#10;#_#_&#10;#_#_&#10;</code></pre><p>(Contains two 3x2 regions, but no alternating 3x3 region.)</p><h3>Problem 2 - Verifying Chessboards</h3><p>Match the entire input, provided all of it consists of alternating <code>#</code> and <code>_</code>. It may start with either of those two characters.</p><p><strong>Match</strong></p><pre><code>_#_#_#_#&#10;#_#_#_#_&#10;_#_#_#_#&#10;</code></pre><p><strong>No match</strong></p><pre><code>_#_#_#__&#10;__#_#_#_&#10;_#_#_#__&#10;</code></pre><h3>Problem 3 - Detect a Rectangle of Digits</h3><p>Match a rectangle (at least 2x2) consisting only of digits and no other characters.</p><p><strong>Match</strong></p><pre><code>hbrewvgr&#10;18774gwe&#10;84502vgv&#10;19844f22&#10;crfegc77&#10;</code></pre><p>You should match either the 5 wide by 3 tall rectangle (or any subset thereof) or the 2 by 2 rectangle.</p><p><strong>No Match</strong></p><pre><code>uv88wn000&#10;vgr88vg0w&#10;v888wrvg7&#10;vvg88wv77&#10;</code></pre><p>There are no rectangles of digits.</p><h3>Problem 4 - Finding a Word in a Word Search</h3><p>Match the smallest rectangular region containing containing the word "GOLF" in any orientation (horizontal, vertical, diagonal, forwards or backwards). If your language supports non-rectangular matches, you may also match diagonal words without the surrounding rectangle.</p><p><strong>Match</strong></p><pre><code>INOWCEF&#10;IFWNOPH&#10;VULUHGY&#10;GUYOIGI&#10;YTFUGYG&#10;FTGYIOO&#10;</code></pre><p>"GOLF" is found backwards along an upper-left to bottom-right diagonal. This is the region containing it:</p><pre><code>FWNO&#10;ULUH&#10;UYOI&#10;TFUG&#10;</code></pre><p><strong>No Match</strong></p><pre><code>BHTGIVUHSR&#10;BWEVYWHBWB&#10;BHTWBYTWYB&#10;</code></pre><p>("GOLF" cannot be found anywhere.)</p><h3>Problem 5 - Detect Square Inputs</h3><p>Match the entire input if it is a square block of characters.</p><p><strong>Match</strong></p><pre><code>qwerty&#10;asdfgh&#10;zx vbn&#10;uiop[]&#10;`1234 &#10;67890-&#10;</code></pre><p>There are six lines, each of which contains six characters, even though two characters are spaces.</p><p><strong>No Match</strong></p><pre><code>   hello&#10;   world&#10;</code></pre><p>The two lines don't each contain two characters.</p><h3>Problem 6 - Find Gliders in a Game of Life</h3><p>In Conway's <a href=http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life rel=nofollow>Game of Life</a> one of the most popular and simple patterns is the <a href=http://www.conwaylife.com/wiki/Glider rel=nofollow>glider</a>. There are two different stages in a glider's life cycle:</p><pre><code>##         ##&#10;# #  and  ##&#10;#           #&#10;</code></pre><p>Of course, the Game of Life is invariant under rotation and reflection, so in total there are 16 different shapes which resemble a glider at some stage.</p><p>Given input consisting only of <code>#</code> and spaces, match a 3x3 block containing a glider in any orientation. Spaces are significant! (Due to the conditions in the surrounding 5x5 layer, these matches might not be actual gliders, but don't worry about that.)</p><p><strong>Match</strong></p><pre><code>##   #  &#10;  # ##  &#10;#   # # &#10;# #     &#10;##   ###&#10;   # #  &#10; #    # &#10;</code></pre><p>This contains three gliders - top right corner, bottom right corner and left centre.</p><p><strong>No match</strong></p><pre><code>##   # &#10;  # ###&#10;##  # #&#10;# #    &#10;##  ###&#10;</code></pre><h3>Problem 7 - Match Nether Portals</h3><p>Based on <a href=http://codegolf.stackexchange.com/questions/45488/nether-portal-detection>this challenge</a> by Calvin's Hobbies.</p><p>In the game of Minecraft, players can construct inter-dimensional portals using blocks of obsidian arranged into a rectangular frame. Given a 2D slice of the world, match a Nether portal. A valid Nether portal is a rectangle of empty space (<code>.</code>) surrounded on all sides by obsidian (<code>X</code>). The rectangle of space can be from 2 wide by 3 tall to 22 wide by 22 tall. Corners don't matter.</p><p><strong>Match</strong></p><pre><code>....X......&#10;.XXXXXX.XX.&#10;...X...X...&#10;.X.X...XXX.&#10;...X...X.X.&#10;.XXX...X.X.&#10;X..XXXXX.X.&#10;</code></pre><p>This is a 3 wide by 4 tall portal.</p><p><strong>No Match</strong></p><pre><code>XX..XXXX&#10;XX..X..X&#10;XX..X..X&#10;..X.X..X&#10;.X..X.XX&#10;</code></pre><p>This is almost a 2 wide by 3 tall portal, but one obsidian block is missing from the bottom.</p><h3>Problem 8 - Minecraft Chest Placement</h3><p>Based on <a href=http://codegolf.stackexchange.com/q/45720/8478>this challenge</a> by Calvin's Hobbies.</p><p>For this problem, returning the position of the match might be more useful than returning the actual match. "Adjacent" refers only to neighbours in four orthogonal directions. You're given a grid of <code>.</code> (empty cell) and <code>C</code> (chest). Two adjacent chests are considered a "double chest". You should match valid positions for placing additional chests. An empty cell is valid as long as it not adjacent to a double chest or two normal chests. Taking the example from the linked challenge, if the input is</p><pre><code>.......C..&#10;...C..C...&#10;.........C&#10;.CC...CC..&#10;..........&#10;</code></pre><p>the pattern should match the cell marked by <code>*</code> in the following grid:</p><pre><code>******.C**&#10;***C**C.**&#10;*..***..*C&#10;.CC.*.CC.*&#10;*..***..**&#10;</code></pre><h3>Problem 9 - Horizontal and Vertical Alignment</h3><p>Match a part of a column or row if it contains two or more <code>#</code> characters. As an extension, you could return the index of the column or row. If your language supports non-contiguous matches, match <em>only</em> the two <code>#</code>, not the row/column in between.</p><p><strong>Match</strong></p><pre><code>.,.,.,.#.,&#10;,.,#,.,.,.&#10;.,.,.,.,.,&#10;,.,.,.,.,.&#10;.,.#.,##.,&#10;,.,.,.,.,.&#10;</code></pre><p>There are 5 possible matches, three horizontal or two vertical. The horizontal matches are <code>#.,#</code>, <code>##</code>, and <code>#.,##</code>. The vertical matches are <code>#,.#</code> and <code>#.,.#</code>. The language can match any one or more of those.</p><p><strong>No Match</strong></p><pre><code>.,.#.,.,&#10;,.,.,.#.&#10;.,#,.,.,&#10;,.,.,.,#&#10;.#.,.,.,&#10;,.,.#.,.&#10;#,.,.,.,&#10;,.,.,#,.&#10;</code></pre><p>This is also a solution to the Eight Queens problem.</p><h3>Problem 10 - Collinear Points</h3><p>Match a set of three <code>#</code>s that are in a straight line, which can have any orientation, not necessarily horizontal or vertical (i.e. it could be diagonal are long knight's move steps). If your language supports non-contiguous matches, match <em>only</em> the three <code>#</code>, not the characters in between.</p><p><strong>Match</strong></p><pre><code>........&#10;#..#..#.&#10;...#....&#10;#.......&#10;...#....&#10;</code></pre><p>There are three possible matches. They are: the second row, the fourth column, and a diagonal line across 7 columns and 3 rows.</p><p><strong>No Match</strong></p><pre><code>.#..#&#10;#..#.&#10;#....&#10;..#.#&#10;</code></pre><p>There are no collinear <code>#</code>s in this input.</p><h3>Problem 11 - Verify Prelude Syntax</h3><p><a href=http://esolangs.org/wiki/Prelude rel=nofollow>Prelude</a> is an esoteric language, which has very few, but unusual, restrictions on what constitutes a valid program. Any block of printable ASCII text is valid provided that:</p><ul><li>Every column of text contains at most one of <code>(</code> and <code>)</code>.</li><li>Ignoring their vertical position, the <code>(</code> and <code>)</code> are balanced. Each <code>(</code> and be paired with exactly one <code>)</code> to the right of it, and vice-versa.</li></ul><p>The pattern should match any valid Prelude program and fail to match invalid programs.</p><p><strong>Match</strong></p><pre><code>?1-(v  #1)-             &#10;1   0v ^(#    0)(1+0)#)!&#10;    (#)  ^#1-(0 #       &#10;</code></pre><p><strong>No match</strong></p><pre><code>#(#(##)##)##(&#10;)##(##(##)#)#&#10;</code></pre><p>For more examples, see <a href=http://codegolf.stackexchange.com/q/47239/8478>this challenge</a>.</p><h3>Problem 12 - Avoid the Letter Q</h3><p>Match any 4x4 square of characters that does not contain the letter <code>Q</code> or <code>q</code>.</p><p><strong>Match</strong></p><pre><code>bhtklkwt&#10;qlwQklqw&#10;vtvlwktv&#10;kQtwkvkl&#10;vtwlkvQk&#10;vnvevwvx&#10;</code></pre><p>There is one 4x4 square that does not contain any Qs. This is</p><pre><code>vlwk&#10;twkv&#10;wlkv&#10;vevw&#10;</code></pre><p><strong>No Match</strong></p><pre><code>zxvcmn&#10;xcvncn&#10;mnQxcv&#10;xcvmnx&#10;azvmne&#10;</code></pre><p>The single <code>Q</code> in the center prevents any matches from being formed.</p><h3>Problem 13 - Diamond Mining</h3><p>Locate a diamond in a field of characters. Diamonds are rotated squares formed by the characters <code>/\X</code>. Each corner of the diamond is formed by an <code>X</code>, and the corners are connected in lines formed by <code>\</code> or <code>/</code>, where each side is the same length. A diamond of size 0 has no <code>/\</code> sides. As an extension, you can return all of the diamonds in the field, return only the diamond's characters, and/or return the size of the diamond found.</p><p><strong>Match</strong></p><pre><code>...X......X....&#10;../.\..../.\...&#10;./.X.\..X...X..&#10;X.X.X.XX.\./.\.&#10;.\.X.//.\.X...X&#10;..\./X...X.\./.&#10;.X.X..\./...X..&#10;X.X....X.......&#10;.X.............&#10;</code></pre><p>There are 6 different diamonds in this field. Two are size 0, three are size 1, and one is size 2. Notice how diamonds can overlap parts or nest.  You should be able to match diamonds of any size up to a reasonably high limit.</p><p><strong>No Match</strong></p><pre><code>.X......./....&#10;.\....X.......&#10;...X.\.\...X..&#10;..X.\...\.X.\.&#10;...X.X...X.\.X&#10;../X\...\...X.&#10;.X...\.\..X...&#10;..\./.X....X..&#10;...X..../.....&#10;</code></pre><p>No diamonds are found here.</p><h3>Problem 14 - Matching Crosses</h3><p>We'll define a cross as a rectangular region, which has been sliced into a (not necessarily regular) grid of 3x3 subregions. The four corner regions are filled with <code>.</code> whereas the other five regions are filled with <code>#</code>.</p><p><strong>Match</strong></p><pre><code>.......&#10;.###...&#10;######.&#10;######.&#10;.###...&#10;.###...&#10;.###.#.&#10;....###&#10;.....#.&#10;</code></pre><p>There is the small cross in the lower right corner, and the large cross yields 5 potential matches: the top and left arms will always have length 1, but the right and bottom arms can each either have length 1 or 2 - in addition the bottom arm can have length 3 if the right arm has length 1. Note that the full large cross cannot be matched because the top of the small cross would protrude into the lower right region.</p><p><strong>No Match</strong></p><pre><code>.######.&#10;...##...&#10;...##...&#10;........&#10;</code></pre><p>Each arm must have length of at least 1.</p><h3>Problem 15 - Match a Word in a Boggle Board</h3><p><a href=http://en.wikipedia.org/wiki/Boggle rel=nofollow>Boggle</a> is a bit like a word search, except that you change direction after each letter. Given a block of text, if it contains the word <code>panama</code> (<em>case-insensitive!</em>) according to the Boggle rules, match the smallest rectangle containing it. You may decide whether single letters can be reused or not. If your language can handle both, show it off! If you allow letters to be reused you can also choose if a letter can be used twice in a row (i.e. whether staying on the same cell is a valid move). If your language supports non-rectangular matches, match <em>only</em> the word.</p><p><strong>Match without reusing letters</strong></p><pre><code>EmYPhNuy&#10;AaaKVsjL&#10;onlGviCw&#10;DdOgFrRn&#10;ISeHZmqc&#10;zMUkBGJQ&#10;</code></pre><p>(There's a snaking <code>panamA</code> or <code>panAma</code> towards the upper left corner, depending on the order it's matched in.)</p><p><strong>Match with reusing letters</strong></p><pre><code>ExYPhNuy&#10;AfEKVsjL&#10;oblGviCw&#10;DdOgArRn&#10;ISepnmqc&#10;zMUkBGJQ&#10;</code></pre><p>(There's a <code>pAnAmA</code> towards the lower right corner, where all three <code>A</code> are the same.)</p><p><strong>No Match</strong></p><pre><code>BpbrzTHY&#10;mAJVRLuF&#10;jyXSPknK&#10;hoeGcsEl&#10;QCZagNMI&#10;dvUOqixt&#10;</code></pre><h3>Problem 16 - Wrap around the Edges</h3><p>Match a rectangle of <code>#</code>, at 3x3 in size, which may wrap around the edges of the input.</p><p><strong>Match</strong></p><pre><code>#..##&#10;#..##&#10;.....&#10;#..##&#10;</code></pre><p>(The 9 <code>#</code> form exactly one 3x3 region if you consider the edges to be adjacent.)</p><p><strong>No Match</strong></p><pre><code>...##&#10;#..##&#10;#..##&#10;#..#.&#10;</code></pre>&#10;

(No, you don't need to read that HTML code. Hit the "Run code snippet" button to get it nicely rendered by your browser, which you can then also view full screen.)

Answer 1

SnakeEx

Solves 15/16 problems so far!

Online Interpreter! - Full Language Spec - Javascript Source

The idea behind this language is to define 'snakes' that move around the text checking characters using a regex-like syntax.

A program in SnakeEx consists of a list of definitions for snakes using different sequences of commands. Snakes can spawn other snakes using these definitions, which is where SnakeEx gets most of its power - we can match branching structures and even do recursion (see Paren Matching example).

Every program will essentially look like a set of regexes, but with the addition of direction commands of the form <dir> that change the snake's direction, and call commands of the form {label<dir>params} that spawn more snakes.

For an entry point, the interpreter spawns one snake using the first definition, moving to the right.

It's not terribly concise, but it's very powerful and (I think) pretty readable.

Updates

• Changed ! to logical not and ~ to not mark matches
• Added <!> to solve colinear
• Solved Matching Crosses
• Solved chessboards in a less terrible way
• Added bounded closure syntax %{min,max}
• Added recursion example

Solutions

15 solved, 1 in progress

You can easily try out these programs out using the Online Interpreter linked above!

Problem 1 - Finding Chessboards

m:{v<R>2}{h<>1}
v:{c<L>A1}+
h:{c<R>A2}+
c:_?(#_)+#?

For a detailed introduction, start at Problem 3.

Problem 2 - Verifying Chessboards

m:{v<R>2}{h<>1}
v:${c<L>A1}+$
h:${c<R>A2}+$
c:$_?(#_)+#?$

Book-ending the appropriate snakes with the out-of-bounds symbol $ is one way to make a program match only the entire input.

Problem 3 - Detect a Rectangle of Digits

m:{c<R>A1}%{2,}
c:[0-9]%{2,}

The m snake moves right, spawning at minimum 2 snakes (%{2,} is a closure meaning "2 to infinity") using definition c (c) and moving right (<R>), or rather down in this case, because all directions are relative to the current snake. The A param is sugar that just specifies that the spawning snake should move after the call. The 1 parameter is how we restrict matches to rectangles - number parameters put snakes in "groups". A match does not count unless all snakes in the same group travel exactly the same distance.

Problem 4 - Finding a Word in a Word Search

m:<*>GOLF

The direction command <*> specifies that the snake should turn in any diagonal or orthogonal direction. Then, it looks for the simple regex.

Problem 5 - Detect Square Inputs

m:{v<R>1}{h<>1}
v:${c<L>A1}+$
h:${c<R>A1}+$
c:$.+$

The key here is the special character $, which only matches if the snake is out-of-bounds. We spawn a horizontal snake and a vertical one; each of those spawns more snakes as it runs along the edge, and all of those are in the same group and must be the same length.

Problem 6 - Find Gliders in a Game of Life

m:<+>[({l1<R>A}{l2<R>A}{l3<R>})({l1<L>A}{l2<L>A}{l3<L>})]
l1:##\.
l2:[(#\.)(\.#)]#
l3:#\.\.

m starts in any of the four orthogonal directions (<+>), achieving rotation. Then, it looks either left or right for the three rows in order, achieving reflection.

(Note that I have replaced the spaces with periods only because the HTML textareas used in my interpreter seem to do stupid things if they have multiple spaces in a row)

Problem 7 - Match Nether Portals

m:{e<R>A1}{d<R>A1}%{2,22}{e<R>1}
e:~.X%{3,22}~.
d:X\.+X

The m snake moves right, spawning a snake to check the left edge, 2-22 snakes to check the middle columns, and finally a snake to check the right edge. The ~ operator indicates that whatever follows should be checked but should not be marked as part of the solution.

Bounded closures now allow us to fully and properly solve this problem!

Problem 8 - Minecraft Chest Placement

m:~{s<>}~!{d<+>}\.
s:<+>.<BR>([$\.]<R>)%{3}
d:.<+>CC

Here we use a logical not (!), which matches if and only if the following token does not match anything. The declaration d detects a double chest in a particular direction, so !{d<+>} makes sure there are no double chests in any orthogonal direction. s moves in a little diamond around the current square, verifying at least 3 of those spaces are either empty or off the board. The trailing \. finally matches the square, assuming all the preceding conditions succeeded.

Problem 9 - Horizontal and Vertical Alignment

m:<R>?#~.*#

The snake m optionally turns right (<R>?) before matching the sequence. . is a wildcard, like in regex.

Problem 10 - Colinear Points

m:<!>#~.*#~.*#

With the addition of the <!> direction, we can solve this now! <!> is like <+> but instead of branching in four directions, it branches in every possible direction.

Problem 12 - Avoid the letter Q

m:{h<R>A}%{4}
h:[^Qq]%{4}

Just spawns 4 snakes that each look for four characters that are not the letter Q.

Problem 13 - Diamond Mining

m:{tl<RB>1}{tr<RF>1}
tl:X/*{bl<L>1}X
tr:X\\*{br<R>1}X
bl:X\\*X
br:X/*X

This one's pretty neat. m spawns two snakes, one going to its back right, and one to its forward right. Each of those follows the slashes to an X, then spawns another snake at a right angle to its current direction, which follows the slashes to the bottom X.

Problem 14 - Matching Crosses

m:{a<R>A}+{b<R>A}+{a<R>A}+
a:{e<>P1}{c<>P2}{e<>P3}
b:{c<>P1}{c<>P2}{c<>P3}
e:\.+
c:#+

Here's the first time I've used the Piggyback parameter. Normally the snakes are independent, but if you make a call with this parameter, the calling snake will be moved with the callee. So e2 can check a sequence of '.', then a sequence of '#', then another sequence of '.', and have them all be separate calls so we can group them with '1, '2', and '3', forcing their lengths to match up.

Problem 15 - Match a Word in a Boggle Board

m{I}:<*>p<*>a<*>n<*>a<*>m<*>a

Simple, if wordy. I parameter specifies case-insensitivity (we can specify parameters on definitions as well as in calls). The snake turns in any direction, matches the character, turns again, and so forth.

m{EI}:<*>p<*>a<*>n<*>a<*>m<*>a

This is the no-reusing-characters version. The Exclusive parameter forbids the snake from matching any character that has already been marked, much like feersum's slime trails.

Problem 16 - Wrap around the Edges

m{W}:{c<R>WA}%{3}
c:###

The W parameter allows the snake to wrap when it runs out-of-bounds. We also have H and V to allow only horizontal or vertical wrapping.

Extra - Maze Solver

m{E}:$(<P>\.)+$

Solves an ASCII maze where the walkable floor is periods. The <P> direction means forward, left, or right (sugar for [<F><L><R>]).

Extra - Paren Matching

m:\(~{r<>P}\)
r:[^\(\)]*(\({r<>P}\))?[^\(\)]*

Haven't figure out how to do Prelude yet, but here's a first step! Here I use the r snake recursively to match corresponding parenthesis by checking that there are no unmatched parenthesis between them.

Extra - ASCII Topology: Counting Loops

Answer 2

Slip, Python 3.4 (Github wiki, online interpreter)

Like feersum's submission this is also based on traversing the grid, but like CarpetPython's submission this is based on regex. Somehow it looks like I managed to take the middle ground.

There's a quite a lot of unimplemented features which I want to add, so where relevant I've noted what I intend to do when I get time.

---

Updates

(See Github page for detailed news)

• Apr 5 2015: Slip now has an online interpreter! It's still in its early stages, so there might be a few bugs.

• Apr 5 2015: Efficiency update! Now does nether portals big input a lot faster (2s). Also there's been a number of syntax changes, so be sure to check the wiki. Group numbering also fixed.

---

Slip has a match pointer which starts at a particular square and is initially facing rightward. When a char is matched, the pointer moves forwards in the current direction (although the implementation doesn't do things exactly in that order).

The match pointer's direction can be set to a particular direction with ^<digit>, where ^0, ^1, ^2, ..., ^7 set the pointer to N, NE, E, ..., NW respectively (going clockwise).

The following shortcuts are also available:

• ^* checks all 8 orthogonal or diagonal directions,
• ^+ checks all 4 orthogonal directions.

(Future plan: Allow setting of arbitrary directions, e.g. (1, 2) for knight's move)

For example (Problem 4 - Finding a word in a word search),

^*GOLF

tries all 8 orthogonal or diagonal directions, looking for the word "GOLF". By default, Slip tries all possible starting squares and returns one result from each, filtering out duplicates, so a grid like

GOLF
O
L
FLOG

returns only the top row and bottom row as matches (since the top row and left column "GOLF"s start from the same square). To get all matches, the o overlapping match mode can be used.

Similarly (Problem 15 - Match a word in a Boggle board),

p^*a^*n^*a^*m^*a

matches panama by trying a different direction each time. Use the i flag for case insensitivity. Slip reuses chars by default, but this can be toggled with the r no-repeat flag.

(Future plan: a search mode modifier which automatically checks sets of directions after each move so that repeating ^* is unnecessary)

The match pointer's direction can also be rotated 90 degrees left or right with < or > respectively. For instance,

 `#`#< `#<  <`#<`#

looks for the pattern

  #
## 
 ##

by looking in the following order:

765
894
123

This allows us to solve Problem 6 - Finding gliders with

^+(`#`# >`# > `#>`#> |`#`# <`# < `#<`#< | `#`#> `#>  >`#>`#| `#`#< `#<  <`#<`#)

where parts 1 and 2 encode the glider shapes, and parts 3 and 4 encode their reflected counterparts.

Note that Slip uses backtick ` for escaping. This is because Slip has another form of movement which gives the language its name — the slip command. / slips the match pointer orthogonally to the left, while \ slips the match pointer orthogonally to the right.

For example,

abc   ghi
   def

can be matched by abc\def/ghi.

While not particularly useful on its own, slipping becomes more important when combined with the (?| <regex> ) stationary group, which acts like a matching lookahead. The regex inside is matched, then at the end of it the position and direction of the match pointer are reset to the state before the stationary group.

For example,

abc
def
ghi

can be matched with (?|abc)\(?|def)\(?|ghi).

Similarly, Problem 12 - Avoid the letter Q can be solved with

%(\(?|[^qQ]{4})){4}

where % is a no-slip command to stop the first \ from activating.

Slip also has a length assert (?_(<group num>) <regex> ), which only matches the regex inside if its match length is the same length as that of the given group num.

For example, Problem 13 - Diamond mining can be easily solved with

^1X(`/*)X>(?_(1)`\*)X>(?_(1)`/*)X>(?_(1)`\*)

which tries to match the top left side of the diamond first, then asserts that the other three sides are the same length.

(Run with v flag for verbose output)

Match found in rectangle: (8, 0), (12, 4)
  X
 / \
X   X
 \ /
  X

Match found in rectangle: (0, 0), (6, 6)
   X
  / \
 /   \
X     X
 \   /
  \ /
   X

Match found in rectangle: (2, 2), (4, 4)
 X
X X
 X

Match found in rectangle: (10, 2), (14, 6)
  X
 / \
X   X
 \ /
  X

Match found in rectangle: (5, 3), (9, 7)
  X
 / \
X   X
 \ /
  X

Match found in rectangle: (0, 6), (2, 8)
 X
X X
 X

A golfier alternative is

^1X(`/*)(X>(?_(1)`\*)X>(?_(1)`/*)){2}

which matches the first side twice.

Many of the other problems can be solved using slipping, stationary groups and length asserts:

Problem 14 - Matching crosses:

(?|(`.+)(`#+)(`.+))(\(?|(?_(2)`.+)(?_(3)`#+)(?_(4)`.+)))*(\(?|(?_(2)`#+)(?_(3)`#+)(?_(4)`#+)))+(\(?|(?_(2)`.+)(?_(3)`#+)(?_(4)`.+)))+

Once you capture the widths of the .s and #s in the first row, it's just slipping all the way down.

Output:

Match found in rectangle: (0, 1), (5, 5)
.###..
######
######
.###..
.###..

Match found in rectangle: (4, 6), (6, 8)
.#.
###
.#.

This one can probably be golfed with a bit of recursion, once I get a few bugs sorted out.

Problem 3 - Detect a rectangle of digits:

(?|`d`d+)(\(?|(?_(1)`d+)))+

Match a top row of two or more digits, then make sure every line below is the same length. `d is a predefined character class equivalent to [0-9].

Note that this finds all matches.

Problem 7 - Match nether portals:

(?|.X{2,22}.)\((?|(?_(1)X`.+X))\){3,22}(?_(1).X+.)

which outputs, for the top example in the original thread:

Match found in rectangle: (2, 1), (5, 5)
XXXX
X..X
X..X
X..X
XXXX

Match found in rectangle: (9, 1), (14, 5)
.XXXX.
X....X
X....X
X....X
.XXXX.

Match found in rectangle: (13, 4), (17, 8)
.XXXX
X...X
X...X
X...X
.XXX.

Finally, some other features of Slip include:

• $0, $1, $2, ..., $7 anchor the north edge, north-east corner, east edge, etc. $+ anchors any edge and $* anchors any corner.
• $ followed by a lowercase character sets an anchor at the current position, which can later be matched by $ followed by the corresponding uppercase character, e.g. $a and $A.
• # toggles the no-move flag, which stops the match pointer from moving forward after the next match.
• , matches a char like ., but doesn't add it to the output, allowing for non-contiguous matches while being able to be recognised by (?_()).

... and more. There's really too many to list on this page.

Other problems

Problem 1 - Finding chessboards:

(?|`#?(`_`#)+`_?)(?_(1)(?|...+))(\(?_(1)(?|`#?(`_`#)+`_?$a)))+<(?|`#?(`_`#)+`_?)(?_(9)(?|...+))(\(?_(9)(?|`#?(`_`#)+`_?)))+$A

The two chessboard problems certainly aren't Slip's forte. We match the top row then make sure it's at least length 3 and alternates between # and _, then slip and match subsequent rows. By the end, the $a anchor should be at the bottom right of the chessboard.

We then turn left and repeat for columns, making sure we match $A at the end.

Problem 2 - Verifying chessboards:

$7%(\(?|`_?(`#`_)*`#?$2))+$5<%(\(?|`_?(`#`_)*`#?$0))+$3

Like the previous problem, we check that each row is correct, then rotate left and do the same for columns. Anchors are used to make sure only the whole board is matched.

Problem 9 - Horizontal and vertical alignment:

>?`#,*`#

We apply the optional ? quantifier to the > rotate command so that we either match rightward or downward. We find all 5 in the example with o overlapping mode, but only 4 without it since #.,## and #.,# start from the same position.

Problem 10 - Collinear points

^+`#(?|(,*)<(,*))(((?_(2),*)<(?_(3),*),>)+#`#){2}

Match a # then some horizontal chars and some vertical chars, then repeat until the second #, and repeat until the third #.

Problem 5 - Detecting square inputs:

$7.(.*)>(?_(1).*)$3>((?|.*)\)*

Anchor the top left corner, and check that the top edge is the same length as the right edge, before anchoring the bottom right corner. If the input passes this, then we go up backwards to match the whole input.

Problem 8 - Minecraft chest placement:

`.^+(($^|(?|`.))>){3}($^|`.|C<(($^|(?|`.))>){3})

Run with the p flag to get the positions of each match. $^ is an anchor which matches if the next move would put the match pointer out of bounds.

First we match a ., then check that we're surrounded by three .s/boundaries, then makes sure that the fourth surrounding square is also a ./boundary or is a single chest (by checking its surrounding squares).

Problem 11 - Verify Prelude syntax:

$7>%(/(?|[^()]+$4)(?1)?|/(?|[^()]*`([^()]*$4)(?1)?/(?|[^()]*`)[^()]*$4)(?1)?)$1

Took a few tries, but I think this one's correct. Here we use recursion, which has the same syntax as PCRE.

This approach requires that the input is rectangular, but once I get non-rectangular matching done that assumption won't be necessary.

Here's the same approach, golfed with more recursion:

$7>%((/(?|([^()]*)$4)|/(?|(?4)`((?3))(?1)?/(?|(?4)`)(?3)))*)$1

Problem 16 - Wrap around the edges:

%(\(?|`#{3})){3}

(Note: Wrapping has not yet been pushed to the online interpreter)

This requires the wrapping flag w. Technically the initial % for no-slip is not necessary, but then the match would be counted as starting from one square higher.

Problem EX 1 - Maze solver:

S(^+`.)*^+E

Problem from BMac's comment in chat. Use the r flag for no repeat mode so that the match pointer doesn't get stuck going back and forth.

Problem EX 2 - Facial recognition:

(?|O(,*),(?_(2),*)O)(?_(2)(\(?|,))*)\(?|,(?_(2),*)O)(?_(2)(\(?|,))*)\`\(?_(2)`_*)`_(?_(2)`_*)`/

Note that I'm only matching faces, not doing any clearing. Note that the question contains euro symbols, which will need to be replaced by some printable ASCII to work.

Answer 3

PMA/Snails (C++)

I envision the language as snails moving around a grid and executing commands. The snails leave a trail of slime on each square which they move onto, which by default causes the square to be subsequently unmatchable. A match is successful if the end of the list of commands is reached.

There are enough operators now that we're going to need a precedence list to keep track of them. The operations are resolved in the following order:

1. Inside of groups ( ) [ ]
2. Split along alternation character |
3. Evaluate everything to the left of a ` as a group
4. Quantifiers [m],[n] and n
5. Assertions = !
6. Concatenation

The interpreter is written in C++. The abysmal source code can be found here.

Problem 4: Word Search

The program

z\G\O\L\F

is sufficient to get a truthy or falsey value for whether the word is found. z (one of the 15 absolute or relative directional commands) matches in any octilinear direction. Multiple consecutive direction commands are ORed together. For example ruldy would be nearly equivalent to z, as those are the commands for right, up, left, down, and any diagonal direction. However, the directions would be tested in a different order. The first character matched is always the one the snail starts on, regardless of direction. \<character> matches a single literal character.

The default strategy is to try the pattern at every square in the bounding box of the left-justified input, and output the number of matches. If a boolean value 1 or 0 is required, the following program can be used:

?
z\G\O\L\F

If there is at least one newline in the source file, the first line is treated as options for the initial conversion of the input into a rectangular form. The ? option prints 0 or 1 depending on whether there is a match anywhere.

Problem 15: Boggle

After implementing alternation, it is now possible to solve Boggle. It would be better to use case-insensitive matching for this one, but implementing that is not my highest priority.

\p|\P)z(\a|\A)z{\n|\N)z{\a|\A}z(\m|\M)z(\a|\A

| works exactly the same as a 1-dimensional regex. There are two matching pairs of delimiters for grouping, namely () and {}. A closing bracket will close any open groups of the opposite type which stand between it and the nearest of the same type. For example, following {({{), only the leftmost group remains open. As you can see, unmatched grouping symbols at the edges are implicitly closed. There is another grouping command ` which I will not go into now.

Problem 8: Minecraft Chests

The program prints the number of valid chest placements. This was the first one I actually had to golf, and reduced my byte count (17) a few times.

\.!(o\C)2o(!\Cw)3

• \. matches a dot literally, at the starting point of the match.
• !(o\C)2 is equivalent to !((o\C)2) as quantification is higher precedence than assertion. <atom> <number> means to repeat <atom> exactly <number> times. o turns the snail in any orthogonal direction. ! is a negative assertion. Thus this part checks for the absence of an adjacent double chest.
• o turns in some orthogonal direction.
  • (!\Cw)3 asserts that there is no C in front of the snail, and then turns counterclockwise, 3 times.

Problem 2: Verifying chessboards

&
\#!(o^_)|\_!(o^#

The & option sets the program's output as 1 if the match succeeds at all positions, and 0 otherwise. ^c matches a character that is not c, equivalently to [^c] in regex. As a whole, the program means: Print 1 if at every position in the bounding rectangle of the input, there is either a # which is not orthogonally adjacent to a character that is not _, or an _ which is not orthogonally adjacent to a character that is not #; otherwise 0.

Answer 4

The Re2d class, Python 2

Update: added "9. Alignment" problem.

My approach is to use the Python re module to do the searching and matching. The Re2d class prepares the text for processing, executes the re functions, and formats the results for output.

Note that this is not a whole new language - it is the standard regular expression language projected into 2 dimensions with added flags for extra 2D modes.

The class has the following usage:

re2dobject = Re2d(<horizontal pattern>, [<vertical pattern>], [<flags>])

Both patterns are standard linear text RE patterns. If a vertical pattern is not supplied, the class will use the horizontal pattern for matching vertically too. The flags are the standard RE flags with some 2D extensions.

Testing

1. Finding chessboards
Chessboard pattern at (2, 1, 4, 3)

print '\n1. Finding chessboards'
reob1 = Re2d('#(_#)+_?|_(#_)+#?')
found = reob1.search('~______~\n~##_#_#~\n~#_#_##~\n~##_#_#~\n~______~')
print 'Chessboard pattern at', found
assert not reob1.search('#_##\n_#_#\n__#_\n#_#_\n#_#_')

The search method found a chessboard pattern and returns a 4-tuple position. The tuple has the x,y position of the first character of the match, and the width, height of the area matched. Only one pattern is given so it will be used for horizontal and vertical matching.

2. Verifying chessboards
Is chess? True

print '\n2. Verifying chessboards'
reob2 = Re2d('^#(_#)*_?|_(#_)*#?$')
print 'Is chess?', reob2.match('_#_#_#_#\n#_#_#_#_\n_#_#_#_#')
assert not reob2.match('_#_#_#__\n__#_#_#_\n_#_#_#__')

The chessboard was verified with the match method which returns a boolean. Note that the ^ and $ start and end characters are required to match the whole text.

3. Rectangle of digits
Found: [(0, 1, 5, 3), (1, 1, 4, 3), (2, 1, 3, 3), (3, 1, 2, 3), (0, 2, 5, 2), (1, 2, 4, 2), (2, 2, 3, 2), (3, 2, 2, 2), (6, 3, 2, 2)]
Not found: None

print '\n3. Rectangle of digits'
reob3 = Re2d(r'\d\d+', flags=MULTIFIND)
print 'Found:', reob3.search('hbrewvgr\n18774gwe\n84502vgv\n19844f22\ncrfegc77')
print 'Not found:', reob3.search('uv88wn000\nvgr88vg0w\nv888wrvg7\nvvg88wv77')

We now use the MULTIFIND flag to return all of the possible matches for the 2+ digit block. The method finds 9 possible matches. Note that they can be overlapping.

4. Word search (orthogonal only)
Words: [(0, 0, 4, 1), (0, 3, 4, 1), (3, 3, -4, -1), (3, 2, -4, -1), (3, 0, -4, -1)] [(0, 0, 1, 4), (3, 0, 1, 4), (3, 3, -1, -4), (0, 3, -1, -4)]
Words: ['SNUG', 'WOLF', 'FLOW', 'LORE', 'GUNS'] ['S\nT\nE\nW', 'G\nO\nL\nF', 'F\nL\nO\nG', 'W\nE\nT\nS']
No words: [] []

print '\n4. Word search (orthogonal only)'
words = 'GOLF|GUNS|WOLF|FLOW|LORE|WETS|STEW|FLOG|SNUG'
flags = HORFLIP | VERFLIP | MULTIFIND
reob4a, reob4b = Re2d(words, '.', flags), Re2d('.', words, flags)
matching = 'SNUG\nTEQO\nEROL\nWOLF'
nomatch = 'ABCD\nEFGH\nIJKL\nMNOP'
print 'Words:', reob4a.search(matching), reob4b.search(matching)
print 'Words:', reob4a.findall(matching), reob4b.findall(matching)
print 'No words:', reob4a.findall(nomatch), reob4b.findall(nomatch)

This test shows the use of vertical and horizontal flipping. This allows matching words that are reversed. Diagonal words are not supported. The MULTIFIND flag allows multiple overlapping matches in all 4 directions. The findall method uses search to find the matching boxes then extracts the matching blocks of text. Note how the search uses negative width and/or height for matches in the reverse direction. The words in the vertical direction have new line characters - this is consistent with the concept of 2D character blocks.

7. Calvins portals
Portals found: [(3, 1, 5, 6)]
Portal not found None

print '\n7. Calvins portals'
reob7 = Re2d(r'X\.{2,22}X|.X{2,22}.', r'X\.{3,22}X|.X{3,22}.', MULTIFIND)
yes = '....X......\n.XXXXXX.XX.\n...X...X...\n.X.X...XXX.\n...X...X.X.\n.XXX...X.X.\nX..XXXXX.X.'
no = 'XX..XXXX\nXX..X..X\nXX..X..X\n..X.X..X\n.X..X.XX'
print 'Portals found:', reob7.search(yes)
print 'Portal not found', reob7.search(no)

This search needed separate patterns for each dimension as the minimum size is different for each.

9. Alignment
Found: ['#.,##', '##'] ['#\n.\n,\n.\n#', '#\n,\n.\n#']
Found: [(3, 4, 5, 1), (6, 4, 2, 1)] [(7, 0, 1, 5), (3, 1, 1, 4)]
Not found: None None

print '\n9. Alignment'
reob9a = Re2d(r'#.*#', r'.', MULTIFIND)
reob9b = Re2d(r'.', r'#.*#', MULTIFIND)
matching = '.,.,.,.#.,\n,.,#,.,.,.\n.,.,.,.,.,\n,.,.,.,.,.\n.,.#.,##.,\n,.,.,.,.,.'
nomatch = '.,.#.,.,\n,.,.,.#.\n.,#,.,.,\n,.,.,.,#\n.#.,.,.,\n,.,.#.,.\n#,.,.,.,\n,.,.,#,.'
print 'Found:', reob9a.findall(matching), reob9b.findall(matching)
print 'Found:', reob9a.search(matching), reob9b.search(matching)
print 'Not found:', reob9a.search(nomatch), reob9b.search(nomatch)

This set of 2 searches finds 2 vertical and 2 horizontal matches, but cannot find the embedded #.,# string.

10. Collinear Points (orthogonal only)
Found: [(0, 1, 7, 1)] [(3, 1, 1, 4)]
Not found: None None

print '\n10. Collinear Points (orthogonal only)'
matching = '........\n#..#..#.\n...#....\n#.......\n...#....'
nomatch = '.#..#\n#..#.\n#....\n..#.#'
reob10h = Re2d(r'#.*#.*#', '.')
reob10v = Re2d('.', r'#.*#.*#')
flags = MULTIFIND
print 'Found:', reob10h.search(matching, flags), reob10v.search(matching, flags)
print 'Not found:', reob10h.search(nomatch, flags), reob10v.search(nomatch, flags)

Here we use 2 searches to find matches in both directions. It is able to find multiple orthogonal matches but this approach does not support diagonal matches.

12. Avoid qQ
Found: (2, 2, 4, 4)
Not found: None

print '\n12. Avoid qQ'
reob12 = Re2d('[^qQ]{4,4}')
print 'Found:', reob12.search('bhtklkwt\nqlwQklqw\nvtvlwktv\nkQtwkvkl\nvtwlkvQk\nvnvevwvx')
print 'Not found:', reob12.search('zxvcmn\nxcvncn\nmnQxcv\nxcvmnx\nazvmne')

This search finds the first match.

13. Diamond Mining
.X.
X.X
.X.

.X.
X.X
.X.

..X..
./.\.
X...X
.\./.
\.X..

..X..
./.\.
X...X
.\./.
..X..

.XX.\
//.\.
X...X
.\./.
..X..

...X...
../.\..
./.X.\.
X.X.X.X
.\.X.//
..\./X.
.X.X..\

Diamonds: [(2, 2, 3, 3), (0, 6, 3, 3)] [(8, 0, 5, 5), (10, 2, 5, 5), (5, 3, 5, 5)] [(0, 0, 7, 7)]
Not found: None None None

print '\n13. Diamond Mining'
reob13a = Re2d(r'.X.|X.X', flags=MULTIFIND)
reob13b = Re2d(r'..X..|./.\\.|X...X|.\\./.', flags=MULTIFIND)
reob13c = Re2d(r'...X...|../.\\..|./...\\.|X.....X|.\\.../.|..\\./..', flags=MULTIFIND)
match = '''
...X......X....
../.\..../.\...
./.X.\..X...X..
X.X.X.XX.\./.\.
.\.X.//.\.X...X
..\./X...X.\./.
.X.X..\./...X..
X.X....X.......
.X.............
'''.strip().replace(' ', '')
nomatch = '''
.X......./....
.\....X.......
...X.\.\...X..
..X.\...\.X.\.
...X.X...X.\.X
../X\...\...X.
.X...\.\..X...
..\./.X....X..
...X..../.....
'''.strip().replace(' ', '')
for diamond in reob13a.findall(match)+reob13b.findall(match)+reob13c.findall(match):
    print diamond+'\n'
print 'Diamonds:', reob13a.search(match), reob13b.search(match), reob13c.search(match)
print 'Not found:', reob13a.search(nomatch), reob13b.search(nomatch), reob13c.search(nomatch)

The diamond problem is more difficult. Three search objects are needed for the three sizes. It can find the six diamonds in the test set, but it does not scale to variable sized diamonds. This is only a partial solution to the diamond problem.

Python 2 code

import sys
import re

DEBUG = re.DEBUG
IGNORECASE = re.IGNORECASE
LOCALE = re.LOCALE
UNICODE = re.UNICODE
VERBOSE = re.VERBOSE
MULTIFIND = 1<<11
ROTATED = 1<<12     # not implemented
HORFLIP = 1<<13
VERFLIP = 1<<14
WRAPAROUND = 1<<15  # not implemented

class Re2d(object):
    def __init__(self, horpattern, verpattern=None, flags=0):
        self.horpattern = horpattern
        self.verpattern = verpattern if verpattern != None else horpattern
        self.flags = flags

    def checkblock(self, block, flags):
        'Return a position if block matches H and V patterns'
        length = []
        for y in range(len(block)):
            match = re.match(self.horpattern, block[y], flags)
            if match:
                length.append(len(match.group(0)))
            else:
                break
        if not length:
            return None
        width = min(length)
        height = len(length)
        length = []
        for x in range(width):
            column = ''.join(row[x] for row in block[:height])
            match = re.match(self.verpattern, column, flags)
            if match:
                matchlen = len(match.group(0))
                length.append(matchlen)
            else:
                break
        if not length:
            return None
        height = min(length)
        width = len(length)
        # if smaller, verify with RECURSIVE checkblock call:
        if height != len(block) or width != len(block[0]):
            newblock = [row[:width] for row in block[:height]]
            newsize = self.checkblock(newblock, flags)
            return newsize
        return width, height

    def mkviews(self, text, flags):
        'Return views of text block from flip/rotate flags, inc inverse f()'
        # TODO add ROTATED to generate more views
        width = len(text[0])
        height = len(text)
        views = [(text, lambda x,y,w,h: (x,y,w,h))]
        if flags & HORFLIP and flags & VERFLIP:
            flip2text = [row[::-1] for row in text[::-1]]
            flip2func = lambda x,y,w,h: (width-1-x, height-1-y, -w, -h)
            views.append( (flip2text, flip2func) )
        elif flags & HORFLIP:
            hortext = [row[::-1] for row in text]
            horfunc = lambda x,y,w,h: (width-1-x, y, -w, h)
            views.append( (hortext, horfunc) )
        elif flags & VERFLIP:
            vertext = text[::-1]
            verfunc = lambda x,y,w,h: (x, height-1-y, w, -h)
            views.append( (vertext, verfunc) )
        return views

    def searchview(self, textview, flags=0):
        'Return matching textview positions or None'
        result = []
        for y in range(len(textview)):
            testtext = textview[y:]
            for x in range(len(testtext[0])):
                size = self.checkblock([row[x:] for row in testtext], flags)
                if size:
                    found = (x, y, size[0], size[1])
                    if flags & MULTIFIND:
                        result.append(found)
                    else:
                        return found
        return result if result else None

    def search(self, text, flags=0):
        'Return matching text positions or None'
        flags = self.flags | flags
        text = text.split('\n') if type(text) == str else text
        result = []
        for textview, invview in self.mkviews(text, flags):
            found = self.searchview(textview, flags)
            if found:
                if flags & MULTIFIND:
                    result.extend(invview(*f) for f in found)
                else:
                    return invview(*found)
        return result if result else None

    def findall(self, text, flags=0):
        'Return matching text blocks or None'
        flags = self.flags | flags
        strmode = (type(text) == str)
        text = text.split('\n') if type(text) == str else text
        result = []
        positions = self.search(text, flags)
        if not positions:
            return [] if flags & MULTIFIND else None
        if not flags & MULTIFIND:
            positions = [positions]
        for x0,y0,w,h in positions:
            if y0+h >= 0:
                lines = text[y0 : y0+h : cmp(h,0)]
            else:
                lines = text[y0 : : cmp(h,0)]
            if x0+w >= 0:
                block = [row[x0 : x0+w : cmp(w,0)] for row in lines]
            else:
                block = [row[x0 : : cmp(w,0)] for row in lines]
            result.append(block)
        if strmode:
            result = ['\n'.join(rows) for rows in result]
        if flags & MULTIFIND:
            return result
        else:
            return result[0]

    def match(self, text, flags=0):
        'Return True if whole text matches the patterns'
        flags = self.flags | flags
        text = text.split('\n') if type(text) == str else text
        for textview, invview in self.mkviews(text, flags):
            size = self.checkblock(textview, flags)
            if size:
                return True
        return False

Answer 5

Grime, Haskell

Introduction

Grime is based on Boolean grammars. The basic idea is to construct rectangular patterns from smaller components, and check whether they are found in the input matrix. So far, Grime only supports rectangular matches, and solves at least 11 problems more or less elegantly.

EDIT: Fixed the crosses (thanks to DLosc for spotting the bug), and added diamond mining.

EDIT2: Added character classes, inspired by those of Slip. Also changed the syntax of option flags, improved the expression parser, and added the no-Q problem.

EDIT3: Implemented size constraints, and added the Nether portals problem.

Usage

A Grime program is called a grammar, and the correct file extension for a grammar is .gr, although this is not enforced. The grammar is evaluated as

runhaskell grime.hs [options] grammarfile matrixfile

where matrixfile is a file containing the character matrix. For example, the digits grammar would be evaluated as

runhaskell grime.hs digits.gr digit-matrix

For extra speed, I recommend compiling the file with optimizations:

ghc -O2 grime.hs
./grime digits.gr digit-matrix

By default, the interpreter prints the first match it finds, but this can be controlled using the option flags:

• -e: match only the entire matrix, print 1 for match and 0 for no match.
• -n: print the number of matches, or the entire matrix if -e is also given.
• -a: print all matches.
• -p: print also the positions of the matches, in the format (x,y,w,h).
• -s: do not print the matches themselves.
• -d: print debug information.

Options can also be specified within the grammar, by inserting them before any line and adding a comma , (see below for examples).

Syntax and Semantics

A Grime grammar consists of one or more definitions, each on a separate line. Each of them defines the value of a nonterminal, and one of them must define the anonymous toplevel nonterminal. The syntax of a definition is either N=E or E, where N is an uppercase letter and E is an expression.

Expressions are constructed as follows.

• Any character escaped with \ matches any 1x1 rectangle containing that character.
• . matches any single character.
• $ matches a 1x1 rectangle outside the character matrix.
• _ matches any rectangle of zero width or height.
• The pre-defined character groups are digit, uppercase, lowercase, alphabetic, alphanumeric, and symbol.
• New character classes can be defined by the syntax [a-prt-w,d-gu]. The letters on the left are included, and those on the right are excluded, so this matches exactly the letters abchijklmnoprtvw. If the left side is empty, it is taken to contain all characters. The comma can be omitted if the right side is empty. The characters [],-\ must be escaped with \.
• An unescaped uppercase letter is a nonterminal, and matches the expression it is assigned.
• If P and Q are expressions, then PQ is just their horizontal concatenation, and P/Q is their vertical concatenation, with P on top.
• P+ is one or more Ps aligned horizontally, and P/+ is the same aligned vertically.
• The Boolean operations are denoted P|Q, P&Q and P!.
• P? is shorthand for P|_, P* for P+|_, and P/* for P/+|_.
• P# matches any rectangle that contains a match of P.
• P{a-b,c-d}, where abcd are nonnegative integers, is a size constraint on P. If P is a character class, then the expression matches any mxn rectangle containing only those characters, provided that m is between a and b inclusive, and n is between c and d inclusive. In other cases, the expression matches any rectangle that has the correct size and that P also matches. If a or c are omitted, they are taken to be 0, and if b or d are omitted, they are infinite. If the hyphen between a and b is omitted, then we use the same number for both ends of the interval. If the entire c-d part is omitted, both axes are constrained. To clarify, {-b} is equivalent to {0-b,0-b}, and {a-,c} is equivalent to {a-infinity,c-c}.

Notes

Grime does allow paradoxical definitions like A=A! with undefined behavior. However, they will not cause crashes or infinite loops.

Grime supports non-rectangular inputs; the rows are simply aligned to the left, and the gaps can be matched using $.

In the future, I'd like to implement the following:

• Faster matching. Currently, the interpreter does not take into account the fact that, for example, . can only match 1x1 rectangles. Until it finds a match, it tries all rectangles of all sizes in order, instantly failing for each of them.
• Rotation and reflection operations, for the word search and glider challenges.

• Non-rectangular matches using contexts, which would be helpful in the Boggle board challenge. For example, Pv(Q>R) means P with bottom context (Q with right context R). It would match the L-shaped patterns

  PPP
  PPP
  QQQRRRR
  QQQRRRR
  QQQRRRR
  

The Tasks

Given roughly in order of complexity.

Rectangle of digits

d{2-}

This is simple: a rectangle of digits of size at least 2x2.

No q or Q

[,qQ]{4}

This is almost as simple as the first one; now we have a more restricted size and a custom character class.

Horizontal and vertical alignment

\#.*\#|\#/./*/\#

Now we have some escaped characters. Basically, this matches one #, then any number of any characters, then #, either horizontally or vertically.

Detect square inputs

S=.|S./+/.+
e,S

This grammar is very simple, it basically defines that a square is either a 1x1 rectangle, or a smaller square with one column tacked on its right edge, and one row tacked to the bottom of that. Note also the e option before the toplevel nonterminal, which toggles entire-input verification.

Finding a word in a word search

G=\G
O=\O
L=\L
F=\F
GOLF|FLOG|G/O/L/F|F/L/O/G|G.../.O../..L./...F|...G/..O./.L../F...|F.../.L../..O./...G|...F/..L./.O../G...

This one's horrible, since Grime has no operations for rotation or reflection. It is also extremely slow, since Grime does not know that the matches can only be of size 4x1, 1x4 or 4x4.

The glider problem could be solved similarly, but I'm too lazy to write that down.

Nether Portals

.\X+./\X/+\.{2-22,3-22}\X/+/.\X+.

With the size restriction operator, this one's not that hard. The middle part \.{2-22,3-22} matches any rectangle of . of the correct sizes, and then we just add columns of Xs on both sides, and tack rows of Xs with ignored ends on the top and bottom of that.

Matching crosses

E=\.+/+
F=\#+/+
EFE/F/EFE&(E/F/E)F(E/F/E)

What we have here is a conjunction (logical AND) of two expressions. The nonterminal E matches a nonempty rectangle of .s, and F a nonempty rectangle of #s. The left side of the conjunction matches rectangles of the type

...####..
...####..
...####..
#########
#########
.....##..
.....##..

where we have EFE on the top, then F, and then EFE again. The right side matches the transposes of these, so we get exactly the crosses.

Diamond mining

C=./+
T=\X|CTC/\/.+\\
B=\X|\\.+\//CBC
CTC/\X.+\X/CBC

The nonterminal C is a shorthand for any 1xn column. The top half of a diamond is matched by T: it is either a single X, or another T surrounded by a column on both sides, and a row /[something]\ below that. B matches the bottom of a diamond in the same way, and the toplevel nonterminal is just row of the form X[something]X between a top half and a bottom half.

Finding chessboards

(\#\#|\#/\#|\_\_|\_/\_)#!&[#_]{3-}

The right-hand side [#_]{3-} matches any 3x3 or larger rectangle of #s and _s, while the left-hand side guarantees that it does not contain two adjacent #s or _s.

Verifying chessboards

e,(\#\#|\#/\#|\_\_|\_/\_)#!&[#_]+/+

This is basically the same as above, except that we can match any non-empty rectangle, but need to use the e flag for entire input verification.

Verify Prelude syntax

A=[,()]/*
P=A*|P(A/\(/A)P(A/\)/A)P
e,P

This is probably the most interesting grammar so far. The nonterminal A matches any column not containing ( or ), and P matches either some number of As, or two matched parentheses, between and outside which there are more Ps.

Answer 6

TMARL

Template Matching and Recognition Language

Description

My interpreter takes up 24K chars (code snippets take up characters?), so the full description can be found here.

The best part: the interpreter is in Javascript, meaning you can try it right here!

var reservedOutsideInput = "\u0007";
var templateChar = "$"
function run(){
    var program = getCode();
    evaluate(program,{},{})
}

function getCode(){
    return document.getElementById('code-area').value;
}

//3 types of objects - templates, match arrays, and integers
function evaluate(program, variables,referenceObject){
    variables["I"] = {};
    variables["I"].value = getInput().split("\n");
    variables["I"].type = "array";
    var lines = program.split("\n");
    var argumentExpected = null;
    var jumpTo = null;
    for(var l = 0; l<lines.length; l++){
        if(!!jumpTo){
            l = jumpTo.line;
        }
        var line = lines[l];
        if(line[0] === templateChar){
            //next few lines is a template
            var template = findTemplate(lines,l);
            
            if(argumentExpected !== null){
                argumentExpected(template);
            }else{
                referenceObject.value = template;
                referenceObject.type = "template";
            }
            l += template.length - 1;
        }else{
            var i = 0;
            if(!!jumpTo){
                i = jumpTo.index;
                jumpTo = null;
            }
            while(i < line.length){
                var character = line[i];
                if(character === "P"){
                    output(referenceObject);
                    argumentExpected = null;
                }else if(character === "R"){
                    argumentExpected = function(arg){
                        referenceObject.value = rotate(referenceObject.value,arg);
                        referenceObject.type = "template";
                    };
                }else if(character === "M"){
                    referenceObject.value = mirror(referenceObject.value);
                    referenceObject.type = "template"
                    argumentExpected = null;
                }else if(character === "^"){
                    if(referenceObject.type === "int"){
                        argumentExpected = function(num){
                            referenceObject.value = Math.pow(referenceObject.value,num);
                            referenceObject.type = "int";
                        }
                    }else{
                        argumentExpected = function(template){
                            referenceObject.value = appendVertically(referenceObject.value,template,true);
                            referenceObject.type = "template";
                        }
                    }
                }else if(character === "v"){
                    argumentExpected = function(template){
                        referenceObject.value = appendVertically(referenceObject.value,template,false);
                        referenceObject.type = "template";
                    }
                }else if(character === "<"){
                    argumentExpected = function(template){
                        referenceObject.value = appendHorizontally(referenceObject.value,template, true);
                        referenceObject.type = "template";
                    }
                }else if(character === ">"){
                    argumentExpected = function(template){
                        referenceObject.value = appendHorizontally(referenceObject.value,template, false);
                        referenceObject.type = "template";
                    }
                }else if(character === "&"){
                    argumentExpected = function(searchArg){
                        referenceObject.value = referenceObject.value.concat(searchArg);
                        referenceObject.type = "search"
                    }
                }else if(character === "*"){
                    if(referenceObject.type === "int"){
                        argumentExpected = function(num){
                            referenceObject.value*=num;
                            referenceObject.type = "int";
                        }
                    }else{
                        argumentExpected = function(num){
                            referenceObject.value = multiply(referenceObject.value,num);
                            referenceObject.type = "template";
                        }
                    }
                }else if(character === "+"){
                    argumentExpected = function(num){
                        referenceObject.value+=num;
                        referenceObject.type = "int";
                    }
                }else if(character === "-"){
                    argumentExpected = function(num){
                        referenceObject.value-=num;
                        referenceObject.type = "int";
                    }
                }else if(character === "/"){
                    argumentExpected = function(num){
                        referenceObject.value = referenceObject.value / num;
                        referenceObject.type = "int";
                    }
                }else if(character === "%"){
                    argumentExpected = function(num){
                        referenceObject.value = referenceObject.value % num;
                        referenceObject.type = "int";
                    }
                }else if(character === "!"){
                    if(referenceObject.value === 0){
                        referenceObject.value = 1;
                    }else{
                        referenceObject.value = 0;
                    }
                    referenceObject.type = "int";
                }else if(character === "~"){
                    argumentExpected = function(num){
                        var original = copyTemplate(referenceObject.value);
                        while(num > 1){
                            referenceObject.value = appendHorizontally(referenceObject.value,original,true);
                            num--;
                        }
                        referenceObject.type = "template";
                    }
                }else if(character === "L"){
                    referenceObject.value = referenceObject.value.length;
                    referenceObject.type = "int";
                }else if(character === "S"){
                    argumentExpected = function(num){
                        var firstOnly = true;
                        var anyRotation = true;
                        if(num >= 4){firstOnly = false;}
                        else{firstOnly = true;}
                        if(num%2 === 0){anyRotation = true;}
                        else{anyRotation = false;}
                        referenceObject.value = search(getInput(),referenceObject.value, 
                            anyRotation,firstOnly);
                            
                        if(firstOnly){referenceObject.type = "match"}
                        else{referenceObject.type = "search";}
                    }
                }else if(character === "G"){
                    argumentExpected = function(num){
                        if(referenceObject.type === "search"){
                            referenceObject.value = referenceObject.value[num];
                            referenceObject.type = "match"
                        }else if(referenceObject.type === "match"){
                            if(num === 0){
                                referenceObject.value = referenceObject.value.x;
                                referenceObject.type = "int"
                            }
                            if(num === 1){
                                referenceObject.value = referenceObject.value.y;
                                referenceObject.type = "int";
                            }
                            if(num === 2){
                                referenceObject.value = referenceObject.value.match;
                                referenceObject.type = "2darray"
                            }
                        }else if(referenceObject.type === "array"){
                            referenceObject.value = referenceObject.value[num];
                            referenceObject.type = "string";
                        }else if(referenceObject.type === "string"){
                            referenceObject.value = referenceObject.value.charAt(num);
                            referenceObject.type = "char";
                        }
                    }
                }else if(character === "("){
                    var parenthese = getParentheses(lines, l, i);
                    var temp = evaluate(parenthese.content,variables,{});
                    if(!!argumentExpected){
                        argumentExpected(temp.value);
                    }else{
                        referenceObject.value = temp.value;
                        referenceObject.type = temp.type;
                    }
                    //keep the program in the loop to catch the jump
                    l--;
                    jumpTo = {line: parenthese.lineEnd, index: parenthese.indexEnd};
                    break;
                }else{
                    if(character < '0' || character > '9'){
                        if(!!variables[character]){
                            //the variable exists
                            if(argumentExpected !== null){
                                argumentExpected(variables[character].value);
                            }else{
                                referenceObject.value = variables[character].value;
                                referenceObject.type = variables[character].type;
                            }
                        }else{
                            variables[character] = {};
                            variables[character].value = cloneReference(referenceObject);
                            variables[character].type = referenceObject.type;
                        }
                    }else{
                        //character must be argument (its a number)
                        if(argumentExpected !== null){
                            argumentExpected(parseFloat(character));
                        }else{
                            referenceObject.value = parseFloat(character);
                            referenceObject.type = "int";
                        }
                    }
                    
                }
                i++;
            }
        }
    }
    return referenceObject;
}

function cloneReference(referenceObject){
    var newObject = {};
    if(referenceObject.type === "template"){
        newObject = copyTemplate(referenceObject.value);
    }
    if(referenceObject.type === "2darray"){
        newObject = copy2D(referenceObject.value);
    }
    if(referenceObject.type === "int"){
        newObject = referenceObject.value;
    }
    if(referenceObject.type === "search"){
        newObject = [];
        for(var i=0;i<referenceObject.value.length;i++){
            newObject.push({x:referenceObject.value[i].x,y:referenceObject.value[i].y,match:referenceObject.value.match});
        }
    }
    if(referenceObject.type === "match"){
        newObject = {x:referenceObject.value.x,y:referenceObject.value.y,match:referenceObject.value.match}
    }
    if(referenceObject.type === "string"){
        newObject = referenceObject.value;
    }
    if(referenceObject.type === "array"){
        newObject = copy(referenceObject.value);
    }
    if(referenceObject.type === "char"){
        newObject = referenceObject.value;
    }
    return newObject;
}

//returns {content, lineEnd, indexEnd}
function getParentheses(lines, line, index){
    var pointer = {line:line, index:index};
    var stack = [1];
    var content = "";
    while(stack.length > 0){
        pointer.index++;
        if(lines[pointer.line].length === pointer.index){
            pointer.line++;
            pointer.index = 0;
            content+="\n";
        }
        var character = lines[pointer.line].charAt(pointer.index);
        if(character === '('){
            stack.push(1);
        }
        if(character === ')'){
            stack.pop();
        }
        content += character;
    }
    pointer.index++;
    if(lines[pointer.line].length === pointer.index){
        pointer.line++;
        pointer.index = 0;
        content+="\n";
    }
    content = content.substring(0, content.length-1);
    return {content:content, lineEnd:pointer.line, indexEnd:pointer.index};
}

function getInput(){
    return document.getElementById("input").value;
}

function search(input, t, anyRotation, first){
    var inputArray = input.split("\n");
    processInput(inputArray);
    
    var possibleTemps = [t];
    if(anyRotation){
        possibleTemps.push(copyTemplate(rotate(t,1)));
        possibleTemps.push(copyTemplate(rotate(t,2)));
        possibleTemps.push(copyTemplate(rotate(t,3)));
    }
    var matches = [];
    for(var v = 0; v < possibleTemps.length; v++){
        var template = possibleTemps[v];
        for(var y = 0; y < inputArray.length; y++){
            for(var x = 0; x < inputArray[y].length; x++){
                var good = true;
                var match = matchTemplate(template);
                for(var ty = 0; ty < template.length; ty++){
                    for(var tx = 0; tx < template[ty].length; tx++){
                        var inputChar = null;
                        if(!!inputArray[y+ty]){
                            if(!!inputArray[y+ty][x+tx]){
                                inputChar = inputArray[y+ty][x+tx];
                            }
                        }
                        if(!charMatch(template[ty][tx],inputChar)){
                            good = false;
                        }else{
                            match[ty][tx] = inputChar;
                        }
                    }
                }
                if(good){
                    if(first){return {x:x,y:y,match:match}}
                    matches.push({x:x,y:y,match:match})
                }
            }
        }
    }
    return matches;
}

function processInput(inputArray){
    //add 'bell' character to outsides for edge recognition
    var filledTop = Array.apply(null, new Array(inputArray[0].length))
        .map(String.prototype.valueOf,reservedOutsideInput);
    var filledBottom = Array.apply(null, new Array(inputArray[inputArray.length-1].length))
        .map(String.prototype.valueOf,reservedOutsideInput);
    for(var row = 0; row < inputArray.length; row++){
        inputArray[row] = inputArray[row].split("");
        inputArray[row].splice(0,0,reservedOutsideInput);
        inputArray[row].push(reservedOutsideInput);
    }
    inputArray.splice(0,0,filledTop);
    inputArray.push(filledBottom);
}

function charMatch(templateC,inputChar){
    if(templateC.inCharClass === false && templateC.options[0] === "*" 
        && templateC.escaped === false){
        return true;
    }
    if(templateC.inCharClass === false && templateC.options[0] === "D" 
        && templateC.escaped === false){
        return inputChar >= '0' && inputChar <= '9'
    }
    if(templateC.inCharClass === false && templateC.options[0] === "L" 
        && templateC.escaped === false){
        return "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".indexOf(inputChar) > -1;
    }
    if(templateC.inCharClass === false && templateC.options[0] === "U" 
        && templateC.escaped === false){
        return "ABCDEFGHIJKLMNOPQRSTUVWXYZ".indexOf(inputChar) > -1;
    }
    if(templateC.inCharClass === false && templateC.options[0] === "l" 
        && templateC.escaped === false){
        return "abcdefghijklmnopqrstuvwxyz".indexOf(inputChar) > -1;
    }
    if(templateC.inCharClass === false && templateC.options[0] === "%" 
        && templateC.escaped === false){
        return inputChar === reservedOutsideInput;
    }
    if(templateC.options.indexOf('%') === -1 && inputChar === reservedOutsideInput){
        return false;
    }
    var good = false;
    if(templateC.not){
        good = true;
    }
    for(var i=0;i<templateC.options.length;i++){
        var option = templateC.options[i];
        console.log(templateC.not + ","+templateC.options)
        if(templateC.not && option === inputChar){
            good = false;
        }
        if(templateC.not === false && option === inputChar){
            good = true;
        }
    }
    return good;
    
}

function multiply(template, num){
    var original = copyTemplate(template);
    while(num > 1){
        template = template.concat(original);
        num--;
    }
    return template;
}

function copyTemplate(template){
    var newTemp = [];
    for(var y = 0; y< template.length; y++){
        newTemp[y] = [];
        for(var x = 0; x < template[y].length;x++){
            newTemp[y][x] = copyChar(template[y][x]);
        }
    }
    return newTemp;
}

function copyChar(character){
    return {not:character.not,options:copy(character.options),escaped:character.escaped,inCharClass:character.inCharClass};
}

function rotate(template,amount){
    while(amount > 0){
        var temp = box(template);
        var newTemplate = [];
        for(var x = 0; x < temp[0].length; x++){
            newTemplate[x] = [];
            for(var y = 0; y < temp.length; y++){
                newTemplate[x][temp.length-y-1] = temp[y][x];
            }
        }
        template = copyTemplate(newTemplate);
        amount--;
    }
    return template;
}

function box(template){
    var maxWidth = 0;
    var maxHeight = template.length;
    for(var y = 0; y < template.length;y++){
        if(template[y].length > maxWidth){maxWidth = template[y].length;}
    }
    var newTemplate = [];
    for(var row = 0 ; row < template.length; row++){
        newTemplate[row] = [];
        for(var x = 0; x < template[row].length;x++){
            newTemplate[row][x] = copyChar(template[row][x]);
        }
        while(newTemplate[row].length < maxWidth){
            newTemplate[row].push({not:false,inCharClass:false,options:["*"],escaped:false});
        }
    }
    return newTemplate;
}

//t1 over t2
function appendVertically(t1, t2, t1OnTop){
    var newTemplate = [];
    if(!t1OnTop){
        newTemplate = copyTemplate(t2).concat(copyTemplate(t1));
    }else{
        newTemplate = copyTemplate(t1).concat(copyTemplate(t2));
    }
    return newTemplate;
}

function appendHorizontally(t1, t2, t1OnLeft){
    var maxWidthT1 = 0;
    var maxWidthT2 = 0;
    for(var row=0;row<t1.length;row++){
        if(t1[row].length > maxWidthT1){maxWidthT1 = t1[row].length;}
    }
    for(var row2 = 0; row2 < t2.length;row2++){
        if(t2[row2].length > maxWidthT2){maxWidthT2 = t2[row2].length;}
    }
    var newTemplate = [];
    for(var r=0;r<Math.max(t1.length,t2.length);r++){
        newTemplate[r] = [];
        if(t1OnLeft){
            if(!!t1[r]){
                newTemplate[r] = newTemplate[r].concat(copyCharArray(t1[r]));
            }
            if(!!t2[r]){
                while(newTemplate[r].length < maxWidthT1){
                    newTemplate[r].push({not:false,inCharClass:false,options:["*"],escaped:false});
                }
                newTemplate[r] = newTemplate[r].concat(copyCharArray(t2[r]))
            }
        }else{
            if(!!t2[r]){
                newTemplate[r] = newTemplate[r].concat(copyCharArray(t2[r]));
            }
            if(!!t1[r]){
                while(newTemplate[r].length < maxWidthT2){
                    newTemplate[r].push({not:false,inCharClass:false,options:["*"],escaped:false});
                }
                newTemplate[r] = newTemplate[r].concat(copyCharArray(t1[r]))
            }
        }
    }
    return newTemplate;
}

function copyCharArray(array){
    var newArray = [];
    for(var i = 0; i<array.length;i++){
        newArray.push(copyChar(array[i]));
    }
    return newArray;
}

function mirror(template){
    template = box(template);
    for(var row = 0; row < template.length; row++){
        template[row].reverse();
    }
    return template;
}

function copy(array){
    var newArray = [];
    for(var i=0;i<array.length;i++){
        newArray.push(array[i].slice())
    }
    return newArray;
}

function copy2D(array){
    var newArray = [];
    for(var i=0;i<array.length;i++){
        newArray.push(copy(array[i]));
    }
    return newArray;
}

function matchTemplate(template){
    var result = [];
    for(var y=0;y<template.length;y++){
        result[y]=[];
        for(var x=0;x<template[y].length;x++){
            result[y][x] = template[y][x].options[0];
        }
    }
    return result;
}

//finds the template in the code and returns a template object
function findTemplate(lines,lineNum){
    var start = lineNum;
    while(lineNum < lines.length && lines[lineNum].indexOf(templateChar) > -1){lineNum++}
    var end = lineNum - 1;
    var templateArray = [];
    for(var l = start; l<=end; l++){
        var subArray = [];
        var line = lines[l];
        var started = false;
        for(var i = 0; i<line.length;i++){
            if(started){
                var character = line[i];
                var real = {};
                real.escaped = false;
                real.options = [];
                real.inCharClass = false;
                real.not = false;
                if(character === "["){
                    var content = getCharClass(line,i);
                    if(content.charAt(0) === "^"){
                        real.not = true;
                        real.inCharClass = true;
                        content =  content.substring(1,content.length);
                    }
                    for(var j = 0; j<content.length;j++){
                        real.options.push(content.charAt(j));
                    }
                    i+=content.length+1;
                    if(real.not){i++;}
                }else if(character === "\\"){
                    real.options.push(line[i+1]);
                    real.escaped = true;
                    i++;
                }else{
                    real.options.push(character);
                }
                subArray[subArray.length] = real;
            }
            if(line[i] === templateChar && started === false){started = true;}
        }
        templateArray[templateArray.length] = subArray;
    }
    return templateArray;
}

function getCharClass(line, index){
    var stack = [1];
    var pointer = index;
    var content = "";
    while(stack.length > 0 && pointer < line.length+1){
        pointer++;
        if(line[pointer] === ']'){
            stack.pop();
        }
        if(line[pointer] === '['){
            stack.push(1);
        }
        content+=line[pointer];
    }
    content = content.substring(0,content.length-1);
    return content;
}

function output(object){
    if(object === undefined){
        realOutput("undefined");
    }
    else if(object.type === "template"){
        for(var i = 0; i<object.value.length;i++){
            var result = "";
            result+=templateChar;
            for(var k = 0; k < object.value[i].length;k++){
                result+=object.value[i][k].options[0];
            }
            realOutput(result);
        }
    }else if(object.type === "search"){
        for(var a = 0; a < object.value.length; a++){
            realOutput("[x: "+object.value[a].x+", y: "+object.value[a].y+
                ", match: "+object.value[a].match+"]");
        }
    }else if(object.type === "match"){
        realOutput("x: "+object.value.x+", y: "+object.value.y+
                ", match: "+object.value.match);
    }else if(object.type === "2darray"){
        for(var h = 0; h<object.value.length;h++){
            var temp = ""
            for(var b = 0; b < object.value[h].length; b++){
                temp += object.value[h][b];
            }
            realOutput(temp);
        }
    }else{
        realOutput(object.value);
    }
}

function realOutput(text){
    document.getElementById("output").value += text+"\n";
}
function clearOutput(){
    document.getElementById("output").value = "";
}

html,body{
    margin:0;
    padding:0;
    height:100%;
    width:100%;
    overflow:auto;
}
#code-area,#input,#output{
    width:80%;
    height:20%;
    margin:5px;
}
#run-button{
    margin:5px;
}
span{
    margin:5px;
}

<span>Code:</span>
    <br>
    <textarea id="code-area"></textarea>
    <br>
    <span>Input:</span>
    <br>
    <textarea id="input"></textarea>
    <br>
    <button id="run-button" onclick="run()">Run</button>
    <button id="clear-button" onclick="clearOutput()">Clear</button>
    <br>
    <span>Output:</span>
    <br>
    <textarea id="output"></textarea>

And for the problems:

#1 - Finding Chessboards

$#_#
a
$_#_
bvacvbS5&(avcS5)G0G2P

& appends searches. The G2 at the end gets the 3rd element in a match element, the actual match. The first 2 elements are x and y coordinates (1 based, not 0).

#3 - Detect a Rectangle of Digits

$DD
$DD
S1G2P

I think this one is pretty straightforward.

#4 - Finding a Word in a Word Search

$GO\LF
a
$G
$*O
$**\L
$***F
S6&(aS6)G0G2P

The S argument is even so that it will search for all rotations. It is greater than 4 because it can then be appended to the next search (individual matches cannot be appended).

#5 - Detect Square Inputs

IL-(IG0L)!P

Not sure if this is completely legal, since it only determines the squareness correctly if the input is a rectangle. It compares the length of the input IL with the length of the first row IG0L and inverts it.

#6 - Find Gliders in a Game of Life

$## 
$# #
$# 
a
$ ##
$## 
$  #
bS6&(bMS6)&(aS6)&(aMS6)G0G2P

Finally, a use for mirror!

#12 - Avoid the Letter Q

$[^Qq]
~4*4S1G2P

S1 because only 1 match is needed.

I will do some of the harder ones later.