Brain-flak to oparty na stosie język Turing-Tarpit, napisany wspólnie przeze mnie, DJMcMayhem i 1000000000 .

Niektórzy użytkownicy są bardzo doświadczeni w tajemniczych sposobach Brain-Flak. Pomyślałem więc, że dobrym pomysłem jest ustawienie tego pytania jako sposobu na to, abyśmy mogli - i mam nadzieję - także inni, podzielić się naszą wiedzą ze społecznością i obniżyć poprzeczkę wejścia do tego języka „zaprojektowanego tak, by był bolesny w użyciu”. A może nawet naucz tych z nas, którzy mają większe doświadczenie, nowych sztuczek.

Jakie masz wskazówki dotyczące gry w golfa? Szukam pomysłów, które można by zastosować do ogólnych problemów z golfem, które są przynajmniej w pewnym stopniu specyficzne dla uderzenia mózgu (np. „Usuń komentarze” nie jest odpowiedzią).

Proszę zamieścić jedną wskazówkę na odpowiedź.

Użyj trzeciego stosu

Jeśli przeczytałeś tytuł, możesz być nieco zdezorientowany. Z pewnością w Brain-Flak są tylko dwa stosy? Zapewniam cię jednak, że istnieje i jest jednym z najpotężniejszych, jeśli nie najpotężniejszym narzędziem do pisania i gry w golfa Brain-Flak.

Co to jest „trzeci stos”?

Każdy program Brain-Flak korzysta z trzeciego stosu w taki czy inny sposób, ale większość zastosowań odbywa się za kulisami i często przydatne jest po prostu zignorowanie faktu, że on istnieje. Każdy nawias w programie albo dodaje lub usuwa jeden element ze stosu. Trzy otwarte nawiasy klamrowe ([<dodają przedmiot do stosu, a )]>wszystkie trzy sprzężone usuwają przedmiot ze stosu. Wartość elementu na stosie jest wartością bieżącego zakresu programu i użycie niladów zmodyfikuje tę wartość w określony sposób. Nawias zamknięty )ma unikalną funkcję przenoszenia elementu z trzeciego stosu na bieżący stos; pchniecie.

Mam nadzieję, że stanie się to dla ciebie jasne. Trzeci stos to rodzaj stosu, który zapamiętuje zwrócone wartości kodu, który został już wykonany. Przejdźmy przez przykład prostego programu śledzącego dwa normalne stosy i trzeci stos.

Przykład

Przejdziemy przez następujący program. Ten program wypycha -3, 1, -2na stos.

(([()()()])(()))

Zaczynamy od trzech otwartych nawiasów klamrowych, z których wszystkie przesuwają zero na trzeci stos.

Nasze stosy wyglądają teraz tak, trzeci stos jest tym po prawej, a aktywny stos ma ^pod spodem:

        0
        0
  0  0  0
  ^

(([()()()])(()))
   ^

Teraz mamy trzy ()nilady. Nie powodują one żadnych zmian w stosunku do dwóch normalnych stosów, jednak każdy z nich dodaje jeden do góry trzeciego stosu, dzięki czemu nasze stosy wyglądają następująco:

        3
        0
  0  0  0
  ^

(([()()()])(()))
         ^

Teraz napotykamy, ]jak stwierdzono, zanim zamknięte nawiasy klamrowe usuwają element z Trzeciego Stosu, ale ]mają funkcję odejmowania elementu, który usuwa z wierzchu stosu. Tak więc nasze nowe stosy będą wyglądały następująco:

       -3
  0  0  0
  ^

(([()()()])(()))
          ^

To ma sens; [...]robi negację, więc ]należy odjąć w dół.

Teraz musimy wykonać ). Jak zapewne pamiętacie, )miejsce w programie, w którym rzeczy są wypychane na stos, więc będziemy przenosić górę Trzeciego Stosu na bieżący stos, dodatkowo dodamy -3następny element na trzecim stosie.

 -3  0 -3
  ^

(([()()()])(()))
           ^

Ponownie napotykamy jeden z naszych trzech otwartych nawiasów klamrowych, więc dodamy kolejny element do naszego Trzeciego Stosu.

        0
 -3  0 -3
  ^

(([()()()])(()))
            ^

Jak powiedzieliśmy wcześniej (), zwiększy górną część naszego trzeciego stosu o jeden.

        1
 -3  0 -3
  ^

(([()()()])(()))
              ^

I )przeniesie górę trzeciego stosu na aktywny stos i doda w dół

  1
 -3  0 -2
  ^

