Este es el desafío quincenal # 6 . Tema: Diseño del lenguaje

Hay una sala de chat para este desafío. ¡Ven y únete a nosotros si quieres discutir ideas!

Y ahora para algo completamente diferente...

Esta quincena, queremos experimentar con un nuevo tipo de desafío. En este desafío, ¡estarás diseñando un lenguaje! La coincidencia de patrones es un problema muy común en la programación y, a menudo, muy útil para el golf de código. Las expresiones regulares, por ejemplo, se pueden usar para detectar un patrón en una línea de texto. Sin embargo, no existen métodos establecidos para describir y detectar patrones bidimensionales.

El reto

Debe diseñar un lenguaje de coincidencia de patrones, que permita la descripción de patrones bidimensionales en bloques de texto. El modo de operación de su lenguaje será similar a las expresiones regulares (aunque su lenguaje no tiene que tener nada en común con regex de lo contrario):

• Como entrada, recibirá un bloque rectangular de texto. Puede suponer que el texto consta solo de caracteres ASCII imprimibles (0x20 a 0x7E), así como de nuevas líneas (0x0A) para separar las filas de la cuadrícula.
• Si se puede encontrar una coincidencia, de acuerdo con la descripción del patrón, como cualquier subconjunto de este bloque de texto, esta coincidencia debe devolverse o imprimirse. Si la coincidencia puede ser no rectangular, debe rellenarse a un área rectangular con algún carácter reservado. Si hay varias coincidencias válidas, puede decidir cómo se elige la coincidencia devuelta (la más grande, la más pequeña, la primera, etc.).

Para algunas aplicaciones, puede ser útil si su implementación puede devolver la posición de una coincidencia en lugar de la coincidencia misma, pero esto no es un requisito.

Como mínimo, su idioma debería poder hacer coincidir un patrón como una subregión contigua y rectangular de su entrada.

Su respuesta debe contener:

• Una descripción del idioma.
• Una implementación de trabajo . Puede ser un programa o un conjunto de funciones / clases en el idioma que elija.
• Debe demostrar su idioma mostrando cómo se puede usar para resolver los ejemplos que se proporcionan a continuación . Su idioma no tiene que ser capaz de hacer coincidir todos ellos, pero debe poder hacer coincidir al menos 8 de estos. Si su idioma puede hacer algo elegante que no pensamos, siéntase libre de incluirlo también.

Si su respuesta se basa en ideas existentes, está bien, pero por favor déle crédito a su debido tiempo.

Extensiones

Lo anterior describe el mínimo que debe cumplir una presentación válida. Sin embargo, varias generalizaciones podrían hacer que un lenguaje de coincidencia de patrones sea aún más útil, incluidos, entre otros:

• Ser capaz de anclar el patrón a uno o más bordes, de modo que se pueda verificar si toda la región de entrada tiene un cierto patrón.
• Produciendo todos los partidos en lugar de solo uno. Puedes elegir la semántica de las coincidencias superpuestas.
• Tomando texto no rectangular como entrada.
• Permitir que los patrones especifiquen coincidencias no rectangulares. En tal caso, la salida debe rellenarse a un rectángulo con algún carácter reservado.
• Permitir patrones para especificar coincidencias con agujeros.
• Permitir coincidencias no contiguas, como dos caracteres que aparecen con un cierto desplazamiento.
• Fácil especificación de rotaciones y reflexiones.
• Opcionalmente, trate la entrada cíclicamente como un cilindro o un toro, de modo que los bordes opuestos se consideren adyacentes.

Puntuación

El objetivo principal de este desafío es producir un lenguaje eficaz de coincidencia de patrones 2D que podría utilizarse en el futuro. Como tal, un sistema de puntaje como "la longitud combinada más corta para resolver los ejemplos" llevaría a la codificación de ciertas funciones a expensas de la usabilidad general. Por lo tanto, hemos decidido que este desafío se ejecuta mejor como un concurso de popularidad. La presentación con más votos netos gana. Si bien no podemos forzar cómo vota la gente, aquí hay algunas pautas sobre lo que los votantes deberían buscar idealmente:

• Expresividad. ¿Puede el lenguaje resolver una variedad de problemas, incluso más allá de los ejemplos presentados en esta pregunta? ¿Es compatible con alguna de las extensiones sugeridas?
• Legibilidad. ¿Qué tan intuitiva es la notación (al menos para las personas que conocen la sintaxis básica)?
• Golfitude Esto sigue siendo CodeGolf.SE. Para los propósitos de este sitio, por supuesto, sería bueno tener un lenguaje coincidente que necesite muy poco código para describir un patrón.

Problemas de ejemplo

El siguiente fragmento de pila muestra 16 problemas de ejemplo con los que un lenguaje de coincidencia de patrones 2-D podría solucionar. Cada ejemplo contiene una breve descripción del problema y luego suele ir seguido de un ejemplo de entrada donde se puede encontrar una coincidencia y un ejemplo donde no se puede encontrar una coincidencia (si corresponde).

