Golunar / Unary ist ein Weg , um alle gültig zu kodieren Brainfuck - Programmen, aber es ist nicht eine Aufzählung, da die meisten natürlichen Zahlen nicht auf ein gültiges Programm entsprechen.

Nehmen Sie für diese Herausforderung ein doppelt unendliches Band und keine Kommentare an, dh ein Brainfuck-Programm ist nur dann gültig, wenn es nur aus den Zeichen besteht <>+-.,[]und alle linken und rechten Klammern übereinstimmen.

Zum Beispiel kann das leere Programm ,[+][-]., [>+<[--].]und +[+[+][+[+]+]+]+.gelten Programme Brainfuck, während ][, und a[]sind es nicht.

Aufgabe

Schreiben Sie ein Programm oder eine Funktion, die ein gültiges Brainfuck-Programm als Eingabe akzeptiert und eine natürliche Zahl ( 1 , 2 , 3 ,…) mit den folgenden Einschränkungen zurückgibt :

• Die generierte Ausgabe muss für alle gültigen Brainfuck-Programme unterschiedlich sein.

• Für jede natürliche Zahl n muss ein gültiges Brainfuck-Programm vorhanden sein, das, wenn es als Eingabe bereitgestellt wird, die Ausgabe n generiert .

Zusätzliche Regeln

• Bei einem Brainfuck-Programm von 100 oder weniger Bytes muss Ihr Programm oder Ihre Funktion innerhalb einer Minute beendet sein.

  Dies bedeutet, dass Sie nicht alle gültigen Brainfuck-Programme durchlaufen können, bis Sie mit der Eingabe übereinstimmen.

• Es gelten die Standardregeln für Code-Golf .

Python 3, 443 158 155 154 134 131 128 124 117 116 115 Bytes

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)

Mehrere Bytes dank Sp3000 und Mitch Schwartz: D

Wie das funktioniert:

