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 .

Python 3, 443 158 155 154 134 131 128 124 117 116 115 bajtów

c=d=C=D=0
for e in input():v='[<>,.-+]'.find(e);d=d*8+v;c+=c<0<6<v;c-=d>1>v;C,D=(c,C+1,d,D)[v>6::2]
print(-~D*8**C)

Kilka 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:

1. Podziel program BF na 3 części. Pierwsza część to największy prefiks składający się wyłącznie z [znaków. Trzecia część to największy postfiks składający się tylko z ]postaci. Druga część to środek.
2. Zutylizuj pierwszą część. Można je ponownie obliczyć później.
3. Usuń wszystkie ]nawiasy w trzeciej części, które pasują do [nawiasów w drugiej części. Można je również obliczyć później.
4. Połącz drugą i trzecią część razem.

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:

1 : 
2 : <
3 : >
4 : ,
5 : .
6 : -
7 : +
8 : []
9 : <[]
10 : <<
11 : <>
12 : <,
13 : <.
14 : <-
15 : <+
16 : [<]
17 : >[]
18 : ><
19 : >>
20 : >,

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!:

>>> ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
457711481836430915510337664562435564418569135809989841510260388418118348571803953323858180392373

Python 2, 157 bajtów

def f(s,o=0,d=0,D={}):T=s,o,d;x=D[T]=D[T]if T in D else~o and 0**o+sum(f(s[1:],cmp(c,"[")%-3-~o,d or cmp(c,s[0]))for c in"+,-.<>[]")if s else~d<0==o;return+x

Wciąż wygląda na golfa, ale piszę to na razie. Wykorzystuje rekurencję z odrobiną buforowania. Irytujące, D.getnie 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 zmienna dprzyjmuje 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 prefiksem s, więc możemy dpóźniej zmienić go na 1 lub -1.

Na przykład, jeśli mamy, s = "[-]"a nasz obecny prefiks jest p = "+", ponieważ pjest później niż sleksykograficznie, wiemy tylko, aby dodać programy, od pktó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:

  (o == 0)               # Adds a program shorter than s if it's valid
                         # For the first expansion, this is 1 for the empty program
+ f(s[1:], o=-1, d=1)    # ']', o goes down by one due to closing bracket
+ f(s[1:], o=1, d=1)     # '[', o goes up by one due to opening bracket
+ f(s[1:], o=0, d=1)     # '>'
+ f(s[1:], o=0, d=1)     # '<'
+ f(s[1:], o=0, d=1)     # '.', d is set to 1 for this and the previous branches
                         # since they are lexicographically earlier than s's first char
+ f(s[1:], o=0, d=0)     # '-', d is still 0 since this is equal to s's first char
+ f(s[1:], o=0, d=-1)    # ',', d is set to -1 for this and the later branches
                         # since they are lexicographically later than s's first char
+ f(s[1:], o=0, d=-1)    # '+'

Uwaga jak w rzeczywistości nie używać prefiksów w rekursji - wszystko dbamy o nich zostaje schwytany przez zmienne d, oa kurczy Program wejściowy s. 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 sjest 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 < 0natychmiastowym zwracaniem 0, ponieważ wszystkie programy z tym prefiksem mają więcej ]s [, a zatem są nieprawidłowe.

Pierwsze 20 wyników to:

 1
> 2
< 3
. 4
- 5
, 6
+ 7
[] 8
>> 9
>< 10
>. 11
>- 12
>, 13
>+ 14
<> 15
<< 16
<. 17
<- 18
<, 19
<+ 20

Korzystając z tego samego przykładu Hello World, co odpowiedź @ TheNumberOne:

>>> f("++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.")
3465145076881283052460228065290888888678172704871007535700516169748342312215139431629577335423L

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.

F={0:1}

def f(n):
    if n not in F:
        F[n]=6*f(n-1) + sum(f(i)*f(n-2-i) for i in range(n-1))

    return F[n]

def h(x):
    if x=='': return 0

    if len(x)==1: return '+-<>,.'.find(x)

    if x[0]!='[':
        return h(x[0]) * f(len(x)-1) + h(x[1:])

    d=i=1
    while d:
        if x[i]==']': d-=1
        elif x[i]=='[': d+=1
        i+=1

    a=i-2
    b=len(x)-i

    return 6*f(a+b+1) + sum(f(i)*f(a+b-i) for i in range(a)) + h(x[1:i-1]) * f(b) + h(x[i:])

def g(x):
    return sum(f(i) for i in range(len(x))) + h(x) + 1

print g(raw_input())

Ta funkcja f(n)zlicza liczbę prawidłowych programów do pieprzenia mózgów o długości n. h(x)mapuje programy o długości ndo [0..f(n)-1]i g(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=4mamy te przypadki:

zxxx
[]xx
[x]x
[xx]

gdzie zoznacza []znak xinny niż dowolny znak, z zastrzeżeniem, że ]musi pasować do znaku początkowego [. Programy są uszeregowane zgodnie z tą kolejnością i rekurencyjnie w xpodsekcjach, przy czym lewa sekcja ma pierwszeństwo przed prawą sekcją w ostatnich przypadkach. Obliczanie rang jest podobne do systemów numerycznych z mieszanymi podstawnikami i fjest ważne przy obliczaniu obecnego „podstawnika”.

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ę:

P(x) = "" (the empty program) when x <= 0
P(x) = "]" when x = 1
P(x) = "]]" when x = 2
etcetera

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)

h(V3) = h(U3) + g(T) - h(T)                           using the construction of V
h(V3) = h(U3) + g(U2) + g(U3) - h(U2) - h(U3)         apply the definition of T
h(V3) = g(U2) - h(U2) *one term cancels, g(U3)        is always zero, as U3 contains only `]` symbols*

Teraz pokazujemy, że f (V) = f (U).

f(U) = U2 ~ P(h(U3) - g(U2)) = U2                     claim 2, definition of P

f(V) = U2 ~ P(h(V3) - g(V2))
     = U2 ~ P(h(V3) - g(U2))
     = U2 ~ P(g(U2) - h(U2) - g(U2))                  claim 3
     = U2 ~ P(-h(U2))
     = U2                                             definition P

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