Najszybsza mini-flak Quine

26

Mini-Flak jest podzbiorem Brain-Flak języku, gdzie <>, <...>i []operacje są niedozwolone. Ściśle mówiąc, nie może pasować do następującego wyrażenia regularnego:

.*(<|>|\[])

Mini-Flak jest najmniejszym znanym kompletnym podzbiorem Brain-Flak z Turinga.

Jakiś czas temu udało mi się stworzyć Quine w Mini-Flak , ale było zbyt wolno, by biegać przez całe życie wszechświata.

Zatem moim wyzwaniem jest szybsze wykonanie Quine.

Punktacja

Aby zdobyć kod, umieść @cyflagę na końcu kodu i uruchom go w interpreterie Ruby ( Wypróbuj online używa interpretera Ruby) za pomocą -dflagi. Twój wynik powinien zostać wydrukowany do STDERR w następujący sposób:

@cy <score>

Jest to liczba cykli, które program wykonuje przed zakończeniem i jest taka sama między uruchomieniami. Ponieważ każdy cykl zajmuje mniej więcej tyle samo czasu, twój wynik powinien być bezpośrednio skorelowany z czasem potrzebnym na uruchomienie programu.

Jeśli twój Quine jest zbyt długi, aby można go było rozsądnie uruchomić na komputerze, możesz ręcznie obliczyć liczbę cykli.

Obliczanie liczby cykli nie jest bardzo trudne. Liczba cykli odpowiada dwukrotności liczby uruchomionych monad plus liczby uruchomionych nilad. Jest to to samo, co zamiana każdego nilada na jeden znak i zliczanie łącznej liczby znaków.

Przykład punktacji

  • (()()()) zdobywa 5, ponieważ ma 1 monadę i 3 nilady.

  • (()()()){({}[()])} zdobywa 29 punktów, ponieważ pierwsza część jest taka sama jak poprzednio i zdobywa 5 punktów, podczas gdy pętla zawiera 6 monad i 2 nilady zdobywające 8. Pętla jest uruchamiana 3 razy, więc liczymy jej wynik 3 razy. 1*5 + 3*8 = 29

Wymagania

Twój program musi ...

  • Bądź co najmniej 2 bajty

  • Wydrukuj kod źródłowy, gdy zostanie wykonany w Brain-Flak przy użyciu -Aflagi

  • Nie pasuje do wyrażenia regularnego .*(<|>|\[])

Porady

  • Crane-Flak interpreter jest kategorycznie szybciej niż interpretera Ruby, ale brakuje niektórych funkcji. Poleciłbym najpierw przetestować kod za pomocą Crane-Flak, a następnie zdobyć go w interpreterie ruby, jeśli wiesz, że działa. Polecam również nie uruchamiać twojego programu w TIO. TIO jest nie tylko wolniejszy niż stacjonarny interpreter, ale także upłynie limit czasu za około minutę. Byłoby niezwykle imponujące, gdyby komuś udało się zdobyć wystarczająco niskie wyniki, aby uruchomić swój program, zanim upłynie limit czasu TIO.

  • [(...)]{}i (...)[{}]działają tak samo, <...>ale nie łamią wymagań ograniczonego źródła

  • Możesz sprawdzić Brain-Flak i Mini-Flak Quines, jeśli chcesz dowiedzieć się, jak podejść do tego wyzwania.

restricted-source  quine  fastest-code  brain-flak 
— Kreator pszenicy
źródło
1
„aktualny najlepszy” -> „tylko bieżący”
— HyperNeutrino

Odpowiedzi:

33

Mini-Flak, 6851113 cykli

Program (dosłownie)

Wiem, że większość ludzi nie spodziewa się, że quine Mini-Flak będzie używać znaków niedrukowalnych, a nawet znaków wielobajtowych (dzięki czemu kodowanie jest odpowiednie). Jednak ta quine tak, a nie drukowalne, w połączeniu z rozmiarem quine (93919 znaków zakodowanych jako 102646 bajtów UTF-8), utrudniają umieszczenie programu w tym poście.

Jednak program jest bardzo powtarzalny i jako taki kompresuje się naprawdę dobrze. Aby cały program był dostępny dosłownie z Stack Exchange, istnieje xxdodwracalny gzipzrzut heksowy skompresowanej wersji pełnej wersji quine ukrytej za składaną poniżej:

Pokaż fragment kodu

(Tak, jest tak powtarzalny, że można nawet zobaczyć powtórzenia po skompresowaniu).

Pytanie brzmi: „Poleciłbym również nie uruchamiać twojego programu w TIO. TIO jest nie tylko wolniejszy niż interpreter na pulpicie, ale także upłynie limit czasu za około minutę. Byłoby to niezwykle imponujące, gdyby komuś udało się zdobyć wystarczająco niskie wyniki, aby uruchomić ich program przed przekroczeniem limitu czasu TIO. ” Mogę to zrobić! Uruchomienie na TIO zajmuje około 20 sekund przy użyciu interpretera Ruby: Wypróbuj online!