(([()()()])(()))
               ^

Ostatni )przenosi trzeci stos na aktywny stos, a ponieważ na trzecim stosie nie ma już żadnych elementów do dodania, nie robi nic więcej.

 -2
  1
 -3  0
  ^

(([()()()])(()))
                ^

Program się zakończył, więc kończymy i wysyłamy.

Ten przykład ma na celu dać ci wyobrażenie o tym, czym jest i co robi trzeci stos. Nie obejmuje wszystkich operacji, ale mam nadzieję, że możesz dowiedzieć się, co każda z nich robi sama. Jeśli nadal masz problemy, zamieściłem „ściągawkę” na dole tej odpowiedzi, aby Ci pomóc.

Ok, i co?

Ok, teraz rozumiesz trzeci stos, ale „co z tego”? Już go używałeś, nawet jeśli nie nazwałeś go „trzecim stosem”. W jaki sposób myślenie w kategoriach trzeciego stacka pomaga ci grać w golfa?

Spójrzmy na problem. Chcesz wziąć Trójkąt liczby . Jest to suma wszystkich liczb mniejszych niż n.

Jednym z podejść może być utworzenie akumulatora na offstacku i dodawanie go podczas odliczania. To tworzy kod, który wygląda następująco:

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

Wypróbuj online!

Ten kod jest dość kompaktowy i można by pomyśleć, że nie może być znacznie mniejszy. Jeśli jednak podchodzimy do niego z punktu widzenia trzeciego stosu, staje się jasne, że jest to rażąco nieefektywne. Zamiast kłaść nasz akumulator na stosie, możemy umieścić go na trzecim stosie za pomocą (i pobrać na końcu, którego używamy ). Ponownie przejdziemy przez wszystkie liczby, ale tym razem nie musimy nic robić, aby zwiększyć nasz Trzeci Stos, program robi to za nas. To wygląda jak:

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

Wypróbuj online

Ten kod jest mniej niż o połowę mniejszy od poprzedniej wersji gry w golfa. W rzeczywistości wyszukiwanie komputerowe wykazało, że ten program jest najkrótszym możliwym programem, który może wykonać to zadanie. Ten program można wyjaśnić za pomocą podejścia „suma wszystkich przebiegów”, ale myślę, że jest o wiele bardziej intuicyjny i przejrzysty, gdy wyjaśniono go przy użyciu podejścia trzeciego stosu.

Kiedy używam trzeciego stosu?

Idealnie, ilekroć zaczynasz pracę nad nowym problemem w Brain-Flak, powinieneś pomyśleć, jak bym to zrobił z myślą o trzecim stosie. Jednak jako ogólna zasada, ilekroć musisz śledzić jakiś rodzaj akumulatora lub mieć bieżącą sumę, dobrym pomysłem jest umieszczenie go na trzecim stosie zamiast dwóch prawdziwych stosów.

Innym razem dobrym pomysłem może być rozważenie użycia trzeciego stosu, gdy nie masz miejsca na przechowywanie wartości na dwóch pozostałych stosach. Może to być szczególnie przydatne, gdy wykonujesz manipulacje na dwóch istniejących stosach i chcesz zapisać wartość do późniejszego wykorzystania bez konieczności śledzenia jej położenia.

Ograniczenia trzeciego stosu

Trzeci stos jest bardzo mocny na wiele sposobów, ale ma swoje ograniczenia i wady.

Po pierwsze, maksymalna wysokość stosu dla trzeciego stosu w dowolnym punkcie jest określana w czasie kompilacji. Oznacza to, że jeśli chcesz użyć miejsca na stosie, musisz przydzielić to miejsce podczas pisania programu.

Po drugie, trzeci stos nie jest dostępem losowym. Oznacza to, że nie można wykonywać żadnych operacji na żadnej wartości poza najwyższą wartością. Ponadto nie możesz przenosić wartości na stosie (powiedz zamień pierwsze dwa elementy).

Wniosek

Trzeci stos to potężne narzędzie, które uważam za niezbędne dla każdego użytkownika Brain-Flak. Trzeba trochę przyzwyczaić się i wymaga zmiany sposobu myślenia o programowaniu w Brain-Flak, ale przy odpowiednim użyciu robi różnicę między przyzwoitym a niesamowitym, jeśli chodzi o golfa.

Ściągawka

Oto lista operacji i ich wpływu na trzeci stos

 Operation  |                 Action
