title: Language Design: 2-D Pattern Matching

text:
# Question
Title: Language Design: 2-D Pattern Matching
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>~______~
~##_#_#~
~#_#_##~
~##_#_#~
~______~
</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>#_##
_#_#
__#_
#_#_
#_#_
</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>_#_#_#_#
#_#_#_#_
_#_#_#_#
</code></pre><p><strong>No match</strong></p><pre><code>_#_#_#__
__#_#_#_
_#_#_#__
</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
18774gwe
84502vgv
19844f22
crfegc77
</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
vgr88vg0w
v888wrvg7
vvg88wv77
</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
IFWNOPH
VULUHGY
GUYOIGI
YTFUGYG
FTGYIOO
</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
ULUH
UYOI
TFUG
</code></pre><p><strong>No Match</strong></p><pre><code>BHTGIVUHSR
BWEVYWHBWB
BHTWBYTWYB
</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
asdfgh
zx vbn
uiop[]
`1234
67890-
</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
   world
</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>##         ##
# #  and  ##
#           #
</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>##   #
  # ##
#   # #
# #
##   ###
   # #
 #    #
</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>##   #
  # ###
##  # #
# #
##  ###
</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......
.XXXXXX.XX.
...X...X...
.X.X...XXX.
...X...X.X.
.XXX...X.X.
X..XXXXX.X.
</code></pre><p>This is a 3 wide by 4 tall portal.</p><p><strong>No Match</strong></p><pre><code>XX..XXXX
XX..X..X
XX..X..X
..X.X..X
.X..X.XX
</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..
...C..C...
.........C
.CC...CC..
..........
</code></pre><p>the pattern should match the cell marked by <code>*</code> in the following grid:</p><pre><code>******.C**
***C**C.**
*..***..*C
.CC.*.CC.*
*..***..**
</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>.,.,.,.#.,
,.,#,.,.,.
.,.,.,.,.,
,.,.,.,.,.
.,.#.,##.,
,.,.,.,.,.
</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>.,.#.,.,
,.,.,.#.
.,#,.,.,
,.,.,.,#
.#.,.,.,
,.,.#.,.
#,.,.,.,
,.,.,#,.
</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>........
#..#..#.
...#....
#.......
...#....
</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>.#..#
#..#.
#....
..#.#
</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)-
1   0v ^(#    0)(1+0)#)!
    (#)  ^#1-(0 #
</code></pre><p><strong>No match</strong></p><pre><code>#(#(##)##)##(
)##(##(##)#)#
</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
qlwQklqw
vtvlwktv
kQtwkvkl
vtwlkvQk
vnvevwvx
</code></pre><p>There is one 4x4 square that does not contain any Qs. This is</p><pre><code>vlwk
twkv
wlkv
vevw
</code></pre><p><strong>No Match</strong></p><pre><code>zxvcmn
xcvncn
mnQxcv
xcvmnx
azvmne
</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....
../.\..../.\...
./.X.\..X...X..
X.X.X.XX.\./.\.
.\.X.//.\.X...X
..\./X...X.\./.
.X.X..\./...X..
X.X....X.......
.X.............
</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......./....
.\....X.......
...X.\.\...X..
..X.\...\.X.\.
...X.X...X.\.X
../X\...\...X.
.X...\.\..X...
..\./.X....X..
...X..../.....
</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>.......
.###...
######.
######.
.###...
.###...
.###.#.
....###
.....#.
</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>.######.
...##...
...##...
........
</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
AaaKVsjL
onlGviCw
DdOgFrRn
ISeHZmqc
zMUkBGJQ
</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
AfEKVsjL
oblGviCw
DdOgArRn
ISepnmqc
zMUkBGJQ
</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
mAJVRLuF
jyXSPknK
hoeGcsEl
QCZagNMI
dvUOqixt
</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>#..##
#..##
.....
#..##
</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>...##
#..##
#..##
#..#.
</code></pre>

```

