Kolejny problem z analizowaniem Brainfuck, ale tym razem ... inaczej.

Pracujesz w Infinite Monkeys Incorporated, firmie produkującej programy Brainfuck, w celu rozwiązania różnych interesujących problemów (przypadkowo, nie mniej - przecież firma tworzy programy losowe). Wydaje się jednak, że twoje szybkie maszyny Turinga, które wykonują tylko Brainfuck, mają mały i kosztowny problem z błędami składniowymi - zrób je, a komputer wybuchnie. Prawdopodobnie jest to wada projektowa, ale nikt nie zadał sobie trudu, aby dowiedzieć się, dlaczego tak się dzieje.

Ponieważ maszyny Turinga (szczególnie szybkie) są drogie (w końcu mają nieskończoną pamięć RAM, która kosztuje), lepiej upewnić się, że program nie ma żadnych błędów składniowych przed wykonaniem kodu. Twoja firma uruchomi dużo kodu, więc ręczna weryfikacja nie będzie działać. Napisz program, który odczytuje STDIN dla kodu Brainfuck i kończy pracę ze statusem wyjścia ustawionym na wartość inną niż 0 (błąd), jeśli program ma jakiś błąd składniowy (na przykład ]jest błędem składniowym, ponieważ nie ma pasującego dopasowania [). Wyjdź ze statusem wyjścia ustawionym na 0, jeśli program działa poprawnie.

Upewnij się, że Twój program poprawnie zauważa błędy dotyczące []. Nie chciałbyś, żeby inny komputer wybuchł, prawda? Aha, i upewnij się, że jest tak krótki, jak to możliwe - twój szef płaci za krótkie programy (ponieważ uważa, że ​​są one szybkie lub coś w tym rodzaju). Aha, i nie musisz kodować w Brainfuck (w rzeczywistości nie możesz, ponieważ Brainfuck nie obsługuje kodów wyjścia) - twój kod zostanie uruchomiony na normalnym komputerze.

Jak widać, Twoim zadaniem jest sprawdzenie, czy program Brainfuck jest „prawidłowy” (ma sparowane []symbole). Pamiętaj, że programy Brainfuck mogą mieć inne znaki niż [], więc nie odrzucaj programu tylko dlatego, że ma inne polecenia. Najmniejszy kod wygrywa, ale prawdopodobnie i tak bardziej zależy Ci na upvotes.

GolfScript, 18 znaków

