Golunar / unaire est un moyen d'encoder tous les valides Brainfuck programmes, mais ce n'est pas une énumération, puisque la plupart des nombres naturels ne correspondent pas à un programme valide.

Pour les besoins de ce défi, supposons une bande doublement infinie et aucun commentaire, c’est-à-dire qu’un programme Brainfuck est valide si et seulement si il est composé uniquement des caractères <>+-.,[]et que tous les crochets gauche et droit correspondent.

Par exemple, les programmes vides ,[+][-]., [>+<[--].]et +[+[+][+[+]+]+]+.sont des programmes Brainfuck valides, alors que ][et a[]ne le sont pas.

Tâche

Ecrivez un programme ou une fonction qui accepte un programme Brainfuck valide en entrée et renvoie un nombre naturel ( 1 , 2 , 3 ,…), avec les contraintes suivantes:

• La sortie générée doit être différente pour tous les programmes Brainfuck valides.

• Pour chaque nombre naturel n , il doit exister un programme Brainfuck valide qui, lorsqu'il est fourni en entrée, génère la sortie n .

Règles supplémentaires

• Avec un programme Brainfuck de 100 octets ou moins, votre programme ou votre fonction doit s'achever en une minute.

  Cela signifie que vous ne pouvez pas parcourir tous les programmes Brainfuck valides tant que vous ne correspondez pas à l'entrée.

• Les règles standard de code-golf s'appliquent.

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

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)

Plusieurs octets grâce à Sp3000 et Mitch Schwartz: D

Comment ça marche:

Ceci mappe tous les programmes BF valides dans tous les programmes BF possibles, valides ou invalides, qui ne commencent pas par un [, dans un rapport un à un. Après cela, le nouveau programme est simplement converti en octal.

Voici la formule de mappage:

1. Séparez un programme BF en 3 parties. La première partie est le plus grand préfixe composé uniquement de [caractères. La troisième partie est le plus grand postfix composé de ]caractères uniquement . La deuxième partie est le milieu.
2. Éliminer la première partie. Ceux-ci peuvent être recalculés plus tard.
3. Supprimez tous les ]supports de la troisième partie qui correspondent aux [supports de la deuxième partie. Ceux-ci peuvent également être recalculés plus tard.
4. Concaténer les deuxième et troisième parties ensemble.

Si vous ne comprenez pas cette explication, vous pouvez trouver une explication détaillée dans le chat en commençant ici .

Pour référence, voici les 20 premiers programmes:

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

Voici les 1000 premiers programmes: http://pastebin.com/qykBWhmD
Voici le programme que j'ai utilisé pour les générer: http://ideone.com/e8oTVl

Voici Hello, World!:

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

Python 2, 157 octets

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

Ça a toujours l'air assez golfable, mais je poste ceci pour le moment. Il utilise la récursivité avec un peu de cache. De manière ennuyeuse, D.getne court-circuite pas pour la mise en cache, je ne peux donc pas économiser 9 octets de cette façon ...

Le mappage donne la priorité à la longueur, puis à l'ordre lexicographique par rapport à l'ordre "][><.-,+"(voir les exemples de sortie ci-dessous). L'idée principale est de comparer les préfixes.

La variable ogarde trace du nombre de [crochets encore ouverts pour le préfixe actuel, tandis que la variable dprend l'une des trois valeurs suivantes:

• d = 1: Le préfixe actuel est lexicographiquement antérieur à s. Ajoutez tous les programmes avec ce préfixe et cette longueur <= s,
• d = -1: Le préfixe actuel est lexicographiquement plus tard que s. Ajoutez tous les programmes avec ce préfixe et cette longueur < s.
• d = 0: Le préfixe actuel est un préfixe de s, nous pourrions donc passer dà 1 ou -1 plus tard.

Par exemple, si nous avons s = "[-]"et que notre préfixe actuel est p = "+", puisqu’il pest plus tard que slexicographe, nous ne savons ajouter que les programmes commençant par pqui sont strictement plus courts que s.

Pour donner un exemple plus détaillé, supposons que nous ayons un programme d’entrée s = "-[]". La première expansion récursive fait ceci:

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

Notez que nous ne pas utiliser réellement les préfixes dans la récursivité - tout ce que nous soucions d'eux est capturé par les variables d, oet le programme d'entrée diminue s. Vous remarquerez beaucoup de répétitions ci-dessus - c’est là que la mise en cache intervient, nous permettant de traiter les programmes de 100 caractères dans les délais impartis.

Quand sest vide, nous regardons (d>=0 and o==0), qui décide s'il faut retourner 1 (compter ce programme parce que c'est lexicographiquement précoce / égal et que le programme est valide), ou 0 (ne pas compter ce programme).

Toute situtation avec o < 0retour immédiat 0, car tous les programmes avec ce préfixe ont plus de ]s que [, et sont donc invalides.

Les 20 premières sorties sont:

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

En utilisant le même exemple Hello World que la réponse de @ TheNumberOne:

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

Python 2, 505 (non golfé)

J'ai aimé développer cette approche, mais je ne me dérangerai peut-être pas parce que ce n'est pas compétitif par rapport à d'autres approches. Je le publie dans l'intérêt de la diversité et de son intérêt esthétique. Cela implique de la récursion et un peu de maths.

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

La fonction f(n)compte le nombre de programmes de brainfuck valides n. h(x)mappe des programmes de longueur nà [0..f(n)-1], et g(x)constitue la fonction de classement bijective en question.

L'idée principale est qu'un programme non vide peut commencer avec [ou avec l'un des 6 []caractères non . Dans le premier cas, nous pouvons itérer sur les emplacements possibles de l'appariement ]et de la récidive sur la partie incluse et sur la queue (où queue signifie la sous-chaîne qui suit la ]). Dans ce dernier cas, on peut récidiver sur la queue (où queue signifie laisser tomber le premier caractère). Ce raisonnement peut être utilisé à la fois pour compter et pour calculer le rang.

