Prelude Syntax-Checker

10

Preludium to ezoteryczny język programowania, który ma bardzo niewiele, ale nietypowe, ograniczeń dotyczących tego, co stanowi prawidłowy program. Każdy blok drukowalnego tekstu ASCII („blok” oznacza, że ​​wiersze drukowalnego ASCII są oddzielone znakami nowej linii - 0x0A) jest prawidłowy, pod warunkiem że:

  • Każda (pionowa) kolumna tekstu zawiera co najwyżej jedną z (i ).
  • Ignorując ich położenie pionowe, (i )są zrównoważone, to znaczy, że każdy (jest sparowany z dokładnie jednym )po prawej stronie i odwrotnie.

Napisz program lub funkcję, która, biorąc pod uwagę ciąg znaków zawierający drukowalne ASCII i znaki nowej linii, określa, czy stanowi on prawidłowy program Prelude. Możesz przyjmować dane wejściowe za pośrednictwem STDIN (lub najbliższej alternatywy), argumentu wiersza poleceń lub argumentu funkcji. Wynik może zostać zwrócony lub wydrukowany do STDOUT przy użyciu dowolnych dwóch ustalonych wartości true / falsy .

Nie można zakładać, że wejście jest prostokątne.

To jest kod golfowy, więc wygrywa najkrótsze przesłanie (w bajtach).

Przykłady

Oto prawidłowe programy Preludium (w rzeczywistości są to nawet prawdziwe programy Preludium):

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

A oto kilka danych wejściowych, z których wszystkie są nieprawidłowe :