Como se indicó anteriormente, su idioma solo necesita poder resolver 8 de estos problemas. Todo lo demás es opcional, pero, por supuesto, debería aumentar la cantidad de votos que obtenga.

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

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

(No, no es necesario que leas ese código HTML. Presiona el botón "Ejecutar fragmento de código" para que tu navegador lo muestre correctamente, que también puedes ver a pantalla completa).

SnakeEx

¡Resuelve 15/16 problemas hasta ahora!

Intérprete en línea ! - Especificación completa del idioma - Fuente Javascript

La idea detrás de este lenguaje es definir 'serpientes' que se mueven alrededor de los caracteres de verificación de texto usando una sintaxis tipo regex.

Un programa en SnakeEx consiste en una lista de definiciones para serpientes que utilizan diferentes secuencias de comandos. Las serpientes pueden engendrar otras serpientes usando estas definiciones, que es donde SnakeEx obtiene la mayor parte de su poder: podemos hacer coincidir las estructuras de ramificación e incluso hacer recursividad (ver ejemplo de coincidencia de Paren).

Esencialmente, cada programa se verá como un conjunto de expresiones regulares, pero con la adición de comandos de dirección de la forma <dir>que cambian la dirección de la serpiente, y los comandos de llamada de la forma {label<dir>params}que generan más serpientes.

Para un punto de entrada, el intérprete genera una serpiente usando la primera definición, moviéndose hacia la derecha.

No es terriblemente conciso, pero es muy poderoso y (creo) bastante legible.

Actualizaciones

• Cambiado para no lógico y ~ para no marcar coincidencias
• Agregado <!>para resolver colinear
• Cruces a juego resueltas
• Tableros de ajedrez resueltos de una manera menos terrible
• Sintaxis de cierre acotada añadida %{min,max}
• Ejemplo de recursión agregado

Soluciones

15 resueltos, 1 en progreso

¡Puede probar estos programas fácilmente con el Intérprete en línea vinculado anteriormente!

Problema 1 - Encontrar tableros de ajedrez

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

Para una introducción detallada, comience en el problema 3.

Problema 2: verificación de tableros de ajedrez

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

Terminar el libro de las serpientes apropiadas con el símbolo de fuera de los límites $es una forma de hacer que un programa coincida solo con la entrada completa.

Problema 3: detectar un rectángulo de dígitos

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

La mserpiente se mueve hacia la derecha, generando al menos 2 serpientes ( %{2,}es un cierre que significa "2 al infinito") usando la definición c ( c) y moviéndose hacia la derecha ( <R>), o más bien hacia abajo en este caso, porque todas las direcciones son relativas a la serpiente actual. El Aparámetro es el azúcar que solo especifica que la serpiente de desove debe moverse después de la llamada. El 1parámetro es cómo restringimos las coincidencias a los rectángulos: los parámetros numéricos colocan a las serpientes en "grupos". Una partida no cuenta a menos que todas las serpientes del mismo grupo viajen exactamente a la misma distancia.

Problema 4 - Encontrar una palabra en una búsqueda de palabras

m:<*>GOLF

El comando de dirección <*>especifica que la serpiente debe girar en cualquier dirección diagonal u ortogonal. Luego, busca la expresión regular simple.

Problema 5 - Detectar entradas cuadradas

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

La clave aquí es el carácter especial $, que solo coincide si la serpiente está fuera de los límites. Engendramos una serpiente horizontal y una vertical; cada uno de ellos genera más serpientes a medida que corre a lo largo del borde, y todos están en el mismo grupo y deben tener la misma longitud.

Problema 6 - Encuentra planeadores en un juego de la vida

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

mcomienza en cualquiera de las cuatro direcciones ortogonales ( <+>), logrando la rotación. Luego, se ve a la izquierda o derecha para las tres filas en orden, logrando la reflexión.

(Tenga en cuenta que he reemplazado los espacios con puntos solo porque las áreas de texto HTML utilizadas en mi intérprete parecen hacer cosas estúpidas si tienen múltiples espacios seguidos)

Problema 7 - Match Portales abisales

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

La mserpiente se mueve hacia la derecha, generando una serpiente para verificar el borde izquierdo, 2-22 serpientes para verificar las columnas del medio, y finalmente una serpiente para verificar el borde derecho. El ~operador indica que lo que sigue se debe verificar pero no se debe marcar como parte de la solución.

¡Los cierres limitados ahora nos permiten resolver este problema de forma completa y adecuada!

Problema 8 - Colocación del cofre de Minecraft

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