(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
> 32 votes
# 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 `P`iggyback 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 `E`xclusive 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
> 22 votes
# 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
> 18 votes
# 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
> 15 votes
# 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 `d`igit, `u`ppercase, `l`owercase, `a`lphabetic, alpha`n`umeric, and `s`ymbol.
* 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 `P`s 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 `X`s on both sides, and tack rows of `X`s 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 `A`s, or two matched parentheses, between and outside which there are more `P`s.

# Answer
> 14 votes
# 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
> 10 votes
# 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.

---
Tags: popularity-contest, string, grid, language-design
---


# Question
Title: Constructing an Orthogonal-Diagonal Greco-Latin Square
Consider a grid of `N`x`N` unique elements. Each element has a letter (from A to the `N`th letter, inclusive) and a number (from 1 to `N`, inclusive). Hence, each number/letter pair is in the grid exactly once.

Your job is to arrange a grid such that:

Each row, column, and diagonal (including wrapping) contains each letter and number exactly once.

By wrapping, I mean that

```
* * * # *
* * # * *
* # * * *
# * * * *
* * * * #

```

is a diagonal, along with all similar diagonals that hit the edges.

An example `5x5` grid is:

```
A1 B2 C3 D4 E5
C4 D5 E1 A2 B3
E2 A3 B4 C5 D1
B5 C1 D2 E3 A4
D3 E4 A5 B1 C2

```

Your task is to write a program that accepts a number, `N`, and print a `N`x`N` grid as described above. Your program should work for any `0 < N <= 26`. If a particular grid is not possible, then you should print `Impossible`.

Hardcoding the answer for any `N` is not allowed. A program is hard coded if it calculates the grid in different manner (as judged by me) for any `N > 26` (or if it fails to calculate). (This is meant to prevent precalculation, including precalculated invalid grids, or offsets for given grids).

This is a fastest-code problem, and your score is the sum of the times taken to run your program across all possible `N` on my computer. In your answer, please have your program run across all `N` (so I only have to time it once). If no program can compute it in under 60 seconds, then the winner is the answer that can calculate the grid with the largest `N` in 60 seconds. If multiple programs have the same maximum `N`, then the tiebreaker is the fastest solution.

(I have a decently powered Windows 8 machine, and any compilers or interpreters needed must be freely available for it).

# Answer
## Python 3

```
letters = []
numbers = []
for n in range(1,27):
    if n%2==0 or n%3==0:
        offsets=False
    else:
        offsets = [x for x in range(0,n,2)]
        offsets.extend([x for x in range(1,n,2)])
    letters.append(chr(96+n))
    numbers.append(n)
    if offsets :
        for y in range(n):
            for x in range(n):
                let=letters[(x+offsets[y])%n]
                num=numbers[(offsets[y]-x)%n]
                print (let+str(num), end= "  " if num<10 else " ")
            print("\n")
    else:
        print("Impossible\n")

```

## How it works?

The naive implementation would be to look through all the possible arrangements of letter and numbers in an NxN grid and look for one that is also a Orthogonal-Diagonal Latin Square (ODLS) (and thus, for some it would just have to go through all configurations and return impossible). Such an algorithm wouldnt suit this challenge due to absurd time complexity. So there are three major simplifications and justifications (partial proofs and insights to why it works) to ODLS constructions used in my implementation:

The first is the notion that we only need to generate a valid Diagonal Latin Square (A NxN grid such that each row, column, wrapped-diagonal contains each element of a set of N distinct elements exactly once) of the first N letters of the alphabet. If we can construct such a Diagonal Latin Square (DLS) then an ODLS can be constructed using the DLS with appropriate exchange of elements and flipping. Justification:

```
Let us first look at an example using the example grid
a1 b2 c3 d4 e5
c4 d5 e1 a2 b3
e2 a3 b4 c5 d1
b5 c1 d2 e3 a4
d3 e4 a5 b1 c2
Every ODLS can be separated into two DLS (by definition), so
we can separate the grid above into two DLS, one containing letters, the other - numbers
a b c d e
c d e a b
e a b c d
b c d e a
d e a b c
and
1 2 3 4 5
4 5 1 2 3
2 3 4 5 1
5 1 2 3 4
3 4 5 1 2
If we transform the number DLS by the mapping 1-->e, 2-->d, 3-->c, 4-->b, 5-->a,
1 2 3 4 5 --> e d c b a
4 5 1 2 3 --> b a e d c
2 3 4 5 1 --> d c b a e
5 1 2 3 4 --> a e d c b
3 4 5 1 2 --> c b a e d
Now if we put the transformed number grid next to the original letter grid,
Original  | Transformed
a b c d e | e d c b a
c d e a b | b a e d c
e a b c d | d c b a e
b c d e a | a e d c b
d e a b c | c b a e d
It can be clearly seen that the number grid is a horizontal flip of
the letter grid withminor letter to number substitutions.
Now this works because flipping guarantees that no two pairs occur more than once,
and each DLS  satisfies the requirements of the ODLS.

```

The second simplification is the notion that if we found a suitable configuration (SC) of one element (A NxN grid such that each row, column, wrapped-diagonal contains that element exactly once), then a DLS could be constructed by replacing the element and shifting the SC. Justification:

```
If "_" is an empty space and "a" the element then a valid SC of a 7x7 grid is
a _ _ _ _ _ _
_ _ a _ _ _ _
_ _ _ _ a _ _
_ _ _ _ _ _ a
_ a _ _ _ _ _
_ _ _ a _ _ _
_ _ _ _ _ a _
or
a _ _ _ _ _ _
_ _ _ a _ _ _
_ _ _ _ _ _ a
_ _ a _ _ _ _
_ _ _ _ _ a _
_ a _ _ _ _ _
_ _ _ _ a _ _
(the second one can actually be obtained from the first one via rotation)
now say we took the second SC, shifted it one unit to the right and
replaced all "a" with "b"
a _ _ _ _ _ _       _ a _ _ _ _ _       _ b _ _ _ _ _
_ _ _ a _ _ _       _ _ _ _ a _ _       _ _ _ _ b _ _
_ _ _ _ _ _ a       a _ _ _ _ _ _       b _ _ _ _ _ _
_ _ a _ _ _ _  -->  _ _ _ a _ _ _  -->  _ _ _ b _ _ _
_ _ _ _ _ a _       _ _ _ _ _ _ a       _ _ _ _ _ _ b
_ a _ _ _ _ _       _ _ a _ _ _ _       _ _ b _ _ _ _
_ _ _ _ a _ _       _ _ _ _ _ a _       _ _ _ _ _ b _
Now if we overlaid the SC of "a" with the SC of "b" we get
a b _ _ _ _ _
_ _ _ a b _ _
b _ _ _ _ _ a
_ _ a b _ _ _
_ _ _ _ _ a b
_ a b _ _ _ _
_ _ _ _ a b _
If we repeated these steps for the other five letters, we would arrive at a DLS
a b c d e f g
e f g a b c d
b c d e f g a
f g a b c d e
c d e f g a b
g a b c d e f
d e f g a b c
This is a DLS, since each SC follows the general requirements of a DLS
and shifting ensured that each element has its own cell.
Another thing to note is that each row contains the string "abcdefg" that is offset
by some cells. This leads to another simplification: we only need to find the
offsets of the string in every row and we are finished.

```

The last simplification is as follows - all DLS of prime N, except for N=2 or N=3, can be constructed, and if N can be factored into two numbers whose appropriate DLS can be constructed, then a DLS of that N can be constructed. I conjecture that the converse also holds. (In other words we can only construct an DLS for N that is not divisible by 2 or 3)

```
Pretty obvious why 2x2 or 3x3 cant be made. For any other prime this can be done
by assigning a each consecutive row a shift that is by two bigger than the previous,
for N=5 and N=7 this looks like (with elements other than "a" ommited)
N=5
a _ _ _ _ offset = 0
_ _ a _ _ offset = 2
_ _ _ _ a offset = 4
_ a _ _ _ offset = 6 = 1 (mod 5)
_ _ _ a _ offset = 8 = 3 (mod 5)
N=7
a _ _ _ _ _ _ offset = 0
_ _ a _ _ _ _ offset = 2
_ _ _ _ a _ _ offset = 4
_ _ _ _ _ _ a offset = 6
_ a _ _ _ _ _ offset = 8 = 1 (mod 7)
_ _ _ a _ _ _ offset = 10 = 3 (mod 7)
_ _ _ _ _ a _ offset = 12 = 5 (mod 7
(Why this works on all prime N (actually all N that are not divisible
by 3 or 2) can probably be proven via some kind of induction but i will
omit that, this is just what my code uses and it works)
Now, the first composite number that is not
divisible by 2 or 3 is 25 (it also occurs in the range our program must test)
Let A denote the DLS of N = 5
a b c d e
d e a b c
b c d e a
e a b c d
c d e a b
Let F be the DLS A where each letter is substituted by the letter five postions after it
a-->f, b-->g etc. So F is
f g h i j
j e f g h
g h i j f
j f g h i
h i j f g
Let K be the DLS a where each letter is substituted by the letter ten postions after it
a-->k, b--> l etc.
Let P be defined likewise (so a-->p, b-->q etc)
Let U be defined likewise (so a-->u, b-->v etc)
Now, since the DLS A could be constructed, then by substituting a --> A, b--> F etc.
we get a DLS of N=5*5 (A has five rows and five columns and each is filled with a
grid of five rows and five columns)
A F K P U
P U A F K
F K P U A
U A F K P
K P U A F
Now since smaller DLS in the big DLS satisfies the
conditions of a DLS and the big one also satisfies the DLS conditions,
then the resulting grid is also a DLS

```

A picture of what i meant with the smaller - bigger DLS

```
Now this kind of thing works for all constructible N and can be proven similiarly.

I have a strong sense that the converse (if some N isnt constructible
(2 and 3) then no multiple of that N is constructible) is also true but have a hard time
proving it (test data up to N=30 (took a veeery long time to calculate) confirm it though)

```
> 5 votes

---
Tags: fastest-code, puzzle-solver, grid, permutations
---