#(#(##)##)##(
)##(##(##)#)#
#(#)
)###
#(##
(##)
(##)
(#)#
(##)
(###
#(#)
(##)
#(#)
###)
#()#
()##
#(#)##
###
###(#)
Martin Ender
źródło
Czy Prelude ma komentarze, które mogłyby zablokować bliskie paren?
Alex A.
@Alex Nie. Powyższe zasady są naprawdę wszystkim, co decyduje o tym, czy program jest ważny, czy nie.
Martin Ender
Fajnie, dziękuję za wyjaśnienie. Chciałem się tylko upewnić.
Alex A.
Reguła 1 - „Każda kolumna tekstu zawiera najwyżej jedną z (i)”; Przykład 1, wiersz 2: „1 0v ^ (# 0) (1 + 0) #)!” -> Widzę 3 )i 2 (. Czy nie powinien to być tylko 1 na linię?
Ismael Miguel
1
„Kolumna” @ IsmaelMiguel zwykle rozumiana jest jako odnosząca się do linii pionowych (szczególnie w kontekście siatek). Ale i tak to wyjaśniłem.
Martin Ender

Odpowiedzi:

3

CJam, 57 56 bajtów

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

Za długo można dużo grać w golfa. Wyjaśnienie, które należy dodać, gdy zacznę grać w golfa.

Krótkie wyjaśnienie

Kod składa się z dwóch kontroli:

  • Pierwszy filtr sprawdza, czy każda kolumna ma najwyżej 1 nawias. Ostatecznym wyjściem filtra jest liczba kolumn z więcej niż 1 nawiasami.
  • Po drugie, przekształcamy dane wejściowe na główny format kolumny, a następnie dzielimy je na każdym indeksie na dwie części.
    • W każdej z tych dwóch części ( Number of "(" - Number of ")") powinny się wzajemnie uzupełniać. Kiedy je dodasz, wynik powinien wynosić 0. Każda część, która nie spełnia tej właściwości, powoduje, że całe dane wejściowe mają niepasujące nawiasy kwadratowe.
    • Muszę również upewnić się, że „(” znajduje się po lewej stronie „)”. Oznacza to, że wartość Number of "(" - Number of ")"nie może być ujemna dla bloku po prawej stronie.

Wypróbuj online tutaj

Optymalizator
źródło
6

Python 2, 128 119 105 bajtów

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

Czy wiesz, że możesz zmapować Brak w Pythonie 2?

Wyjaśnienie

Chcemy zacząć od transpozycji Preludium, aby kolumny stały się wierszami. Zwykle robilibyśmy to za pomocą zip, ale ponieważ zipskraca się do najkrótszej długości rzędu i itertools.zip_longestjest zdecydowanie za długi dla gry w golfa, wydaje się, że nie ma krótkiego sposobu na zrobienie tego, co chcemy ...

Z wyjątkiem mapowania None:

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

Niestety (a raczej, na szczęście dla wszystkich celów innych niż golf), działa to tylko w Pythonie 2.

Co do ni v:

  • ndziała jak stos, licząc 1 - <number of unmatched '(' remaining>. Za każde, (co widzimy, odejmujemy 1, a za każde, )co widzimy, dodajemy 1. Stąd, jeśli n >= 2w którymś momencie, widzieliśmy zbyt wiele )s, a program jest nieprawidłowy. Jeśli nnie zakończy się na 1, oznacza to, że pozostała nam co najmniej jedna niedopasowana (.
  • vsprawdza ważność i rozpoczyna się od 1. Jeśli program jest kiedykolwiek nieprawidłowy ( n >= 2lub A+B >= 2), wówczas przyjmuje wartość v0, oznaczając nieważność.

Dlatego jeśli program jest ważny, to do końca musimy go mieć n = 1, v = 1. Jeśli program jest nieprawidłowy, to do końca musimy albo v = 0, albo v = 1, n <= 0. Dlatego ważność można zwięźle wyrazić jako n*v>0.

(Dzięki @feersum za wiele dobrych sugestii, które pobrały 14 bajtów!)

Poprzednie, bardziej czytelne przesłanie:

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
źródło
To szalone użycie 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 Thanks! Ja staram się zmienić ordo porównania łańcuchowych, ale nie myślę o zmianie |=na *=. Ale
wziąłem
2

J, 64 bajty

Dane wejściowe to ciąg znaków z końcowym znakiem nowej linii. Wyjście wynosi 0 lub 1.

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

Przykładowe użycie

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

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

Metoda jest następująca

  • wyciąć dane wejściowe na nowych liniach i umieścić w macierzy ];.2
  • map (/ )/ anything elseinto 1/ -1/0 1 _1 0{~[:'()'&i.]
  • zdefiniuj s=.+/@:przysłówek, który dodany do czasownika sumuje dane wyjściowe tablicy czasowników
  • dodaj wartości w kolumnach ]s

    • sprawdź dodatnie ()saldo w każdym prefiksie [:(0>])s)[:+/\]
    • sprawdź ()równowagę na całej liście (tj. w ostatnim prefiksie) |@{:@]
  • dodaj abs (wartości) w kolumnach i sprawdź każdy element pod kątem maksymalnej wartości 1 (1<|s)s

  • ponieważ wszystkie poprzednie kontrole dały wynik pozytywny w przypadku niepowodzenia, dodajemy je i porównujemy z 0, aby uzyskać poprawność danych wejściowych 0=]

randomra
źródło
2

J, 56 bajtów

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

Jest to anonimowa funkcja akceptująca ciąg z końcowym znakiem nowej linii i zwracająca 0 lub 1. Czytanie od prawej do lewej:

  • ];.2 y, podobnie jak w drugim przedłożeniu J, odcina ciąg znaków ywe wszystkich wystąpieniach jego ostatniego znaku (dlatego dane wejściowe wymagają nowej linii) i tworzy prostokątną macierz, której rzędy są kawałkami, w razie potrzeby wypełnionymi spacjami.

  • '()'=/porównuje najpierw każdy znak w tej macierzy z, (a następnie )zwracając listę dwóch macierzy 0-1.

  • +.^:_1]0|:zamienia listę dwóch macierzy w jedną macierz liczb zespolonych. Jak dotąd program zamienia każde (wejście na 1, każde )na i, a każdy inny znak na 0.

  • b=.+/przypisuje do sumy wierszy tej złożonej macierzy b.

  • -.|btworzy listę 1- | z | dla każdego z b. Warunek, że każda kolumna zawiera co najwyżej jeden nawias, przekłada się na wszystkie te liczby 1- | z | być nieujemnym.

  • +/\*:bto wektor sum sumy kwadratów liczb w b. Jeśli każda kolumna zawiera co najwyżej jeden nawias, wszystkie kwadraty liczb bto 0, 1 lub -1. W ,Łączy tego wektora z wektorem 1- | Z | 's.

  • Teraz wszystko, co musisz zrobić, to sprawdzić, czy wpisy naszego połączonego wektorem vsą nieujemnymi numery liczb rzeczywistych, to jest prawie */0<:v, z wyjątkiem tego, który powoduje błąd, jeśli niektóre wpisy vnie są prawdziwe, więc możemy zastąpić <:z <: ::0:których po prostu zwraca 0 w przypadku błędu .

Omar
źródło
Świetne pomysły z liczbami zespolonymi, ale musisz także sprawdzić, czy 0={:+/\*:bnp. (Nie jest poprawny.
randomra
Och, masz rację, @randomra, zapomniałem!
Omar
1
0=(-|)vjest o 2 bajty krótszy do sprawdzania nieujemnych wartości rzeczywistych. (Pokonajmy CJam!: P)
randomra
1
Aha, a invzamiast ^:_1 oszczędza kolejny bajt.
randomra
1
Powrót do 56 (z kontroli bilansu) 3 :'*/0=({:,]-|)(-.@|,+/\@:*:)+/+.inv]0|:''()''=/];.2 y'.
randomra