Wyzwanie to opublikowano w ramach wyzwania LotM z kwietnia 2018 r. , A także na drugie urodziny Brain-flak

Myślałem o tym, jaki byłby najskuteczniejszy sposób kodowania programów do wyłamywania mózgów. Oczywistą rzeczą do zrobienia, ponieważ jest tylko 8 prawidłowych znaków, jest mapowanie każdego znaku na 3-bitową sekwencję. Jest to z pewnością bardzo skuteczne, ale wciąż bardzo zbędne. Istnieją pewne cechy kodu wyrywającego mózg, które moglibyśmy wykorzystać, aby skrócić kodowanie.

• Nilady, które są reprezentowane przez 2 dopasowane nawiasy, naprawdę działają jak pojedyncza jednostka informacji, a nie 2. Gdybyśmy zastąpili każdy nawias jednym znakiem bajtu, spowodowałoby to, że kodowanie byłoby znacznie mniejsze bez utraty danych.

• Ten jest mniej oczywisty, ale bajty końcowe monad są również zbędne. Myślisz, że możesz zgadnąć, co '?'przedstawiają postacie w poniższym fragmencie?

   {(({}?<>?<>?
  

  Jeśli założymy, że wprowadzony kod jest prawidłowy, jest to jedna opcja dla każdego z tych znaków zapytania. Oznacza to, że możemy jednoznacznie użyć znaku zamkniętej monady do przedstawienia każdego zamykającego nawiasu. Ma to dodatkową zaletę polegającą na utrzymywaniu niewielkiego zestawu znaków, co byłoby bardzo pomocne, gdybyśmy chcieli użyć kodowania huffmana. Ponieważ postać z bliskiej monady najprawdopodobniej będzie najczęstszą postacią z szerokim marginesem, może być reprezentowana przez pojedynczy bit, co jest niezwykle wydajne.

Te dwie sztuczki pozwolą nam skompresować kod uderzenia mózgu za pomocą następującego algorytmu:

1. Zamień każdy wspornik zamykający monady na |. Innymi słowy, zamień każdą klamrę zamykającą, która nie jest poprzedzona dopasowaniem otwierającym, na słupek. Więc...

   (({})<(()()())>{})
   

   stanie się

   (({}|<(()()()||{}|
   

2. Zastąp każdy nilad wspornikiem zamykającym. Dlatego dopasowane nawiasy klamrowe bez niczego używają następującego mapowania:

   () --> )
   {} --> }
   [] --> ]
   <> --> >
   

   Teraz naszym ostatnim przykładem jest:

   ((}|<()))||}|
   

3. Usuń końcowe |znaki. Ponieważ wiemy, że całkowita liczba pasków powinna być równa całkowitej liczbie ({[<znaków, jeśli na końcu brakuje pasków, możemy je wywnioskować. Oto przykład:

   ({({})({}[()])})
   

   stanie się

   ({(}|(}[)
   

Twoim dzisiejszym wyzwaniem jest odwrócenie tego procesu.

Biorąc pod uwagę ciąg skompresowanego ataku mózgu zawierającego tylko znaki (){}[]<>|, rozwiń go do oryginalnego kodu ataku mózgu. Możesz założyć, że dane wejściowe zawsze będą rozszerzane do prawidłowego uderzenia mózgu. Oznacza to, że żaden prefiks wejścia nigdy nie będzie zawierał więcej |niż ({[<znaków.

Dane wejściowe nie będą zawierać końcowych |znaków. Należy je wywnioskować z kontekstu.

Jak zwykle możesz przesłać pełny program lub funkcję, a formaty wejścia / wyjścia są dozwolone. A ponieważ jest to golfowy kod , twój kod będzie oceniany na podstawie długości kodu źródłowego w bajtach, im mniejszy wynik, tym lepiej.

Przypadki testowe

Oto kilka przypadków testowych. Jeśli chcesz więcej, możesz wygenerować własne przypadki testowe za pomocą tego skryptu python i Wiki Brain-Flak , skąd pochodzi większość tych przypadków testowych.

#Compressed code
#Original code

())))
(()()()())


([([}()||||(>||{(})|>|}{((<}|||>}|}>}
([([{}(())])](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

({(}|(}[)|||}
({({})({}[()])}{})


(((()))||(](((}}||(}([(((}))||||(]((}}|}|}}|||]||]|[))||(}))|}(}|(}]]|}
((((()()()))([]((({}{}))({}([((({}()())))]([](({}{}){}){}{})))[]))[])[()()])({}()()){}({})({}[][]){}

Brain-Flak , 952916818 bajtów

{(({})[(((()()()()()){}){}){}])((){[()](<{}>)}{}){{}(({})()<>)(<>)}{}(<>)<>(({})[(((()()()){}){}()){({}[()])}{}])((){[()](<{}>)}{})({}<>{})<>(({})[((((()()()()()){}){})){}{}])((){[()](<{}>)}{})({}<>{})<>(({})[(((((()()()()()){}){}){}())){}{}])((){[()](<{}>)}{})({}<>{}){{}(<(<>({})()()<>)>)}{}<>(({})[(((()()()()()){}){}){}()])((){[()](<{}>)}{}){{}(({})[()])(<>)<>(<({}<{({}<>)<>}{}>)>)<>{({}<>)<>}{}(<>)}{}(<>)<>(({})[(((((()()()()()){})){}{}())){}{}])((){[()](<{}>)}{})({}<>{})<>(({})[((((()()()()()){}){})()){}{}])((){[()](<{}>)}{})({}<>{})<>(({})[(((((()()()()()){}){}){}())()){}{}])((){[()](<{}>)}{})({}<>{}){{}<>(<(({})[()()])(<>)<>(<({}<{({}<>)<>}{}>)>)<>{({}<>)<>}{}>)}{}<>(({})[(((((()()()()()){}){})()){}{}){}])((){[()](<{}>)}{}){{}{}(<(<>{}<>)>)}{}(<>)<>(<({}<{({}<>)<>}{}>)>)<>{({}<>)<>}{}<>}{}{({}<>)<>}<>

Oszczędność 360 bajtów poprzez obliczenie przeciwnych nawiasów względnie zamiast od zera (np. ')'= '(' + 1Zamiast (((5 * 2) * 2) * 2) + 1)

Zapisano 34 bajty z kilkoma bezpośrednimi zamiennikami z DJMcMayhem

Zapisano 10 bajtów, nakładając się na >]}kod obsługi

Zaoszczędzono 118 bajtów, deduplikując rolki

Oszczędność 40 bajtów dzięki wykorzystaniu pustego stosu w celu uproszczenia pierwszego rzutu

Zaoszczędzono 48 bajtów, oznaczając EOF wartością -1, umożliwiając bardziej zwięzły kod roll

Zaoszczędziłem 36 bajtów, stosując zapas równy logice zamiast mojej

Zaoszczędzono 98 bajtów dzięki Jo Kingowi, który znalazł bardziej efektywny sposób na zbudowanie wyjścia

Wypróbuj online!

Po raz pierwszy gra w golfa w Brain-Flak, więc prawdopodobnie jest kilka naprawdę dużych ulepszeń, ale działa. Dużo kopiowania / wklejania do obsługi każdego rodzaju nawiasów i duże dzięki automatycznemu generatorowi liczb całkowitych i fragmentowi Roll z tego miejsca .

Wyjaśnienie tutaj , TIO formatuje go łatwiej

Dodatkowa odpowiedź:

Skompresowane 583 bajty Brain-Flak

{((}|[((()))))|}|}|}||(){[)|(<}|||}|{}((}|)>|(>||}(>|>((}|[((()))|}|})|{(}[)|||}||(){[)|(<}|||}|(}>}|>((}|[(((()))))|}|}||}}||(){[)|(<}|||}|(}>}|>((}|[((((()))))|}|}|})||}}||(){[)|(<}|||}|(}>}|{}(<(>(}|))>||||}>((}|[((()))))|}|}|})||(){[)|(<}|||}|{}((}|[)||(>|>(<(}<{(}>|>|}||||>{(}>|>|}(>||}(>|>((}|[((((()))))|}||}})||}}||(){[)|(<}|||}|(}>}|>((}|[(((()))))|}|}|)|}}||(){[)|(<}|||}|(}>}|>((}|[((((()))))|}|}|})|)|}}||(){[)|(<}|||}|(}>}|{}>(<((}|[))||(>|>(<(}<{(}>|>|}||||>{(}>|>|}|||}>((}|[((((()))))|}|}|)|}}|}||(){[)|(<}|||}|{}}(<(>}>||||}(>|>(<(}<{(}>|>|}||||>{(}>|>|}>|}{(}>|>|>

Wypróbuj online!

(Zauważ, że powyższy link nie działa, ponieważ TIO nie posiada tłumacza Compressed Brain-Flak. Można znaleźć transpiler do Brain-Flak tutaj )

Sprawdziłem, czy jest to poprawne, dokonując transpozycji do Brain-Flak za pomocą tego narzędzia, teraz na tyle wydajnego, że przekroczenie limitu czasu jest mało prawdopodobne.

Retina 0.8.2 , 103 98 bajtów

[])}>]
$&;
T`])}>|`[({<;
r`(.*)((;)|(?<-3>.))*
$&$.1$*;
(?<=(.)((;)|(?<-3>.))*);
;$1
T`;-{`_>-}`;.

Wypróbuj online! Link zawiera przypadki testowe. Edycja: Zapisano 5 bajtów z inspiracją @MartinEnder. Wyjaśnienie:

[])}>]
$&;
T`])}>|`[({<;

Umieść ;po każdym zamkniętym nawiasie i zmień je wszystkie na otwarte nawiasy, a także zmień |s na ;s.

r`(.*)((;)|(?<-3>.))*
$&$.1$*;

Policz liczbę niedopasowanych otwartych nawiasów i dodaj tyle ;s.

(?<=(.)((;)|(?<-3>.))*);
;$1

Skopiuj każdy otwierający wspornik do pasującego ;.

T`;-{`_>-}`;.

Odwróć skopiowane nawiasy i usuń ;s.

TIS , 670 666 bajtów

^{-4 bajty do przeskakiwania do przodu i do tyłu}

Kod:

@0
MOV UP RIGHT
@1
MOV ANY ACC
SUB 41
NOP
NOP
NOP
NOP
NOP
NOP
NOP
NOP
MOV ACC DOWN
@2
NOP
MOV 124 LEFT
@3
MOV ANY DOWN
@4
MOV UP ACC
JGZ O
MOV 40 LEFT
JLZ (
MOV 41 LEFT
JRO 3
O:SUB 21
MOV ACC DOWN
JRO -8
(:MOV 41 RIGHT
@5
MOV ANY DOWN
@6
MOV ANY DOWN
@7
MOV UP ACC
JGZ O
MOV 60 LEFT
JLZ <
MOV 62 LEFT
JRO 3
O:SUB 31
MOV ACC DOWN
JRO -8
<:MOV 62 RIGHT
@8
MOV ANY DOWN
@9
MOV ANY DOWN
@10
S:MOV UP ACC
JGZ O
MOV 91 LEFT
JLZ [
MOV 93 LEFT
JRO 3
O:SUB 31
MOV ACC DOWN
JRO -8
[:MOV 93 RIGHT
@11
MOV ANY DOWN
@12
MOV ANY DOWN
@13
MOV UP ACC
JEZ |
MOV 123 LEFT
JLZ {
MOV 125 LEFT
JRO 2
|:MOV DOWN LEFT
JRO -7
{:MOV 125 RIGHT
@14
MOV ANY DOWN
@15
MOV UP DOWN
@16
MOV UP LEFT

Układ:

6 3
CCCCCCCCCCCCCCCCSC
I0 ASCII -
O0 ASCII -

Wypróbuj online!

Wątpię, aby to było najmniejsze, ale nie widzę sposobu, aby go zmniejszyć. Niestety, wszystkie NOPs wydają się niezbędne do czasu, a ja nie mogę umieścić stos, gdzie @14obecnie jest ze względu na odczyt z ANYw @11.

Struktura tego rozwiązania jest następująca:

Input
  |
  V
  0    1:synchro  2:EOF
  3    4:parens     5
  6    7:angles     8
  9   10:squares   11
 12   13:curlies   14
 15      stack     16
  |
  V
Output

Po zobaczeniu otwartego nawiasu otwierającego jest wysyłany wzdłuż lewej kolumny do wyprowadzenia, a zamknięcie jest wysyłane wzdłuż prawej kolumny do stosu.

Po zobaczeniu nawiasu klamrowego, zarówno otwieranie, jak i zamykanie są wysyłane wzdłuż lewej kolumny w celu wyjścia.

Po zobaczeniu potoku stos jest otwierany i wysyłany do wyjścia.

Po EOF @1zacznie czytać z @2zamiast strumienia wejściowego z @0. @2tworzy nieskończony strumień rur, więc stos zostanie opróżniony.

Po wyczerpaniu zarówno wejścia, jak i stosu program zatrzymuje się.

Ostrzeżenie: z powodu ograniczeń TIS rozmiar stosu jest ograniczony do 15. Jeśli cokolwiek jest zagnieżdżone głębiej, implementacja spowoduje niepoprawny wynik.

JavaScript (ES6), 107 bajtów

Pobiera dane wejściowe jako tablicę znaków. Zwraca ciąg.

a=>a.map(c=>(n=(S='|()[]{}<>').indexOf(c))?n&1?(s=[S[n+1],...s],c):S[n-1]+c:s.shift(),s=[]).join``+s.join``

Wypróbuj online!

Haskell, 127 121 bajtów

(""#)
(u:t)#('|':b)=u:t#b 
s#(c:b)|elem c")>]}"=m c:c:s#b|q<-m c:s=c:q#b
s#b=b++s
m c="> < ] [)(} {"!!mod(fromEnum c-6)27

Wypróbuj online!

Edytuj: -6 bajtów za pomocą funkcji @ Laikoni, aby znaleźć pasujący nawias .

Rubinowy , 104 bajty

a=[];$<.chars{|c|r="|[{(<>)}]";i=r.index(c);i<1||(i<5?a:$>)<<r[-i];$>.<<i<1?a.pop: c};$><<a.reverse.join

Jest to pełny program wysyłany do konsoli. (i<5?a:$>)<<r[-i]musi być jednym z najfajniejszych golfów, jakie kiedykolwiek grałem.

Wypróbuj online!

Rubinowy , 106 bajtów

->s{a=[];(s.chars.map{|c|r="|>)}][{(<";d=r[-i=r.index(c)];i<5||a<<d;i<1?a.pop: i<5?d+c:c}+a.reverse).join}

To jest moje pierwsze rozwiązanie. Anonimowa funkcja lambda, która pobiera i zwraca łańcuchy.

Wypróbuj online!

Brain-Flak , 606548 496 418 394 390 bajtów

{((({})))(<>)(((((((([(())()()()]){}){}){}())(()))(((())()())()){}{})){}[()])({<(({}<>{}[()]))>(){[()](<{}>)}{}<>}{}<><{}>){({}({})<>)(<>)}{}({}<>)(<>)(((((((([(())()()()]){}){}){}())(()))(((())()){}()){})){})({<(({}<>{}[()]))>[()]{()(<{}>)}{}<>}{}<>){(<({}(<()>)<>({})<{({}<>)<>}>)>)<>{({}<>)<>}}{}({}()<>){{}({}<>)((<>))}{}{}<>(<({}(<()>)<><{({}<>)<>}>)>)<>{({}<>)<>}{}<>}{}{({}{}<>)<>}<>

Wypróbuj online!

Zacząłem od gry w golfa odpowiedzi Kamila Drakariego , ale dotarło to do mnie do tego stopnia, że ​​postanowiłem opublikować ją jako osobną odpowiedź.

Wyjaśnienie:

{ #While input on stack
	((({})))(<>)	#Preserve copy of the character
	(((((		#Push the differences between start bracket characters
	((([(())()()()]){}){}){}())	#Push -31, 1
	(()))				#Push -30, 1
	(((())()())()){}{})		#Push -19, 1
	){}[()])			#Push -39
	({<(({}<>{}[()]))>(){[()](<{}>)}{}<>}{}<><{}>)	#If the character is any of the start brackets
	{({}({})<>)(<>)}{}					#Push the current character + TOS to the other stack

	({}<>)(<>)
	(((((		#Push the differences between end bracket characters
	((([(())()()()]){}){}){}())	#Push -31, 1
	(()))				#Push -30, 1
	(((())()){}()){})		#Push -19, 1
	){})				#Push -40
	({<(({}<>{}[()]))>[()]{()(<{}>)}{}<>}{}<>)	#If the character is any of the end brackets
	{(<({}(<()>)<>({})<{({}<>)<>}>)>)<>{({}<>)<>}}{}	#Push the character + TOS to the output

	({}()<>)	#If the character is not a |
	{{}({}<>)((<>))}{}	#Move current character to the other stack and push a zero
	{}		#Pop the top value of the stack, either the | or a 0
	<>(<({}(<()>)<><{({}<>)<>}>)>)<>{({}<>)<>}{}<>	#And push top of other stack to the output
}{}
{({}{}<>)<>}<>	#Reverse output and append the excess end brackets

I oczywiście...

Compressed Brain-Flak, 285 bajtów:

{(((}|||(>|(((((((([()|)))||}|}|})|()||((()|))|)|}}||}[)||({<((}>}[)||||){[)|(<}|||}>|}><}||{(}(}|>|(>||}(}>|(>|(((((((([()|)))||}|}|})|()||((()|)|})|}||}|({<((}>}[)||||[)|{)(<}|||}>|}>|{(<(}(<)||>(}|<{(}>|>|||||>{(}>|>||}(})>|{}(}>|((>|||}}>(<(}(<)||><{(}>|>|||||>{(}>|>|}>|}{(}}>|>|>

Java 10, 424 bajty

s->{int i=0;for(var c:s.toCharArray()){if("(<[{".indexOf(c)>-1)i++;if(c=='|')i--;}for(;i-->0;)s+='|';s=s.replace(")","()").replace(">","<>").replace("]","[]").replace("}","{}");char[]c=s.toCharArray(),r=new char[124];r[40]=41;r[60]=62;r[91]=93;r['{']='}';var o="";for(;++i<c.length ;){if(c[i]=='|'){c[i]=o.charAt(0);o=o.substring(1);}if("(<[{".indexOf(c[i])>-1&")>]}".indexOf(i+1<c.length?c[i+1]:0)<0)o=r[c[i]]+o;}return c;}

Jest to dość długie, ale nie mogłem wymyślić, jak je skrócić. To jednak niezłe wyzwanie.

Wypróbuj online tutaj .

Wersja bez golfa:

s -> { // lambda taking a String argument and returning a char[]
    int i = 0; // used for counting the number of '|'s that have been removed at the end of the input
    for(var c : s.toCharArray()) { // look at every character
        if("(<[{".indexOf(c) > -1) // if it's an open monad character
            i++; // we will need one more '|'
        if(c == '|') // if it's a close monad character
            i--; // we will need one '|' less
    }
    for(; i-- > 0; ) // add as many '|'
        s += '|';    // as necessary
    s = s.replace(")", "()").replace(">", "<>").replace("]", "[]").replace("}", "{}"); // replace compressed nilads with their uncompressed versions
    char[] c = s.toCharArray(), // from now on working on a char[] is more efficient since we will only be comparing and replacing
    r = new char[124]; // map open monad characters to their counterparts:
    r[40] = 41;   // '(' to ')'
    r[60] = 62;   // '<' to '>'
    r[91] = 93;   // '[' to ']'
    r['{'] = '}'; // '{' to '}'
    var o = ""; // we use this String as a kind of stack to keep track of the last open monad character we saw
    for(; ++i < c.length ;) { // iterate over the length of the expanded code
        if(c[i] == '|') { // if the current character is a close monad character
            c[i] = o.charAt(0); // replace it with the top of the stack
            o = o.substring(1); // and pop the stack
        }
        if("(<[{".indexOf(c[i]) > -1 // if the current character is an open monad/nilad character
         & ")>]}".indexOf(i+1 < c.length ? c[i+1] : 0) < 0) // and it's not part of a nilad (we need to test for length here to avoid overshooting)
            o = r[c[i]]+o; // using the mapping we established, push the corresponding character onto the stack
    }
    return c; // return the uncompressed code
}

Python 2, 188 184 180 177 174 173 bajtów

p,q='([{<',')]}>'
d,s,a=dict(zip(p,q)),[],''
for c in input():
 if c in d:a+=c;s+=[c]
 elif'|'==c:a+=d[s.pop()]
 else:a+=dict(zip(q,p))[c]+c
for c in s[::-1]:a+=d[c]
print a

Zaoszczędzono 4 bajty dzięki DJMcMayhem.
Wypróbuj online!

Python 3 , 122 bajty

D='()<>[]{} '
def f(x):
 a=s=''
 for c in x:i=D.find(c);a+=i<0and s[0]or D[i-(i&1):i+1];s=D[i+1][i&1:]+s[i<0:]
 return a+s

Wypróbuj online!

Haskell , 152 bajty

fst.p
m c="> < ] [)(} {"!!mod(fromEnum c-6)27
p(c:r)|elem c")]}>",(s,t)<-p r=(m c:c:s,t)|c/='|',(s,'|':t)<-p$r++"|",(u,v)<-p t=(c:s++m c:u,v)
p e=("",e)

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe . pimplementuje parser rekurencyjny, który może być zakończony zabijaniem dla prostej gramatyki.

Python 2 , 244 bajty

s=input()
B='([{<'
C=')]}>'
Z=zip(B,C)
P=sum(map(s.count,B))-s.count('|')
for i,j in Z:s=s.replace(j,i+j)
s+=P*'|'
b=[0]
for i in s:[b.pop()for j,k in Z if j==b[-1]<k==i];b+=[i][:i in B];s=i=='|'and s.replace(i,C[B.find(b.pop())],1)or s
print s

Wypróbuj online!

Uruchomienie tej funkcji zajęło mi ponad godzinę lub dwie ...