Dies ist die sechzehntägige Herausforderung Nr. 6 . Thema: Sprachdesign

Für diese Herausforderung gibt es einen Chatroom . Kommen Sie zu uns, wenn Sie Ideen diskutieren möchten!

Und jetzt etwas ganz anderes...

In diesen 14 Tagen wollen wir mit einer neuen Art von Herausforderung experimentieren. In dieser Herausforderung entwerfen Sie eine Sprache! Pattern Matching ist ein sehr häufiges Problem bei der Programmierung und oft sehr nützlich für Code Golf. Beispielsweise können reguläre Ausdrücke verwendet werden, um ein Muster in einer Textzeile zu erkennen. Es gibt jedoch keine etablierten Methoden, um zweidimensionale Muster zu beschreiben und zu erfassen.

Die Herausforderung

Sie müssen eine Pattern-Matching-Sprache entwerfen, mit der zweidimensionale Muster in Textblöcken beschrieben werden können. Die Funktionsweise Ihrer Sprache ist ähnlich wie bei regulären Ausdrücken (obwohl Ihre Sprache sonst nichts mit Regex zu tun haben muss):

• Als Eingabe erhalten Sie einen rechteckigen Textblock. Sie können davon ausgehen, dass der Text nur aus druckbaren ASCII-Zeichen (0x20 bis 0x7E) sowie Zeilenumbrüchen (0x0A) besteht, um die Zeilen des Rasters zu trennen.
• Wenn eine Übereinstimmung gemäß der Musterbeschreibung als eine Teilmenge dieses Textblocks gefunden werden kann, sollte diese Übereinstimmung zurückgegeben oder gedruckt werden. Wenn die Übereinstimmung nicht rechteckig sein kann, sollte sie auf einen rechteckigen Bereich mit einem reservierten Zeichen aufgefüllt werden. Wenn es mehrere gültige Übereinstimmungen gibt, können Sie entscheiden, wie die zurückgegebene Übereinstimmung ausgewählt wird (größte, kleinste, erste usw.).

Für einige Anwendungen kann es hilfreich sein, wenn Ihre Implementierung die Position eines Matches anstelle des Matches selbst zurückgibt, dies ist jedoch keine Voraussetzung.

Zumindest sollte Ihre Sprache in der Lage sein, ein Muster als zusammenhängenden, rechteckigen Teilbereich seiner Eingabe abzugleichen.

Ihre Antwort sollte enthalten:

• Eine Beschreibung der Sprache.
• Eine funktionierende Implementierung . Dies kann ein Programm oder eine Reihe von Funktionen / Klassen in einer Sprache Ihrer Wahl sein.
• Sie sollten Ihre Sprache demonstrieren, indem Sie zeigen, wie sie zur Lösung der unten aufgeführten Beispiele verwendet werden kann . Ihre Sprache muss nicht in der Lage sein, alle zuzuordnen, Sie müssen jedoch in der Lage sein, mindestens 8 davon zuzuordnen. Wenn Ihre Sprache etwas Phantasievolles kann, woran wir nicht gedacht haben, können Sie es auch einbeziehen.

Wenn Ihre Antwort auf vorhandenen Ideen aufbaut, ist das in Ordnung, aber geben Sie bitte an, wo es fällig ist.

Erweiterungen

Das Obige beschreibt das Minimum, das eine gültige Einreichung erfüllen muss. Verschiedene Verallgemeinerungen könnten eine solche Mustervergleichssprache jedoch noch nützlicher machen, einschließlich, aber nicht beschränkt auf:

• In der Lage sein, das Muster an einer oder mehreren Kanten zu verankern, so dass überprüft werden kann, ob der gesamte Eingabebereich ein bestimmtes Muster aufweist.
• Produziere alle Übereinstimmungen anstatt nur einer. Sie können die Semantik überlappender Übereinstimmungen auswählen.
• Eingabe von nicht rechteckigem Text.
• Zulassen, dass Muster nicht rechteckige Übereinstimmungen angeben. In einem solchen Fall sollte die Ausgabe in ein Rechteck mit einem reservierten Zeichen aufgefüllt werden.
• Zulassen, dass Muster Übereinstimmungen mit Löchern angeben.
• Zulassen von nicht zusammenhängenden Übereinstimmungen, z. B. zwei Zeichen, die mit einem bestimmten Versatz angezeigt werden.
• Einfache Angabe von Rotationen und Reflexionen.
• Behandeln Sie den Eingang optional zyklisch als Zylinder oder Torus, sodass gegenüberliegende Kanten als benachbart betrachtet werden.

Wertung

Das primäre Ziel dieser Herausforderung besteht darin, eine effektive 2D-Pattern-Matching-Sprache zu erstellen, die möglicherweise in Zukunft verwendet werden könnte. Als solches würde ein Bewertungssystem wie "kürzeste kombinierte Länge zum Lösen der Beispiele" zu einer Festcodierung bestimmter Funktionen auf Kosten der allgemeinen Verwendbarkeit führen. Aus diesem Grund haben wir beschlossen, dass diese Herausforderung am besten als Beliebtheitswettbewerb durchgeführt wird. Die Einsendung mit den meisten Netto-Stimmen gewinnt. Wir können zwar nicht erzwingen, wie die Menschen wählen, aber hier sind ein paar Richtlinien, nach denen die Wähler im Idealfall suchen sollten:

• Ausdruckskraft. Kann die Sprache eine Vielzahl von Problemen lösen, die über die in dieser Frage dargestellten Beispiele hinausgehen? Unterstützt es eine der vorgeschlagenen Erweiterungen?
• Lesbarkeit. Wie intuitiv ist die Notation (zumindest für Leute, die die grundlegende Syntax kennen)?
• Golfitude. Das ist noch CodeGolf.SE. Für die Zwecke dieser Site wäre es natürlich schön, eine passende Sprache zu haben, die nur sehr wenig Code benötigt, um ein Muster zu beschreiben.

