C'est le défi bimensuel n ° 6 . Thème: Conception de la langue

Il y a une salle de discussion pour ce défi. Venez nous rejoindre si vous voulez discuter d’idées!

Et maintenant pour quelque chose de complètement différent...

Cette quinzaine, nous voulons expérimenter un nouveau type de défi. Dans ce défi, vous allez concevoir une langue! La correspondance de modèle est un problème très courant en programmation et souvent très utile pour le golf de code. Les expressions régulières, par exemple, peuvent être utilisées pour détecter un motif dans une ligne de texte. Cependant, il n’existe aucune méthode établie pour décrire et détecter les régularités bidimensionnelles.

Le défi

Vous devez concevoir un langage de correspondance de modèle qui permette la description de modèles bidimensionnels dans des blocs de texte. Le mode de fonctionnement de votre langue sera similaire à celui des expressions régulières (bien que votre langue n'ait rien d'autre en commun avec regex sinon):

• En entrée, vous recevrez un bloc de texte rectangulaire. Vous pouvez supposer que le texte ne comprend que des caractères ASCII imprimables (0x20 à 0x7E) ainsi que des nouvelles lignes (0x0A) pour séparer les lignes de la grille.
• Si une correspondance, conformément à la description du modèle, peut être trouvée en tant que sous-ensemble de ce bloc de texte, cette correspondance doit être renvoyée ou imprimée. Si la correspondance peut être non rectangulaire, elle doit être complétée dans une zone rectangulaire avec un caractère réservé. S'il existe plusieurs correspondances valides, vous pouvez décider comment la correspondance renvoyée est choisie (la plus grande, la plus petite, la première, etc.).

Pour certaines applications, il peut être utile que votre implémentation puisse renvoyer la position d'une correspondance au lieu de la correspondance elle-même, mais cela n'est pas obligatoire.

À tout le moins, votre langue devrait pouvoir faire correspondre un modèle en tant que sous-région rectangulaire contiguë de son entrée.

Votre réponse devrait contenir:

• Une description de la langue.
• Une mise en œuvre de travail . Cela peut être un programme ou un ensemble de fonctions / classes dans la langue de votre choix.
• Vous devriez montrer votre langage en montrant comment il peut être utilisé pour résoudre les exemples fournis ci-dessous . Votre langue ne doit pas nécessairement être capable de les faire correspondre à toutes, mais vous devez être capable d’en faire correspondre au moins 8 . Si votre langue peut faire quelque chose d'extraordinaire auquel nous n'avions pas pensé, n'hésitez pas à l'inclure également.

Si votre réponse s'appuie sur des idées existantes, c'est très bien, mais merci de bien vouloir le créditer.

Les extensions

Ce qui précède décrit le minimum qu'une soumission valide doit satisfaire. Cependant, plusieurs généralisations pourraient rendre un tel langage de correspondance de modèle encore plus utile, notamment:

• Être capable d'ancrer le motif à un ou plusieurs bords, de sorte que l'on puisse vérifier si toute la région d'entrée a un certain motif.
• Produire tous les matches au lieu d'un seul. Vous pouvez choisir la sémantique des correspondances qui se chevauchent.
• Prendre un texte non rectangulaire en entrée.
• Permettre aux modèles de spécifier des correspondances non rectangulaires. Dans un tel cas, la sortie devrait être complétée en un rectangle avec un caractère réservé.
• Permettre aux modèles de spécifier des correspondances avec des trous.
• Permettre des correspondances non contiguës, comme deux caractères apparaissant avec un certain décalage.
• Spécification facile des rotations et des réflexions.
• Traiter éventuellement l'entrée cycliquement comme un cylindre ou un tore, de sorte que les bords opposés soient considérés comme adjacents.

Notation

Le principal objectif de ce défi est de produire un langage de filtrage de motifs 2D efficace pouvant éventuellement être utilisé à l'avenir. En tant que tel, un système de notation du type "longueur combinée la plus courte pour résoudre les exemples" conduirait à coder en dur certaines fonctionnalités aux dépens de la convivialité générale. Par conséquent, nous avons décidé que ce défi serait mieux géré comme un concours de popularité. La soumission avec le plus de votes nets gagne. Bien que nous ne puissions pas forcer les gens à voter, voici quelques lignes directrices concernant ce que les électeurs devraient idéalement rechercher:

• Expressivité. Le langage peut-il résoudre divers problèmes, même au-delà des exemples présentés dans cette question? Est-ce qu'il supporte les extensions suggérées?
• Lisibilité. À quel point la notation est-elle intuitive (du moins pour les personnes connaissant la syntaxe de base)?
• Golfitude. C'est toujours CodeGolf.SE. Pour les besoins de ce site, il serait bien sûr d’avoir un langage correspondant qui nécessite très peu de code pour décrire un motif.

Exemple de problèmes

