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:
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ę
(({}|<(()()()||{}|
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:
((}|<()))||}|
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
())))
(()()()())
([([}()||||(>||{(})|>|}{((<}|||>}|}>}
([([{}(())])](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}
({(}|(}[)|||}
({({})({}[()])}{})
(((()))||(](((}}||(}([(((}))||||(]((}}|}|}}|||]||]|[))||(}))|}(}|(}]]|}
((((()()()))([]((({}{}))({}([((({}()())))]([](({}{}){}){}{})))[]))[])[()()])({}()()){}({})({}[][]){}
źródło
Odpowiedzi:
Brain-Flak ,
952916818bajtówOszczędność 360 bajtów poprzez obliczenie przeciwnych nawiasów względnie zamiast od zera (np.
')'
='(' + 1
Zamiast(((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ługiZaoszczę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.
źródło
<>(<()>)
z(<>)
. Możesz także zmienić(<>{}<>)(<()>)
na(<(<>{}<>)>)
Retina 0.8.2 ,
10398 bajtówWypróbuj online! Link zawiera przypadki testowe. Edycja: Zapisano 5 bajtów z inspiracją @MartinEnder. Wyjaśnienie:
Umieść
;
po każdym zamkniętym nawiasie i zmień je wszystkie na otwarte nawiasy, a także zmień|
s na;
s.Policz liczbę niedopasowanych otwartych nawiasów i dodaj tyle
;
s.Skopiuj każdy otwierający wspornik do pasującego
;
.Odwróć skopiowane nawiasy i usuń
;
s.źródło
|
na coś podobnego!
. Nie byłoby nawet kosztować bajtów jeśli przełoży>-}
się<-{
(co moim zdaniem dajez
za|
).z
ale i tak wymyśliłem sposób na zgolenie jeszcze kilku bajtów.TIS ,
670666 bajtów-4 bajty do przeskakiwania do przodu i do tyłu
Kod:
Układ:
Wypróbuj online!
Wątpię, aby to było najmniejsze, ale nie widzę sposobu, aby go zmniejszyć. Niestety, wszystkie
NOP
s wydają się niezbędne do czasu, a ja nie mogę umieścić stos, gdzie@14
obecnie jest ze względu na odczyt zANY
w@11
.Struktura tego rozwiązania jest następująca:
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
@1
zacznie czytać z@2
zamiast strumienia wejściowego z@0
.@2
tworzy 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.
źródło
JavaScript (ES6), 107 bajtów
Pobiera dane wejściowe jako tablicę znaków. Zwraca ciąg.
Wypróbuj online!
źródło
Haskell,
127121 bajtówWypróbuj online!
Edytuj: -6 bajtów za pomocą funkcji @ Laikoni, aby znaleźć pasujący nawias .
źródło
Rubinowy , 104 bajty
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
To jest moje pierwsze rozwiązanie. Anonimowa funkcja lambda, która pobiera i zwraca łańcuchy.
Wypróbuj online!
źródło
Brain-Flak ,
606548 496 418 394390 bajtówWypró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:
I oczywiście...
Compressed Brain-Flak, 285 bajtów:
źródło
Java 10, 424 bajty
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:
źródło
Python 2,
188184180177174173 bajtówZaoszczędzono 4 bajty dzięki DJMcMayhem.
Wypróbuj online!
źródło
s
kończy się puste. W przeciwnym razie dodatkowe znaki znajdą się na niewłaściwym końcu.Python 3 , 122 bajty
Wypróbuj online!
źródło
Haskell , 152 bajty
Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .
p
implementuje parser rekurencyjny, który może być zakończony zabijaniem dla prostej gramatyki.źródło
m
aby znaleźć pasujący wspornik.Python 2 , 244 bajty
Wypróbuj online!
Uruchomienie tej funkcji zajęło mi ponad godzinę lub dwie ...
źródło