Sprawdź program Brainfuck

17

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.

Konrad Borowski
źródło
1
Co z językami, które nie pozwalają na ustawienie kodu zakończenia procesu?
Kendall Frey
1
@KendallFrey: Proste, użyj czegoś innego. Lub w GolfScript, osadz kod Ruby. Być może blokuje to niektóre ezoteryczne języki programowania, ale cóż ...
Konrad Borowski
1
Czy w przypadku niepowodzenia można ustawić kod błędu na wartość inną niż 1 (o ile oczywiście nie jest to zero)?
marinus
@marinus: Nie wiem, dlaczego tego chcesz, ale myślę, że jest w porządku.
Konrad Borowski
@GlitchMr: ponieważ wtedy mogę użyć GCD(a,b)zamiast 0 != a || b.
marinus

Odpowiedzi:

6

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

Ilmari Karonen
źródło
czy to jest zrównoważone ?: ][(tzn. czy zawodzi w twoim programie?)
Justin
@Quincunx: kończy się niepowodzeniem, tak jak powinno.
Ilmari Karonen
Okazało się jednak, że się zgadza [[]; Naprawiłem to teraz, kosztem 4 znaków, i teraz przechodzi wszystkie moje testy.
Ilmari Karonen
Jeśli dobrze cię rozumiem, masz 14-znakowe rozwiązanie, które nie rozróżnia łańcucha i tablicy tylko w przypadku, gdy tablica jest pusta. 1+zamieni pustą tablicę w niepustą tablicę, niepustą tablicę w niepustą tablicę, a łańcuch w łańcuch.
Peter Taylor
@PeterTaylor: Tak, tak było .{[]`?)},~](n<. Próbowałem twojego 1+, ale wygląda na to, że tablica musi zawierać coś innego niż liczbę (przypuszczalnie tak, że interpreter się zawiesi, gdy spróbuje rekurencyjnie porównać znak z tablicą / łańcuchem). Użycie n+również nie działa, ponieważ wymusza tablicę na ciąg; [n]+ ma pracę, ale nadal stawia mnie na 18 znaków.
Ilmari Karonen
17

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
Sylwester
źródło
5
Podoba mi się to, jak używałeś Brainfuck, chociaż pytanie brzmiało, że to niemożliwe.
Riking
Och, wow. Jestem szczerze zaskoczony. Zakładałem, że to niemożliwe, ale nie jest.
Konrad Borowski
1
@xfix: Brainfuck jest gotowy do pracy, więc może zrobić wszystko (biorąc pod uwagę ograniczenia I / O).
marinus
2
@marinus Turing kompletność oznacza tylko, że może wykonywać wszystkie obliczenia. Brainfuckjest zakończony Turinga bez I / O, ponieważ można uruchomić program, który oblicza dowolne obliczenia i zobaczyć wynik, sprawdzając jego pamięć po uruchomieniu. BF bez I / O sprawiłoby, że ludzie byliby mniej zainteresowani, ponieważ trudno byłoby tworzyć narzędzia. np. nigdy nie mogłem zrobić mojego tłumacza seplenienia .
Sylwester
14

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
Justin
źródło
1
18 bajtów
Jo King
@JoKing to całkiem fajne, używając odległości między [i ]aby porównać z obu.
Justin,
6

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ź.
marinus
źródło
Niezły podział ...
Chris Cashwell,
6

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

przepisane
źródło
To jest codegolf. Jestem pewien, że możesz tutaj usunąć trochę białych znaków. Ruby jest nieco wrażliwy na białe znaki, ale w wielu przypadkach ignoruje go. Na początek nie potrzebujesz białych znaków w pobliżu =operatora.
Konrad Borowski
lepsza wersja (nieco zainspirowana rozwiązaniem sed + tr). Nie jestem pewien, czy mogę być znacznie lepszy od tego. Przynajmniej ma aż 4 białe spacje!
przepisany
1
A jednak mogę usunąć dwa z nich.
Konrad Borowski
2
Myślę, że przestrzenie wokół 0mogą pójść.
marinus
niesamowita sztuczka kosmiczna, dzięki!
przepisany
5

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.

chlebak
źródło
Chyba będę musiał lepiej pograć w golfa, aby pokonać to 30-znakowe rozwiązanie.
Justin
Tam. Moje rozwiązanie jest teraz znacznie krótsze niż wcześniej. Niezłe rozwiązanie. +1
Justin
4

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.

shiona
źródło
O ile niczego nie przegapię, masz bezużyteczne użycie cati $()( "[]"można również zapisać jako []). Zaakceptowałem tę odpowiedź, ale dopóki nie zobaczę poprawy długości, nie zamierzam jej głosować, ponieważ choć jest krótka, może być o wiele krótsza dla bash.
Konrad Borowski
Właściwie nie znam tak dobrze skryptów powłoki. Nie jestem w stanie zmusić większości z nich do pracy. Wymieniłem $()z backticks i zrobił to "[]"-> []pan sugeruje.
shiona
Nadal bezużyteczne korzystanie z kota .
Konrad Borowski
1
Mógłbym mieć miecz, próbowałem i nie udało mi się, ale się myliłem.
shiona
3

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.

Peter Taylor
źródło
3

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)

użytkownik13350
źródło
och, wow, widziałem ten komentarz tylko wtedy, gdy został wskazany dzisiaj. Naprawiłem mój kod, ale tak, fajnie, strażnicy wydają się gęstsi (+1).
jgon
3

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;}
puszysty
źródło
Użycie getchar()zamiast odczytu skróci kod i pozwoli na użycie (niejawne) intzamiast charzmiennej. Pamiętaj również, że globały są automatycznie inicjowane na zero.
breadbox
Dzięki, zapomniałem o getchar (). Nie jestem jednak pewien, w jaki sposób pomaga globalny init - zdefiniowanie globalnego int zajmuje więcej znaków niż użycie domyślnego argc.
puszysty
1
Globalne mogą być również domniemane. Poza funkcją c;definiuje globalny int.
breadbox
Tymczasem getchar (c) nie czyni go wcale krótszym, przynajmniej stosując to podejście, ponieważ musi być w jakiś sposób przetestowany na> = 0, a niejawna int dla c przekazana do read () nie jest gwarantowana praca z powodu endianizmu.
puszysty
Co ][? Jestem pewien, że nie jest zrównoważony. Czy nie musisz śledzić, czy co najmniej raz jest ujemny?
vsz
2

Lua, 56 lat

os.exit(("["..io.read"*a".."]"):match"^%b[]$"and 0 or 1)
mniip
źródło
"^%b[]$"co to jest? Możesz wytłumaczyć? Z pewnością to nie jest wyrażenie regularne?
Cruncher
@Cruncher: To nie jest. To wzór Lua, a nie wyrażenia regularne (wzory Lua są podobne do wyrażeń regularnych, ale nie są). W tym przypadku dopasowuje początek string ( ^), zbalansowany zestaw [iz ]dowolną inbetween ( %b[]) i koniec string ( $).
Konrad Borowski
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ć.

Timtech
źródło
1

MATHEMATICA, 88 znaków

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

r=StringReplace;
StringLength@FixedPoint[r[#,"[]"-> ""]&,r[s,Except@Characters["[]"]-> ""]]
Murta
źródło
Dzięki funkcji s name like RegularExpression` i StringLengthnigdy nie mogę wygrać tekstowego golfa w kontekście matematyki! :)
Murta
Wiem, co masz na myśli :) ToCharacterCodejest znacznie dłuższy niż ord... PS: A co z ustawieniem kodu wyjścia?
Ajasja
Length[StringCases[s,"["|"]"]//.{x___,"[","]",y___}:>{x,y}]
alephalpha
1

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
daniero
źródło
1
Uznany i skrócony o jedną postać (usunąłem białe znaki exit 1na wypadek, gdybyś poprosił).
Konrad Borowski
1

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

Jacob Misirian
źródło
1

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 .

SuperJedi224
źródło
halt-errmoże być krótszy, halt*na przykład na przykład.
Erik the Outgolfer
1

Pyth, 25 bajtów

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

Wypróbuj online!

Tłumaczenie Python 3:
import re
z=input()
if len(z):
 print(eval(re.sub("]\[","],[",re.sub("[^[\]]","",z))))
hakr14
źródło
1

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.

jgon
źródło
@ user202729 To doskonały punkt, który był bardzo nieostrożny. Jestem prawie pewien, że to już naprawione.
jgon
1

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.

Weijun Zhou
źródło
1
Ładny. Możesz użyć .[]|&do filtrowania znaków, a następnie ponownie użyć literału dla 11
rekurencyjny