Dies ordnet alle gültigen BF-Programme allen möglichen, gültigen oder ungültigen BF-Programmen zu, die nicht mit einem beginnen [, und zwar in einem Eins-zu-Eins-Verhältnis. Danach wird das neue Programm einfach in Oktal konvertiert.

Hier ist die Mapping-Formel:

1. Teilen Sie ein BF-Programm in 3 Teile. Der erste Teil ist das größte Präfix, das nur aus [Zeichen besteht. Der dritte Teil ist das größte Postfix, das nur aus ]Zeichen besteht. Der zweite Teil ist die Mitte.
2. Entsorgen Sie den ersten Teil. Diese können später neu berechnet werden.
3. Entfernen Sie alle ]Klammern im dritten Teil, die mit den [Klammern im zweiten Teil übereinstimmen . Diese können auch später neu berechnet werden.
4. Verketten Sie den zweiten und dritten Teil miteinander.

Wenn Sie diese Erklärung nicht verstehen, können Sie eine erweiterte Erklärung im Chat finden starten hier .

Als Referenz sind hier die ersten 20 Programme:

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

Hier sind die ersten 1000 Programme: http://pastebin.com/qykBWhmD
Hier ist das Programm, mit dem ich sie erstellt habe: http://ideone.com/e8oTVl

Hier ist Hello, World!:

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

Python 2, 157 Bytes

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

Sieht immer noch ziemlich gut aus, aber ich poste dies erstmal. Es wird eine Rekursion mit etwas Zwischenspeicherung verwendet. Ärgerlicherweise wird D.getdas Caching nicht kurzgeschlossen, so dass ich auf diese Weise keine 9 Bytes sparen kann ...

Das Mapping priorisiert zuerst die Länge und dann die lexikografische Reihenfolge über die Reihenfolge "][><.-,+"(siehe Ausgabebeispiele unten). Die Hauptidee ist es, Präfixe zu vergleichen.

Die Variable overfolgt die Anzahl der [Klammern, die für das aktuelle Präfix noch offen sind, während die Variable deinen der drei folgenden Werte annimmt:

• d = 1: Das aktuelle Präfix ist lexikografisch früher als s. Fügen Sie alle Programme mit diesem Präfix und dieser Länge hinzu <= s.
• d = -1: Das aktuelle Präfix ist lexikografisch später als s. Fügen Sie alle Programme mit diesem Präfix und dieser Länge hinzu < s.
• d = 0: Das aktuelle Präfix ist ein Präfix von s, daher können wir dspäter auf 1 oder -1 wechseln .

Zum Beispiel, wenn wir haben s = "[-]"und unser aktuelles Präfix ist p = "+", da pes später als slexikographisch ist, wissen wir nur, dass wir die Programme hinzufügen müssen, die mit pdem streng kürzeren als beginnen s.

Nehmen wir an, wir haben ein Eingabeprogramm s = "-[]". Die erste rekursive Erweiterung führt dies aus:

  (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)    # '+'

Beachten Sie, wie wir eigentlich nicht die Präfixe in der Rekursion verwenden - alles , was wir uns um sie kümmern wird durch die Variablen erfasst d, ound die schrumpfende Eingabeprogramm s. Oben werden Sie eine Menge Wiederholungen bemerken - hier kommt das Cachen ins Spiel, sodass wir 100-Zeichen-Programme auch innerhalb des Zeitlimits verarbeiten können.

Wenn sleer ist, schauen wir uns an (d>=0 and o==0), was entscheidet, ob 1 (zähle dieses Programm, weil es lexikographisch früh / gleich ist und das Programm gültig ist) oder 0 (zähle dieses Programm nicht) zurückgegeben wird.

Jede Situation mit o < 0sofort kehrt zurück 0, da alle Programme mit diesem Präfix mehr ]als s [haben und daher ungültig sind.

Die ersten 20 Ausgänge sind:

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

Verwenden Sie dasselbe Hello World-Beispiel wie die Antwort von @ TheNumberOne:

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

Python 2, 505 (nicht golfen)

Es hat mir Spaß gemacht, diesen Ansatz zu entwickeln, aber ich werde mich vielleicht nicht darum kümmern, Golf zu spielen, weil er im Vergleich zu anderen Ansätzen nicht wettbewerbsfähig ist. Ich poste es aus Gründen der Vielfalt und des möglichen ästhetischen Interesses. Es beinhaltet Rekursion und ein bisschen Mathe.

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())

Die Funktion f(n)zählt die Anzahl der gültigen Brainfuck-Programme der Länge n. h(x)ordnet Programme mit einer Länge nzu [0..f(n)-1]und g(x)ist die fragliche bijektive Rangfolgefunktion.

Die Hauptidee ist, dass ein nicht leeres Programm entweder mit [oder mit einem der 6 Nicht- []Zeichen beginnen kann. Im ersteren Fall können wir die möglichen Positionen des Abgleichs ]durchlaufen und auf den eingeschlossenen Teil und auf den Schwanz zurückgreifen (wobei Schwanz die Unterzeichenfolge bedeutet, die dem folgt ]). Im letzteren Fall können wir auf den Schwanz zurückgreifen (wobei Schwanz bedeutet, das erste Zeichen fallen zu lassen). Diese Überlegung kann sowohl zum Zählen als auch zum Berechnen des Ranges verwendet werden.

Kürzere Programme haben immer einen niedrigeren Rang als längere Programme, und das Klammernmuster ist ein sekundärer Bestimmungsfaktor. Die Nicht- []Zeichen sind nach "+ - <>," sortiert. (was willkürlich ist).

Zum Beispiel mit haben n=4wir diese Fälle:

zxxx
[]xx
[x]x
[xx]

