Golunar / Unary to sposób na zakodowanie wszystkich prawidłowych programów Brainfuck , ale nie jest to wyliczenie, ponieważ większość liczb naturalnych nie odpowiada prawidłowemu programowi.
Na potrzeby tego wyzwania załóżmy podwójnie nieskończoną taśmę i brak komentarzy, tj. Program Brainfuck jest ważny tylko wtedy, gdy składa się wyłącznie ze znaków <>+-.,[]
i pasują wszystkie lewe i prawe nawiasy.
Na przykład, pusty program ,[+][-].
, [>+<[--].]
i +[+[+][+[+]+]+]+.
są ważne, natomiast programy brainfuck ][
, a a[]
nie są.
Zadanie
Napisz program lub funkcję, która akceptuje poprawny program Brainfuck jako dane wejściowe i zwraca liczbę naturalną ( 1 , 2 , 3 ,…), z następującymi ograniczeniami:
Wygenerowane wyjście musi być inne dla wszystkich prawidłowych programów Brainfuck.
Dla każdej liczby naturalnej n musi istnieć prawidłowy program Brainfuck, który podany jako dane wejściowe generuje wyjście n .
Dodatkowe zasady
Biorąc pod uwagę program Brainfuck o wielkości 100 lub mniej bajtów, twój program lub funkcja musi zakończyć się w ciągu jednej minuty.
Oznacza to, że nie możesz iterować wszystkich prawidłowych programów Brainfuck, dopóki nie dopasujesz danych wejściowych.
Obowiązują standardowe zasady gry w golfa .
źródło
Odpowiedzi:
Python 3,
443158155154134131128124117116115 bajtówKilka bajtów dzięki Sp3000 i Mitchowi Schwartzowi: D
Jak to działa:
Odwzorowuje to wszystkie prawidłowe programy BF na wszystkie możliwe, prawidłowe lub nieprawidłowe programy BF, które nie zaczynają się od
[
, w stosunku jeden do jednego. Następnie nowy program jest po prostu konwertowany na ósemkowy.Oto formuła mapowania:
[
znaków. Trzecia część to największy postfiks składający się tylko z]
postaci. Druga część to środek.]
nawiasy w trzeciej części, które pasują do[
nawiasów w drugiej części. Można je również obliczyć później.Jeśli nie rozumiesz tego wyjaśnienia, możesz znaleźć obszerne wyjaśnienie na czacie, zaczynając tutaj .
Dla porównania, oto pierwsze 20 programów:
Oto pierwsze 1000 programów: http://pastebin.com/qykBWhmD
Oto program, którego użyłem do ich wygenerowania: http://ideone.com/e8oTVl
Oto
Hello, World!
:źródło
Python 2, 157 bajtów
Wciąż wygląda na golfa, ale piszę to na razie. Wykorzystuje rekurencję z odrobiną buforowania. Irytujące,
D.get
nie powoduje zwarcia do buforowania, więc nie mogę w ten sposób zapisać 9 bajtów ...Odwzorowanie najpierw traktuje długość, a następnie porządek leksykograficzny nad uporządkowaniem
"][><.-,+"
(patrz przykłady wyjściowe poniżej). Główną ideą jest porównanie przedrostków.Zmienna
o
śledzi liczbę[
otwartych nawiasów dla bieżącego prefiksu, podczas gdy zmiennad
przyjmuje jedną z trzech wartości wskazujących:d = 1
: Bieżący prefiks jest leksykograficznie starszy niżs
. Dodaj wszystkie programy z tym prefiksem i długością<= s
,d = -1
: Bieżący prefiks jest leksykograficznie późniejszy niżs
. Dodaj wszystkie programy z tym prefiksem i długością< s
.d = 0
: Bieżący prefiks jest prefiksems
, więc możemyd
później zmienić go na 1 lub -1.Na przykład, jeśli mamy,
s = "[-]"
a nasz obecny prefiks jestp = "+"
, ponieważp
jest później niżs
leksykograficznie, wiemy tylko, aby dodać programy, odp
których są ściśle krótsze niżs
.Aby podać bardziej szczegółowy przykład, załóżmy, że mamy program do wprowadzania danych
s = "-[]"
. Pierwsze rekurencyjne rozszerzenie wykonuje to:Uwaga jak w rzeczywistości nie używać prefiksów w rekursji - wszystko dbamy o nich zostaje schwytany przez zmienne
d
,o
a kurczy Program wejściowys
. Powyżej zauważysz wiele powtórzeń - w tym miejscu pojawia się buforowanie, co pozwala nam przetwarzać programy o długości 100 znaków w odpowiednim czasie.Kiedy
s
jest pusta, patrzymy na(d>=0 and o==0)
, która decyduje, czy zwrócić 1 (policzyć ten program, ponieważ jest on leksykograficznie wczesny / równy, a program jest poprawny), lub 0 (nie licz tego programu).Każda situtation z
o < 0
natychmiastowym zwracaniem0
, ponieważ wszystkie programy z tym prefiksem mają więcej]
s[
, a zatem są nieprawidłowe.Pierwsze 20 wyników to:
Korzystając z tego samego przykładu Hello World, co odpowiedź @ TheNumberOne:
źródło
Python 2, 505 (nie golfowy)
Podobało mi się rozwijanie tego podejścia, ale nie zawracam sobie głowy graniem w golfa, ponieważ nie jest ono konkurencyjne w porównaniu z innymi podejściami. Zamieszczam to ze względu na różnorodność i możliwe zainteresowanie estetyczne. Obejmuje rekurencję i odrobinę matematyki.
Ta funkcja
f(n)
zlicza liczbę prawidłowych programów do pieprzenia mózgów o długościn
.h(x)
mapuje programy o długościn
do[0..f(n)-1]
ig(x)
jest funkcją bijective ranking.Główną ideą jest to, że niepusty program może albo zaczynać się od
[
albo z jednym z 6[]
znaków innych niż znaki. W pierwszym przypadku możemy iterować po możliwych miejscach dopasowania]
i powtarzać się na zamkniętej części i na ogonie (gdzie ogon oznacza podciąg następujący po]
). W tym drugim przypadku możemy powrócić na ogon (gdzie ogon oznacza upuszczenie pierwszego znaku). Takie rozumowanie można wykorzystać zarówno do zliczania, jak i do obliczania rangi.Krótsze programy zawsze będą miały niższą rangę niż dłuższe programy, a wzór nawiasów jest drugorzędnym czynnikiem determinującym. Nie-
[]
znaki są sortowane według „+ - <> ,.” (co jest arbitralne).Na przykład z
n=4
mamy te przypadki:gdzie
z
oznacza[]
znakx
inny niż dowolny znak, z zastrzeżeniem, że]
musi pasować do znaku początkowego[
. Programy są uszeregowane zgodnie z tą kolejnością i rekurencyjnie wx
podsekcjach, przy czym lewa sekcja ma pierwszeństwo przed prawą sekcją w ostatnich przypadkach. Obliczanie rang jest podobne do systemów numerycznych z mieszanymi podstawnikami if
jest ważne przy obliczaniu obecnego „podstawnika”.źródło
Ta odpowiedź jest formalnym dowodem na odpowiedź przez TheNumberOne , Wyliczanie ważny Brainf ** k programów , w których może to być trochę trudne do zrozumienia punktów drobne dlaczego wyliczenie jest prawidłowe. Nie jest łatwo zrozumieć, dlaczego nie ma żadnego nieprawidłowego programu, który mapuje na liczbę nieobjętą prawidłowym programem.
W tej odpowiedzi wielkie litery są używane do oznaczenia programów, a zmienne pisane małymi literami są używane dla funkcji i liczb całkowitych. ~ jest operatorem konkatenacji.
Twierdzenie 1:
Niech funkcja f będzie programem opisanym w tej odpowiedzi. Następnie dla każdego programu U istnieje poprawny program V taki, że f (U) = f (V)
Definicja 1:
Niech g (X) będzie liczbą,
[
która pojawi się w programie X, i niech h (X) będzie liczbą,]
która pojawi się.Definicja 2:
Zdefiniuj P (x) jako tę funkcję:
Definicja 3:
Biorąc pod uwagę program X, oznacz X1 jako największy prefiks
[
znaków, X2 jego środek, a X3 jego największy sufiks]
znaków.Dowód propozycji 1:
Jeśli g (U) = h (U), to U jest poprawnym programem i możemy przyjąć V = U. (trywialny przypadek).
Jeśli g (U) <h (U), możemy stworzyć V, poprzedzając symbole n = h (U) - g (U)
[
. Oczywiście f (V) = f (U), ponieważ wszystkie[
symbole w prefiksie są usuwane.Teraz rozważ g (U)> h (U). Zdefiniuj T = U2 ~ U3. jeśli g (T) <= h (T), to możemy zbudować V usuwając
[
symbole n = g (U) - h (U) .Możemy więc założyć, że h (T) <g (T). Konstruuj V = T ~ P (g (T) - h (T)).
Potrzebujemy trzech drobnych faktów:
Zastrzeżenie 1: g (U2) = g (T)
U3
[
z definicji nie zawiera żadnych symboli. Ponieważ T = U2 ~ U3, wszystkie jego[
symbole znajdują się w pierwszej części.Twierdzenie 2: h (U3) <g (T)
Wynika to z faktu, że h (T) <g (T) i h (U3) <h (U3 ~ U2) = h (T).
Twierdzenie 3: h (V3) = g (U2) - h (U2)
Teraz pokazujemy, że f (V) = f (U).
To kończy dowód. CO BYŁO DO OKAZANIA
Zróbmy także wyjątkowość.
Twierdzenie 2:
Niech U, V będą dwoma różnymi, poprawnymi programami. Następnie f (U)! = F (V)
Jest to dość proste w porównaniu z poprzednią propozycją.
Załóżmy, że U2 = V2. Ale wtedy jedynym sposobem, w jaki U i V mogą być różne, jest dodanie lub usunięcie n
[
i]
symboli odpowiednio do U1 i U3. Zmienia to jednak wynik f, ponieważ f policzy liczbę niedopasowanych]
symboli w sufiksie.Zatem U2! = V2.
Oczywiście prowadzi to do sprzeczności. Ponieważ U2 i V2 są dosłownie zawarte w danych wyjściowych odpowiednio f (U) i f (V), nie mogą się różnić, z wyjątkiem „krawędzi” miejsca, w którym U2 jest połączone z U3. Ale pierwszy i ostatni symbol U2 i V2 nie mogą być
[
lub]
z definicji, podczas gdy są to jedyne symbole dozwolone odpowiednio w U1, U3, V1, V3 i odpowiednio. Otrzymujemy U2 = V2. CO BYŁO DO OKAZANIAźródło