Beispielprobleme

Das folgende Stack-Snippet zeigt 16 Beispielprobleme, mit denen eine 2-D-Pattern-Matching-Sprache umgehen kann. Jedes Beispiel enthält eine kurze Problembeschreibung und wird dann normalerweise von einem Eingabebeispiel gefolgt, in dem eine Übereinstimmung gefunden werden kann, und einem Beispiel, in dem keine Übereinstimmung gefunden werden kann (falls zutreffend).

Wie oben erwähnt, muss Ihre Sprache nur 8 dieser Probleme lösen können. Alles darüber hinaus ist optional, sollte aber natürlich die Anzahl der abgegebenen Stimmen erhöhen.

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;

(Nein, Sie müssen diesen HTML-Code nicht lesen. Klicken Sie auf die Schaltfläche "Code-Snippet ausführen", damit er von Ihrem Browser gut wiedergegeben wird. Sie können ihn dann auch im Vollbildmodus anzeigen.)

SnakeEx

Löst 15/16 Probleme bis jetzt!

Online-Dolmetscher ! - Vollständige Sprachspezifikation - Javascript-Quelle

Die Idee hinter dieser Sprache ist es, "Schlangen" zu definieren, die sich unter Verwendung einer regulären Syntax um die Textprüfzeichen bewegen.

Ein Programm in SnakeEx besteht aus einer Liste von Definitionen für Schlangen, die unterschiedliche Befehlsfolgen verwenden. Mit diesen Definitionen können Schlangen andere Schlangen erzeugen. SnakeEx kann hier seine Stärken voll ausschöpfen. Wir können Verzweigungsstrukturen abgleichen und sogar Rekursionen durchführen (siehe Beispiel für Paren Matching).

Jedes Programm sieht im Wesentlichen aus wie eine Reihe von regulären Ausdrücken, enthält jedoch Richtungsbefehle des Formulars <dir>, die die Richtung der Schlange ändern, und ruft Befehle des Formulars auf {label<dir>params}, das mehr Schlangen erzeugt.

Für einen Einstiegspunkt erzeugt der Interpreter eine Schlange mit der ersten Definition und bewegt sich nach rechts.

Es ist nicht besonders präzise, ​​aber sehr leistungsfähig und (glaube ich) ziemlich lesbar.

Aktualisierung

• Geändert ! zu logisch nicht und ~ um keine Übereinstimmungen zu markieren
• Hinzugefügt <!>, um kolinear zu lösen
• Passende Kreuze gelöst
• Schachbretter auf weniger schreckliche Weise gelöst
• Bounded Closure-Syntax hinzugefügt %{min,max}
• Rekursionsbeispiel hinzugefügt

Lösungen

15 gelöst, 1 in Bearbeitung

Sie können diese Programme ganz einfach mit dem oben verlinkten Online-Interpreter ausprobieren!

Problem 1 - Finden von Schachbrettern

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

Beginnen Sie mit Problem 3, um eine detaillierte Einführung zu erhalten.

Problem 2 - Überprüfen von Schachbrettern

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

Wenn Sie die entsprechenden Schlangen mit dem Symbol "Out-of-Bound" versehen $, können Sie ein Programm so konfigurieren, dass es nur mit der gesamten Eingabe übereinstimmt.

Problem 3 - Ermitteln Sie ein Rechteck von Ziffern

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

Die mSchlange bewegt sich nach rechts und laicht %{2,}mit der Definition c ( c) mit mindestens 2 Schlangen ( ein Verschluss bedeutet "2 bis unendlich") und bewegt <R>sich in diesem Fall nach rechts ( ) bzw. nach unten, da alle Richtungen relativ zur aktuellen Schlange sind. Der AParameter ist sugar, der nur angibt, dass sich die laichende Schlange nach dem Aufruf bewegen soll. Der 1Parameter ist, wie wir Übereinstimmungen auf Rechtecke beschränken - Zahlenparameter setzen Schlangen in "Gruppen". Ein Match zählt nur dann, wenn alle Schlangen in derselben Gruppe genau dieselbe Distanz zurücklegen.

Problem 4 - Ein Wort in einer Wortsuche finden

m:<*>GOLF

Der Befehl direction <*>gibt an, dass sich die Schlange in eine beliebige diagonale oder orthogonale Richtung drehen soll. Dann sucht es nach dem einfachen Regex.

Problem 5 - Quadratische Eingaben erkennen

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

Der Schlüssel hier ist das Sonderzeichen $, das nur passt, wenn die Schlange außerhalb der Grenzen ist. Wir laichen eine horizontale und eine vertikale Schlange. Jede dieser Arten bringt mehr Schlangen hervor, wenn sie am Rand entlang rennen, und alle gehören derselben Gruppe an und müssen gleich lang sein.

Aufgabe 6 - Finden Sie Segelflugzeuge in einem Spiel des Lebens

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

mStartet in einer der vier orthogonalen Richtungen ( <+>) und erzielt eine Drehung. Dann sieht es für die drei Zeilen nach links oder rechts aus, um eine Reflektion zu erzielen.

(Beachten Sie, dass ich die Leerzeichen nur durch Punkte ersetzt habe, weil die in meinem Interpreter verwendeten HTML-Textbereiche dumme Dinge zu tun scheinen, wenn sie mehrere Leerzeichen in einer Reihe enthalten.)

Aufgabe 7 - Match Nether Portals

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

Die mSchlange bewegt sich nach rechts und erzeugt eine Schlange, um den linken Rand zu überprüfen, 2-22 Schlangen, um die mittleren Spalten zu überprüfen, und schließlich eine Schlange, um den rechten Rand zu überprüfen. Der ~Bediener weist darauf hin, dass Folgendes überprüft, jedoch nicht als Teil der Lösung gekennzeichnet werden sollte.

Dank beschränkter Verschlüsse können wir dieses Problem jetzt vollständig und richtig lösen!