Aquí usamos un no lógico ( !), que coincide si y solo si el siguiente token no coincide con nada. La declaración ddetecta un cofre doble en una dirección particular, por !{d<+>}lo que se asegura de que no haya cofres dobles en ninguna dirección ortogonal. sse mueve en un pequeño diamante alrededor del cuadrado actual, verificando que al menos 3 de esos espacios estén vacíos o fuera del tablero. El final \.finalmente coincide con el cuadrado, suponiendo que todas las condiciones anteriores tuvieron éxito.

Problema 9 - Alineación horizontal y vertical

m:<R>?#~.*#

La serpiente mopcionalmente gira a la derecha ( <R>?) antes de hacer coincidir la secuencia. .es un comodín, como en regex.

Problema 10 - Puntos colineales

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

¡Con la adición de la <!>dirección, podemos resolver esto ahora! <!>es como, <+>pero en lugar de ramificarse en cuatro direcciones, se ramifica en todas las direcciones posibles.

Problema 12 - Evita la letra Q

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

Solo genera 4 serpientes que buscan cuatro caracteres que no son la letra Q.

Problema 13 - Minería de diamantes

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

Este es muy bueno. mgenera dos serpientes, una yendo hacia atrás a la derecha y otra hacia adelante a la derecha. Cada uno de ellos sigue las barras a una X, luego genera otra serpiente en ángulo recto a su dirección actual, que sigue las barras a la X inferior.

Problema 14 - Cruces coincidentes

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:#+

Esta es la primera vez que uso el Pparámetro iggyback. Normalmente las serpientes son independientes, pero si realiza una llamada con este parámetro, la serpiente que llama se moverá con la persona que llama. Entonces e2puede verificar una secuencia de '.', Luego una secuencia de '#', luego otra secuencia de '.', Y hacer que todas sean llamadas separadas para que podamos agruparlas con '1,' 2 'y' 3 ' , obligando a sus longitudes a coincidir.

Problema 15: unir una palabra en un tablero de Boggle

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

Simple, si es prolijo. IEl parámetro especifica mayúsculas y minúsculas (podemos especificar parámetros en las definiciones y en las llamadas). La serpiente gira en cualquier dirección, coincide con el personaje, gira de nuevo, y así sucesivamente.

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

Esta es la versión sin caracteres de reutilización. El Eparámetro xclusive prohíbe que la serpiente coincida con cualquier personaje que ya haya sido marcado, al igual que los rastros de baba de feersum.

Problema 16 - Envuelva los bordes

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

El Wparámetro permite que la serpiente se ajuste cuando se ejecuta fuera de los límites. También tenemos Hy Vpermitir solo envoltura horizontal o vertical.

Extra - Solucionador de laberintos

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

Resuelve un laberinto ASCII donde el piso transitable es períodos. La <P>dirección significa hacia adelante, izquierda o derecha (azúcar para [<F><L><R>]).

Extra - Emparejamiento Paren

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

Todavía no he descubierto cómo hacer Prelude, ¡pero aquí hay un primer paso! Aquí uso la rserpiente de forma recursiva para hacer coincidir los paréntesis correspondientes comprobando que no haya paréntesis sin igual entre ellos.

Extra - Topología ASCII: Bucles de conteo

Slip, Python 3.4 ( wiki de Github , intérprete en línea )

Al igual que el envío de feersum, esto también se basa en atravesar la cuadrícula, pero al igual que el envío de CarpetPython, esto se basa en expresiones regulares. De alguna manera parece que logré tomar el término medio.

Hay muchas características no implementadas que quiero agregar, así que, cuando sea relevante, he notado lo que pretendo hacer cuando tenga tiempo.

Actualizaciones

(Ver la página de Github para noticias detalladas)

• 5 de abril de 2015 : ¡Slip ahora tiene un intérprete en línea ! Todavía está en sus primeras etapas, por lo que puede haber algunos errores.

• 5 de abril de 2015 : ¡Actualización de eficiencia! Ahora, los portales inferiores hacen una gran entrada mucho más rápido (2s). También ha habido una serie de cambios de sintaxis, así que asegúrese de consultar el wiki. Numeración grupal también fija.

El deslizamiento tiene un puntero de coincidencia que comienza en un cuadrado particular y que inicialmente está orientado hacia la derecha. Cuando se hace coincidir un carácter, el puntero se mueve hacia adelante en la dirección actual (aunque la implementación no hace las cosas exactamente en ese orden).

La dirección del puntero del partido se puede establecer en una dirección particular con ^<digit>, en donde ^0, ^1, ^2, ..., ^7establecer el puntero a N, NE, E, ..., NW, respectivamente (las agujas del reloj en marcha).

Los siguientes accesos directos también están disponibles:

• ^* comprueba las 8 direcciones ortogonales o diagonales,
• ^+ comprueba las 4 direcciones ortogonales.

(Plan futuro: Permitir la configuración de direcciones arbitrarias, por ejemplo, (1, 2)para el movimiento del caballero)

