To pytanie jest pierwszym z kilku wyzwań związanych z urodzinami Brain-flak zaprojektowanych z okazji pierwszych urodzin Brain-Flak! Więcej informacji na temat urodzin Brain-Flaka można znaleźć tutaj
Zeszłego lata mieliśmy Brain-flak Integer Metagolf , a wygenerowane odpowiedzi były bardzo przydatne dla społeczności Brain-Flak. Najważniejszą rzeczą, która sprawia, że Integer Metagolf jest tak skuteczny, jest technika o nazwie hardcoding Multiplication.
W Brain-Flak zwielokrotnienie czasu wykonania jest niezwykle kosztowne. Najkrótszy znany fragment mnożenia to:
({}<>)({<({}[()])><>({})<>}{}<><{}>)
Odkryte przez Megatom
Istnieje jednak bardzo prosty sposób na pomnożenie czasu kompilacji. Na przykład następujący kod zostanie pomnożony przez 5:
(({})({})({})({}){})
Działa to, ponieważ kolejne wyrażenia są dodawane razem. Każdy z nich ({})
nic nie robi na stosie ( {}
wyskakuje i (..)
odsuwa go z powrotem) i ocenia wszystko, co znajduje się na stosie. Wszystkie te wyrażenia razem sumują się nawet pięciokrotnie, niezależnie od tego, co było na górze stosu.
Dla dowolnego n
następującego wyrażenia ciąg utworzy fragment, który zwielokrotni górę stosu przez n
:
"("+"({})"*(n-1)+"{})"
Działa to poprzez tworzenie n
wyrażeń, które wszystkie oceniają na górę stosu. Pierwszy n-1
nie zmienia niczego, a ostatni usuwa wierzch stosu przed pchnięciem.
W przypadku liczb zespolonych można połączyć wiele mniejszych wyrażeń, aby zaoszczędzić bajty. Na przykład możesz pomnożyć przez 25, mnożąc dwukrotnie przez 5:
(({})({})({})({}){})(({})({})({})({}){})
Jest to dość proste i dla niektórych liczb działa całkiem dobrze, ale istnieją lepsze sposoby na to. Na przykład jedna metoda, którą wymyśliłem, wykorzystuje binarną reprezentację liczby. ( Oto implementacja Pythona ) Ta nowa metoda jest o wiele bardziej skuteczna niż proste wyrażenie łańcuchowe pokazane wcześniej, ale to nie koniec, istnieje wiele interesujących sposobów mnożenia kodu i prawdopodobnie tona, której nikt jeszcze nie odkrył.
Myślę więc, że nadszedł czas, aby zobaczyć, jak dobrze możemy uzyskać.
Krótki przegląd Brain-Flak
Oto opis wszystkiego, co musisz wiedzieć o Brain-Flak do tego wyzwania.
Brain-Flak ma „nilady” i „monady”. Nilady to nawiasy, w których nie ma nic. Każdy nilad robi coś i zwraca wartość. W przypadku tego wyzwania dwie nilady, którymi się zajmujemy, to {}
i <>
. {}
wyskakuje u góry aktywnego stosu i zwraca jego wartość. <>
przełącza aktywny stos i aktywny stos, tak że aktywny stos staje się nieaktywny, a nieaktywny stos staje się aktywny, zwraca zero.
Monady są nawiasami, w których są rzeczy. Biorą jeden argument, sumę wszystkiego w sobie, czasami wykonują akcję, a następnie zwracają wartość. Te trzy, którymi się zajmujemy, to (...)
: <...>
i [...]
. Najważniejsza monada tego wyzwania (...)
przyjmuje wartość wnętrza i wypycha ją na aktywny stos. Następnie zwraca argument. <...>
i [...]
oba są „obojętnymi” monadami, tzn. nie wykonują żadnej akcji, a raczej modyfikują przekazywaną wartość. <...>
zawsze zwraca zero niezależnie od przekazanego argumentu. Tymczasem [...]
zawsze zwraca czasy argumentów -1
.
Przykładowe programy z wyjaśnieniem
Jeśli nigdy nie programowałeś w Brain-Flak, dobrym pomysłem może być zapoznanie się z przykładowymi programami przy użyciu opisanych operacji
({}{})
Dodaje to dwie najlepsze liczby ze stosu. Każdy {}
zrzuca wartość ze stosu i (...)
odsuwa swoją sumę z powrotem.
({}[{}])
Podobnie odejmuje to drugi element na stosie od pierwszego. Tak jak poprzednio, każda {}
wyskakuje wartość, ale [..]
około druga powoduje jej dodanie. Ponownie (...)
przesuwa sumę.
({}<{}>)
To usuwa drugą wartość ze stosu, pozostawiając najwyższą wartość nietkniętą. Działa tak jak dwa ostatnie, z tą różnicą, że druga wartość jest wyciszona przez, <...>
więc push wypycha tylko pierwszą wartość z powrotem.
(({}))
To tworzy drugą kopię wartości na górze stosu. Robi to, {}
podnosząc górną część stosu, aby uzyskać jego wartość, a (..)
następnie najpierw wypycha go z powrotem, oceniając do wartości. Drugi (...)
pobiera wartość zwróconą przez pierwszą i wypycha ją również na stos. tworzenie drugiej kopii.
Zadanie
Biorąc pod uwagę liczbę całkowitą, n
utwórz fragment kodu Brain-Flak, który czyści stos, który zwielokrotnia górę bieżącego stosu przez n
.
Możesz używać następujących operacji Brain-Flak
(...) -> Push Monad, Pushes the result of its contents
<...> -> Zero Monad, Returns zero
[...] -> Negative Monad, Returns the opposite of its contents result
{} -> Pop nilad, Pops the TOS and returns its value
<> -> Switch nilad, Switches the active and inactive stack
Inne operacje są zakazane na potrzeby wyzwania.
Punktacja
Twój wynik będzie sumą długości wszystkich programów od n=2
do n=10000
. Pamiętaj o dołączeniu linku do danych wyjściowych programu w celu weryfikacji.
źródło
[...]
, więc jest to początek.Odpowiedzi:
Ruby, 669856
To jest szybka odpowiedź wyjściowa. Znaleziono tutaj pierwsze 1000 min-programów . (Próbowałem opublikować wszystkie, ale to przeciążało maksymalny rozmiar pastebinu). Mogę dodać wyjaśnienie kodu później.
Przykłady:
źródło