Aufgabe 8 - Platzierung der Minecraft-Truhe

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

Hier verwenden wir ein logisches nicht ( !), das genau dann zutrifft, wenn das folgende Token nicht zutrifft. Die Deklaration derkennt eine doppelte Truhe in einer bestimmten Richtung, sodass !{d<+>}sichergestellt ist, dass in keiner orthogonalen Richtung doppelte Truhen vorhanden sind. sBewegt sich mit einer kleinen Raute um das aktuelle Quadrat und überprüft, ob mindestens drei dieser Felder leer oder nicht auf dem Spielfeld sind. Der Schlusskurs \.stimmt schließlich mit dem Quadrat überein, vorausgesetzt, alle vorhergehenden Bedingungen waren erfolgreich.

Problem 9 - Horizontale und vertikale Ausrichtung

m:<R>?#~.*#

Die Schlange mdreht sich optional nach rechts ( <R>?), bevor sie der Sequenz entspricht. .ist ein Platzhalter, wie in Regex.

Aufgabe 10 - Kolineare Punkte

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

Mit der Hinzufügung der <!>Richtung können wir das jetzt lösen! <!>ist wie, <+>aber anstatt sich in vier Richtungen zu verzweigen, verzweigt es sich in jede mögliche Richtung.

Problem 12 - Vermeiden Sie den Buchstaben Q

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

Lässt nur 4 Schlangen entstehen, die jeweils nach vier Zeichen suchen, die nicht dem Buchstaben Q entsprechen.

Aufgabe 13 - Diamond Mining

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

Das ist ziemlich ordentlich. mbringt zwei Schlangen hervor, eine nach rechts hinten und eine nach rechts vorne. Jede davon folgt den Schrägstrichen zu einem X und erzeugt dann eine weitere Schlange im rechten Winkel zu ihrer aktuellen Richtung, die den Schrägstrichen zu dem unteren X folgt.

Aufgabe 14 - Passende Kreuze

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

Hier ist das erste Mal, dass ich den PParameter iggyback verwende. Normalerweise sind die Schlangen unabhängig, aber wenn Sie mit diesem Parameter einen Anruf tätigen, wird die aufrufende Schlange mit dem Angerufenen verschoben. So e2können Sie eine Folge von '.', Dann eine Folge von '#', dann eine andere Folge von '.' Überprüfen und sie alle getrennte Aufrufe haben, sodass wir sie mit '1', '2' und '3' gruppieren können. und zwingen ihre Längen zusammenzupassen.

Aufgabe 15 - Finde ein Wort in einem Boggle Board

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

Einfach, wenn auch wortreich. Iparameter gibt an, dass zwischen Groß- und Kleinschreibung unterschieden wird (Parameter können sowohl in Definitionen als auch in Aufrufen angegeben werden). Die Schlange dreht sich in eine beliebige Richtung, passt sich dem Charakter an, dreht sich wieder und so weiter.

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

Dies ist die Version ohne Wiederverwendung von Zeichen. Der Exclusive-Parameter verhindert, dass die Schlange mit einem bereits markierten Zeichen übereinstimmt, ähnlich wie bei Feersums Schleimpfaden.

Problem 16 - Wickeln Sie die Kanten um

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

Mit diesem WParameter kann die Schlange einen Zeilenumbruch ausführen, wenn sie außerhalb der Grenzen läuft. Wir haben auch Hund Vnur horizontale oder vertikale Verpackung zu erlauben.

Extra - Maze Solver

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

Löst ein ASCII-Labyrinth, in dem der begehbare Boden aus Punkten besteht. Die <P>Richtung bedeutet vorwärts, links oder rechts (Zucker für [<F><L><R>]).

Extra - Paren Matching

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

Noch nicht herausgefunden, wie man Prelude macht, aber hier ist ein erster Schritt! Hier benutze ich die rSchlange rekursiv, um die entsprechenden Klammern zuzuordnen, indem ich überprüfe, dass sich keine nicht übereinstimmenden Klammern zwischen ihnen befinden.

Extra- ASCII-Topologie: Zählen von Schleifen

Slip, Python 3.4 ( Github-Wiki , Online-Dolmetscher )

Wie bei Feersums Vorlage basiert auch dies auf dem Durchlaufen des Gitters, aber wie bei CarpetPythons Vorlage basiert dies auf Regex. Irgendwie sieht es so aus, als hätte ich es geschafft, den Mittelweg einzuschlagen.

Es gibt eine ganze Reihe von nicht implementierten Funktionen, die ich hinzufügen möchte. Daher habe ich, wo relevant, notiert, was ich vorhabe, wenn ich Zeit habe.

Aktualisierung

(Siehe Github Seite für detaillierte Nachrichten)

• 5. April 2015 : Slip hat jetzt einen Online-Dolmetscher ! Es befindet sich noch in einem frühen Stadium, daher kann es zu einigen Fehlern kommen.

• 5. April 2015 : Effizienz-Update! Jetzt können große Portale viel schneller eingegeben werden (2s). Außerdem wurden einige Syntaxänderungen vorgenommen. Überprüfen Sie daher unbedingt das Wiki. Gruppennummerierung ebenfalls behoben.

Slip hat einen Übereinstimmungszeiger, der an einem bestimmten Feld beginnt und anfangs nach rechts zeigt. Wenn ein Zeichen übereinstimmt, bewegt sich der Zeiger in der aktuellen Richtung vorwärts (obwohl die Implementierung die Dinge nicht genau in dieser Reihenfolge ausführt).

Die Richtung des Spiel - Zeiger kann mit auf eine bestimmte Richtung festgelegt werden ^<digit>, in denen ^0, ^1, ^2, ..., ^7den Zeiger auf N, NE, E, ..., NW jeweils (im Uhrzeigersinn).

Die folgenden Verknüpfungen sind ebenfalls verfügbar:

• ^* prüft alle 8 orthogonalen oder diagonalen Richtungen,
• ^+ prüft alle 4 orthogonalen Richtungen.

