Prelude Syntax-Checker

10

Prelude ist eine esoterische Programmiersprache, die nur sehr wenige, aber ungewöhnliche Einschränkungen für ein gültiges Programm aufweist. Jeder Block druckbaren ASCII-Textes ("Block" bedeutet, dass Zeilen druckbaren ASCII durch Zeilenumbrüche getrennt sind - 0x0A) ist gültig, sofern:

  • Jede (vertikale) Textspalte enthält höchstens eine von (und ).
  • Wenn man ihre vertikale Position ignoriert, sind die (und )ausgeglichen, das heißt, jede (ist mit genau einer )rechts davon gepaart und umgekehrt.

Schreiben Sie ein Programm oder eine Funktion, die anhand einer Zeichenfolge mit druckbarem ASCII und Zeilenumbrüchen bestimmt, ob es sich um ein gültiges Prelude-Programm handelt. Sie können Eingaben über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen. Das Ergebnis kann unter Verwendung von zwei festen Wahrheits- / Falschwerten Ihrer Wahl an STDOUT zurückgegeben oder gedruckt werden .

Sie dürfen nicht davon ausgehen, dass die Eingabe rechteckig ist.

Dies ist Code Golf, daher gewinnt die kürzeste Übermittlung (in Bytes).

Beispiele

Die folgenden sind gültige Prelude-Programme (tatsächlich sind sie sogar echte Prelude-Programme):