Dabei zsteht Wobei für Nicht- []Zeichen und xfür ein beliebiges Zeichen unter der Einschränkung, dass das Zeichen ]mit dem Anfangsbuchstaben übereinstimmen muss [. Programme werden in dieser Reihenfolge und rekursiv in den xUnterabschnitten angeordnet, wobei der linke Abschnitt in den letzteren Fällen Vorrang vor dem rechten Abschnitt hat. Die Rangberechnung ist ähnlich wie bei Zahlensystemen mit gemischtem Radix und fist wichtig für die Berechnung des aktuellen "Radix".

Diese Antwort ist ein formaler Beweis für die Antwort von TheNumberOne , Enumerate valid Brainf ** k programs , wobei es etwas schwierig sein kann , die genauen Punkte zu verstehen, warum die Aufzählung korrekt ist. Es ist nicht trivial zu verstehen, warum es kein ungültiges Programm gibt, das einer Nummer zugeordnet ist, die nicht von einem gültigen Programm abgedeckt wird.

In dieser Antwort werden Großbuchstaben für Programme und Kleinbuchstaben für Funktionen und ganze Zahlen verwendet. ~ ist der Verkettungsoperator.

Satz 1:

Die Funktion f sei das in dieser Antwort beschriebene Programm. Dann existiert für jedes Programm U ein gültiges Programm V, so dass f (U) = f (V)

Definition 1:

Sei g (X) die Nummer [, die im Programm X erscheint, und sei h (X) die Nummer ], die erscheint.

Definition 2:

Definiere P (x) als diese Funktion:

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

Definition 3:

In einem gegebenen Programm X bezeichnen Sie X1 als das größte Präfix von [Zeichen, X2 als das Zentrum und X3 als das größte Suffix von ]Zeichen.

Beweis von Satz 1:

Wenn g (U) = h (U) ist, dann ist U ein gültiges Programm und wir können V = U nehmen. (Trivialfall).

Wenn g (U) <h (U) ist, können wir V erzeugen, indem wir n = h (U) - g (U) [Symbole voranstellen . Offensichtlich ist f (V) = f (U), da alle [Symbole im Präfix entfernt werden.

Betrachte nun g (U)> h (U). Definiere T = U2 ~ U3. wenn g (T) <= h (T), dann können wir V konstruieren, indem wir n = g (U) - h (U) [Symbole entfernen .

Wir können also annehmen, dass h (T) <g (T) ist. Konstruiere V = T ~ P (g (T) - h (T)).

Wir brauchen drei kleine Fakten, um fortzufahren:

Anspruch 1: g (U2) = g (T)

U3 enthält [laut Definition keine Symbole. Als T = U2 ~ U3 [befinden sich alle Symbole im ersten Teil.

Anspruch 2: h (U3) <g (T)

Dies folgt aus der Feststellung, dass h (T) <g (T) und h (U3) <h (U3 - U2) = h (T) ist.

Anspruch 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*

Nun zeigen wir, dass 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

Damit ist der Beweis abgeschlossen. QED

Lassen Sie uns auch die Einzigartigkeit tun.

Satz 2:

Sei U, V zwei verschiedene gültige Programme. Dann ist f (U)! = F (V)

Dies ist im Vergleich zum vorherigen Satz ziemlich einfach.

Nehmen wir an, U2 = V2. Aber dann können sich U und V nur dadurch unterscheiden, dass n [und ]Symbole zu U1 bzw. U3 hinzugefügt oder daraus entfernt werden . Dies ändert jedoch die Ausgabe von f, da f die Anzahl nicht übereinstimmender ]Symbole im Suffix zählt.

Also U2! = V2.

Dies führt offensichtlich zu einem Widerspruch. Da U2 und V2 buchstäblich in der Ausgabe von f (U) bzw. f (V) enthalten sind, können sie sich nicht unterscheiden, außer am 'Rand' der Stelle, an der U2 mit U3 verkettet ist. Das erste und das letzte Symbol von U2 und V2 können jedoch nicht [oder ]definitionsgemäß sein, während dies die einzigen Symbole sind, die in U1, U3, V1, V3 bzw. erneut zulässig sind. Somit erhalten wir U2 = V2. QED