Program (czytelnie)

Teraz podałem wersję programu, którą mogą czytać komputery, wypróbujmy wersję, którą ludzie mogą przeczytać. Przekształciłem bajty tworzące quine na stronę kodową 437 (jeśli mają ustawiony wysoki bit) lub obrazy kontrolne Unicode (jeśli są to kody sterujące ASCII), dodałem białe znaki (wszelkie istniejące wcześniej białe znaki zostały przekonwertowane na obrazy kontrolne ), zakodowane według długości przebiegu przy użyciu składni «string×length», a niektóre bity o dużej ilości danych pominęły:

␠
(((()()()()){}))
{{}
    (({})[(()()()())])
    (({})(
        {{}{}((()[()]))}{}
        (((((((({})){}){}{})){}{}){}){}())
        {
            ({}(
                (␀␀!S␠su! … many more comment characters … oq␝qoqoq)
                («()×35» («()×44» («()×44» («()×44» («()×44» («()×45»
                … much more data encoded the same way …
                («()×117»(«()×115»(«()×117»
                «000010101011┬â┬ … many more comment characters … ┬â0┬â┬à00␈␈
                )[({})(
                    ([({})]({}{}))
                    {
                        ((()[()]))
                    }{}
                    {
                        {
                            ({}(((({}())[()])))[{}()])
                        }{}
                        (({}))
                        ((()[()]))
                    }{}
                )]{}
                %Wwy$%Y%ywywy$wy$%%%WwyY%$$wy%$$%$%$%$%%wy%ywywy'×almost 241»
                ,444454545455┬ç┬ … many more comment characters … -a--┬ü␡┬ü-a␡┬ü
            )[{}()])
        }{}
        {}({}())
    )[{}])
    (({})(()()()()){})
}{}{}␊

(„Prawie 241” wynika z tego, że 241-sza kopia nie ma końca ', ale poza tym jest identyczna z pozostałą 240.)

Wyjaśnienie

O komentarzach

Pierwszą rzeczą do wyjaśnienia jest to, co jest z postaciami do drukowania i innymi śmieciami, które nie są poleceniami Mini-Flak? Może ci się wydawać, że dodawanie komentarzy do quine tylko utrudnia pracę, ale jest to konkurencja prędkości (a nie konkurencja wielkościowa), co oznacza, że ​​komentarze nie zaszkodzą szybkości programu. Tymczasem Brain-Flak, a tym samym Mini-Flak, po prostu zrzuca zawartość stosu na standardowe wyjście; gdybyś musiał upewnić się, że stos zawierał tylkopostaci, które składają się na polecenia twojego programu, będziesz musiał spędzić cykle czyszcząc stos. W tej chwili Brain-Flak ignoruje większość postaci, o ile upewnimy się, że elementy stosu śmieci nie są prawidłowymi poleceniami Brain-Flak (co czyni go poliglotą Brain-Flak / Mini-Flak) i nie są negatywne ani zewnętrzne w zakresie Unicode, możemy po prostu zostawić je na stosie, pozwolić im na wyjście i umieścić ten sam znak w naszym programie w tym samym miejscu, aby zachować właściwość quine.

Jest jeden szczególnie ważny sposób, w jaki możemy z tego skorzystać. Quine działa przy użyciu długiego ciągu danych, a zasadniczo całe wyjście z quinu jest wytwarzane przez formatowanie ciągu danych na różne sposoby. Jest tylko jeden ciąg danych, mimo że program ma wiele elementów; więc musimy być w stanie użyć tego samego ciągu danych do wydrukowania różnych części programu. Sztuczka „śmieciowe dane nie mają znaczenia” pozwala nam to zrobić w bardzo prosty sposób; przechowujemy znaki tworzące program w ciągu danych, dodając lub odejmując wartość do lub od kodu ASCII. W szczególności znaki składające się na początek programu są przechowywane jako kod ASCII + 4, znaki tworzą sekcję, która jest powtarzana prawie 241 razy jako kod ASCII - 4,każdy znak ciągu danych z przesunięciem; jeśli, na przykład, wydrukujemy go z 4 dodanymi do każdego kodu znakowego, otrzymamy jedno powtórzenie powtarzanej sekcji z kilkoma komentarzami przed i po. (Te komentarze to po prostu inne sekcje programu, z przesuniętymi kodami znaków, aby nie tworzyły żadnych prawidłowych poleceń Brain-Flak, ponieważ dodano nieprawidłowe przesunięcie. Musimy unikać poleceń Brain-Flak, a nie tylko Mini- Polecenia Flak, aby uniknąć naruszenia części pytania o ograniczonym źródle ; wybór przesunięć został zaprojektowany, aby to zapewnić.)

Z powodu tej sztuczki komentowania, w rzeczywistości musimy być w stanie wyprowadzić ciąg danych sformatowany na dwa różne sposoby: a) zakodowany w taki sam sposób jak w źródle, b) jako kody znaków z określonym przesunięciem dodanym do każdego kodu. To ogromne uproszczenie, które sprawia, że ​​dodatkowa długość jest tego warta.

Struktura programu

Ten program składa się z czterech części: wprowadzenie, ciąg danych, formatator ciągu danych i zakończenie. Intro i outro są w zasadzie odpowiedzialne za uruchamianie ciągu danych i jego formatyzatora w pętli, określając za każdym razem odpowiedni format (tj. Czy kodować czy offsetować i jakiego przesunięcia użyć). Ciąg danych jest tylko danymi i jest jedyną częścią quine, dla której znaki, które go tworzą, nie są dosłownie określone w ciągu danych (robienie tego byłoby oczywiście niemożliwe, ponieważ musiałoby być dłuższe niż on sam); jest więc napisany w sposób, który jest szczególnie łatwy do zregenerowania. Formatyzator ciągu danych składa się z 241 prawie identycznych części, z których każda formatuje określony układ odniesienia z 241 ciągu ciągu danych.

Każda część programu może być utworzona za pomocą ciągu danych i jego formatyzatora w następujący sposób:

  • Aby wygenerować wyjście, sformatuj ciąg danych z przesunięciem +8
  • Aby utworzyć formatyzator ciągu danych, sformatuj ciąg danych z przesunięciem +4, 241 razy
  • Aby utworzyć ciąg danych, sformatuj ciąg danych, kodując go do formatu źródłowego
  • Aby utworzyć wprowadzenie, sformatuj ciąg danych z przesunięciem -4

Wystarczy więc spojrzeć na działanie tych części programu.

Ciąg danych

(«()×35» («()×44» («()×44» («()×44» («()×44» («()×45» …

Potrzebujemy prostego kodowania ciągu danych, ponieważ musimy być w stanie odwrócić kodowanie w kodzie Mini-Flak. Nie możesz stać się o wiele prostszy!

Kluczową ideą tej quine (oprócz sztuczki komentowania) jest zauważenie, że w zasadzie jest tylko jedno miejsce, w którym możemy przechowywać duże ilości danych: „sumy wartości zwracanych poleceń” w różnych poziomach zagnieżdżania źródła programu. (Jest to powszechnie znane jako trzeci stos, chociaż Mini-Flak nie ma drugiego stosu, więc „stos roboczy” jest prawdopodobnie lepszą nazwą w kontekście Mini-Flak.) Inne możliwości przechowywania danych to główny / pierwszy stos (który nie działa ponieważ tam właśnie musi iść nasz wynik i nie możemy przenieść wyjścia poza magazyn w zdalnie efektywny sposób) i zakodowane w bignum w jednym elemencie stosu (co jest nieodpowiednie dla tego problemu, ponieważ zajmuje to wykładniczy czas wyodrębnij z niego dane); gdy je wyeliminujesz, działający stos będzie jedyną pozostałą lokalizacją.

Aby „przechowywać” dane na tym stosie, używamy niezbalansowanych poleceń (w tym przypadku pierwszej połowy (…)polecenia), które zostaną później zrównoważone w formatorze ciągu danych. Za każdym razem, gdy zamkniemy jedno z tych poleceń w formatyzatorze, przesunie on sumę danych pobranych z ciągu danych i zwróci wartości wszystkich poleceń na tym poziomie zagnieżdżenia w formatyzatorze; możemy zapewnić, że ta ostatnia doda zero, więc formatyzator po prostu widzi pojedyncze wartości pobrane z ciągu danych.

Format jest bardzo prosty: (po nim następuje n kopii (), gdzie n to liczba, którą chcemy zapisać. (Uwaga: oznacza to, że możemy przechowywać tylko liczby nieujemne, a ostatni element ciągu danych musi być dodatni.)

Nieco intuicyjny punkt dotyczący ciągu danych to kolejność, w jakiej się znajduje. „Początek” ciągu danych to koniec bliżej początku programu, tj. Najbardziej zewnętrzny poziom zagnieżdżenia; ta część jest formatowana jako ostatnia (ponieważ formater działa od najbardziej wewnętrznego do najbardziej zewnętrznego poziomu zagnieżdżenia). Jednak pomimo sformatowania jako ostatniego, drukowane jest ono jako pierwsze, ponieważ wartości wypychane najpierw na stos są drukowane jako ostatnie przez interpreter Mini-Flak. Ta sama zasada dotyczy całego programu; najpierw musimy sformatować outro, potem formatator ciągu danych, potem ciąg danych, potem wprowadzenie, tj. odwrotność kolejności, w jakiej są przechowywane w programie.

Formater string danych

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

Formatator ciągu danych składa się z 241 sekcji, z których każda ma identyczny kod (jedna sekcja ma nieznacznie inny komentarz), z których każda formatuje jeden określony znak ciągu danych. (Nie mogliśmy tutaj użyć pętli: potrzebujemy niezrównoważenia, )aby odczytać ciąg danych poprzez dopasowanie jego niezrównoważonego (i nie możemy umieścić jednego z nich w {…}pętli, jedynej istniejącej formie pętli. Zamiast tego „ rozwiń „formatyzator i po prostu uzyskaj wprowadzenie / wyjście, aby wyprowadzić ciąg danych z przesunięciem formatyzatora 241 razy.)

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

Najbardziej zewnętrzna część elementu formatującego odczytuje jeden element ciągu danych; prostota kodowania ciągu danych prowadzi do niewielkiej złożoności jego odczytu. Zaczynamy od zamknięcia niedopasowanego (…)ciągu danych, a następnie negujemy ( […]) dwie wartości: dane, które właśnie odczytaliśmy z ciągu danych ( ({})) i wartość zwracaną przez resztę programu. Kopiujemy wartość zwrotną reszty elementu formattera za pomocą (…)i dodajemy kopię do negowanej wersji za pomocą {}. Ostateczny wynik jest taki, że zwracana wartość elementu ciągu danych i elementu formatującego razem to układ odniesienia minus układ odniesienia minus wartość zwrotu plus wartość zwrotu lub 0; jest to konieczne, aby kolejny element ciągu danych wygenerował poprawną wartość.

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

Formatyzator używa elementu najwyższego stosu, aby dowiedzieć się, w jakim trybie jest (0 = format w formatowaniu ciągu danych, każda inna wartość = przesunięcie wyjściowe z). Jednak po odczytaniu ciągu danych układ odniesienia znajduje się nad formatem na stosie, a my chcemy je odwrócić. Ten kod jest krótszą odmianą kodu wymiany Brain-Flak, przyjmując wartość powyżej b do b powyżej a  +  b ; jest nie tylko krótszy, ale także (w tym konkretnym przypadku) bardziej użyteczny, ponieważ efekt uboczny dodania b do a nie jest problematyczny, gdy b wynosi 0, a gdy b nie jest 0, wykonuje dla nas obliczenie przesunięcia.

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

Brain-Flak ma tylko jedną strukturę sterowania przepływem, więc jeśli chcemy czegoś innego niż whilepętla, zajmie to trochę pracy. Jest to struktura „negująca”; jeśli na stosie znajduje się 0, usuwa go, w przeciwnym razie umieszcza 0 na stosie. (Działa to po prostu: tak długo, jak na stosie nie ma 0, pchnij 1 - 1 do stosu dwa razy; kiedy skończysz, pop element górnego stosu.)

Możliwe jest umieszczenie kodu w strukturze negacji, jak pokazano tutaj. Kod będzie działał tylko wtedy, gdy górna część stosu była niezerowa; więc jeśli mamy dwie struktury negować, przyjmując wierzchołek stosu dwa elementy nie są zarówno zero, będą one znoszą się nawzajem, ale każdy kod wewnątrz pierwszej struktury będzie działać tylko wtedy, gdy element górny stos było niezerowe, a wewnątrz kodu druga struktura będzie działać tylko wtedy, gdy element najwyższego stosu miał wartość zero. Innymi słowy, jest to odpowiednik instrukcji if-then-else.

W klauzuli „then”, która działa, jeśli format jest niezerowy, w rzeczywistości nie mamy nic do roboty; chcemy przesunąć dane + przesunięcie do głównego stosu (aby można go było wyprowadzić na końcu programu), ale już tam jest. Mamy więc do czynienia tylko z przypadkiem kodowania elementu ciągu danych w postaci źródłowej.

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

Oto jak to robimy. {({}( … )[{}()])}{}Struktura powinny być znane jako pętla z numerem konkretnej iteracji (który działa przesuwając licznik pętli do stosu pracy i trzymając go tam, to będzie bezpieczne od innych kodów, ponieważ dostęp do stosu pracy jest związana z poziom zagnieżdżenia programu). Ciało pętli ((({}())[()]))tworzy trzy kopie elementu z górnego stosu i dodaje 1 do najniższego. Innymi słowy, przekształca 40 na szczycie stosu w 40 powyżej 40 powyżej 41, lub postrzegane jako ASCII, (w ((); wielokrotne wykonywanie tego (przekształca (()się (()()w (()()()i tak dalej, a zatem jest to prosty sposób na wygenerowanie naszego ciągu danych (zakładając, że (stos jest już na szczycie stosu).

Gdy skończymy z pętlą, (({}))duplikuje górę stosu (tak, że teraz się zaczyna, ((()…a nie (()…. Wiodąca (kolejka użyje następnej kopii formatera łańcucha danych w celu sformatowania następnego znaku (rozwinie go w (()(()…następnie (()()(()…itd., więc generuje to separację (w ciągu danych).

%Wwy$%Y%ywywy$wy$%%%WwyY%$$wy%$$%$%$%$%%wy%ywywy'

Ostatnie zainteresowanie budzi formatowanie ciągów danych. OK, więc przeważnie jest to tylko przesunięcie o 4 punkty kodowe w dół; jednak apostrof na końcu może wydawać się nie na miejscu. '(codepoint 39) zmieni się na +(codepoint 43), co nie jest poleceniem Brain-Flak, więc być może zgadłeś, że jest tam w innym celu.

Powodem tego jest to, że formatyzator ciągu danych oczekuje, że już (na stosie jest już znak (nie zawiera dosłownie 40). The'znajduje się na początku bloku, który jest powtarzany w celu utworzenia formatera łańcucha danych, a nie na końcu, więc po tym, jak znaki formatera łańcucha danych zostały wypchnięte na stos (i kod ma zamiar przejść do drukowania łańcucha danych sam), outro dopasowuje 39 na górze stosu do 40, gotowych dla formatyzatora (tym razem uruchomionego formatyzatora, a nie jego reprezentacji w źródle), aby z niego skorzystać. Dlatego mamy „prawie 241” kopii formatera; w pierwszej kopii brakuje pierwszego znaku. I ten znak, apostrof, jest jednym z trzech znaków w ciągu danych, które nie odpowiadają kodowi Mini-Flak gdzieś w programie; jest tam wyłącznie jako metoda zapewnienia stałej.

Wprowadzenie i zakończenie

(((()()()()){}))
{{}
    (({})[(()()()())])
    (({})(
        {{}{}((()[()]))}{}
        (((((((({})){}){}{})){}{}){}){}())
        {
            ({}(
                (␀␀!S␠su! … many more comment characters … oq␝qoqoq)
                …
            )[{}()])
        }{}
        {}({}())
    )[{}])
    (({})(()()()()){})
}{}{}␊

Wstęp i zakończenie są koncepcyjnie tą samą częścią programu; Jedynym powodem, dla którego wyróżniamy to, jest to, że wyjście musi być wyprowadzone przed łańcuchem danych i jego formatyzatorem (aby drukował po nich), podczas gdy intro musi być wyprowadzane po nich (drukowanie przed nimi).

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

Zaczynamy od umieszczenia dwóch kopii 8 na stosie. Jest to przesunięcie dla pierwszej iteracji. Druga kopia jest spowodowana tym, że główna pętla oczekuje, że na stosie powyżej przesunięcia będzie znajdował się element śmieci, pozostawiony po teście, który decyduje o tym, czy istnieje pętla główna, dlatego musimy umieścić tam element śmieci, aby nie wyrzuca elementu, którego tak naprawdę chcemy; kopia jest najkrótszym (a więc najszybszym wyjściem) sposobem na zrobienie tego.

Istnieją inne przedstawienia liczby 8, które nie są już dłuższe niż ten. Jednak przy wybieraniu najszybszego kodu jest to zdecydowanie najlepsza opcja. Po pierwsze, użycie ()()()()jest szybsze niż, powiedzmy, (()()){}ponieważ pomimo tego, że oba mają długość 8 znaków, pierwszy jest szybszy o jeden cykl, ponieważ (…)jest liczony jako 2 cykle, ale ()tylko jako jeden. Zapisanie jednego cyklu jest jednak pomijalne w porównaniu do znacznie większej uwagi na quine : (i )mają znacznie niższe punkty kodowe niż {i }, więc wygenerowanie dla nich fragmentu danych będzie znacznie szybsze (a fragment danych zajmie mniej miejsca w kodzie, zbyt).

{{} … }{}{}

Główna pętla. To nie liczy iteracji (jest to whilepętla, a nie forpętla i używa testu, aby się wyłamać). Po wyjściu odrzucamy dwa górne elementy stosu; górny element jest nieszkodliwym 0, ale elementem poniżej będzie „format do użycia przy następnej iteracji”, który (będący ujemnym przesunięciem) jest liczbą ujemną, a jeśli na stosie są jakieś liczby ujemne, gdy Mini -Flak kończy działanie, interpreter zawiesza się, próbując je wyprowadzić.

Ponieważ ta pętla używa jawnego testu do wybicia, wynik tego testu zostanie pozostawiony na stosie, więc odrzucamy go jako pierwszą czynność (jego wartość nie jest przydatna).

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

Ten kod popycha 4 i f  - 4 powyżej elementu stosu f , pozostawiając ten element na miejscu. Format z wyprzedzeniem obliczamy format następnej iteracji (podczas gdy mamy stałą wartość 4) i jednocześnie ustawiamy stos w odpowiedniej kolejności dla kilku kolejnych części programu: będziemy używać f jako formatu dla ta iteracja i 4 są potrzebne wcześniej.

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

Zapisuje to kopię f  - 4 na stosie roboczym, dzięki czemu możemy go użyć do następnej iteracji. (Wartość f nadal będzie w tym momencie obecna, ale będzie w niezręcznym miejscu na stosie, a nawet gdybyśmy mogli manewrować nią w odpowiednie miejsce, musielibyśmy spędzić cykle odejmując od niej 4, i wykonuje cykl drukowania kodu, aby wykonać to odejmowanie. O wiele łatwiej po prostu zapisać go teraz.)

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

Test sprawdzający, czy przesunięcie wynosi 4 (tzn. F  - 4 wynosi 0). Jeśli tak, drukujemy formatyzator ciągu danych, więc musimy uruchomić ciąg danych i jego formator 241 razy, a nie tylko raz z tym przesunięciem. Kod jest dość prosty: jeśli f  -4 jest niezerowe, zamień f  -4 i samą 4 na parę zer; w obu przypadkach pop element górnego stosu. Na stosie mamy teraz liczbę powyżej f , 4 (jeśli chcemy wydrukować tę iterację 241 razy) lub 0 (jeśli chcemy wydrukować ją tylko raz).

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

Jest to interesujący rodzaj stałej Brain-Flak / Mini-Flak; długa linia tutaj reprezentuje liczbę 60. Możesz być zdezorientowany brakiem (), które zwykle są wszędzie w stałych Brain-Flak; nie jest to zwykła liczba, ale liczba kościelna, która interpretuje liczby jako operację powielania. Na przykład, widziana tutaj cyfra Kościoła dla 60, tworzy 60 kopii danych wejściowych i łączy je wszystkie w jedną wartość; w Brain-Flak jedyne, co możemy połączyć, to zwykłe liczby, przez dodanie, więc w rezultacie dodajemy 60 kopii góry stosu, a tym samym mnożąc górę stosu przez 60.

Na marginesie możesz użyć wyszukiwarki liczb niedociążonych , która generuje cyfry kościelne w składni niedociążenia, aby znaleźć odpowiednią liczbę również w Mini-Flak. Liczby niedociążone (inne niż zero) używają operacji „zduplikuj górny element stosu” :i „połącz dwa górne elementy stosu” *; obie te operacje występują w Brain-Flak, tak po prostu przełożyć :do ), *do {}, przedrostek {}i dodać tyle (na początek równowagi (ten stosuje dziwną mieszankę głównego stosu i stosu pracy, ale działa).

Ten konkretny fragment kodu używa kościelnej cyfry 60 (w rzeczywistości fragmentu „pomnóż przez 60”), wraz z przyrostem, do wygenerowania wyrażenia 60 x  + 1. Więc jeśli mielibyśmy 4 z poprzedniego kroku, to daje nam wartość z 241, lub jeśli mieliśmy 0, otrzymujemy po prostu wartość 1, tj. to poprawnie oblicza liczbę potrzebnych iteracji.

Wybór 241 nie jest przypadkowy; wybrano wartość a) w przybliżeniu długość, przy której program i tak skończyłby, oraz b) 1 więcej niż 4 razy zaokrąglona liczba. Okrągłe liczby, w tym przypadku 60, mają zwykle krótsze reprezentacje jako liczby kościelne, ponieważ masz większą elastyczność w kopiowaniu czynników. Program zawiera później dopełnienie, aby dokładnie zwiększyć długość do 241.

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

Jest to pętla for, jak poprzednio, która po prostu uruchamia w niej kod kilka razy równy górnej części głównego stosu (który zużywa; sam licznik pętli jest przechowywany na stosie roboczym, ale widoczność jest to powiązane z poziomem zagnieżdżenia programu, a zatem nie jest możliwe, aby cokolwiek innego niż sama pętla for mogła z nim współdziałać). To faktycznie uruchamia łańcuch danych i jego formatyzator 1 lub 241 razy, a ponieważ podaliśmy teraz wszystkie wartości, których używaliśmy do naszych obliczeń przepływu sterującego z głównego stosu, mamy format do użycia na nim, gotowy do formatyzator do użycia.

(␀␀!S␠su! … many more comment characters … oq␝qoqoq)

Komentarz tutaj nie jest całkowicie pozbawiony zainteresowania. Po pierwsze, istnieje kilka poleceń Brain-Flak; )na końcu jest naturalnie generowane jako efekt uboczny sposobu przejścia między poszczególnymi segmentami pracy programu, a więc (na początku było ręcznie dodać do niego wagi (i mimo długości komentarza wewnątrz, kładąc komentarz wnętrze ()komenda jest jeszcze ()komenda, więc wszystko robi jest dodać 1 do wartości zwracanej ciągu danych i jej formater, coś co dla pętli całkowicie ignoruje).

Co ważniejsze, te znaki NUL na początku komentarza wyraźnie nie są niczym przesunięte (nawet różnica między +8 a -4 nie wystarcza, aby zamienić a (w NUL). Są to czyste dopełnienia, dzięki którym 239-elementowy ciąg danych może zawierać maksymalnie 241 elementów (które łatwo się opłacają: wygenerowanie 1 vs. 239 zamiast 1 vs. 241 przy obliczaniu liczby wymaganych iteracji wymagałoby znacznie więcej niż dwóch bajtów ). Jako znak wypełniający zastosowano NUL, ponieważ ma on najniższy możliwy punkt kodowy (co powoduje, że kod źródłowy ciągu danych jest krótszy, a zatem szybszy do wydrukowania).

{}({}())

Upuść element najwyższego stosu (format, którego używamy), dodaj 1 do następnego (ostatni znak, który ma zostać wydrukowany, tj. Pierwszy znak do wydrukowania, z właśnie sformatowanej sekcji programu). Nie potrzebujemy już starego formatu (nowy format ukrywa się na stosie roboczym); a przyrost jest w większości przypadków nieszkodliwy i zmienia 'na jednym końcu źródłową reprezentację formatyzatora łańcucha danych na ((wymagany na stosie przy następnym uruchomieniu formatyzatora, aby sformatować sam łańcuch danych). Potrzebujemy takiego przekształcenia w outro lub intra, bo zmusza każdy ciąg danych formatyzatora elementu zacząć (stałaby się nieco bardziej skomplikowana (jak musielibyśmy zamknąć (, a następnie cofnąć swoje działanie później), imusielibyśmy (gdzieś wygenerować dodatkową, ponieważ mamy tylko prawie 241 kopii formatera, a nie wszystkie 241 (więc najlepiej, aby taki nieszkodliwy znak 'był tym, którego brakuje).

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

Na koniec test wyjścia z pętli. Obecny szczyt głównego stosu to format, którego potrzebujemy do następnej iteracji (która właśnie wróciła ze stosu roboczego). Spowoduje to skopiowanie go i dodanie 8 do kopii; wynikowa wartość zostanie odrzucona następnym razem w pętli. Jeśli jednak właśnie wydrukowaliśmy wprowadzenie, przesunięcie wynosi -4, więc przesunięcie dla „następnej iteracji” będzie wynosić -8; -8 + 8 wynosi 0, więc pętla zakończy się, a nie będzie kontynuowana na iteracji.

— Konto tymczasowe ais523
źródło
16

128.673.515 cykli

Wypróbuj online

Wyjaśnienie

Powodem, dla którego quiny Miniflak są powolne, jest brak losowego dostępu Miniflak. Aby obejść ten problem, tworzę blok kodu, który przyjmuje liczbę i zwraca dane. Każdy układ odniesienia reprezentuje pojedynczy znak, jak poprzednio, a główny kod po prostu odpytuje ten blok dla każdego z nich na raz. Zasadniczo działa to jako blok pamięci o dostępie swobodnym.

Ten blok kodu ma dwa wymagania.

  • Musi przyjąć liczbę i wypisać tylko kod znaku dla tego znaku

  • Odtworzenie tabeli odnośników w Brain-Flak musi być łatwe

Aby skonstruować ten blok, faktycznie użyłem metody z mojego dowodu, że Miniflak jest ukończony w Turingu. Dla każdego układu odniesienia istnieje blok kodu, który wygląda następująco:

(({}[()])[(())]()){(([({}{})]{}))}{}{(([({}{}(%s))]{}))}{}

Odejmuje to jeden od liczby na górze stosu, a jeśli zero popycha %sukład odniesienia pod nim. Ponieważ każdy kawałek zmniejsza rozmiar o jeden, jeśli zaczniesz od n na stosie, otrzymasz n-te dane odniesienia.

Jest to ładne i modułowe, więc może być łatwo napisane przez program.

Następnie musimy skonfigurować maszynę, która faktycznie tłumaczy tę pamięć na źródło. Składa się z 3 części jako takich:

(([()]())())
{({}[(
  -Look up table-
 )]{})
 1. (({}[()])[(())]()){(([({}{})]{}))}{}{([({}{}(([{}]))(()()()()()))]{})}{}

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

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

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

Maszyna składa się z czterech części, które są uruchamiane w kolejności, zaczynając od 1, a kończąc na 3. Oznacziłem je w powyższym kodzie. Każda sekcja używa również tego samego formatu tabeli odnośników, którego używam do kodowania. Wynika to z faktu, że cały program jest zawarty w pętli i nie chcemy uruchamiać każdej sekcji za każdym razem, gdy przechodzimy przez pętlę, dlatego umieszczamy tę samą strukturę RA i za każdym razem sprawdzamy żądaną sekcję.

1

Sekcja 1 to prosta sekcja konfiguracji.

Program informuje pierwsze zapytania o sekcji 1 i układzie odniesienia 0. Układ odniesienia 0 nie istnieje, więc zamiast zwracać tę wartość, po prostu zmniejsza zapytanie raz dla każdego układu odniesienia. Jest to przydatne, ponieważ możemy wykorzystać wynik do ustalenia liczby danych, które staną się ważne w przyszłych sekcjach. Sekcja 1 rejestruje liczbę danych, negując wynik i odpytuje Sekcja 2 i ostatni układ odniesienia. Jedynym problemem jest to, że nie możemy bezpośrednio wysłać zapytania do sekcji 2. Ponieważ pozostało jeszcze jedno zmniejszenie, musimy wykonać zapytanie do nieistniejącej sekcji 5. W rzeczywistości będzie to miało miejsce za każdym razem, gdy przeszukamy sekcję w innej sekcji. Zignoruję to w moim objaśnieniu, jednak jeśli szukasz kodu, pamiętaj, że 5 oznacza powrót do sekcji, a 4 oznacza ponowne uruchomienie tej samej sekcji.

2)

Sekcja 2 dekoduje dane na znaki, które składają się na kod po bloku danych. Za każdym razem oczekuje, że stos będzie wyglądał następująco:

Previous query
Result of query
Number of data
Junk we shouldn't touch...

Mapuje każdy możliwy wynik (liczbę od 1 do 6) na jedną z sześciu prawidłowych postaci Miniflak ( (){}[]) i umieszcza go poniżej liczby danych za pomocą „Śmieci, których nie powinniśmy dotykać”. To daje nam stos takich jak:

Previous query
Number of data
Junk we shouldn't touch...

Odtąd musimy albo zapytać o kolejny układ odniesienia, albo jeśli przesłuchaliśmy je wszystkie, przejdź do sekcji 3. Poprzednie zapytanie nie jest właściwie wysłanym zapytaniem, lecz zapytaniem pomniejszonym o liczbę danych w bloku. Wynika to z faktu, że każdy punkt odniesienia zmniejsza zapytanie o jeden, więc zapytanie jest dość zniekształcone. Aby wygenerować następne zapytanie, dodajemy kopię liczby danych i odejmujemy jeden. Teraz nasz stos wygląda następująco:

Next query
Number of data
Junk we shouldn't touch...

Jeśli nasze następne zapytanie jest równe zero, przeczytaliśmy całą pamięć potrzebną w sekcji 3, więc ponownie dodajemy liczbę danych do zapytania i uderzamy 4 na górze stosu, aby przejść do sekcji 3. Jeśli następne zapytanie nie jest zerowe, połóż 5 na stosie, aby ponownie uruchomić sekcję 2.

3)

Sekcja 3 tworzy blok danych, przeszukując naszą pamięć RAM, podobnie jak sekcja 3.

Ze względu na zwięzłość pominę większość szczegółów dotyczących działania części 3. Jest prawie identyczny jak w sekcji 2, z tym wyjątkiem, że zamiast tłumaczyć każdy układ odniesienia na jeden znak, tłumaczy każdy na długi fragment kodu reprezentujący jego wejście do pamięci RAM. Po zakończeniu sekcji 3 program informuje program o wyjściu z pętli.

Po uruchomieniu pętli program musi tylko wcisnąć pierwszy bit quine ([()]())(()()()()){({}[(. Robię to za pomocą następującego kodu implementującego standardowe techniki złożoności Kołmogorowa.

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

Mam nadzieję, że to było jasne. Proszę o komentarz, jeśli jesteś zdezorientowany.

— Kreator pszenicy
źródło
Jak długo to trwa? Czas na TIO.
— Pavel
@Pavel Nie uruchamiam go na TIO, ponieważ byłoby to bardzo wolne, używam tego samego interpretera, którego używa TIO ( rubinowy ). Uruchomienie na starym serwerze stelażowym, do którego mam dostęp, zajmuje około 20 minut. W Crain-Flak zajmuje około 15 minut, ale Crain-Flak nie ma flag debugowania, więc nie mogę go zdobyć bez uruchomienia go w interpreterie Ruby.
— Wheat Wizard
@Pavel Uruchomiłem go ponownie i sprawdziłem czas. Zajęło 30m45.284s, aby zakończyć na dość niskim serwera końcowego (w przybliżeniu równowartość średniej nowoczesnego pulpitu) przy użyciu interpretera Ruby.
— Wheat Wizard
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.