Liczby całkowite są uciążliwe do reprezentowania w Brain-Flak . Istnieje 8 operatorów:
() Evaluates to 1, but does not push anything on any stack
[] Evaluates to an indeterminate value for the purposes of this question
{} Removes the top of the stack and evaluates to it
<> Switches to or back from the alternate stack and evaluates to zero
(foo) Pushes the value of the expression foo to the stack and evaluates to it
[foo] Evaluates to the negation of foo
{foo} Evaluates the expression foo until the top of the stack is zero
<foo> Evaluates to zero but executes foo anyway
foo
może składać się z wielu operatorów, w którym to przypadku są one oceniane i sumowane. Na przykład (()())
wypycha 2
na stos (i ocenia 2
też).
Oczywiście ten (()...())
mechanizm nie jest użyteczny w Code Golf, ponieważ duże liczby zajmowałyby n*2+2
bajty. Wyzwaniem jest więc napisanie programu lub funkcji, która wyświetli jak najmniej bajtów programu Brain-Flak, który wypchnie daną liczbę całkowitą dodatnią n
do aktywnego stosu. Ten program nie może przyjmować żadnych założeń dotyczących istniejącej zawartości stosów, więc nie może pozostawiać stosów wymienianych ani dodawać ani usuwać dodatkowych wartości ze stosów.
Chociaż Twój program lub funkcja musi mieć możliwość zwrócenia działającego programu Brain-Flak dla wszystkich danych wejściowych od 1 do 1 000 000, zwycięzcą zostanie program lub funkcja, która generuje najmniejszy zestaw odpowiednich programów Brain-Flak dla wszystkich 1061 liczb pierwszych od 1000 do 10 000 . Powinieneś zanotować całkowity rozmiar twoich wyników dla tych 1061 danych wejściowych jako część twojego przesłania. Twój program lub funkcja może zaakceptować liczbę całkowitą i zwrócić (ciąg) program Brain-Flak w dowolnym akceptowalnym formacie We / Wy. Więzy zostaną zerwane przy użyciu rozmiaru programu lub funkcji.
źródło
2n
wynosi4^n catalan(n)
.(()()()...())
. Dodatkowo, jeśli użyjesz liczb pierwszych, może to spowodować pominięcie niektórych możliwych optymalizacji kompozytów.[]
zdefiniowane dla tego wyzwania? Dziwne jest dla mnie wdrożenie 7 z 8 operatorów. Tak czy inaczej, fajne wyzwanie, jestem zaszczycony, że ktoś napisze wyzwanie inspirowane moim własnym językiem![]
w swojej odpowiedzi.Odpowiedzi:
Python 2,
593945924458534584165839458250Ok, oto moje rozwiązanie.
Odpowiednią funkcją jest
push(n)
. Aby to nazwać, po prostu zadzwoń naciśnij liczbę całkowitą, którą chcesz reprezentować.Wyjaśnienie
Główną optymalizacją wykonaną przez program jest mnożenie na stałe. Pomysł zwielokrotnienia na stałe jest dość prosty. Naciskasz cyfrę, a następnie pop i pchasz ją, aby utworzyć nową wartość. Na przykład, aby pomnożyć przez dwa, możesz użyć następującego kodu,
((n){})
gdzie n kod tworzy określoną liczbę. To działa, ponieważ oba(n)
i{}
mają wartość n.Ten prosty pomysł można uczynić bardziej złożonym dla większych liczb. Weźmy na przykład 5, jakiś czas temu odkryto, że najlepszym sposobem pomnożenia przez pięć jest
(((n)){}){}{}
. Ten kod tworzy dwie kopie n mnożą jeden przez 4 i dodaje dwa. Stosując tę samą strategię, dokonuję każdego mnożenia na podstawie reprezentacji binarnej liczby. Nie będę wchodził w szczegóły, jak to działa w tej chwili, ale robię to, odcinając pierwszą reprezentację binarną i zastępując 0 przez){}
i 1 przez){}{}
. Następnie upewnia się, że n jest popychane odpowiednią liczbę razy i równoważy wszystkie nawiasy. (Jeśli chcesz wiedzieć, jak to zrobić, możesz spojrzeć na mój kod). Jeśli chcesz wiedzieć, dlaczego to działa, po prostu zapytaj mnie w komentarzu. Nie sądzę, aby ktokolwiek faktycznie czytał wszystkie aktualizacje mojego postu, więc pominąłem wyjaśnienie.Gdy algorytm próbuje znaleźć stały kod mnożenia, próbuje wszystkich liczb pierwszych czynników. Ignoruje czynniki złożone, ponieważ w pewnym momencie czynniki złożone można zawsze wyrazić bardziej zwięźle jako własne czynniki pierwsze, nie wiadomo, czy jest to nadal prawdą.
Innym mechanizmem zapisywania bajtów jest wielomianowa wyszukiwarka rozwiązań. Istnieją pewne formy wielomianów, które można łatwo przedstawić za pomocą pętli zmniejszających. Te wielomiany obejmują między innymi liczby wielokątne. Ta optymalizacja wyszukuje wielomiany pasujące do formy i tworzy kod, który je tworzy.
Wydajność
pojemnik na pastę
źródło
n
jest większa czy mniejsza niżn+1
if n % 3 == 2:
do końca tej funkcji o jeden poziom.Brain-Flak, 64664
Wypróbuj online!
Oto mój kod z adnotacjami
Wyjaśnienie
To implementuje tylko dwie reguły od teraz:
Jeśli n jest podzielne przez dwa znaki powrotu
(n/2){}
Jeśli n nie jest podzielne przez dwa znaki powrotu
n-1()
Koduje także wszystkie liczby mniejsze niż 6.
źródło
Perl,
592225915658460 znakówn()
(11322660 znaków)(n){}()
(64664 znaków)((n)){}{}
(63610 znaków)((n)()){}{}
(63484 znaków) - to nowatorskie obliczenie(n){({}[()])}{}
(60748 znaków)n[m]
(62800 znaków)(n){m({}[l])}{}
(58460 znaków) - to nowatorskie obliczenieWzór na ostatnie obliczenia to
n(n/l+1)/2+mn/l
. Próbowałem innych obliczeń, ale nie są one już pomocne dla danych wyjściowych. Program faktycznie generuje wszystkie wartości do 9999, ale następnie podaje podane liczby pierwsze i ich całkowitą długość.źródło
&try($i * $i, "$numbers[$i]{({})({}[()])}{}");
, co spada do 58032, gdy również dodam&try((3 * $i * $i - $i) / 2, "$numbers[$i]{({})({}[()])({})}{}");
(liczby kwadratowe / pięciokątne) - to stądPython,
5913658676 znakówFunkcja gry w numer Brainflak:
Iteracja liczb pierwszych:
Wydajność:
Pastebin
Wyjaśnienie:
Wstępnie wypełniamy listę R reprezentacji płata mózgowego, oceniając poszczególne liczby całkowite w zakresie większym niż konieczny [1, m -1], aby zdefiniować naszą funkcję f . Reprezentacje są tworzone przez przyjęcie najniższej nieużywanej reprezentacji (indeksowanej przez l ) i utworzenie z niej wielu nowych reprezentacji, zachowując tylko najkrótszą. Najniższa nieużywana reprezentacja zakłada, że wszystkim numerom od 1 do 1 przypisano reprezentację i że te reprezentacje zostały już wykorzystane do wytworzenia nowych liczb. Jeśli wartość mniejsza niż l ma krótszą reprezentację, musimy cofnąć się i odtworzyć liczby zaczynające się od tego punktu. Funkcja f tworzy program zapisujący numer na stosie przez dodanie nawiasu.
Na początku nie znałem żadnego Brainflaka i bardzo doceniam odpowiedź Eamona Olive'a za wskazanie wzoru na liczby trójkątów. Głównie uogólniłem podsumowanie i byłem nieustępliwy w sprawdzaniu sum i różnic. Dodanie wielu wielokrotności sum ma świetny efekt.
Dla tych, którzy są zainteresowani, oto kod zdrapki , w którym sprawdziłem, które formuły były tego warte.
Formuły reprezentacji:
(X){}
((X)){}{}
((((X)))){}{}{}{}
((((((X)))))){}{}{}{}{}{}
XY
X[Y]
(X){({}[Y])}{}
(X)({({}[Y])}{}){}
(X)(({({}[Y])}{})){}{}
(X)(({({}[Y])}{}){}){}
itd ...
źródło
Lua 5.3, 57522
Właściwie zacząłem nad tym pracować, kiedy pytanie zostało opublikowane, ale zapomniałem o tym aż do rocznicy Brain-Flak.
Podobny pomysł do innych odpowiedzi, w których znane-przydatne funkcje są używane do tworzenia większych liczb z dobrych reprezentacji liczb prostszych.
Jedną różnicą jest to, że zamiast rozwiązywać podproblemy w kategoriach mniejszych liczb, rozwiązuję podproblemy w kategoriach liczb o krótszych reprezentacjach. Myślę, że to sprawia, że bardziej elegancko jest korzystać z liczb ujemnych, a także zajmować się przypadkiem, w którym mniejsze liczby są reprezentowane przez większe liczby.
Ponadto próba znalezienia wszystkich liczb, które mogą być reprezentowane w określonym rozmiarze, a raczej próba przedstawienia konkretnej liczby tak krótko, jak to możliwe, w rzeczywistości upraszcza pewne obliczenia. Zamiast pracować z formułą w odwrotnej kolejności, aby sprawdzić, czy można ją zastosować do liczby, można ją przerobić do przodu i zastosować do każdej liczby.
Inna różnica polega na tym, że znane rozwiązania są przechowywane w dwóch częściach - (opcjonalnym) „przedrostku” i „sufiksie” (bardziej przypominającym przedrostek). Oczekuje się, że wycena prefiksu zostanie zignorowana podczas obliczania podanej liczby - prefiks zawiera tylko kod, który ustawia sufiks do uruchomienia (zazwyczaj przez wypchnięcie jednej lub więcej rzeczy na stos). Tak więc, biorąc pod uwagę prefiks i sufiks, odpowiednią liczbę można wypchnąć na stos za pomocą
prefix(suffix)
.Ten podział zasadniczo rozwiązuje ten sam problem, co
unpack
funkcja w odpowiedzi Kreatora pszenicy. Zamiast owijania kodu<...>
tylko w celu cofnięcia tego później, taki kod jest po prostu dodawany do prefiksu.W kilku przypadkach prefiks faktycznie jest oceniany (głównie dla operacji pseudoeksponentiacyjnej), więc jego wycena jest również przechowywana. Nie stanowi to jednak dużego problemu, ponieważ generator nie próbuje konstruować określonych liczb. Wydaje się teoretycznie sugerować, że mogą istnieć dwa fragmenty kodu o tej samej długości i generujące ten sam numer, który nie byłby zbędny w pamięci podręcznej z powodu różnych wycen prefiksów. Nie zawracałem sobie głowy rozliczaniem tego, ponieważ wydaje się, że nie ma to większego znaczenia (przynajmniej w tej dziedzinie).
Wyobrażam sobie, że łatwo byłoby zmniejszyć liczbę bajtów, dodając więcej przypadków, ale na razie mam dość.
Dobiegłem do 1000000, ale sprawdziłem tylko zdrowie psychiczne do 100000.
Pastebin produkcji na danych liczbach pierwszych.
źródło
k_limit
i cok_max_len
robisz? Nie jestem pewien, czy rozumiem nagłówek.k_max_len
. Równie łatwo mógł sprawdzić, czy znalazł wszystkie liczby, o które prosiłeś po przetworzeniu każdej długości, ale przydało mi się ograniczenie maksymalnej długości podczas testowania, aby program działał szybciej. (Przetwarzanie większych długości może być bardzo powolne.)k_limit
Jest zasadniczo parametrem wejściowym - wyświetli programy dla liczb do tego - zakładając, żek_max_len
było wystarczająco duże, aby je znaleźć.rubin, 60246 bajtów
Używam skrótu. Znajduję najlepszy golf dla danej liczby i używam mniejszych, aby znaleźć większe.
Hasła rekurencyjne to świetna zabawa!
źródło
Python, 64014 znaków
Przed tym wyzwaniem nie wiedziałem nic na temat ataku mózgowego i tylko trochę się nim bawiłem na tryitonline, więc mogłem zauważyć oczywiste skróty, których mi brakowało. Jest to dość nudne rozwiązanie, po prostu dzieli dane wejściowe na
x=x/2+x%2
lubx=x/3+x%3
, w zależności od tego, co jest krótsze.Nazwij to tak:
b(42)
wyjście na pastebin
źródło
Lua, 64664 bajtów
Program wypisuje całkowitą długość programów i program dla 203. liczby pierwszej (tam jest linia, którą możesz zmienić, aby zmienić, który jest drukowany, lub odkomentować linię, aby wydrukować wszystkie programy)
W tej chwili jedyną optymalizacją jest x = 2 * n + 1
Mam nadzieję, że będę miał czas, aby dodać więcej optymalizacji w celu obniżenia wyniku.
źródło