====================================================
   (,[,<    | Put a zero on top of the Third Stack
----------------------------------------------------
     )      | Add the top of the Third Stack to the
            | second element and move it to the 
            | active stack
----------------------------------------------------
     ]      | Subtract the top of the Third Stack
            | from the second element and pop it
----------------------------------------------------
     >      | Pop the top of the Third Stack
----------------------------------------------------
     ()     | Add one to the top of the Third Stack
----------------------------------------------------
     {}     | Pop the top of the active stack and
            | add it to the top of the Third Stack
----------------------------------------------------
     []     | Add the stack height to the Third
            | Stack
----------------------------------------------------
   <>,{,}   | Nothing

Znalezienie modułu / reszty

Znalezienie n modulo m jest jedną z podstawowych operacji arytmetycznych, ważnych dla wielu wyzwań. W przypadkach m> 0 i n> = 0 można zastosować następujący 46-bajtowy fragment kodu. Zakłada, że n znajduje się na wierzchu aktywnego stosu, a m następny jest na dole, i zastępuje je n mod m . Pozostawia nienaruszone pozostałe stosy.

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

Ta wersja z adnotacjami pokazuje zawartość stosu w niektórych punktach programu. ;oddziela dwa stosy i .oznacza aktywny stos.

. n m;
({}(<>))<>
{   . m; r 0   (r = n - km)
    (({}))
    . m m; r 0
    {({}[()])<>}
    {}
}
m-n%m-1 m; . 0
{}<>([{}()]{})
. n%m;

Redundancja Push-Pop

Ten jest duży. Jest to również trochę bardziej dopracowane.

Chodzi o to, że jeśli popchniesz coś, a następnie przebijesz go bez robienia czegokolwiek, nie powinieneś go w ogóle popychać.

Na przykład, jeśli chcesz przenieść coś do offstacka, a następnie dodać jeden, możesz napisać następujący kod:

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

Może to być prostsze:

({}<>())

Pierwszy program podnosi przedmiot przenosi go, podnosi go ponownie i dodaje jeden, podczas gdy drugi robi oba za jednym zamachem.

Ten przykład był prosty, ale może stać się o wiele bardziej złożony. Weź na przykład:

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

Redukcja jest tutaj mniej wyraźna, ale 4. pop w programie można zmniejszyć za pomocą 2. wciśnięcia, tak:

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

Jest to najpotężniejsze narzędzie w moim repertuarze golfowym, ale potrzeba trochę praktyki, aby być w tym dobrym. Gdy już to robisz, będziesz w stanie je zauważyć niemal natychmiast.

Zoptymalizuj liczby całkowite

Liczby całkowite są uciążliwe do reprezentowania w Brain-Flak. Na szczęście mamy pytanie, które pomoże ci w golfa liczb całkowitych Brain-Flak . (Pamiętaj, że pytanie ma na celu wypchnięcie liczby całkowitej na stos, więc redundancja push-pop prawdopodobnie dotyczy bardziej realistycznych programów).

Wciśnij dodatkowe liczniki pętli

Często będziesz chciał zrobić coś takiego

Wykonaj operację X na każdym elemencie stosu

lub

Wykonaj operację X na każdej parze sąsiednich elementów na stosie

Gdy dane wejściowe mogą zawierać „0” lub wynik operacji X może dać 0, jest to naprawdę niewygodne. Ponieważ musisz zrobić:

([])
{

  {}

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

}

Aby wykonać X dla każdego elementu, a następnie

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

Aby ponownie odwrócić tablicę.

Co gorsza, jeśli operujemy parami sąsiednich elementów, musimy to zrobić ([][()])zamiast ([]). To jest naprawdę niewygodne. Oto sztuczka: gdy wykonujesz X dla każdego elementu, przesuń 1 na alternatywny stos tuż nad X(element). Następnie, podczas cofania, możesz po prostu to zrobić

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

Jest to 8 bajtów krótszych, więc jeśli weźmiesz pod uwagę dodatkowy kod do wypychania 1, w końcu zaoszczędzisz 4-6 bajtów. Aby uzyskać bardziej konkretny przykład, porównaj zadanie uzyskiwania delt tablicy. Bez tej sztuczki potrzebujesz:

([][()]){

    {}

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

    ([][()])

}{}{}<>

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

Za 62. Dzięki tej lewie będziesz miał

([][()]){

    {}

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

    ([][()])

}{}{}<>

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

Dla 58. Jeśli użyjesz go we właściwy sposób (na przykład najpierw ([][()])cofniesz i usuniesz dwa z późniejszego), może to zaoszczędzić jeszcze więcej w nietypowych sytuacjach.