Les programmes les plus courts auront toujours un rang inférieur aux programmes les plus longs et le modèle de parenthèse est un facteur déterminant secondaire. Les non- []caractères sont triés selon "+ - <>,". (ce qui est arbitraire).

Par exemple avec n=4nous avons ces cas:

zxxx
[]xx
[x]x
[xx]

où zreprésente non- []caractère et xdésigne n'importe quel caractère, sous réserve du ]fait qu'il doit correspondre à l'initiale [. Les programmes sont classés en fonction de cet ordre, et de manière récurrente dans les xsous - sections, la section de gauche ayant la priorité sur la section de droite dans les derniers cas. Le calcul du rang est similaire à celui des systèmes à numération à base variable et fest important pour le calcul de la "base" courante.

Cette réponse est une preuve formelle de la réponse fournie par TheNumberOne . Énumérez des programmes Brainf ** k valides , où il peut être un peu difficile de comprendre les détails de la raison pour laquelle l'énumération est correcte. Il n’est pas inutile de comprendre pourquoi aucun programme non valide ne correspond à un nombre non couvert par un programme valide.

Tout au long de cette réponse, les majuscules désignent les programmes et les variables minuscules, les fonctions et les entiers. ~ est l'opérateur de concaténation.

Proposition 1:

Soit la fonction f le programme décrit dans cette réponse. Il existe alors pour chaque programme U un programme valide V tel que f (U) = f (V)

Définition 1:

Soit g (X) le numéro de [celui qui apparaît dans le programme X, et h (X) le nombre de ]celui-ci.

Définition 2:

Définissez P (x) comme étant cette fonction:

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

Définition 3:

Pour un programme X, notons X1 comme étant son plus grand préfixe de [caractères, X2 son centre et X3 son suffixe le plus grand ].

Preuve de la proposition 1:

Si g (U) = h (U), U est un programme valide et nous pouvons prendre V = U. (cas trivial).

Si g (U) <h (U), nous pouvons créer V en ajoutant des symboles n = h (U) à g (U) [. Évidemment, f (V) = f (U) car tous les [symboles du préfixe sont supprimés.

Considérons maintenant g (U)> h (U). Définissez T = U2 ~ U3. si g (T) <= h (T), alors nous pouvons construire V en supprimant n = g (U) - h (U) [symboles.

Nous pouvons donc supposer que h (T) <g (T). Construire V = T ~ P (g (T) - h (T)).

Nous avons besoin de trois petits faits pour procéder:

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

U3 ne contient aucun [symbole par sa définition. Comme T = U2 ~ U3, ses [symboles sont tous dans la première partie.

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

Cela découle du fait que h (T) <g (T) et h (U3) <h (U3 ~ U2) = h (T).

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

Maintenant, nous montrons que 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

Ceci complète la preuve. QED

Faisons l'unicité aussi.

Proposition 2:

Soit U, V deux programmes différents et valides. Alors f (U)! = F (V)

Ceci est assez simple par rapport à la proposition précédente.

Supposons que U2 = V2. Mais alors la seule façon dont U et V peuvent être différents est d’ajouter ou de supprimer n [et les ]symboles dans U1 et U3 respectivement. Pourtant, cela change la sortie de f, puisque f comptera le nombre de ]symboles non appariés dans le suffixe.

Donc, U2! = V2.

Évidemment, cela mène à une contradiction. Comme U2 et V2 sont littéralement contenus dans les sorties de f (U) et f (V) respectivement, ils ne peuvent pas différer, sauf au niveau du "bord", le lieu où U2 est concaténé avec U3. Mais les premier et dernier symboles de U2 et V2 ne peuvent pas être [ou ]par définition, alors que ce sont les seuls symboles autorisés dans U1, U3, V1, V3 respectivement et respectivement à nouveau. Nous obtenons donc U2 = V2. QED