(Zukunftsplan: Einstellung beliebiger Richtungen zulassen, zB (1, 2)für Ritterzug)

Zum Beispiel ( Problem 4 - Finden eines Wortes in einer Wortsuche ),

^*GOLF

probiert alle 8 orthogonalen oder diagonalen Richtungen aus und sucht nach dem Wort "GOLF". Standardmäßig probiert Slip alle möglichen Startquadrate aus und gibt jeweils ein Ergebnis zurück, wobei Duplikate herausgefiltert werden, sodass ein Raster entsteht

GOLF
O
L
FLOG

gibt nur die oberste und die unterste Zeile als Treffer zurück (da die oberste und die linke Spalte "GOLF" vom selben Quadrat ausgehen). Um alle Übereinstimmungen zu erhalten, kann der oüberlappende Übereinstimmungsmodus verwendet werden.

In ähnlicher Weise ( Problem 15 - Ein Wort in einem Boggle-Brett finden ),

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

Spiele, panamaindem du jedes Mal eine andere Richtung ausprobierst. Verwenden Sie die iFlagge für Groß- und Kleinschreibung. Slip verwendet Zeichen standardmäßig wieder, dies kann jedoch mit dem rNo-Repeat-Flag umgeschaltet werden .

(Zukunftsplan: Ein Modifikator für den Suchmodus, der nach jeder Bewegung automatisch die Richtungssätze überprüft, sodass keine Wiederholung erforderlich ^*ist.)

Die Richtung des Übereinstimmungszeigers kann auch mit <oder um 90 Grad nach links oder rechts gedreht werden >. Zum Beispiel,

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

sucht nach dem Muster

  #
## 
 ##

indem Sie in der folgenden Reihenfolge suchen:

765
894
123

Dies ermöglicht es uns, Problem 6 zu lösen - Segelflugzeuge finden mit

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

Dabei codieren die Teile 1 und 2 die Segelflugzeugformen und die Teile 3 und 4 ihre reflektierten Gegenstücke.

Beachten Sie, dass Slip Backtick `für die Flucht verwendet. Dies liegt daran, dass Slip eine andere Form der Bewegung hat, die der Sprache ihren Namen gibt - den Slip-Befehl. /Bewegt den Übereinstimmungszeiger orthogonal nach links und \den Übereinstimmungszeiger orthogonal nach rechts.

Zum Beispiel,

abc   ghi
   def

kann durch abgestimmt werden abc\def/ghi.

In Kombination mit der (?| <regex> )stationären Gruppe, die wie ein passender Lookahead wirkt , wird das Verrutschen wichtiger, obwohl es für sich genommen nicht besonders nützlich ist . Der Regex im Inneren wird abgeglichen, und am Ende werden Position und Richtung des Abgleichzeigers auf den Zustand vor der stationären Gruppe zurückgesetzt.

Zum Beispiel,

abc
def
ghi

kann mit abgestimmt werden (?|abc)\(?|def)\(?|ghi).

Ebenso kann Problem 12 - Vermeiden Sie den Buchstaben Q mit gelöst werden

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

Wo %ist ein No-Slip-Befehl, um die \Aktivierung des ersten zu stoppen .

Slip hat auch eine Längenangabe (?_(<group num>) <regex> ), die nur dann mit der Regex übereinstimmt, wenn ihre Übereinstimmungslänge mit der Länge der angegebenen Gruppennummer übereinstimmt.

Zum Beispiel kann Problem 13 - Diamond Mining leicht mit gelöst werden

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

die zuerst versucht, die obere linke Seite des Diamanten abzugleichen, und dann bestätigt, dass die anderen drei Seiten die gleiche Länge haben.

(Mit vFlag für ausführliche Ausgabe ausführen)

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

Eine golferische Alternative ist

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

welches die erste Seite zweimal zusammenbringt.

Viele der anderen Probleme können mithilfe von rutschenden, stationären Gruppen und Längenangaben gelöst werden:

Aufgabe 14 - Übereinstimmende Kreuze:

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

Sobald Sie die Breite des .s und #s in der ersten Reihe erfasst haben , rutscht es einfach ganz nach unten.

Ausgabe:

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

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

Dieser kann wahrscheinlich mit ein bisschen Rekursion golfen werden, sobald ich ein paar Bugs aussortiert habe.

Problem 3 - Ermitteln Sie ein Rechteck aus Ziffern:

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

Ordnen Sie eine obere Reihe mit zwei oder mehr Ziffern zu und stellen Sie dann sicher, dass jede Zeile darunter dieselbe Länge hat. `dist eine vordefinierte Zeichenklasse, die äquivalent zu ist [0-9].

Beachten Sie, dass dies alle Übereinstimmungen findet .

Aufgabe 7 - Match-Nether-Portale:

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

welche Ausgaben, für das oberste Beispiel im Original-Thread :

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

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

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

Zu den weiteren Funktionen von Slip gehören:

• $0, $1, $2, ..., $7Verankern Sie die Nordkante, die Nordostecke, die Ostkante usw. $+Verankern Sie jede Kante und $*verankern Sie jede Ecke.
• $gefolgt von einem Kleinbuchstaben setzt einen Anker an der aktuellen Position, dem später $das entsprechende Großbuchstaben, z . B. $aund, folgen kann $A.
• # Schaltet das No-Move-Flag um, wodurch verhindert wird, dass sich der Übereinstimmungszeiger nach der nächsten Übereinstimmung vorwärts bewegt.
• ,Stimmt mit einem Zeichen überein ., fügt es jedoch nicht zur Ausgabe hinzu, sodass nicht zusammenhängende Übereinstimmungen möglich sind, während sie von erkannt werden (?_()).

... und mehr. Es gibt wirklich zu viele, um sie auf dieser Seite aufzulisten.

Andere Probleme

Problem 1 - Finden von Schachbrettern:

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