Skorzystaj z niladu „Stack-Height”

Zwłaszcza w wyzwaniach złożoności Kołmogorowa lub wyzwaniach, w których zawsze znasz rozmiar danych wejściowych, możesz skorzystać z opcji nilad „Wysokość stosu”, []aby utworzyć liczby całkowite.

Przepracujmy to przy hipotetycznym wyzwaniu: wynik CAT. Nie golfowym sposobem jest użycie internetowego golfisty z liczbami całkowitymi do wypchnięcia 67, 65 i 84. Daje to:

(((((()()()()){}){}){}()){}())

(((((()()()()){}){}){}){}())

((((((()()()){}()){}){})){}{})

(Newlines dla jasności). To jest 88 bajtów i nie jest tak świetne. Jeśli zamiast tego naciskamy kolejne różnice między wartościami, możemy dużo zaoszczędzić. Więc zawijamy pierwszy numer w wywołaniu push i odejmujemy 2:

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

Następnie bierzemy ten kod, zawijamy go w wywołaniu push i dodajemy 19 na końcu:

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

To 62 bajty, co daje 26 bajtów golfa!

Teraz tutaj jest, gdy mamy do skorzystania z nilad stosu wysokości. Zanim zaczniemy pchać 19, wiemy, że na stosie są już 2 przedmioty, więc []oceniamy to 2. Możemy go użyć do utworzenia 19 w mniejszej liczbie bajtów. Oczywistym sposobem jest zmiana wewnętrznego ()()()na ()[]. To oszczędza tylko dwa bajty. Przy odrobinie majsterkowania okazuje się, że możemy popchnąć 19 za pomocą

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

To oszczędza nam 6 bajtów. Teraz jesteśmy na poziomie 56.

Możesz zobaczyć, jak ta wskazówka jest bardzo skutecznie wykorzystywana w tych odpowiedziach:

• Hello World V1

• Hello World V2

• Magic The Gathering, Friend or Foe

• Wyjście Brakująca liczba całkowita

• Diagonalny alfabet (mój ulubiony)

Użyj wiki

Mamy wiki ! Ma kilka niedociągnięć, ale jest pomocnym zasobem. Zawiera listy przydatnych, dobrze grających w golfa programów do czyszczenia stosów, które można wkleić do kodu. Jeśli chcesz zrobić coś, co według ciebie ktoś mógł zrobić, zanim istnieje duża szansa, jest to na wiki.

Lepsze zapętlenie

Oto łatwy:

Dość powszechnym konstruktem jest:

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

Gdzie chcesz zapętlić n razy, ale nadal zachować n. Można to jednak zapisać jako:

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

aby zapisać 2 bajty.

Innym dość powszechnym paradygmatem jest

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

Który zapętli i zgromadzi cały stos. Z powodu niektórych fantazyjnych matematyki jest to to samo, co:

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

Sprawdź swoje negatywy

Czasami możesz zagrać w golfa kilka bajtów, wybierając strategicznie to, co negować za pomocą [...]monady.

Prostym przykładem jest zagnieżdżony [...]s. Na przykład [()()()[()()]]może po prostu być[()()()]()()

Powiedz, że chcesz sprawdzić, czy wartość jest którymś z nawiasów początkowych (<{[. Pierwszą próbą jest przesunięcie różnicy między każdym znakiem i zapętleniem nad odjęcie go

({}<(((((       #Push the differences between start bracket characters
(((()()()()){}){}){})   #Push 32
[()])                   #Push 31
[((()()())()){}{}])     #Push 20
){})><>)                #Push 40
<>({<(([{}]<>{}))>(){[()](<{}>)}<>})

Możesz jednak zaoszczędzić 4 bajty, wypychając zamiast tego negatywne wersje różnic!

({}<(((((       #Push the differences between start bracket characters
((([()()()()]){}){}){}) #Push -32
())                     #Push -31
((()()())()){}{})       #Push -20
){})><>)                #Push -40
<>({<(({}<>{}))>(){[()](<{}>)}<>})

Zasadniczo nie oszczędza to zbyt wiele, ale także kosztuje niewiele wysiłku, aby zmienić [...]otoczenie. Uważaj na sytuacje, w których możesz przesunąć ujemną wartość licznika zamiast wartości dodatniej, aby zaoszczędzić na wielokrotnym zwiększaniu zamiast zmniejszać później. Lub zamiana (a[b])z, ([a]b)aby różnica między dwiema liczbami była ujemna zamiast dodatniej.