Sprachdesign: 2-D Pattern Matching

49

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.

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

PhiNotPi
quelle
Gibt es eine allgemeine Frist für diese Probleme? Ich bin sehr daran interessiert, dieses Problem zu lösen, aber ich bin sehr beschäftigt. Es könnte leicht 2 Wochen dauern, es zu lösen.
Devon Parsons
7
@ DevonParsons Es gibt keinen Einsendeschluss.
PhiNotPi
Sieht interessant aus, zumal Sie dafür ein neues Tag erstellt haben. Ich denke, es sollte Bonuspunkte für die Erstellung einer 2D-Sprache geben.
mbomb007
1
@ mbomb007 Es gibt Bonuspunkte für die Erstellung einer 2D-Sprache. Ich bin mir ziemlich sicher, dass es eine ordentliche Menge an positiven Stimmen geben würde. ;)
Martin Ender
@ MartinBüttner Ich weiß nicht mal wirklich, wie man eine Sprache erstellt. Könnte es so etwas wie (einfach?) Sein, ein Python-Programm zu erstellen, das eine Datei mit dem Code Ihrer neuen Sprache erstellt (und diese basierend auf Ihrer definierten Syntax interpretiert / ausführt) und eine Ausgabe erzeugt?
mbomb007

Antworten:

32

SnakeEx

Löst 15/16 Probleme bis jetzt!

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

Screenshot des Interpreten

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

BMac
quelle
Möchten Sie Syntax hinzufügen, damit diese Sprache ersetzt und nicht nur abgeglichen wird? Ich möchte eine Lösung für diese Herausforderung verwenden, um einen Eintrag für codegolf.stackexchange.com/questions/51231/… zu schreiben, aber hier wird keine einzige Lösung gefunden und ersetzt. (Ich weiß, dass meine Antwort aufgrund der Zeitregeln für die Sprachspezifikation nicht gültig ist.)
Sparr
@Sparr. Keine schlechte Idee, es wäre sicherlich nützlicher für Code-Golf. Ich bin mir nicht sicher, wann ich Zeit habe, es selbst zu tun, aber ich werde es im Hinterkopf behalten.
BMac,
3
separat: Die Syntax für Richtungsänderungen ist verwirrend. Da die Schlange nach der Übereinstimmung mit einem Charakter voranschreitet, muss ich meine Richtung offenbar um einen Charakter ändern, bevor es für mich Sinn ergibt. Beispiel: String "ABC \ nDEF" und ich möchte mit dem von ABCF definierten L-förmigen Tetris-Teil übereinstimmen. Ich möchte meine Schlange als "m: ABC <R> F" schreiben, aber ich muss "m: AB <R>" schreiben CF "statt. Ich verstehe, dass dies der Spezifikation entspricht, aber ich finde es sehr eingängig.
Sparr
Ich habe eine Teillösung für die Vorsyntax. Das einzige Problem ist, dass ich es nicht m:{a<>} a:[({n<R>A})({n<R>A}*{l<R>A}{a<>P}{r<R>A})]*{n<R>A}* l:$[^\(\)]*\([^\(\)]*$ r:$[^\(\)]*\)[^\(\)]*$ n:$[^\(\)]+$
hinbekomme,
21

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.

Sp3000
quelle
Das Hash-Muster ist ein Conway-Segelflugzeug
Heimdall
17

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.

Feersum
quelle
Die Slime-Trail-Idee ist gut für den Umgang mit Boggle, ich hatte einige Probleme damit
BMac
Das ist eine schöne Lösung für das Boggle-Problem. Das kann ich mit meinem Ansatz nicht lösen.
Logic Knight
14

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
Logik-Ritter
quelle
Wenn das Diamantenproblem nicht klar war, können Diamanten jede Größe haben, nicht nur 0, 1 oder 2. Bearbeiten: Ich habe die Spezifikation bearbeitet, um dies deutlicher zu machen.
PhiNotPi
Verstanden. Ich werde in der Antwort vermerken, dass die Re2d nur eine teilweise Lösung für dieses Problem hat. Es kann nicht auf variable Größen skaliert werden. Ist das in Ordnung?
Logic Knight
Ja das ist in Ordnung.
PhiNotPi
14

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.

Zgarb
quelle
@ DLosc behoben, danke, dass du den Fehler gefunden hast!
Zgarb
Würde \#(.*|./*)\#funktionieren
Siehe auch
@Sieg Für die Ausrichtung? Leider nein, denn das würde als "eins #links, dann eine Zeile oder Spalte von irgendetwas, dann eins #rechts" analysiert . Ich muss angeben, dass die #s vertikal an die Spalte mit den Schrägstrichen verkettet sind /.
Zgarb,
10

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!

Und für die Probleme:

# 1 - Schachbretter finden

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

&fügt Suchanfragen hinzu. Der G2 am Ende erhält das 3. Element in einem Match-Element, das eigentliche Match. Die ersten beiden Elemente sind x- und y-Koordinaten (1 basierend, nicht 0).

# 3 - Ermitteln Sie ein Rechteck von Ziffern

$DD
$DD
S1G2P

Ich denke, das ist ziemlich einfach.

# 4 - Ein Wort in einer Wortsuche finden

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

Das S Argument ist gerade, damit es nach allen Umdrehungen sucht. Es ist größer als 4, da es dann an die nächste Suche angehängt werden kann (einzelne Übereinstimmungen können nicht angehängt werden).

# 5 - Quadratische Eingaben erkennen

IL-(IG0L)!P

Ich bin mir nicht sicher, ob dies völlig legal ist, da es nur dann die Rechtwinkligkeit korrekt bestimmt, wenn die Eingabe ein Rechteck ist. Es vergleicht die Länge der Eingabe ILmit der Länge der ersten ZeileIG0L und kehrt sie um.

# 6 - Finde Segelflugzeuge in einem Spiel des Lebens

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

Endlich eine Verwendung für den Spiegel!

# 12 - Vermeiden Sie den Buchstaben Q

$[^Qq]
~4*4S1G2P

S1 weil nur 1 Treffer benötigt wird.

Ich werde später einige der schwierigeren machen.

Stretch Maniac
quelle