Die beiden Probleme mit dem Schachbrett sind sicherlich nicht Slips Stärke. Wir passen die oberste Reihe an und stellen dann sicher, dass sie mindestens die Länge 3 hat und zwischen #und _wechselt. Am Ende $asollte sich der Anker unten rechts auf dem Schachbrett befinden.

Wir biegen dann nach links ab und wiederholen den Vorgang für die Spalten, um sicherzustellen, dass wir $Aam Ende übereinstimmen .

Problem 2 - Überprüfen von Schachbrettern:

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

Wie beim vorherigen Problem prüfen wir, ob jede Zeile korrekt ist, drehen uns dann nach links und machen dasselbe für Spalten. Anker werden verwendet, um sicherzustellen, dass nur das gesamte Board übereinstimmt.

Problem 9 - Horizontale und vertikale Ausrichtung:

>?`#,*`#

Wir wenden die optionalen? Quantifizierer für den >Befehl "Drehen", sodass wir entweder nach rechts oder nach unten passen. Wir finden alle 5 im Beispiel mit oÜberlappungsmodus, aber nur 4 ohne #.,##und #.,#beginnen an derselben Position.

Aufgabe 10 - Kollineare Punkte

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

Ordnen Sie #dann einige horizontale und einige vertikale Zeichen zu, wiederholen Sie diese bis zur zweiten #und wiederholen Sie sie bis zur dritten #.

Problem 5 - Quadratische Eingaben erkennen:

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

Verankern Sie die obere linke Ecke und prüfen Sie, ob die obere Kante dieselbe Länge wie die rechte Kante hat, bevor Sie die untere rechte Ecke verankern. Wenn die Eingabe dies passiert, gehen wir rückwärts nach oben, um der gesamten Eingabe zu entsprechen.

Aufgabe 8 - Platzierung der Minecraft-Truhe:

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

Laufen Sie mit der pFlagge, um die Positionen jedes Matches zu ermitteln. $^ist ein Anker, der passt, wenn der Match-Zeiger beim nächsten Zug außerhalb der Grenzen liegt.

Zuerst passen wir a an ., dann überprüfen wir, ob wir von drei .s / Grenzen umgeben sind, und stellen dann sicher, dass das vierte umgebende Quadrat auch eine ./ Grenze oder eine einzelne Truhe ist (indem wir die umgebenden Quadrate überprüfen ).

Problem 11 - Überprüfen Sie die Prelude-Syntax :

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

Ich habe ein paar Versuche unternommen, aber ich denke, das ist richtig. Hier verwenden wir die Rekursion, die die gleiche Syntax wie PCRE hat.

Dieser Ansatz setzt voraus, dass die Eingabe rechteckig ist, aber sobald ich einen nicht rechteckigen Abgleich durchgeführt habe, ist diese Annahme nicht mehr erforderlich.

Hier ist der gleiche Ansatz, mit mehr Rekursion golfen:

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

Problem 16 - Wickeln Sie die Kanten um:

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

(Hinweis: Wrapping wurde noch nicht an den Online-Interpreter übertragen.)

Dies erfordert das Wrapping-Flag w. Technisch gesehen ist die Initiale %für No-Slip nicht erforderlich, aber dann wird das Match ab einem Feld höher gewertet.

Problem EX 1 - Labyrinthlöser:

S(^+`.)*^+E

Problem von BMacs Kommentar im Chat . Verwenden Sie das rFlag für den Modus "Keine Wiederholung", damit der Übereinstimmungszeiger nicht hängen bleibt.

Problem EX 2 - Gesichtserkennung :

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

Beachten Sie, dass ich nur Gesichter abgleiche und keine Reinigung durchführe. Beachten Sie, dass die Frage Euro-Symbole enthält, die von einigen druckbaren ASCII-Zeichen ersetzt werden müssen, um zu funktionieren.

PMA / Schnecken (C ++)

Ich stelle mir die Sprache als Schnecken vor, die sich in einem Raster bewegen und Befehle ausführen. Die Schnecken hinterlassen auf jedem Feld, auf das sie sich bewegen, eine Spur von Schleim, was standardmäßig dazu führt, dass das Feld anschließend nicht mehr angepasst werden kann. Eine Übereinstimmung ist erfolgreich, wenn das Ende der Befehlsliste erreicht ist.

Es gibt jetzt genug Operatoren, für die wir eine Prioritätsliste benötigen, um sie zu verfolgen. Die Vorgänge werden in der folgenden Reihenfolge ausgeführt:

1. Innerhalb von Gruppen ( ) [ ]
2. Entlang des Wechselzeichens teilen |
3. Werten Sie alles links von a `als Gruppe aus
4. Quantifizierer [m],[n]undn
5. Behauptungen = !
6. Verkettung

Der Interpreter ist in C ++ geschrieben. Den abgrundtiefen Quellcode finden Sie hier .

Problem 4: Wortsuche

Das Programm

z\G\O\L\F

ist ausreichend, um einen Wahrheitswert oder einen falschen Wert dafür zu erhalten, ob das Wort gefunden wurde. z(einer der 15 absoluten oder relativen Richtungsbefehle) passt in jede oktilineare Richtung. Mehrere aufeinanderfolgende Richtungsbefehle werden miteinander ODER-verknüpft. Zum Beispiel ruldywäre fast gleichbedeutend mit z, da dies die Befehle für rechts, oben, links, unten und eine beliebige diagonale Richtung sind. Die Anweisungen werden jedoch in einer anderen Reihenfolge getestet. Das erste übereinstimmende Zeichen ist immer dasjenige, mit dem die Schnecke beginnt, unabhängig von der Richtung. \<Zeichen> entspricht einem einzelnen Literalzeichen.

Die Standardstrategie besteht darin, das Muster an jedem Quadrat im Begrenzungsrahmen der linksbündigen Eingabe auszuprobieren und die Anzahl der Übereinstimmungen auszugeben. Wenn ein boolescher Wert 1oder 0erforderlich ist, kann das folgende Programm verwendet werden:

?
z\G\O\L\F

Befindet sich mindestens eine neue Zeile in der Quelldatei, wird die erste Zeile als Option für die anfängliche Konvertierung der Eingabe in eine rechteckige Form behandelt. Die ?Option gibt 0 oder 1 aus, je nachdem, ob irgendwo eine Übereinstimmung vorliegt.

Aufgabe 15: Boggle

Nach der Implementierung von Alternation ist es nun möglich, Boggle zu lösen. Es wäre besser, bei diesem Matching zwischen Groß- und Kleinschreibung zu unterscheiden, aber die Implementierung hat nicht meine höchste Priorität.

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

|Funktioniert genauso wie ein eindimensionaler Regex. Es gibt zwei übereinstimmende Trennzeichenpaare für die Gruppierung, nämlich ()und {}. Eine schließende Klammer schließt alle offenen Gruppen des entgegengesetzten Typs, die zwischen ihr und der nächsten Gruppe desselben Typs stehen. Im Folgenden {({{)bleibt beispielsweise nur die Gruppe ganz links geöffnet. Wie Sie sehen, werden nicht übereinstimmende Gruppierungssymbole an den Rändern implizit geschlossen. Es gibt einen weiteren Gruppierungsbefehl, auf `den ich jetzt nicht eingehen werde.

Aufgabe 8: Minecraft-Truhen

Das Programm gibt die Anzahl der gültigen Brustplatzierungen aus. Dies war das erste Mal, dass ich Golf spielen musste und reduzierte meine Byteanzahl (17) ein paar Mal.

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

• \. Stimmt buchstäblich mit einem Punkt am Startpunkt des Spiels überein.
• !(o\C)2entspricht, !((o\C)2)da die Quantifizierung Vorrang vor der Behauptung hat. <atom> <number>bedeutet, <atom>genau <number>mal zu wiederholen . odreht die Schnecke in jede orthogonale Richtung. !ist eine negative Behauptung. Somit prüft dieser Teil das Fehlen einer benachbarten Doppelkiste.
• o dreht sich in eine orthogonale Richtung.
  • (!\Cw)3behauptet, dass sich keine CSchnecke vor der Schnecke befindet, und dreht sich dann dreimal gegen den Uhrzeigersinn.

Problem 2: Überprüfen von Schachbrettern

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

Die &Option legt die Ausgabe des Programms so fest, als 1ob die Übereinstimmung an allen Positionen erfolgreich wäre, und 0ansonsten. Entspricht ^ceinem Zeichen, das nicht cdem [^c]regulären Ausdruck entspricht. Insgesamt bedeutet das Programm: 1 ausgeben, wenn an jeder Position im Begrenzungsrechteck der Eingabe entweder #ein Zeichen vorhanden ist _, _das nicht orthogonal zu einem nicht vorhandenen Zeichen benachbart ist , oder ein Zeichen, das nicht orthogonal zu einem vorhandenen Zeichen benachbart ist nicht #; sonst 0.

Die Re2d-Klasse, Python 2

Update: Problem "9. Ausrichtung" hinzugefügt.

Mein Ansatz ist es, das Python Re-Modul zu verwenden, um die Suche und den Abgleich durchzuführen. Die Re2d-Klasse bereitet den Text für die Verarbeitung vor, führt die Re-Funktionen aus und formatiert die Ergebnisse für die Ausgabe.

Beachten Sie, dass dies keine völlig neue Sprache ist - es ist die Standardsprache für reguläre Ausdrücke, die in zwei Dimensionen projiziert wird und zusätzliche Flags für zusätzliche 2D-Modi enthält.

Die Klasse hat die folgende Verwendung:

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

Beide Muster sind Standard-RE-Muster mit linearem Text. Wird kein vertikales Muster angegeben, verwendet die Klasse das horizontale Muster auch für den vertikalen Abgleich. Die Flags sind die Standard-RE-Flags mit einigen 2D-Erweiterungen.

Testen

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

Die Suchmethode hat ein Schachbrettmuster gefunden und gibt eine 4-Tupel-Position zurück. Das Tupel hat die x,yPosition des ersten Zeichens der Übereinstimmung und die Position des width, heightübereinstimmenden Bereichs. Es ist nur ein Muster angegeben, sodass es für die horizontale und vertikale Anpassung verwendet wird.

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

Das Schachbrett wurde mit der Match-Methode überprüft, die einen Booleschen Wert zurückgibt. Beachten Sie, dass die ^und $Start- und Endezeichen sind erforderlich , um das Übereinstimmen ganzen Textes.

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

Wir verwenden nun das MULTIFINDFlag, um alle möglichen Übereinstimmungen für den 2+ Ziffernblock zurückzugeben. Die Methode findet 9 mögliche Übereinstimmungen. Beachten Sie, dass sie sich überlappen können.

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)

Dieser Test zeigt die Verwendung von vertikalem und horizontalem Spiegeln. Dies ermöglicht die Zuordnung von Wörtern, die umgekehrt sind. Diagonale Wörter werden nicht unterstützt. Die MULTIFINDFlagge erlaubt mehrere überlappende Übereinstimmungen in alle 4 Richtungen. Die findall-Methode verwendet die Suche, um die übereinstimmenden Felder zu finden, und extrahiert dann die übereinstimmenden Textblöcke. Beachten Sie, wie die Suche negative Breite und / oder Höhe für Übereinstimmungen in umgekehrter Richtung verwendet. Die Wörter in vertikaler Richtung haben neue Zeilenzeichen - dies entspricht dem Konzept von 2D-Zeichenblöcken.

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)

Diese Suche erforderte separate Muster für jede Dimension, da die Mindestgröße für jede Dimension unterschiedlich ist.

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)

Diese Gruppe von 2 Suchen findet 2 vertikale und 2 horizontale Übereinstimmungen, kann jedoch die eingebettete #.,#Zeichenfolge nicht finden .

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)

Hier verwenden wir 2 Suchen, um Übereinstimmungen in beide Richtungen zu finden. Es ist möglich, mehrere orthogonale Übereinstimmungen zu finden, aber dieser Ansatz unterstützt keine diagonalen Übereinstimmungen.

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

Diese Suche findet die erste Übereinstimmung.

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)

Das Diamantproblem ist schwieriger. Für die drei Größen werden drei Suchobjekte benötigt. Es kann die sechs Diamanten im Testsatz finden, skaliert jedoch nicht auf Diamanten mit variabler Größe. Dies ist nur eine Teillösung des Diamantproblems.

Python 2-Code

import sys
import re

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

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

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

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

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

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

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

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

Schmutz , Haskell

Einführung

Grime basiert auf booleschen Grammatiken . Die Grundidee besteht darin, rechteckige Muster aus kleineren Komponenten zu konstruieren und zu prüfen, ob sie in der Eingabematrix enthalten sind. Bisher unterstützt Grime nur rechteckige Übereinstimmungen und löst mindestens 11 Probleme mehr oder weniger elegant.

BEARBEITEN: Die Kreuze wurden korrigiert (dank DLosc für das Erkennen des Fehlers) und Diamantenabbau hinzugefügt.

EDIT2: Charakter-Klassen hinzugefügt, inspiriert von denen von Slip. Außerdem wurde die Syntax von Optionsflags geändert, der Ausdrucksparser verbessert und das No-Q-Problem hinzugefügt.

EDIT3: Größenbeschränkungen wurden implementiert und das Problem mit den Nether-Portalen wurde hinzugefügt.

Verwendungszweck

Ein Grime-Programm wird als Grammatik bezeichnet , und die richtige Dateierweiterung für eine Grammatik lautet .gr, obwohl dies nicht erzwungen wird. Die Grammatik wird als ausgewertet

runhaskell grime.hs [options] grammarfile matrixfile

wo matrixfileist eine Datei mit der Zeichenmatrix. Beispielsweise würde die Zifferngrammatik als ausgewertet

runhaskell grime.hs digits.gr digit-matrix

Für zusätzliche Geschwindigkeit empfehle ich, die Datei mit Optimierungen zu kompilieren:

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

Standardmäßig gibt der Interpreter die erste Übereinstimmung aus, die er findet. Dies kann jedoch mithilfe der Optionsflags gesteuert werden:

• -e: Übereinstimmung nur mit der gesamten Matrix, Ausdruck 1für Übereinstimmung und 0für keine Übereinstimmung.
• -n: Gibt die Anzahl der Übereinstimmungen oder die gesamte Matrix aus, falls diese -eebenfalls angegeben ist.
• -a: Alle Übereinstimmungen drucken.
• -p: Gibt auch die Positionen der Übereinstimmungen im Format aus (x,y,w,h).
• -s: drucke die Übereinstimmungen nicht selbst aus.
• -d: Debug-Informationen drucken.

Optionen können auch in der Grammatik angegeben werden, indem sie vor einer Zeile eingefügt und mit einem Komma versehen werden ,(Beispiele siehe unten).

Syntax und Semantik

Eine Grime-Grammatik besteht aus einer oder mehreren Definitionen in einer separaten Zeile. Jeder von ihnen definiert den Wert eines Nicht - Terminal , und eine von ihnen muss die anonym definiert Toplevel nicht terminale . Die Syntax einer Definition lautet entweder N=Eoder E, wobei Nes sich um einen Großbuchstaben und Eeinen Ausdruck handelt .

Ausdrücke werden wie folgt konstruiert.

• Jedes Zeichen, das mit \einem 1x1Escapezeichen versehen ist, entspricht einem Rechteck, das dieses Zeichen enthält.
• . Stimmt mit jedem einzelnen Zeichen überein.
• $Stimmt mit einem 1x1Rechteck außerhalb der Zeichenmatrix überein .
• _ Entspricht einem beliebigen Rechteck mit der Breite oder Höhe Null.
• Die vordefinierten Zeichengruppen sind digit, uppercase, lowercase, alphabetic, alpha numeric und symbol.
• Neue Zeichenklassen können durch die Syntax definiert werden [a-prt-w,d-gu]. Die Buchstaben links sind eingeschlossen, und die rechts sind ausgeschlossen, so dass dies genau mit den Buchstaben übereinstimmt abchijklmnoprtvw. Wenn die linke Seite leer ist, enthält sie alle Zeichen. Das Komma kann weggelassen werden, wenn die rechte Seite leer ist. Die Zeichen [],-\müssen mit maskiert werden \.
• Ein nicht entkappter Großbuchstabe ist ein Nichtterminal und entspricht dem zugewiesenen Ausdruck.
• Wenn Pund Qsind Ausdrücke, dann PQist nur ihre horizontale Verkettung und P/Qist ihre vertikale Verkettung mit Poben.
• P+ist eine oder mehrere Ps horizontal ausgerichtet und P/+ist die gleiche vertikal ausgerichtet.
• Die Boolesche Operationen bezeichnet werden P|Q, P&Qund P!.
• P?ist die Abkürzung für P|_, P*für P+|_und P/*für P/+|_.
• P#Stimmt mit jedem Rechteck überein, das eine Übereinstimmung von enthält P.
• P{a-b,c-d}, wo abcdsind nichtnegative ganze Zahlen, ist eine Größenbeschränkung auf P. Wenn Pes sich um eine Zeichenklasse handelt, stimmt der Ausdruck mit jedem mxnRechteck überein, das nur diese Zeichen enthält, vorausgesetzt, es mliegt zwischen aund beinschließlich sowie nzwischen cund deinschließlich. In anderen Fällen stimmt der Ausdruck mit jedem Rechteck überein, das die richtige Größe hat und Pauch übereinstimmt. Wenn aoder cweggelassen werden, werden sie genommen werden 0, und wenn boder dweggelassen werden, sind sie unendlich. Wenn der Bindestrich zwischen aund bweggelassen wird, verwenden wir für beide Enden des Intervalls dieselbe Nummer. Wenn das ganzec-dTeil weggelassen wird, sind beide Achsen beschränkt. Zur Verdeutlichung {-b}ist gleichbedeutend mit {0-b,0-b}und {a-,c}ist gleichbedeutend mit {a-infinity,c-c}.

Anmerkungen

Schmutz erlaubt paradoxe Definitionen wie A=A!bei undefiniertem Verhalten. Sie verursachen jedoch keine Abstürze oder Endlosschleifen.

Grime unterstützt nicht rechteckige Eingaben. Die Zeilen werden einfach nach links ausgerichtet und die Lücken können mit angepasst werden $.

In Zukunft möchte ich Folgendes implementieren:

• Schnelleres Matching. Derzeit berücksichtigt der Interpreter nicht, dass beispielsweise .nur 1x1Rechtecke abgeglichen werden können. Bis eine Übereinstimmung gefunden wird, werden alle Rechtecke aller Größen in der angegebenen Reihenfolge geprüft, wobei jeder Fehler sofort auftritt.
• Rotations- und Reflexionsoperationen für die Wortsuche und Segelflugherausforderungen.

• Nicht rechteckige Übereinstimmungen mit Kontexten , die bei der Boggle-Brett-Herausforderung hilfreich wären. Zum Beispiel Pv(Q>R)bedeutet Pmit unterem Kontext ( Qmit richtigem Kontext R). Es würde zu den L-förmigen Mustern passen

  PPP
  PPP
  QQQRRRR
  QQQRRRR
  QQQRRRR
  

Die Aufgaben

Gegeben ungefähr in der Reihenfolge der Komplexität.

Rechteck aus Ziffern

d{2-}

Das ist einfach: ein Rechteck mit mindestens einer Zifferngröße 2x2.

Kein q oder Q

[,qQ]{4}

Das ist fast so einfach wie das erste; Jetzt haben wir eine eingeschränktere Größe und eine benutzerdefinierte Zeichenklasse.

Horizontale und vertikale Ausrichtung

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

Jetzt haben wir einige entkommene Zeichen. Grundsätzlich entspricht dies einem #, dann einer beliebigen Anzahl von beliebigen Zeichen #, entweder horizontal oder vertikal.

Quadratische Eingaben erkennen

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

Diese Grammatik ist sehr einfach. Sie definiert im Grunde genommen, dass ein Quadrat entweder ein 1x1Rechteck oder ein kleineres Quadrat mit einer Spalte am rechten Rand und einer Zeile am unteren Rand ist. Beachten Sie auch die eOption vor dem obersten Nichtterminal, mit der die Überprüfung der gesamten Eingabe umgeschaltet wird.

Ein Wort in einer Wortsuche finden

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

Dies ist schrecklich, da Grime keine Rotations- oder Reflektionsoperationen hat. Es ist auch extrem langsam, da Grime nicht weiß, dass die Streichhölzer nur von Größe sein können 4x1, 1x4oder 4x4.

Das Segelflugproblem könnte auf ähnliche Weise gelöst werden, aber ich bin zu faul, das aufzuschreiben.

Nether-Portale

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

Mit dem Größenbeschränkungsoperator ist dies nicht so schwer. Der mittlere Teil \.{2-22,3-22}passt zu jedem Rechteck .der richtigen Größe. Dann fügen wir einfach Spalten mit Xs auf beiden Seiten hinzu und heften Reihen mit Xs mit ignorierten Enden oben und unten an.

Passende Kreuze

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

Was wir hier haben, ist eine Verknüpfung (logisches UND) zweier Ausdrücke. Das Nichtterminal Eentspricht einem nicht leeren Rechteck von .s und Feinem nicht leeren Rechteck von #s. Die linke Seite der Konjunktion entspricht Rechtecken des Typs

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

wo haben wir dann EFEoben Fund dann EFEwieder. Die rechte Seite stimmt mit den Transponierten überein, sodass wir genau die Kreuze erhalten.

Diamant-Bergbau

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

Das Nichtterminal Cist eine Abkürzung für jede 1xnSpalte. Die obere Hälfte eines Diamanten entspricht T: Es handelt sich entweder um einen einzelnen Diamanten Xoder Tum einen anderen Diamanten , der auf beiden Seiten von einer Säule und einer Reihe /[something]\darunter umgeben ist. BStimmt auf die gleiche Weise mit der Unterseite eines Diamanten überein, und das oberste Nicht-Terminal ist nur eine Reihe der Form X[something]Xzwischen einer oberen Hälfte und einer unteren Hälfte.

Schachbretter finden

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

Die rechte Seite [#_]{3-}entspricht einem 3x3oder mehreren Rechtecken von #s und _s, während die linke Seite garantiert, dass sie keine zwei benachbarten #s oder _s enthält.

Überprüfen von Schachbrettern

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

Dies ist im Grunde das gleiche wie oben, außer dass wir jedes nicht leere Rechteck zuordnen können, aber das eFlag für die gesamte Eingabeüberprüfung verwenden müssen.

Überprüfen Sie die Prelude-Syntax

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

Dies ist wahrscheinlich die bisher interessanteste Grammatik. Das Nichtterminal Astimmt mit jeder Spalte überein, die nicht (oder enthält ), und Pstimmt entweder mit einer bestimmten Anzahl von As oder mit zwei übereinstimmenden Klammern überein, zwischen und außerhalb derer sich mehr Ps befinden.

TMARL

Template Matching und Erkennungssprache

Beschreibung

Mein Interpreter nimmt 24K-Zeichen auf ( Code-Schnipsel nehmen Zeichen auf? ), Daher finden Sie die vollständige Beschreibung hier .

Das Beste: Der Dolmetscher ist in Javascript, das heißt, Sie können es gleich hier ausprobieren!

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