Le fragment de pile ci-dessous montre 16 exemples de problèmes qu’un langage de correspondance de modèle 2D pourrait traiter. Chaque exemple contient une courte description du problème. Il est ensuite généralement suivi d'un exemple d'entrée où une correspondance peut être trouvée et d'un exemple où aucune correspondance ne peut être trouvée (le cas échéant).

Comme indiqué ci-dessus, votre langue n'a besoin que de pouvoir résoudre 8 de ces problèmes. Tout ce qui est supplémentaire est facultatif, mais il faut bien entendu augmenter le nombre de votes obtenus.

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;

(Non, vous n'avez pas besoin de lire ce code HTML. Appuyez sur le bouton "Exécuter l'extrait de code" pour obtenir un rendu fidèle par votre navigateur, que vous pourrez ensuite afficher en plein écran.)

SnakeEx

Résout 15/16 problèmes jusqu'à présent!

Interprète en ligne ! - Spéc. De langage complet - Source Javascript

L'idée derrière ce langage est de définir des "serpents" qui se déplacent dans le texte en vérifiant les caractères en utilisant une syntaxe de type regex.

Un programme dans SnakeEx consiste en une liste de définitions pour les serpents utilisant différentes séquences de commandes. Les serpents peuvent engendrer d'autres serpents à l'aide de ces définitions. C’est là que SnakeEx tire le meilleur parti de sa puissance: nous pouvons faire correspondre les structures de branchement et même faire de la récursion (voir l’exemple de Paren Matching).

Chaque programme ressemblera essentiellement à un ensemble de regex, mais avec l’ajout de commandes de direction de la forme <dir>qui changent la direction du serpent et d’ appeler des commandes de la forme {label<dir>params}qui engendrent plus de serpents.

Pour un point d'entrée, l'interprète génère un serpent en utilisant la première définition, en se déplaçant vers la droite.

Ce n'est pas très concis, mais c'est très puissant et (je pense) assez lisible.

Mises à jour

• Modifié ! Logiquement pas et ~ ne pas marquer les correspondances
• Ajouté <!>pour résoudre colinéaire
• Résoudre les croix correspondantes
• Résoudre les échiquiers d'une manière moins terrible
• Ajout de la syntaxe de fermeture liée %{min,max}
• Exemple de récursion ajouté

Solutions

15 résolus, 1 en cours

Vous pouvez facilement essayer ces programmes en utilisant l’interprète en ligne (lien ci-dessus)!

Problème 1 - Trouver des échiquiers

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

Pour une introduction détaillée, commencez par le problème 3.

Problème 2 - Vérification des échiquiers

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

Mettre fin aux livres avec les symboles hors limites $est un moyen de faire en sorte qu'un programme ne corresponde qu'à la totalité de l'entrée.

Problème 3 - Détecter un rectangle de chiffres

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

Le mserpent se déplace vers la droite, apparaissant à au moins 2 serpents ( %{2,}une fermeture signifie "2 à l'infini") en utilisant la définition c ( c) et en se déplaçant vers la droite ( <R>), ou plutôt vers le bas dans ce cas, car toutes les directions sont relatives au serpent actuel. Le Aparamètre est un sucre qui spécifie simplement que le serpent en train de se reproduire doit se déplacer après l'appel. Le 1paramètre indique comment nous limitons les correspondances aux rectangles - les paramètres numériques placent les serpents dans des "groupes". Une correspondance ne compte pas à moins que tous les serpents du même groupe parcourent exactement la même distance.

Problème 4 - Trouver un mot dans une recherche par mot

m:<*>GOLF

La commande direction <*>spécifie que le serpent doit tourner dans n'importe quelle direction diagonale ou orthogonale. Ensuite, il cherche la regex simple.

Problème 5 - Détecter les entrées carrées

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

La clé ici est le caractère spécial $, qui ne correspond que si le serpent est hors limites. Nous engendrons un serpent horizontal et un vertical; chacun de ceux-ci engendre plus de serpents lorsqu'il court le long du bord, et tous ceux-ci appartiennent au même groupe et doivent avoir la même longueur.

Problème 6 - Trouver des planeurs dans un jeu de la vie

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

mcommence dans l’une des quatre directions orthogonales ( <+>), en effectuant la rotation. Ensuite, les trois rangées apparaissent dans l’ordre, ce qui permet de réfléchir.

(Notez que j'ai remplacé les espaces par des points uniquement parce que les zones de texte HTML utilisées dans mon interprète semblent faire des choses stupides si elles ont plusieurs espaces consécutifs)

Problème 7 - Faire correspondre les portails du Nether

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

Le mserpent se déplace à droite, engendrant un serpent pour vérifier le bord gauche, 2 à 22 serpents pour vérifier les colonnes du milieu et enfin un serpent pour vérifier le bord droit. L' ~opérateur indique que ce qui suit doit être vérifié mais ne doit pas être marqué comme faisant partie de la solution.

Les fermetures délimitées nous permettent maintenant de résoudre pleinement et correctement ce problème!

Problème 8 - Placement de la poitrine dans Minecraft

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

Ici, nous utilisons une logique not ( !), qui correspond si et seulement si le jeton suivant ne correspond à rien. La déclaration ddétecte un double coffre dans une direction particulière. !{d<+>}Assurez-vous qu'il n'y a pas de double coffre dans une direction orthogonale. sdéplace un petit diamant autour du carré actuel, en vérifiant qu'au moins 3 de ces espaces sont vides ou non. La fin \.correspond finalement au carré, en supposant que toutes les conditions précédentes soient remplies.

Problème 9 - Alignement horizontal et vertical

m:<R>?#~.*#

Le serpent mtourne éventuellement à droite ( <R>?) avant de faire correspondre la séquence. .est un caractère générique, comme dans regex.

Problème 10 - Points colinéaires

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

Avec l'ajout de la <!>direction, nous pouvons résoudre ce problème maintenant! <!>est comme <+>mais au lieu de se ramifier dans quatre directions, il se ramifie dans toutes les directions possibles.

Problème 12 - Évitez la lettre Q

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

Il crée juste 4 serpents qui recherchent chacun quatre personnages qui ne sont pas la lettre Q.

Problème 13 - Extraction de diamants

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

Celui-ci est plutôt chouette. mengendre deux serpents, l'un à l'arrière droit et l'autre à l'avant droit. Chacune de celles-ci suit les barres obliques jusqu'à un X, puis engendre un autre serpent perpendiculaire à sa direction actuelle, qui suit les barres obliques jusqu'au X inférieur.

Problème 14 - Croix correspondante

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

Voici la première fois que Pj'utilise le paramètre iggyback. Normalement, les serpents sont indépendants, mais si vous appelez avec ce paramètre, le serpent appelant sera déplacé avec l'appelé. Donc, e2on peut vérifier une séquence de '.', Puis une séquence de '#', puis une autre séquence de '.', Et les faire tous être des appels séparés afin que nous puissions les regrouper avec '1,' 2 'et' 3 ' , forçant leurs longueurs à correspondre.

Problème 15 - Correspondre à un mot dans un tableau de Boggle

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

Simple, si verbeux. Iparamètre spécifie la non-sensibilité à la casse (nous pouvons spécifier des paramètres sur les définitions ainsi que dans les appels). Le serpent tourne dans n'importe quelle direction, correspond au personnage, se tourne à nouveau, etc.

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

Ceci est la version sans caractères de réutilisation. Le Eparamètre xclusive interdit au serpent de faire correspondre tout caractère déjà marqué, un peu comme les traces de slime de feersum.

Problème 16 - Enrouler les bords

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

Ce Wparamètre permet au serpent de s’enrouler quand il est hors limites. Nous avons également Het Vpour permettre uniquement l'emballage horizontal ou vertical.

Extra - Solutionneur de labyrinthe

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

Résout un labyrinthe ASCII dont le sol est piétonnier. La <P>direction signifie en avant, à gauche ou à droite (sucre pour [<F><L><R>]).

Extra - Paren Matching

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

Vous ne savez pas encore comment utiliser Prelude, mais voici un premier pas! Ici, j'utilise le rserpent de manière récursive pour faire correspondre les parenthèses correspondantes en vérifiant qu'il n'y a pas de parenthèses sans correspondance entre elles.

Topologie Extra - ASCII: Comptage de boucles

Slip, Python 3.4 ( wiki Github , interpréteur en ligne )

Comme la soumission de Feersum, ceci est également basé sur la traversée de la grille, mais comme la soumission de CarpetPython, cela est basé sur la regex. On dirait que j’ai réussi à prendre une position intermédiaire.

Je souhaite ajouter un grand nombre de fonctionnalités non implémentées. C'est pourquoi, le cas échéant, j'ai noté ce que j'avais l'intention de faire lorsque le temps me le permettrait.

Mises à jour

(Voir la page Github pour les nouvelles détaillées)

• 5 avril 2015 : Slip a maintenant un interprète en ligne ! Il en est encore à ses débuts, il pourrait donc y avoir quelques bugs.

• 5 avril 2015 : Mise à jour de l'efficacité! Maintenant, les portails inférieurs ont une grande entrée beaucoup plus rapide (2s). De plus, il y a eu un certain nombre de changements de syntaxe, alors assurez-vous de vérifier le wiki. La numérotation des groupes a également été corrigée.

Le glissement a un pointeur de correspondance qui commence à une case particulière et est initialement tourné vers la droite. Lorsqu'un caractère est mis en correspondance, le pointeur avance dans la direction actuelle (bien que l'implémentation ne fasse pas les choses exactement dans cet ordre).

La direction du pointeur de la correspondance peut être réglé à une direction particulière avec ^<digit>, où ^0, ^1, ^2, ..., ^7régler le pointeur vers N, NE, E, ..., NW respectivement (en sens horaire).

Les raccourcis suivants sont également disponibles:

• ^* vérifie les 8 directions orthogonales ou diagonales,
• ^+ vérifie les 4 directions orthogonales.

(Plan futur: autoriser la définition de directions arbitraires, par exemple (1, 2)pour le déplacement d'un chevalier)

Par exemple ( Problème 4 - Trouver un mot dans une recherche par mot ),

^*GOLF

essaie les 8 directions orthogonales ou diagonales, en recherchant le mot "GOLF". Par défaut, Slip essaie tous les carrés de départ possibles et renvoie un résultat pour chaque filtre, en filtrant les doublons.

GOLF
O
L
FLOG

ne renvoie que les lignes du haut et du bas comme correspondances (puisque la ligne du haut et la colonne de gauche "GOLF" partent du même carré). Pour obtenir toutes les correspondances, le omode de correspondance qui se chevauche peut être utilisé.

De même ( Problème 15 - Faire correspondre un mot dans un tableau Boggle ),

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

correspond panamaen essayant une direction différente à chaque fois. Utilisez le idrapeau pour l'insensibilité à la casse. Slip réutilise les caractères par défaut, mais cela peut être basculé avec le rdrapeau no-repeat.

(Plan futur: un modificateur de mode de recherche qui vérifie automatiquement des ensembles d’orientations après chaque déplacement, évitant ainsi toute répétition ^*inutile)

La direction du pointeur de correspondance peut également être tournée de 90 degrés vers la gauche ou vers la droite avec <ou >respectivement. Par exemple,

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

cherche le motif

  #
## 
 ##

en regardant dans l'ordre suivant:

765
894
123

Cela nous permet de résoudre le problème 6 - Trouver des planeurs avec

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

où les parties 1 et 2 codent les formes du planeur et les parties 3 et 4 leurs codes réfléchis.

Notez que Slip utilise backtick `pour s'échapper. En effet, le glissement a une autre forme de mouvement qui donne son nom à la langue - la commande de glissement. /glisse le pointeur de correspondance orthogonalement à gauche, alors que \le pointeur de correspondance orthogonale à droite.

Par exemple,

abc   ghi
   def

peut être jumelé par abc\def/ghi.

Bien que n'étant pas particulièrement utile en soi, le glissement devient plus important lorsqu'il est combiné avec le (?| <regex> )groupe stationnaire, qui agit comme un effet d'apparence identique. Les expressions rationnelles à l'intérieur sont mises en correspondance, puis à la fin, la position et la direction du pointeur de correspondance sont réinitialisées à l'état situé avant le groupe stationnaire.

Par exemple,

abc
def
ghi

peut être jumelé avec (?|abc)\(?|def)\(?|ghi).

De même, Problème 12 - Éviter la lettre Q peut être résolu avec

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

où %est une commande antidérapante pour empêcher le premier \de s’activer.

Slip a aussi une assertion de longueur (?_(<group num>) <regex> ), qui ne correspond à la regex à l'intérieur que si sa longueur de correspondance est la même longueur que celle du groupe donné.

Par exemple, le problème 13 - L’exploitation de diamants peut être facilement résolu avec

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

qui tente de faire correspondre le premier côté gauche du diamant en premier, puis affirme que les trois autres côtés ont la même longueur.

(Run avec vflag pour une sortie prolixe)

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

Une alternative golfier est

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

qui correspond deux fois au premier côté.

De nombreux autres problèmes peuvent être résolus en utilisant des groupes de glissement, stationnaires et des affirmations de longueur:

Problème 14 - Croix correspondante:

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

Une fois que vous avez capturé les largeurs .s et #s de la première rangée, vous ne faites que glisser vers le bas.

Sortie:

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

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

Celui-ci peut probablement être joué au golf avec un peu de récursion, une fois que j'ai corrigé quelques bugs.

Problème 3 - Détecter un rectangle de chiffres:

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

Faites correspondre une rangée supérieure de deux chiffres ou plus, puis assurez-vous que chaque ligne ci-dessous a la même longueur. `dest une classe de caractères prédéfinie équivalente à [0-9].

Notez que cela trouve toutes les correspondances .

Problème 7 - Faites correspondre les portails inférieurs:

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

qui affiche, pour le premier exemple dans le thread d'origine :

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.

Enfin, certaines autres fonctionnalités de Slip incluent:

• $0, $1, $2, ..., $7ancrez le bord nord, le coin nord-est, le bord est, etc. $+ancrez n'importe quel bord et $*ancrez n'importe quel coin.
• $suivi d'un caractère minuscule définit une ancre à la position actuelle, qui peut être comparée ultérieurement à $suivie du caractère majuscule correspondant, par exemple, $aet $A.
• # bascule l'indicateur de non-déplacement, qui empêche le pointeur de correspondance d'avancer après le prochain match.
• ,correspond à un caractère comme ., mais ne l'ajoute pas à la sortie, ce qui permet des correspondances non contiguës tout en pouvant être reconnu par (?_()).

... et plus. Il y en a vraiment trop à énumérer sur cette page.

D'autres problèmes

Problème 1 - Trouver des échiquiers:

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

Les deux problèmes d’échiquier ne sont certainement pas le point fort de Slip. Nous faisons correspondre la ligne du haut, puis nous assurons qu’elle fait au moins la longueur 3 et alterne entre #et _, puis nous glissons et faisons correspondre les lignes suivantes. À la fin, l' $aancre devrait être en bas à droite de l'échiquier.

Nous tournons ensuite à gauche et répétons pour les colonnes, en nous assurant que la correspondance est établie $Aà la fin.

Problème 2 - Vérification des échiquiers:

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

Comme pour le problème précédent, nous vérifions que chaque ligne est correcte, puis pivotons à gauche et faisons de même pour les colonnes. Les ancres sont utilisées pour s’assurer que seul le tableau entier est assorti.

Problème 9 - Alignement horizontal et vertical:

>?`#,*`#

Nous appliquons les facultatifs? quantifier à la >commande de rotation afin que nous puissions faire correspondre soit vers le bas ou vers la droite. Nous trouvons tous les 5 dans l'exemple avec le omode de chevauchement, mais seulement 4 sans #.,##et depuis et #.,#partons de la même position.

Problème 10 - Points colinéaires

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

Faites correspondre #ensuite quelques caractères horizontaux et certains caractères verticaux, puis répétez jusqu'au deuxième #et répétez jusqu'au troisième #.

Problème 5 - Détection des entrées carrées:

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

Ancrez le coin supérieur gauche et vérifiez que le bord supérieur a la même longueur que le bord droit avant d’ancrer le coin inférieur droit. Si l'entrée réussit ceci, alors nous allons en arrière pour faire correspondre l'entrée entière.

Problème 8 - Placement de la poitrine de Minecraft:

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

Courez avec le pdrapeau pour obtenir les positions de chaque match. $^est une ancre qui correspond si le prochain mouvement mettrait le pointeur de correspondance en dehors des limites.

Nous avons d' abord correspondre à un ., puis vérifier que nous sommes encerclés par trois .s / limites, puis fait en sorte que la quatrième place environnante est également une ./ limite ou est un coffre (en vérifiant ses places environnantes).

Problème 11 - Vérifier la syntaxe Prelude :

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

J'ai pris quelques essais, mais je pense que c'est correct. Ici, nous utilisons la récursion, qui a la même syntaxe que PCRE.

Cette approche nécessite que l'entrée soit rectangulaire, mais une fois que j'ai obtenu une correspondance non rectangulaire, cette hypothèse ne sera plus nécessaire.

Voici la même approche, golfée avec plus de récursivité:

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

Problème 16 - Enrouler sur les bords:

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

(Remarque: le wrapping n'a pas encore été poussé vers l'interprète en ligne)

Cela nécessite le drapeau d'emballage w. Techniquement, l'initiale %pour le non-glissement n'est pas nécessaire, mais le match compterait alors comme commençant à partir d'une case plus haute.

Problème EX 1 - Solutionneur de labyrinthe:

S(^+`.)*^+E

Problème du commentaire de BMac dans le chat . Utilisez le rdrapeau pour le mode sans répétition afin que le pointeur de correspondance ne reste pas bloqué dans les deux sens.

Problème EX 2 - Reconnaissance faciale :

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

Notez que je ne fais que faire correspondre les visages sans faire de compensation. Notez que la question contient des symboles de l’euro, qui devront être remplacés par des ASCII imprimables pour fonctionner.

PMA / Escargots (C ++)

J'envisage le langage comme des escargots se déplaçant autour d'une grille et exécutant des commandes. Les escargots laissent une traînée de boue sur chaque case sur laquelle ils se déplacent, ce qui rend par défaut la case inégalable. Une correspondance est réussie si la fin de la liste de commandes est atteinte.

Il y a suffisamment d'opérateurs maintenant que nous aurons besoin d'une liste de priorité pour les suivre. Les opérations sont résolues dans l'ordre suivant:

1. À l'intérieur des groupes ( ) [ ]
2. Caractère divisé le long de l'alternance |
3. Évaluez tout à gauche d' `un groupe
4. Quantificateurs [m],[n]etn
5. Assertions = !
6. Enchaînement

L'interprète est écrit en C ++. Le code source abyssal peut être trouvé ici .

Problème 4: Recherche par mot

Le programme

z\G\O\L\F

est suffisant pour obtenir une valeur de vérité ou de falsey quant à savoir si le mot est trouvé. z(une des 15 commandes directionnelles absolues ou relatives) correspond dans n'importe quelle direction octilinéaire. Plusieurs ordres de direction consécutifs sont combinés ensemble. Par exemple, ce ruldyserait presque équivalent à z, car ce sont les commandes pour droite, haut, gauche, bas et toute diagonale. Cependant, les instructions seraient testées dans un ordre différent. Le premier caractère correspondant est toujours celui sur lequel l'escargot commence, quelle que soit sa direction. \<caractère> correspond à un seul caractère littéral.

La stratégie par défaut consiste à essayer le motif à chaque carré dans la boîte englobante de l'entrée justifiée à gauche et à générer le nombre de correspondances. Si une valeur booléenne 1ou 0est requise, le programme suivant peut être utilisé:

?
z\G\O\L\F

S'il y a au moins une nouvelle ligne dans le fichier source, la première ligne est traitée comme une option pour la conversion initiale de l'entrée sous une forme rectangulaire. L' ?option imprime 0 ou 1 selon qu'il existe une correspondance n'importe où.

Problème 15: Boggle

Après la mise en œuvre de l'alternance, il est maintenant possible de résoudre Boggle. Il serait préférable d’utiliser la correspondance sans distinction de casse pour celle-ci, mais sa mise en œuvre n’est pas ma plus haute priorité.

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

|fonctionne exactement comme une regex à 1 dimension. Il existe deux paires de délimiteurs correspondants pour le regroupement, à savoir ()et {}. Un crochet de fermeture ferme tous les groupes ouverts du type opposé qui le séparent du plus proche du même type. Par exemple, {({{)seul le groupe le plus à gauche reste ouvert. Comme vous pouvez le constater, des symboles de regroupement sans correspondance sur les bords sont implicitement fermés. Il y a une autre commande de regroupement dans `laquelle je n'entrerai pas maintenant.

Problème 8: Coffres Minecraft

Le programme imprime le nombre de placements valides de la poitrine. C'était la première fois que je devais jouer au golf et j'ai réduit mon nombre d'octets (17) à quelques reprises.

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

• \. correspond à un point littéralement, au point de départ du match.
• !(o\C)2équivaut à !((o\C)2)la quantification est une priorité plus élevée que l'assertion. <atom> <number>signifie répéter <atom>exactement les <number>temps. otourne l'escargot dans n'importe quelle direction orthogonale. !est une affirmation négative. Ainsi, cette partie vérifie l'absence d'un double coffre adjacent.
• o tourne dans une direction orthogonale.
  • (!\Cw)3affirme qu'il n'y a pas Cdevant l'escargot, puis 3 fois dans le sens antihoraire.

Problème 2: Vérification des échiquiers

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

L' &option définit la sortie du programme comme 1si la correspondance réussissait à toutes les positions et 0sinon. ^ccorrespond à un caractère qui n'est pas céquivalent à [^c]regex. Dans l’ensemble, le programme signifie: Print 1 Si à chaque position dans le rectangle de délimitation de l’entrée, il existe soit un #qui n’est pas orthogonalement adjacent à un caractère qui ne l’est pas _, soit un _qui n’est pas orthogonalement adjacent à un caractère qui est non #; sinon 0.

La classe Re2d, Python 2

Mise à jour: ajout du problème "9. Alignement".

Mon approche consiste à utiliser le module Python re pour effectuer la recherche et la correspondance. La classe Re2d prépare le texte pour le traitement, exécute les fonctions et formate les résultats pour la sortie.

Notez qu'il ne s'agit pas d'un tout nouveau langage: il s'agit du langage d'expression régulière standard projeté en 2 dimensions avec des indicateurs supplémentaires pour les modes 2D supplémentaires.

La classe a les usages suivants:

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

Les deux modèles sont des modèles RE de texte linéaire standard. Si aucun motif vertical n'est fourni, la classe utilisera également le motif horizontal pour la correspondance verticale. Les drapeaux sont les drapeaux RE standard avec certaines extensions 2D.

Essai

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

La méthode de recherche a trouvé un motif d’échiquier et renvoie une position de 4 tuple. Le tuple a la x,yposition du premier caractère de la correspondance et width, heightla zone correspondante. Un seul motif est donné, il sera donc utilisé pour la correspondance horizontale et verticale.

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

L'échiquier a été vérifié avec la méthode de correspondance qui renvoie un booléen. Notez que les caractères ^et les caractères de $début et de fin doivent obligatoirement correspondre au texte entier .

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

Nous utilisons maintenant le MULTIFINDdrapeau pour renvoyer toutes les correspondances possibles pour le bloc de 2 chiffres ou plus. La méthode trouve 9 correspondances possibles. Notez qu'ils peuvent se chevaucher.

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)

Ce test montre l'utilisation du retournement vertical et horizontal. Cela permet de faire correspondre les mots inversés. Les mots en diagonale ne sont pas supportés. Le MULTIFINDdrapeau permet plusieurs correspondances qui se chevauchent dans les 4 directions. La méthode findall utilise la recherche pour trouver les cases correspondantes, puis extrait les blocs de texte correspondants. Notez que la recherche utilise la largeur et / ou la hauteur négatives pour les correspondances dans le sens inverse. Les mots dans la direction verticale ont des caractères de nouvelle ligne - ceci est cohérent avec le concept de blocs de caractères 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)

Cette recherche nécessitait des modèles distincts pour chaque dimension, la taille minimale étant différente pour chacune.

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)

Cet ensemble de 2 recherches trouve 2 correspondances verticales et 2 correspondances horizontales, mais ne peut pas trouver la #.,#chaîne incorporée .

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)

Ici, nous utilisons 2 recherches pour trouver des correspondances dans les deux sens. Il est capable de trouver plusieurs correspondances orthogonales mais cette approche ne prend pas en charge les correspondances en diagonale.

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

Cette recherche trouve la première correspondance.

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)

Le problème des diamants est plus difficile. Trois objets de recherche sont nécessaires pour les trois tailles. Il peut trouver les six diamants dans le jeu d’essais, mais il n’est pas adapté aux diamants de taille variable. Ce n'est qu'une solution partielle au problème des diamants.

Code 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

Grime , Haskell

introduction

Grime est basé sur les grammaires booléennes . L'idée de base est de construire des motifs rectangulaires à partir de composants plus petits et de vérifier s'ils se trouvent dans la matrice d'entrée. Jusqu'à présent, Grime ne prend en charge que les allumettes rectangulaires et résout au moins 11 problèmes avec plus ou moins d'élégance.

EDIT: Correction des croix (merci à DLosc d’avoir repéré le bogue), et ajout de l’exploitation de diamants.

EDIT2: Ajout des classes de caractères, inspirées de celles de Slip. Également modifié la syntaxe des indicateurs d'option, amélioré l'analyseur d'expression et ajouté le problème no-Q.

EDIT3: Implémentation des contraintes de taille et ajout du problème des portails Nether.

Usage

Un programme Grime est appelé une grammaire et l'extension de fichier correcte pour une grammaire est .gr, bien que cela ne soit pas appliqué. La grammaire est évaluée comme

runhaskell grime.hs [options] grammarfile matrixfile

où matrixfileest un fichier contenant la matrice de caractères. Par exemple, la grammaire des chiffres serait évaluée comme suit:

runhaskell grime.hs digits.gr digit-matrix

Pour plus de rapidité, je vous recommande de compiler le fichier avec les optimisations suivantes:

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

Par défaut, l'interprète imprime la première correspondance trouvée, mais cela peut être contrôlé à l'aide de l'option flags:

• -e: correspond uniquement à la matrice entière, impression 1pour correspondance et 0pour aucune correspondance.
• -n: affiche le nombre de correspondances, ou la matrice entière si -eest également donné.
• -a: imprimer toutes les correspondances.
• -p: affiche également les positions des matchs, au format (x,y,w,h).
• -s: ne pas imprimer les allumettes elles-mêmes.
• -d: affiche les informations de débogage.

Des options peuvent également être spécifiées dans la grammaire, en les insérant avant toute ligne et en ajoutant une virgule ,(voir ci-dessous pour des exemples).

Syntaxe et sémantique

Une grammaire Grime consiste en une ou plusieurs définitions , chacune sur une ligne distincte. Chacun d'entre eux définit la valeur d'un terminal , et l'un d'entre eux doit définir le terminal anonyme de niveau supérieur . La syntaxe d'une définition est N=Eou E, où Nest une lettre majuscule et Eune expression .

Les expressions sont construites comme suit.

• Tout caractère échappé avec \correspond à tout 1x1rectangle contenant ce caractère.
• . correspond à n'importe quel caractère unique.
• $correspond à un 1x1rectangle en dehors de la matrice de caractères.
• _ correspond à tout rectangle de largeur ou hauteur nulle.
• Les groupes de caractères prédéfinis sont digit, uppercase, lowercase, alphabetic, alpha numeric et symbol.
• De nouvelles classes de caractères peuvent être définies par la syntaxe [a-prt-w,d-gu]. Les lettres de gauche sont incluses et celles de droite sont exclues. Cela correspond donc exactement aux lettres abchijklmnoprtvw. Si le côté gauche est vide, il est supposé contenir tous les caractères. La virgule peut être omise si le côté droit est vide. Les personnages [],-\doivent être échappés avec \.
• Une lettre majuscule non échappée est une minuscule et correspond à l'expression qui lui est attribuée.
• Si Pet Qsont des expressions, alors PQn’est que leur concaténation horizontale et P/Qleur concaténation verticale, avec Pen haut.
• P+est un ou plusieurs Ps alignés horizontalement, et P/+est le même aligné verticalement.
• Les opérations booléennes sont notées P|Q, P&Qet P!.
• P?est un raccourci pour P|_, P*pour P+|_et P/*pour P/+|_.
• P#correspond à tout rectangle contenant une correspondance P.
• P{a-b,c-d}, Où abcdsont des entiers non négatifs, est une contrainte de taille sur P. Si Pest une classe de caractères, l'expression correspond à tout mxnrectangle contenant uniquement ces caractères, à condition qu'il msoit compris entre aet binclusif et nentre cet dinclusif. Dans d'autres cas, l'expression correspond à tout rectangle ayant la taille correcte et qui Pcorrespond également. Si aou csont omis, ils sont pris pour être 0, et si bou dsont omis, ils sont infinis. Si le trait d'union entre aet best omis, nous utilisons le même nombre pour les deux extrémités de l'intervalle. Si l'ensemblec-dune partie est omise, les deux axes sont contraints. Pour clarifier, {-b}équivaut à {0-b,0-b}et {a-,c}équivaut à {a-infinity,c-c}.

Remarques

Grime permet des définitions paradoxales comme A=A!avec un comportement indéfini. Cependant, ils ne provoqueront pas de crash ni de boucle infinie.

Grime prend en charge les entrées non rectangulaires; les lignes sont simplement alignées à gauche et les espaces peuvent être appariés à l'aide de $.

Dans le futur, j'aimerais implémenter ce qui suit:

• Correspondance plus rapide. Actuellement, l'interprète ne prend pas en compte le fait que, par exemple, .ne peut correspondre qu'à des 1x1rectangles. Jusqu'à ce qu'il trouve une correspondance, il essaie tous les rectangles de toutes les tailles dans l'ordre, en échouant instantanément pour chacun d'eux.
• Opérations de rotation et de réflexion, pour les défis de recherche de mots et de planeur.

• Les correspondances non rectangulaires utilisant des contextes , ce qui serait utile dans le cas du défi Boggle. Par exemple, Pv(Q>R)signifie Pavec contexte inférieur ( Qavec contexte droit R). Il correspondrait aux motifs en forme de L

  PPP
  PPP
  QQQRRRR
  QQQRRRR
  QQQRRRR
  

Les tâches

Étant donné en gros par ordre de complexité.

Rectangle de chiffres

d{2-}

C'est simple: un rectangle de chiffres de taille au moins 2x2.

Non q ou Q

[,qQ]{4}

C'est presque aussi simple que le premier. nous avons maintenant une taille plus restreinte et une classe de caractères personnalisée.

Alignement horizontal et vertical

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

Maintenant, nous avons quelques caractères échappés. En gros, cela correspond à un #, puis à un nombre quelconque de caractères, #horizontalement ou verticalement.

Détecter les entrées carrées

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

Cette grammaire est très simple, elle définit en gros qu’un carré est soit un 1x1rectangle, soit un carré plus petit avec une colonne fixée sur son bord droit et une rangée située au bas de celle-ci. Notez également l' eoption située avant le nonterminal toplevel, qui bascule la vérification de l'entrée entière.

Trouver un mot dans une recherche par mot

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

Celui-ci est horrible, car Grime n'a pas d'opération de rotation ou de réflexion. Il est également extrêmement lent, car Grime ne sait pas que les allumettes ne peuvent être que de taille 4x1, 1x4ou 4x4.

Le problème de planeur pourrait être résolu de la même manière, mais je suis trop paresseux pour le noter.

Portails du Néant

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

Avec l'opérateur de restriction de taille, celui-ci n'est pas si difficile. La partie centrale \.{2-22,3-22}correspond à n’importe quel rectangle de .la bonne taille, puis nous ajoutons simplement des colonnes de Xs des deux côtés et nous ajoutons des rangées de Xs avec des extrémités ignorées en haut et en bas de celle-ci.

Croix correspondantes

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

Ce que nous avons ici est une conjonction (ET logique) de deux expressions. Le non-terminal Ecorrespond à un rectangle non vide de .s et à Fun rectangle non vide de #s. Le côté gauche de la conjonction correspond aux rectangles du type

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

où nous avons EFEsur le dessus, puis F, puis EFEencore. Le côté droit correspond à la transposition de ceux-ci, nous obtenons donc exactement les croix.

Extraction de diamants

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

Le non terminal Cest un raccourci pour n'importe quelle 1xncolonne. La moitié supérieure d'un diamant est assortie T: c'est un seul Xou un autre Tentouré d'une colonne des deux côtés et d'une rangée en /[something]\dessous. Bcorrespond au bas d'un diamant de la même manière, et le niveau supérieur non terminal est juste rangé de la forme X[something]Xentre une moitié supérieure et une moitié inférieure.

Trouver des échiquiers

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

Le côté droit [#_]{3-}correspond à tout 3x3rectangle ou plus de #s et _s, tandis que les garanties de gauche qu'il ne contient pas de deux adjacents #s ou _s.

Vérification des échiquiers

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

Ceci est fondamentalement le même que ci-dessus, sauf que nous pouvons faire correspondre tout rectangle non vide, mais nous devons utiliser l' eindicateur pour la vérification complète de l'entrée.

Vérifier la syntaxe de prélude

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

C'est probablement la grammaire la plus intéressante à ce jour. Le non-terminal Acorrespond à toute colonne ne contenant pas (ou ), et Pcorrespond soit à un certain nombre de As, soit à deux parenthèses correspondantes, entre et en dehors desquelles il y a plus de Ps.

TMARL

Langage de reconnaissance et de correspondance des modèles

La description

Mon interprète utilise des caractères 24K (les extraits de code prennent des caractères? ). Vous trouverez la description complète ici .

La meilleure partie: l'interprète est en Javascript, ce qui signifie que vous pouvez l'essayer ici!

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