Por ejemplo ( Problema 4 - Encontrar una palabra en una búsqueda de palabras ),

^*GOLF

intenta las 8 direcciones ortogonales o diagonales, buscando la palabra "GOLF". Por defecto, Slip intenta todos los cuadrados iniciales posibles y devuelve un resultado de cada uno, filtrando duplicados, por lo que una cuadrícula como

GOLF
O
L
FLOG

devuelve solo la fila superior y la fila inferior como coincidencias (ya que la fila superior y la columna izquierda "GOLF" comienzan desde el mismo cuadrado). Para obtener todas las coincidencias, ose puede utilizar el modo de coincidencia superpuesta.

Del mismo modo ( Problema 15 - Une una palabra en un tablero de Boggle ),

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

coincide panamaintentando una dirección diferente cada vez. Use la ibandera para la insensibilidad a mayúsculas y minúsculas. Slip reutiliza los caracteres de forma predeterminada, pero esto se puede alternar con el rindicador de no repetición.

(Plan futuro: un modificador de modo de búsqueda que verifica automáticamente conjuntos de direcciones después de cada movimiento para que no ^*sea ​​necesario repetir )

La dirección del puntero del partido también se puede girar 90 grados hacia la izquierda o hacia la derecha con <o >respectivamente. Por ejemplo,

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

busca el patrón

  #
## 
 ##

mirando en el siguiente orden:

765
894
123

Esto nos permite resolver el problema 6: encontrar planeadores con

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

donde las partes 1 y 2 codifican las formas del planeador, y las partes 3 y 4 codifican sus contrapartes reflejadas.

Tenga en cuenta que Slip usa la tecla `de retroceso para escapar. Esto se debe a que Slip tiene otra forma de movimiento que le da nombre al idioma: el comando slip. /desliza el puntero de coincidencia ortogonalmente hacia la izquierda, mientras \desliza el puntero de coincidencia ortogonalmente hacia la derecha.

Por ejemplo,

abc   ghi
   def

puede ser igualada por abc\def/ghi.

Si bien no es particularmente útil por sí solo, el deslizamiento se vuelve más importante cuando se combina con el (?| <regex> )grupo estacionario, que actúa como una búsqueda anticipada coincidente. La expresión regular en el interior coincide, luego, al final, la posición y la dirección del puntero de coincidencia se restablecen al estado anterior al grupo estacionario.

Por ejemplo,

abc
def
ghi

se pueden combinar con (?|abc)\(?|def)\(?|ghi).

Del mismo modo, el problema 12: evitar la letra Q se puede resolver con

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

donde %hay un comando antideslizante para detener la \activación del primero .

El deslizamiento también tiene una aserción de longitud (?_(<group num>) <regex> ), que solo coincide con la expresión regular dentro si su longitud de coincidencia es la misma que la del número de grupo dado.

Por ejemplo, Problema 13: la minería de diamantes se puede resolver fácilmente con

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

que intenta hacer coincidir el lado superior izquierdo del diamante primero, luego afirma que los otros tres lados tienen la misma longitud.

(Ejecutar con vbandera para salida detallada)

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

Una alternativa más golfista es

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

que coincide con el primer lado dos veces.

Muchos de los otros problemas se pueden resolver mediante deslizamiento, grupos estacionarios y afirmaciones de longitud:

Problema 14 - Cruces coincidentes:

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

Una vez que capture las anchuras de las .s y #s en la primera fila, es simplemente deslizarse hasta el fondo.

Salida:

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

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

Este probablemente se pueda jugar con un poco de recurrencia, una vez que solucione algunos errores.

Problema 3 - Detecta un rectángulo de dígitos:

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

Haga coincidir una fila superior de dos o más dígitos, luego asegúrese de que cada línea de abajo tenga la misma longitud. `des una clase de caracteres predefinida equivalente a [0-9].

Tenga en cuenta que esto encuentra todas las coincidencias .

Problema 7: coincide con los portales inferiores:

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

que sale, para el ejemplo superior en el hilo original :

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.

Finalmente, algunas otras características de Slip incluyen:

• $0, $1, $2, ..., $7ancla el borde norte, la esquina noreste, el borde este, etc. $+ancla cualquier borde y $*ancla cualquier esquina.
• $seguido de un carácter en minúscula establece un ancla en la posición actual, que luego puede coincidir $con el carácter en mayúscula correspondiente, por ejemplo, $ay $A.
• # alterna la bandera de no mover, lo que impide que el puntero de la partida avance después de la próxima partida.
• ,coincide con un carácter similar ., pero no lo agrega a la salida, lo que permite coincidencias no contiguas mientras puede ser reconocido por (?_()).

... y más. Realmente hay demasiados para enumerar en esta página.

Otros problemas

Problema 1 - Encontrar tableros de ajedrez:

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