?1-(v  #1)-             
1   0v ^(#    0)(1+0)#)!
    (#)  ^#1-(0 #       
1(#  1) v #  - 1+)
    vv (##^v^+
? v-(0 # ^   #)
?
  1+              1-!

Und hier sind einige Eingaben, die alle ungültig sind :

#(#(##)##)##(
)##(##(##)#)#
#(#)
)###
#(##
(##)
(##)
(#)#
(##)
(###
#(#)
(##)
#(#)
###)
#()#
()##
#(#)##
###
###(#)
Martin Ender
quelle
Hat Prelude Kommentare, die einen engen Paren blockieren könnten?
Alex A.
@Alex Nein. Die oben genannten Regeln sind wirklich alles, um zu entscheiden, ob ein Programm gültig ist oder nicht.
Martin Ender
Cool, danke für die Klarstellung. Ich wollte nur sicher gehen.
Alex A.
Regel 1 - "Jede Textspalte enthält höchstens eines von (und)"; Beispiel 1, Zeile 2: "1 0v ^ (# 0) (1 + 0) #)!" -> Ich sehe 3 )und 2 (. Sollte es nicht nur 1 pro Zeile sein?
Ismael Miguel
1
Unter @IsmaelMiguel wird unter "Spalte" normalerweise vertikale Linien verstanden (insbesondere im Zusammenhang mit Gittern). Ich habe es trotzdem geklärt.
Martin Ender

Antworten:

3

CJam, 57 56 Bytes

qN/z_{_"()"--W<},,\s:Q,{)Q/({_')/,\'(/,-}:T~\sT0e>+z+}/!

Zu lange kann viel Golf gespielt werden. Erklärung, die hinzugefügt werden muss, sobald ich Golf spiele.

Kurze Erklärung

Der Code enthält zwei Überprüfungen:

  • Der erste Filter überprüft, ob jede Spalte höchstens 1 Klammer enthält. Die endgültige Ausgabe des Filters ist die Anzahl der Spalten mit mehr als 1 Klammern.
  • Zweitens konvertieren wir die Eingabe in das Hauptformat der Spalte und teilen sie dann für jeden Index in zwei Teile auf.
    • In jedem dieser beiden Teile Number of "(" - Number of ")"sollte sich ( ) gegenseitig ergänzen. Wenn Sie sie addieren, sollte dies zu 0 führen. Jeder Teil, der diese Eigenschaft nicht erfüllt, führt dazu, dass die gesamte Eingabe nicht übereinstimmende Klammern enthält.
    • Ich muss auch sicherstellen, dass "(" links von ")" steht. Dies bedeutet, dass der Wert von Number of "(" - Number of ")"für den rechten Seitenblock nicht negativ sein kann.

Probieren Sie es hier online aus

Optimierer
quelle
6

Python 2, 128 119 105 Bytes

def F(p):
 v=n=1
 for r in map(None,*p.split("\n")):A,B=map(r.count,"()");n+=B-A;v*=n<2>A+B
 return n*v>0

Wussten Sie, dass Sie None in Python 2 zuordnen können?

Erläuterung

Wir möchten zunächst das Prelude so transponieren, dass Spalten zu Zeilen werden. Normalerweise würden wir dies mit tun zip, aber da es zipauf die kürzeste Reihenlänge gekürzt wird und itertools.zip_longestviel zu lang für Code-Golf ist, scheint es keinen kurzen Weg zu geben, das zu tun, was wir wollen ...

Mit Ausnahme der Zuordnung None:

>>> print map(None,*[[1,2,3],[4],[5,6]])
[(1, 4, 5), (2, None, 6), (3, None, None)]

Leider (oder besser gesagt, zum Glück für alle Nicht-Golf-Zwecke) funktioniert dies nur in Python 2.

Wie für nund v:

  • nwirkt wie ein Stapel und zählt 1 - <number of unmatched '(' remaining>. Für jedes, was (wir sehen, subtrahieren wir 1 und für jedes, was )wir sehen, addieren wir 1. Wenn wir also n >= 2zu irgendeinem Zeitpunkt zu viele )s gesehen haben und das Programm ungültig ist. Wenn nes nicht mit 1 endet, haben wir noch mindestens eine unübertroffene (.
  • vprüft die Gültigkeit und beginnt bei 1. Wenn das Programm jemals ungültig ist ( n >= 2oder A+B >= 2), vwird es 0, um die Ungültigkeit zu markieren.

Wenn also das Programm gültig ist, müssen wir es am Ende haben n = 1, v = 1. Wenn das Programm ungültig ist, müssen wir am Ende entweder v = 0oder haben v = 1, n <= 0. Daher kann die Gültigkeit kurz ausgedrückt werden als n*v>0.

(Danke an @feersum für eine Vielzahl guter Vorschläge, die 14 Bytes entfernt haben!)

Vorherige, besser lesbare Einreichung:

def F(p):
 p=map(None,*p.split("\n"));v=n=0
 for r in p:R=r.count;A=R("(");B=R(")");n+=A-B;v|=A+B>1or n<0
 return n<1>v
Sp3000
quelle
Das ist eine verrückte Verwendung von map...
xnor
1
119 -> 106def F(p): v=n=3 for r in map(None,*p.split("\n")):A,B=map(R.count,"()");n+=A-B;v*=n>2>A+B return n*v==9
Feersum
@feersum Danke! Ich habe versucht , das zu ändern , orin Vergleich Verkettungs, aber ich dachte nicht , ändert |=in *=. Nahm ein weiteres Byte obwohl ab, durch die Dinge selbst zu machen mehr zurück :)
SP3000
2

J, 64 Bytes

Die Eingabe ist eine Zeichenfolge mit einem nachgestellten Zeilenumbruch. Die Ausgabe ist 0 oder 1.

(0=(1<|s)s+[:(|@{:+(0>])s)[:+/\]s=.+/@:)@(1 _1 0{~[:'()'&i.];.2)

Anwendungsbeispiel

   ]in=.'#(#)##',LF,'###',LF,'###(#)',LF
#(#)##
###
###(#)

   ((0=(1<|s)s+[:(|@{:+(0>])s)[:+/\]s=.+/@:)@(1 _1 0{~[:'()'&i.];.2)) in
0

Die Methode ist die folgende

  • Schneiden Sie Eingaben an Zeilenumbrüchen ab und fügen Sie sie in eine Matrix ein ];.2
  • Karte (/ )/ anything elsein 1/ -1/0 1 _1 0{~[:'()'&i.]
  • Definieren Sie ein s=.+/@:Adverb, das einem Verb hinzugefügt wird und die Ausgabe des Verbenarrays summiert
  • Werte in Spalten hinzufügen ]s

    • Überprüfen Sie das positive ()Gleichgewicht in jedem Präfix [:(0>])s)[:+/\]
    • Überprüfen Sie das gleiche ()Gleichgewicht in der gesamten Liste (dh im letzten Präfix). |@{:@]
  • Fügen Sie abs (Werte) in Spalten hinzu und überprüfen Sie jedes Element auf einen Maximalwert von 1 (1<|s)s

  • Da alle vorherigen Überprüfungen bei einem Fehler positiv waren, addieren wir sie und vergleichen sie mit 0, um die Gültigkeit der Eingabe zu erhalten 0=]

randomra
quelle
2

J, 56 Bytes

3 :'*/0<: ::0:(+/\*:b),-.|b=.+/+.^:_1]0|:''()''=/];.2 y'

Dies ist eine anonyme Funktion, die eine Zeichenfolge mit einem nachgestellten Zeilenumbruch akzeptiert und 0 oder 1 zurückgibt. Lesen von rechts nach links:

  • ];.2 yschneidet, wie in der anderen J-Übermittlung, die Zeichenfolge ybei allen Vorkommen ihres letzten Zeichens (weshalb die Eingabe eine nachgestellte neue Zeile benötigt) und erstellt eine rechteckige Matrix, deren Zeilen die Teile sind, die bei Bedarf mit Leerzeichen aufgefüllt werden.

  • '()'=/vergleicht jedes Zeichen in dieser Matrix zuerst mit (und dann mit der )Rückgabe einer Liste von zwei 0-1-Matrizen.

  • +.^:_1]0|:verwandelt diese Liste von zwei Matrizen in eine einzige Matrix komplexer Zahlen. Bisher wandelt das Programm jedes (in der Eingabe in eine 1, jedes )in i und jedes andere Zeichen in 0 um.

  • b=.+/weist die Summe der Zeilen dieser komplexen Matrix zu b.

  • -.|bmacht eine Liste von 1- | z | für jedes z in b. Die Bedingung, dass jede Spalte höchstens eine einzige Klammer enthält, übersetzt sich in alle diese Zahlen 1- | z | nicht negativ sein.

  • +/\*:bist der Vektor der laufenden Summen der Quadrate der Zahlen in b. Wenn jede Spalte höchstens eine Klammer enthält, sind die Quadrate der Zahlen in b0, 1 oder -1. Der ,verkettet diesen Vektor mit dem Vektor von 1- | z | 's.

  • jetzt alle brauchen wir ist Test zu tun , dass die Einträge unseres verketteten Vektor vnicht negative reelle Zahlen Zahlen sind, ist dies fast */0<:v, mit der Ausnahme , dass die einen Fehler verursacht , wenn einige Einträge vnicht real sind, so ersetzen wir <:mit <: ::0:dem zurück nur 0 im Fehlerfall .

Omar
quelle
Tolle Ideen mit den komplexen Zahlen, aber Sie müssen auch prüfen, ob 0={:+/\*:bzB (nicht gültig ist.
Randomra
Oh, du hast recht, @randomra, ich habe es vergessen!
Omar
1
0=(-|)vist 2 Bytes kürzer für die Überprüfung nicht negativer Realzahlen. (Lass uns CJam schlagen !: P)
randomra
1
Oh, und invanstatt ein ^:_1 weiteres Byte zu speichern.
Randomra
1
Zurück zu 56 (mit Kontostandprüfung) : 3 :'*/0=({:,]-|)(-.@|,+/\@:*:)+/+.inv]0|:''()''=/];.2 y'.
Randomra