.{[]`?)},~](`91?./

Ten kod działa poprawnie z kodem wyjścia 0 (i drukuje śmieci na standardowe wyjście), jeśli nawiasy kwadratowe na wejściu są zrównoważone. Jeśli nie są, nie działa z niezerowym kodem wyjścia i wyświetla komunikat o błędzie na stderr, np .:

(eval):2:in `/': divided by 0 (ZeroDivisionError)

lub

(eval):1:in `initialize': undefined method `ginspect' for nil:NilClass (NoMethodError)

Ponieważ wyzwanie nie mówiło nic o wyjściu do stdout / stderr, sądzę, że to kwalifikuje się. W każdym razie możesz zawsze przekierować je do /dev/null.

Wyjaśnienie:

Kod {[]`?)},usuwa z danych wszystko oprócz nawiasów kwadratowych i ~ocenia wynik jako kod GolfScript. Problem polega na tym, że niezbalansowane nawiasy klamrowe są całkowicie legalne w GolfScript (a tak naprawdę mój kod zawiera jeden!), Więc potrzebujemy innego sposobu, aby spowodować awarię kodu.

Sztuką, której używam, jest pozostawienie kopii danych wejściowych na dole stosu, zebranie całego stosu do tablicy (używając niezrównoważonego ]) i przesunięcie pierwszego elementu. W tym momencie mogą się zdarzyć trzy rzeczy:

• Jeśli dane wejściowe zakończyły się niezamknięte [, próba przesunięcia elementu poza pustą tablicę spowoduje awarię interpretera (co w tym przypadku jest dokładnie tym, czego chcemy!)
• Jeśli nawiasy na wejściu są zrównoważone, przesunięty element będzie oryginalnym ciągiem wejściowym.
• W przeciwnym razie (jeśli dane wejściowe miały nieotwarte ]lub niezamknięte[ ) będzie to tablica.

Mój oryginalny 14-znakowy wpis porównał następnie przesuniętą wartość z łańcuchem, który zawiesiłby się, gdyby była zagnieżdżoną tablicą. Niestety okazuje się, że porównując mieszkanie (lub, w szczególności, pustej) tablicy z łańcuchem jest również dozwolone w GolfScript, więc musiałem zmienić tack.

Zamiast tego moje bieżące zgłoszenie wykorzystuje metodę bardzo brutalnej siły, aby odróżnić tablice od łańcuchów: odkrywa je i próbuje znaleźć pierwsze wystąpienie [ (kod ASCII 91), które będzie zerowe, jeśli tylko nieewaluowane zmienna była tablicą. Jeśli tak, podzielenie zera samym sobą powoduje pożądaną awarię.

Ps. Dwa inne 18-znakowe rozwiązania to:

.{[]`?)},{.}%~](n<

i

.{[]`?)},~]([n]+n<

Niestety, nie znalazłem jeszcze krótszego sposobu rozwiązania „problemu pustej tablicy”.

Brainfuck 76 bajtów

>>+[<+++++++++[->---------<]+>-[--[[-]<->]<[<[->-]>[<+]<]>]<[-<+>]+>,]<<[<+]

To wychodzi z więzów, jeśli nawiasy kwadratowe są niezrównoważone, co powoduje, że interpreter / kompilator bf nie działa w czasie wykonywania, a niektóre z nich mają kody wyjścia, które to odzwierciedlają.

wymaga eof = 0, zawijania wartości i skończonej liczby komórek

W Ubuntu możesz użyć interpretera bf( sudo apt-get install bf)

% echo '[[[]' | bf -n bf_matching.bf
Error: Out of range! Youwanted to '<' below the first cell.
To solve, add some '>'s at the beginning, for example.
an error occured
% echo $? 
5
% bf -n bf_matching.bf < bf_matching.bf
% echo $?
0

Befunge 98 - 26 31 20 19 znaków

~:']-!\'[-!-+:0`j#q

Pozbyłem się ogromnych warunków. Teraz program działa w następujący sposób:

~:   read an input char and duplicate it

']-! push a 1 if the char is the ] char, 0 otherwise

\    swap the comparison value for the duplicated input char

'[-! push a 1 if the char is the [ char, 0 otherwise

-    subtract the two comparison values. If the second one is 1, the first is 0, 
     so the result is -1. Else if the second one is 0, the first is 1 and the result is
     1. Else, the first and the second are both 0 and the result is 0

+    Add the number to the counter (which is 0 if there is none already)

:0`  test if the counter is positive (that'd mean an invalid program). Pushes a 1 if 
     positive, 0 otherwise.

j#q  if the counter is positive, then this jumps to the q. Otherwise, it skips the q 
     and continues to the ~ at the beginning of the line. If there are no more chars in
     the input, then the IP will be sent back to the q. 

qzamyka program i wyświetla najwyższą wartość jako wartość błędu. Wartość błędu wyniesie -1 1, jeśli jest ich zbyt wiele ], 0, jeśli są zrównoważone, i dodatnia ujemna, jeśli jest ich zbyt wiele [. Jeśli liczba jest dodatnia ujemna, to tyle absolutnej wartości tej liczby] jest potrzebnych do zrównoważenia programu.

Edycja: Przełączany przyrost i spadek. [służy do zwiększania licznika i ]służy do zmniejszania go. Przełączając go, zapisuję 1 znak, ponieważ dla warunku wyjścia muszę tylko sprawdzić, czy licznik jest dodatni, a nie ujemny.

Stara wersja

~:'[-!j;\1+\#;']-!j;1-#;:0\`j#q

Ten kod działa w następujący sposób:

~    read one char of input
:    duplicate it
'[-! push 1 if the character is [, 0 otherwise
j    jump that number of characters
;    skip until next ;
\1+\ increment counter

similarily for ].

#q when end of input is reached, ~ reflects the IP back. q ends the program with the error value on the stack.

Edycja: zdałem sobie sprawę, że to zaakceptowane dane wejściowe, takie jak ][, teraz kończy się, gdy liczba staje się ujemna, używając

:0\`j

J ( 38 35)

exit({:+.<./)+/\+/1 _1*'[]'=/1!:1[3

Wyjaśnienie:

• 1!:1[3: przeczytaj standardowe
• '[]'=/: utwórz macierz, w której pierwszy wiersz jest maską bitową [s na wejściu, a drugi wiersz to ]s.
• 1 _1*: pomnóż pierwszy rząd przez 1, a drugi rząd przez -1.
• +/: zsumuj kolumny macierzy razem, podając wcięcie delta na znak
• +/\: utwórz ich bieżącą sumę, podając poziom wcięcia dla każdej postaci
• ({:+.<./): zwraca GCD ostatniego elementu ( {:) i najmniejszego elementu ( <./). Jeśli wszystkie nawiasy klamrowe pasują do siebie, oba powinny być, 0więc to zwróci 0. Jeśli nawiasy klamrowe nie pasują, zwróci niezerową wartość.
• exit: ustaw na tym wartość wyjścia i wyjdź.

rubin (64)

exit $<.read.tr('^[]','').tap{|x|0while x.gsub!('[]','')}.empty?

poprzednio (68) było to:

exit ARGF.read.tr('^[]','').tap{|x| 0 while x.gsub!('[]','')}.empty?

Używa innego równoważnego rozwiązania

exit $<.read.tr('^[]','').tap{|x|0while x.gsub!('[]','')}.size>0

nie można używać w sizepojedynkę, ponieważ dałoby to fałszywe negatywy (!!!), gdy całkowita liczba niewyważonych nawiasów jest wielokrotnością 256

Perl, 30 znaków

Twoje podstawowe rekurencyjne wyrażenie Perla na ratunek:

perl -0ne 'exit!/^(([^][]|\[(?1)\])*)$/'

Dla osób niezaznajomionych z używanymi tutaj argumentami wiersza poleceń: -0pozwala ustawić znak końca wiersza na potrzeby wprowadzania plików; użycie -0bez argumentu ustawia znak końca linii na EOF. -nautomatycznie odczytuje wcześniej dane wejściowe (w tym przypadku cały plik) $_.

Jeśli wyrażenie regularne pasuje, zwraca wartość true, która jest negowana do 0 dla kodu wyjścia. W przeciwnym razie fałszywa wartość zwracana daje kod wyjścia 1.

bash (tr + sed) - 42

[ -z `tr -Cd []|sed ":a;s/\[\]//g;t a"` ]

Jeśli nie przeszkadza ci komunikat o błędzie, możesz usunąć ostatnią spację między `i, ]aby uzyskać długość 41.

Perl (56 znaków)

$/=0;$r=qr/[^][]*(\[(??{$r})\])*[^][]*/;<>=~m/^$r$/||die

Oczywiste rozwiązanie Perla: rekursywne wyrażenie regularne. Niestety jest to dość rozbudowana konstrukcja.

Haskell (143)

import System.Exit
f=exitFailure
v c []|c==0=exitSuccess|True=f
v c (s:t)|c<0=f|s=='['=v(c+1)t|s==']'=v(c-1)t|True=v c t
main=getContents>>=v 0

do jgon: Używanie 2 strażników wydaje się być bardziej gęste niż jeśli-to-inaczej. Poza tym nie sądzę, żeby sprawdził, czy nawiasy są w odpowiedniej kolejności („] [” przechodzi)

C, 73 64 znaków

Dzięki sugestiom z breadboksa (choć to prawdopodobnie wymaga little-endian do pracy):

i;main(c){while(read(0,&c,1)*(i+1))i+=(c==91)-(c==93);return i;}

Jak to działa:

• niejawna wartość globalna ijest inicjowana na 0
• cstaje się domyślną int, która dostaje argc(inicjowana na 1, ale nie obchodzi nas to, o ile wyższe bity nie są ustawione)
• read(0,&c,1)wczytuje pojedynczy znak do niskiego bajtu c (w architekturze little-endian) i zwraca 0 w EOF; i+1 != 0chyba że cytat w zbilansowanym nawiasie wynosi -1; pomnożenie ich razem działa jako (bezpieczna) wartość logiczna ORAZ, która zajmuje jeden mniej znaków niż&&
• c==91ocenia na 1 dla '[', i c==93ocenia na 1 dla']' . (Może być trochę sztuczek, które byłyby mniejsze, ale nic nie mogę wymyślić.)
• return iwychodzi z kodem stanu 0, jeśli jest zrównoważony, niezerowy, jeśli nie jest. Zwracanie -1 technicznie narusza POSIX, ale nikt tak naprawdę nie dba o to.

Poprzednia wersja:

main(i){char c;i=0;while(read(0,&c,1)*(i+1))i+=(c==91)-(c==93);return i;}

Lua, 56 lat

os.exit(("["..io.read"*a".."]"):match"^%b[]$"and 0 or 1)

GTB , 55

0→O:0→X[`I@I="[":X+1→X@I="]":X-1→X@X<0:1→O@!!Ig;e]l;e~O

Brakuje []

Użyj, 0aby zatrzymać.

MATHEMATICA, 88 znaków

s = "[ [ my crazy code ] [ don't explode please! [] [ :)Ahh) ]  [] []]]";

r=StringReplace;
StringLength@FixedPoint[r[#,"[]"-> ""]&,r[s,Except@Characters["[]"]-> ""]]

Rubin, 59 58

Skanuje nawias otwierający i zamykający, licząc [jako 1 i ]jako -1, i kończy działanie, jeśli liczba spadnie poniżej 0.

b=0
$<.read.scan(/\]|\[/){exit 1if(b+=92-$&.ord)<0}
exit b

Wapń , 104 bajty

func main(){l=0;r=0;b=input();foreach (c in b){if(c=="[")l++;if(c=="]")r++;}if(!(r==l))exit(1);exit(0);}

Pełny rozwinięty (notatka nie działa w tłumaczu online, ponieważ input () jest wyłączony) tutaj

Kod maszynowy Turinga, 286 276 bajtów

Ponownie używam zdefiniowanej tutaj składni tabeli reguł .

0 * * l 1
1 _ ! r Q
5 _ _ r 5
5 * * * W
W [ ! l E
W ] ! l T
W _ _ l I
W * ! r *
E ! ! l *
E * * * R
R _ [ r O
R * * l *
T ! ! l *
T * * * Y
Y _ _ r U
Y * * l *
U [ _ r O
U ! ! * halt-err
I ! ! l *
I _ _ r halt
I * * l halt-err
O ! ! r Q
O _ _ l I
O * * r *
Q ! ! r *
Q * * * W

Kończy się w stanie, haltaby zaakceptować i halt-errodrzucić dane wejściowe .

Pyth, 25 bajtów

Ilzv::z"[^[\]]"k"]\[""],[

Wypróbuj online!

import re
z=input()
if len(z):
 print(eval(re.sub("]\[","],[",re.sub("[^[\]]","",z))))

Haskell ( 167 , 159)

Zrobiłem to głównie dla zabawy, jeśli ktoś ma jakieś sugestie, jak to skrócić, chętnie je usłyszę :)

import System.Exit
p x y b|b=x|True=y
main=getContents>>=(return.all (>=0).scanl (\v->p (v-1) (v+1).(==']')) 0.filter (`elem`"[]"))>>=p exitSuccess exitFailure

Edycja: Naprawiono problem wskazany mi w komentarzach (dodano 11 bajtów).

Edycja 2: Utworzono funkcję pomocniczą do testowania predykatów przy użyciu strażników zainspirowanych przez user13350, usuwając 8 bajtów.

Stax , 14 11 znaków

╬Äτ↔EªÉs «Ü

Uruchom i debuguj

Kredyt @recursive za -3 bajty.

Odpowiednik ASCII:

.[]Y|&{yz|egp!

Usuń wszystkie znaki z wyjątkiem [], a następnie usuń, []aż łańcuch się nie zmieni. Zwraca, 1jeśli ostatni ciąg jest pusty.