Los dos problemas del tablero de ajedrez ciertamente no son el fuerte de Slip. Hacemos coincidir la fila superior y luego nos aseguramos de que tenga al menos la longitud 3 y alterna entre #y _, luego deslice y combine las filas posteriores. Al final, el $aancla debe estar en la parte inferior derecha del tablero de ajedrez.

Luego giramos a la izquierda y repetimos para las columnas, asegurándonos de que coincidamos $Aal final.

Problema 2 - Verificación de tableros de ajedrez:

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

Al igual que el problema anterior, verificamos que cada fila sea correcta, luego giramos a la izquierda y hacemos lo mismo para las columnas. Los anclajes se utilizan para asegurarse de que solo coincida toda la tabla.

Problema 9 - Alineación horizontal y vertical:

>?`#,*`#

Aplicamos el opcional? cuantificador al >comando rotar para que coincidamos hacia la derecha o hacia abajo. Encontramos los 5 en el ejemplo con omodo superpuesto, pero solo 4 sin él desde entonces #.,##y #.,#comenzamos desde la misma posición.

Problema 10 - Puntos colineales

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

Haga coincidir #unos caracteres horizontales y algunos caracteres verticales, luego repita hasta el segundo #y repita hasta el tercero #.

Problema 5 - Detección de entradas cuadradas:

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

Ancle la esquina superior izquierda y verifique que el borde superior tenga la misma longitud que el borde derecho, antes de anclar la esquina inferior derecha. Si la entrada pasa esto, entonces vamos hacia atrás para que coincida con toda la entrada.

Problema 8 - Colocación del cofre de Minecraft:

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

Corre con la pbandera para obtener las posiciones de cada partido. $^es un ancla que coincide si el próximo movimiento pondría el puntero fuera de límites.

Primero hacemos coincidir a ., luego verificamos que estamos rodeados por tres .s / límites, luego nos aseguramos de que el cuarto cuadrado circundante también sea un ./ límite o sea un solo cofre (verificando sus cuadrados circundantes).

Problema 11: verificar la sintaxis del preludio :

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

Hice algunos intentos, pero creo que este es correcto. Aquí usamos recursividad, que tiene la misma sintaxis que PCRE.

Este enfoque requiere que la entrada sea rectangular, pero una vez que haga una coincidencia no rectangular, esa suposición no será necesaria.

Aquí está el mismo enfoque, golf con más recursividad:

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

Problema 16 - Envuelva alrededor de los bordes:

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

(Nota: el ajuste aún no se ha enviado al intérprete en línea)

Esto requiere la bandera de ajuste w. Técnicamente, la inicial %para no deslizarse no es necesaria, pero luego el partido se contará como comenzar desde un cuadrado más alto.

Problema EX 1 - Solucionador de laberintos:

S(^+`.)*^+E

Problema del comentario de BMac en el chat . Use la rbandera para el modo de no repetición para que el puntero de coincidencia no se atasque yendo y viniendo.

Problema EX 2 - Reconocimiento facial :

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

Tenga en cuenta que solo estoy haciendo coincidir caras, no haciendo ningún borrado. Tenga en cuenta que la pregunta contiene símbolos de euro, que deberán ser reemplazados por algunos ASCII imprimibles para funcionar.

PMA / Caracoles (C ++)

Imagino el lenguaje como caracoles moviéndose alrededor de una cuadrícula y ejecutando comandos. Los caracoles dejan un rastro de limo en cada cuadro al que se mueven, lo que por defecto hace que el cuadrado sea inigualable. Una coincidencia tiene éxito si se alcanza el final de la lista de comandos.

Hay suficientes operadores ahora que vamos a necesitar una lista de precedencia para realizar un seguimiento de ellos. Las operaciones se resuelven en el siguiente orden:

1. Dentro de grupos ( ) [ ]
2. División a lo largo del carácter de alternancia |
3. Evalúa todo a la izquierda de a `como grupo
4. Cuantificadores [m],[n]yn
5. Aserciones = !
6. Concatenación

El intérprete está escrito en C ++. El código fuente abismal se puede encontrar aquí .

Problema 4: Búsqueda de palabras

El programa

z\G\O\L\F

es suficiente para obtener un valor verdadero o falso para determinar si se encuentra la palabra. z(uno de los 15 comandos direccionales absolutos o relativos) coincide en cualquier dirección octilineal. Múltiples comandos de dirección consecutivos son OR juntos. Por ejemplo ruldy, sería casi equivalente a z, ya que esos son los comandos para derecha, arriba, izquierda, abajo y cualquier dirección diagonal. Sin embargo, las instrucciones se probarían en un orden diferente. El primer personaje que coincide siempre es el que comienza el caracol, independientemente de la dirección. \<carácter> coincide con un único carácter literal.

La estrategia predeterminada es probar el patrón en cada cuadrado en el cuadro delimitador de la entrada justificada a la izquierda y generar el número de coincidencias. Si se requiere un valor booleano 1o 0, se puede utilizar el siguiente programa:

?
z\G\O\L\F

Si hay al menos una nueva línea en el archivo fuente, la primera línea se trata como opciones para la conversión inicial de la entrada en una forma rectangular. La ?opción imprime 0 o 1 dependiendo de si hay una coincidencia en alguna parte.

Problema 15: Boggle

Después de implementar la alternancia, ahora es posible resolver Boggle. Sería mejor utilizar coincidencias que no distingan entre mayúsculas y minúsculas para este, pero implementar esa no es mi máxima prioridad.

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

|funciona exactamente igual que una expresión regular unidimensional. Hay dos pares de delimitadores para agrupar, a saber, ()y {}. Un corchete de cierre cerrará cualquier grupo abierto del tipo opuesto que se interponga entre él y el más cercano del mismo tipo. Por ejemplo, a continuación {({{), solo el grupo de la izquierda permanece abierto. Como puede ver, los símbolos de agrupación no coincidentes en los bordes están implícitamente cerrados. Hay otro comando de agrupación en el `que no entraré ahora.

Problema 8: Cofres de Minecraft

El programa imprime el número de ubicaciones de cofres válidas. Este fue el primero que tuve que jugar al golf, y reduje mi número de bytes (17) varias veces.

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

• \. coincide con un punto literalmente, en el punto de partida del partido.
• !(o\C)2es equivalente a !((o\C)2)que la cuantificación tiene mayor precedencia que la afirmación. <atom> <number>significa repetir tiempos <atom>exactos <number>. ogira el caracol en cualquier dirección ortogonal. !Es una afirmación negativa. Por lo tanto, esta parte verifica la ausencia de un cofre doble adyacente.
• o gira en alguna dirección ortogonal.
  • (!\Cw)3afirma que no hay Cfrente al caracol y luego gira 3 veces en sentido antihorario.

Problema 2: Verificación de tableros de ajedrez

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

La &opción establece la salida del programa como 1si la coincidencia tuviera éxito en todas las posiciones, y de lo 0contrario. ^ccoincide con un carácter que no es c, equivalente a [^c]en regex. En conjunto, el programa significa: Imprimir 1 si en cada posición en el rectángulo delimitador de la entrada, hay una #que no es ortogonalmente adyacente a un carácter que no lo es _o una _que no es ortogonalmente adyacente a un carácter que es no #; de lo contrario 0.

La clase Re2d, Python 2

Actualización: se agregó el problema "9. Alineación".

Mi enfoque es usar el módulo Python re para hacer la búsqueda y la coincidencia. La clase Re2d prepara el texto para el procesamiento, ejecuta las funciones re y formatea los resultados para la salida.

Tenga en cuenta que este no es un lenguaje completamente nuevo: es el lenguaje de expresión regular estándar proyectado en 2 dimensiones con banderas agregadas para modos 2D adicionales.

La clase tiene el siguiente uso:

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

Ambos patrones son patrones RE estándar de texto lineal. Si no se proporciona un patrón vertical, la clase también usará el patrón horizontal para hacer coincidir verticalmente. Las banderas son las banderas RE estándar con algunas extensiones 2D.

Pruebas

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#_#_')

El método de búsqueda encontró un patrón de tablero de ajedrez y devuelve una posición de 4 tuplas. La tupla tiene la x,yposición del primer personaje del partido y la width, heightdel área coincidente. Solo se proporciona un patrón, por lo que se utilizará para la coincidencia horizontal y vertical.

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_#_#_#__')

El tablero de ajedrez se verificó con el método de coincidencia que devuelve un valor booleano. Tenga en cuenta que el ^e $inician y se requieren caracteres finales para que coincida con el conjunto del texto.

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')

Ahora usamos la MULTIFINDbandera para devolver todas las coincidencias posibles para el bloque de más de 2 dígitos. El método encuentra 9 posibles coincidencias. Tenga en cuenta que pueden superponerse.

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)

Esta prueba muestra el uso de volteo vertical y horizontal. Esto permite palabras coincidentes que se invierten. Las palabras diagonales no son compatibles. La MULTIFINDbandera permite múltiples coincidencias superpuestas en las 4 direcciones. El método findall utiliza la búsqueda para encontrar los cuadros coincidentes y luego extrae los bloques de texto coincidentes. Observe cómo la búsqueda usa ancho y / o alto negativo para coincidencias en la dirección inversa. Las palabras en la dirección vertical tienen nuevos caracteres de línea, esto es consistente con el concepto de bloques de caracteres 2D.

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)

Esta búsqueda necesitaba patrones separados para cada dimensión, ya que el tamaño mínimo es diferente para cada una.

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)

Este conjunto de 2 búsquedas encuentra 2 coincidencias verticales y 2 horizontales, pero no puede encontrar la #.,#cadena incrustada .

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)

Aquí usamos 2 búsquedas para encontrar coincidencias en ambas direcciones. Es capaz de encontrar múltiples coincidencias ortogonales, pero este enfoque no admite coincidencias diagonales.

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')

Esta búsqueda encuentra la primera coincidencia.

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)

El problema del diamante es más difícil. Se necesitan tres objetos de búsqueda para los tres tamaños. Puede encontrar los seis diamantes en el conjunto de prueba, pero no escala a diamantes de tamaño variable. Esta es solo una solución parcial al problema del diamante.

Código de Python 2

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

Mugre , Haskell

Introducción

Grime se basa en gramáticas booleanas . La idea básica es construir patrones rectangulares a partir de componentes más pequeños y verificar si se encuentran en la matriz de entrada. Hasta ahora, Grime solo admite coincidencias rectangulares y resuelve al menos 11 problemas de manera más o menos elegante.

EDITAR: se corrigieron las cruces (gracias a DLosc por detectar el error) y se agregó minería de diamantes.

EDIT2: Se agregaron clases de personajes, inspiradas en las de Slip. También cambió la sintaxis de los indicadores de opción, mejoró el analizador de expresiones y agregó el problema de no Q.

EDITAR3: Se implementaron restricciones de tamaño y se agregó el problema de los portales de Nether.

Uso

Un programa Grime se llama gramática , y la extensión de archivo correcta para una gramática es .gr, aunque esto no se aplica. La gramática se evalúa como

runhaskell grime.hs [options] grammarfile matrixfile

donde matrixfilees un archivo que contiene la matriz de caracteres. Por ejemplo, la gramática de los dígitos se evaluaría como

runhaskell grime.hs digits.gr digit-matrix

Para mayor velocidad, recomiendo compilar el archivo con optimizaciones:

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

De forma predeterminada, el intérprete imprime la primera coincidencia que encuentra, pero esto se puede controlar mediante los indicadores de opción:

• -e: coincide solo con toda la matriz, imprime 1por coincidencia y 0sin coincidencia.
• -n: imprime el número de coincidencias, o la matriz completa si -etambién se da.
• -a: imprime todos los partidos.
• -p: imprime también las posiciones de los partidos, en el formato (x,y,w,h).
• -s: no imprima las coincidencias ellos mismos.
• -d: imprime información de depuración.

Las opciones también se pueden especificar dentro de la gramática, insertándolas antes de cualquier línea y agregando una coma ,(ver ejemplos a continuación).

Sintaxis y Semántica

Una gramática de Grime consta de una o más definiciones , cada una en una línea separada. Cada uno de ellos define el valor de un no terminal , y uno de ellos debe definir el nivel anónimo no terminal . La sintaxis de una definición es N=Eo E, donde Nes una letra mayúscula y Ees una expresión .

Las expresiones se construyen de la siguiente manera.

• Cualquier carácter que se haya escapado \coincide con cualquier 1x1rectángulo que contenga ese carácter.
• . coincide con cualquier personaje individual.
• $coincide con un 1x1rectángulo fuera de la matriz de caracteres.
• _ coincide con cualquier rectángulo de ancho o alto cero.
• Los grupos de caracteres predefinidos son digit, uppercase, lowercase, alphabetic, alpha numeric y symbol.
• Las nuevas clases de caracteres se pueden definir por la sintaxis [a-prt-w,d-gu]. Se incluyen las letras de la izquierda y se excluyen las de la derecha, por lo que coincide exactamente con las letras abchijklmnoprtvw. Si el lado izquierdo está vacío, se considera que contiene todos los caracteres. La coma se puede omitir si el lado derecho está vacío. Los personajes [],-\deben escapar con \.
• Una letra mayúscula sin escape no es un terminal y coincide con la expresión que se le asigna.
• Si Py Qson expresiones, entonces PQes solo su concatenación horizontal, y P/Qes su concatenación vertical, con Parriba.
• P+es uno o más Ps alineados horizontalmente, y P/+es el mismo alineado verticalmente.
• Las operaciones booleanas se denotan P|Q, P&Qy P!.
• P?es la abreviatura de P|_, P*para P+|_y P/*para P/+|_.
• P#coincide con cualquier rectángulo que contenga una coincidencia de P.
• P{a-b,c-d}, donde abcdhay enteros no negativos, es una restricción de tamaño en P. Si Pes una clase de caracteres, entonces la expresión coincide con cualquier mxnrectángulo que contenga solo esos caracteres, siempre que mesté entre ae binclusive, y nesté entre ce dinclusive. En otros casos, la expresión coincide con cualquier rectángulo que tenga el tamaño correcto y que Ptambién coincida. Si ao cse omiten, que se considera que son 0, y si bo dse omiten, que son infinitos. Si se omite el guión entre ay b, entonces usamos el mismo número para ambos extremos del intervalo. Si todoc-dse omite parte, ambos ejes están restringidos. Para aclarar, {-b}es equivalente a {0-b,0-b}, y {a-,c}es equivalente a {a-infinity,c-c}.

Notas

Grime permite definiciones paradójicas como A=A!con el comportamiento indefinido. Sin embargo, no causarán bloqueos o bucles infinitos.

Grime admite entradas no rectangulares; las filas se alinean simplemente a la izquierda y los espacios se pueden combinar usando $.

En el futuro, me gustaría implementar lo siguiente:

• Emparejamiento más rápido. Actualmente, el intérprete no tiene en cuenta el hecho de que, por ejemplo, .solo puede coincidir con 1x1rectángulos. Hasta que encuentre una coincidencia, intenta todos los rectángulos de todos los tamaños en orden, fallando instantáneamente para cada uno de ellos.
• Operaciones de rotación y reflexión, para la búsqueda de palabras y desafíos de planeadores.

• Partidos no rectangulares que utilizan contextos , lo que sería útil en el desafío del tablero Boggle. Por ejemplo, Pv(Q>R)significa Pcon contexto inferior ( Qcon contexto correcto R). Coincidiría con los patrones en forma de L

  PPP
  PPP
  QQQRRRR
  QQQRRRR
  QQQRRRR
  

Las tareas

Dado aproximadamente en orden de complejidad.

Rectángulo de dígitos

d{2-}

Esto es simple: un rectángulo de dígitos de tamaño al menos 2x2.

No q o Q

[,qQ]{4}

Esto es casi tan simple como el primero; ahora tenemos un tamaño más restringido y una clase de caracteres personalizada.

Alineación horizontal y vertical

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

Ahora tenemos algunos personajes escapados. Básicamente, esto coincide con uno #, luego cualquier número de caracteres, luego #, ya sea horizontal o verticalmente.

Detectar entradas cuadradas

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

Esta gramática es muy simple, básicamente define que un cuadrado es un 1x1rectángulo o un cuadrado más pequeño con una columna pegada en su borde derecho y una fila pegada en la parte inferior. Tenga en cuenta también la eopción antes del nivel superior no terminal, que alterna la verificación de entrada completa.

Encontrar una palabra en una búsqueda de palabras

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...

Este es horrible, ya que Grime no tiene operaciones de rotación o reflexión. También es extremadamente lento, ya que Grime no sabe que los partidos solo pueden ser de tamaño 4x1, 1x4o 4x4.

El problema del planeador podría resolverse de manera similar, pero soy demasiado vago para escribirlo.

Portales abisales

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

Con el operador de restricción de tamaño, este no es tan difícil. La parte central \.{2-22,3-22}coincide con cualquier rectángulo de .los tamaños correctos, y luego solo agregamos columnas de Xs en ambos lados, y agregamos filas de Xs con extremos ignorados en la parte superior e inferior de eso.

Cruces a juego

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

Lo que tenemos aquí es una conjunción (lógica Y) de dos expresiones. El no terminal Ecoincide con un rectángulo no vacío de .s y Fun rectángulo no vacío de #s. El lado izquierdo de la conjunción coincide con rectángulos del tipo

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

donde tenemos EFEen la parte superior, luego F, y luego EFEotra vez. El lado derecho coincide con las transposiciones de estos, por lo que obtenemos exactamente las cruces.

Minería de diamantes

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

El no terminal Ces una abreviatura de cualquier 1xncolumna. La mitad superior de un diamante se corresponde con T: es un simple Xu otro Trodeado por una columna en ambos lados, y una fila /[something]\debajo de eso. Bcoincide con la parte inferior de un diamante de la misma manera, y el nivel superior no terminal es solo una fila de la forma X[something]Xentre la mitad superior y la mitad inferior.

Encontrar tableros de ajedrez

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

El lado derecho [#_]{3-}coincide con uno 3x3o más rectángulos de #sys _, mientras que el lado izquierdo garantiza que no contiene dos #s o _s adyacentes .

Verificando tableros de ajedrez

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

Esto es básicamente lo mismo que el anterior, excepto que podemos hacer coincidir cualquier rectángulo no vacío, pero necesitamos usar el eindicador para la verificación de entrada completa.

Verifique la sintaxis del preludio

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

Esta es probablemente la gramática más interesante hasta ahora. El no terminal Acoincide con cualquier columna que no contenga (o ), y Pcoincide con algún número de As, o dos paréntesis coincidentes, entre y fuera de los cuales hay más Ps.

TMARL

Lenguaje de reconocimiento y coincidencia de plantillas

Descripción

Mi intérprete ocupa 24K caracteres (¿los fragmentos de código toman caracteres? ), Por lo que la descripción completa se puede encontrar aquí .

La mejor parte: el intérprete está en Javascript, lo que significa que puedes probarlo aquí mismo.

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 = "";
}