Napisz program do pieprzenia mózgu o długości nie większej niż 256 znaków, który wykonuje tyle kroków, ile to możliwe, ale nie zapętla się w nieskończoność. Program nie może przyjmować żadnych danych wejściowych.
Dokładniej:
- Załóż nieskończoną liczbę komórek po prawej stronie.
- A
<kiedy komórka po lewej stronie nic nie robi. -Gdy wartość komórki wynosi zero zestawy do komórek255.- Wszystkie instrukcje
+-<>.liczone są jako jeden krok po ich wykonaniu. - Gdy napotkasz a
[lub], liczy się to jako jeden krok. Jeśli jednak warunek jest spełniony, a przepływ sterowania przeskakuje, odpowiadający]lub[nie jest ponownie liczony jako krok. - Rozwiązanie, które wykonuje najwięcej kroków, wygrywa.
- Jeśli w twoim rozwiązaniu jest jakiś wzorzec, podanie funkcji określającej liczbę kroków podobnego programu długości
njest mile widziane, ale nie jest obowiązkowe. - Aby policzyć instrukcje, możesz użyć tego zmodyfikowanego interpretera :
Przykład:
++[-]
Napotkano instrukcje ++[-]-], a program działał przez 7 kroków.
code-challenge
brainfuck
busy-beaver
Anton Golov
źródło
źródło
floatlubdoubleprymitywne używane do ogólnych codziennych obliczeń. (W tym momencie komputer jest najczęściej tylko manipulowania ciągi, które reprezentują równania)Odpowiedzi:
Oto 41-znakowy program, który ostatecznie zatrzymuje się, pozostawiając więcej niż 10 ↑ (10 ↑ 28) ciągłych komórek ustawionych na 1 (więc liczba wykonanych instrukcji jest znacznie większa):
Jeśli się nie mylę, jest to poprawne tłumaczenie następującego programu w języku BF, który używa jednego bitu dla każdej komórki pamięci (tj. Zawartości komórki 0..1 zamiast 0..255, więc „+” działa po prostu odwracając wartość bitową):
Dokładna wartość (liczba sąsiadujących 1-bitów) wygenerowana przez ten ostatni program to
Powyższy program inicjuje i oblicza funkcję, która rośnie jak 2 ↑↑ x (w zapisie strzałki w górę Knutha ). Podobna konwersja programu BF wariantu, który inicjuje i oblicza funkcję rosnącą jak 2 ↑ 23 x, zapewnia następujący program składający się z 256 znaków:
co ostatecznie zatrzymuje się, pozostawiając więcej niż 2 ↑ 23 6 sąsiednich komórek ustawionych na 1 (więc liczba kroków jest znacznie większa).
NB-1 : 2 ↑ 23 6 jest „niewyobrażalnie dużą” liczbą; np. nawet 2 ↑ 4 6 = 2 ↑↑↑↑ 6 już przekracza pierwszy wyraz (3 ↑↑↑↑ 3) w sekwencji użytej do obliczenia liczby Grahama .
NB-2 : Myślę, że prawdopodobnie 256 znaków wystarcza, aby program BF zainicjował i obliczył funkcję o wyjściu znacznie większym niż liczba Grahama - jeśli znajdę czas, może spróbuję napisać jeden.
NB-3 : Jeśli ktoś jest zainteresowany pochodzeniem powyższych programów, oto niektóre zasoby programistyczne dla „Brainf * ck F” , z różnymi programami napisanymi w Pythonie. („Brainf * ck F” lub po prostu „F” to tak zwany kompletny wariant Turinga esolanguage Smallf * ck .) Właśnie przesłałem te pliki, które były nieaktywne od kilku lat, a na razie połączona strona internetowa to tylko „szafka na pliki” - szczegółowe informacje dotyczące powyższych programów można znaleźć w pliku Busy_Beavers.txt.
źródło
Oto ładny 39 postaci:
Zasadniczo tworzy 3-przestrzeniowy „sanie”, które porusza się w prawo i zmniejsza o jeden. Ukończono 31 919 535 558 instrukcji, przy czym wewnętrzna pętla wykonała 256 ^ 3 razy. Wciąż mam dużo miejsca, aby rozszerzyć to dość daleko w tempie 14 znaków do innego rzędu wielkości w stosunku do czasu działania.
Działa na dowolnym tłumaczu z niepowiązaną pamięcią lub z opakowaniem pamięci.
Zostawiam to ćwiczenie czytelnikowi, aby ustalić, kiedy zakończy się ulepszona wersja z 2 pętlami:
Teraz działa przez noc i ma ponad 3 miliony milionów kroków. Nadal nie przeszedł ani jednej iteracji zewnętrznej pętli. Zaledwie przeszedł przez 15% drugiej pętli.
źródło
Ten program działa w nieskończonej liczbie komórek. Początkowo dwie wartości są inicjalizowane wartościami ascii 255. Pierwsza wartość przy pierwszym obrocie głównej pętli jest podzielona na 255 komórek i są one inicjalizowane po 255 każda, przy drugim obrocie głównej pętli każda wartość w 255 komórkach ponownie się dzieli do 255 * 255 komórek, w ten sam sposób dla 255 obrotów głównej pętli całkowita zainicjowana liczba komórek będzie wynosić 255 ^ 255. Druga wartość określa, ile razy główna pętla ma być powtarzana.
źródło
Ten program jest prawie taki sam jak mój poprzedni program, różnica polega na tym, że wartość określająca pętlę zewnętrzną pozostaje stała w określonej komórce, dzięki czemu można zwiększyć zarówno liczbę zainicjowanych komórek, jak i całkowitą liczbę kroków na końcu programu
komórki zainicjowane na końcu programu 255 ^ 255
komórki zainicjowane na końcu programu 255 ^ 255 ^ 3
Następnie zmodyfikowałem go, aby działał jeszcze z większą liczbą kroków.
inicjuje 255 ^ 255 komórek podczas pierwszego obrotu głównej 255 ^ (255 ^ 255 * 255) komórek podczas drugiego obrotu głównej pętli 255 ^ {255 ^ (255 ^ 255 * 255) * 255} komórek podczas trzeciego obrotu głównej pętli w ten sposób pętla powtarza się 255 razy
źródło