Le défi est simple: écrire un programme ou une fonction qui, lorsqu'il reçoit un entier fini non négatif, génère un tableau imbriqué.

Les règles

• Votre code doit produire un tableau imbriqué valide unique pour chaque entier 0 ‌≤ n ‌ <2 ³¹ .
• Chaque tableau imbriqué possible avec jusqu'à 16 parenthèses ouvertes doit être sorti dans cette plage. (Cela ne signifie pas que votre code ne peut jamais sortir un tableau imbriqué avec plus de 16 crochets ouverts.)
• Votre code peut générer une représentation sous forme de chaîne du tableau imbriqué au lieu d'un tableau réel (avec ou sans virgules).

Une cartographie possible:

0 -> []
1 -> [[]]
2 -> [[[]]]
3 -> [[], []]
4 -> [[[[]]]]
5 -> [[[], []]]
6 -> [[[]], []]
7 -> [[], [[]]]
8 -> [[], [], []]
9 -> [[[[[]]]]]
etc.

Notation

Il s'agit de code-golf , donc le code le plus court en octets l'emporte.

Python 2.7, 172 149 124 124 118 octets

x=input();y="";z=0
for b in bin(x)[2+(x<1):]:y+="[]"[b<"1"];z+=b>"0"or-1;z+=99*(z<0)
print"["+(y,"[]"*(x+16))[z>0]+"]"

Explication:

Définissez une bijection par [↔ 1et ]↔ 0. Tout arrangement de parenthèses peut alors être écrit comme un nombre binaire et vice versa, par exemple [][]↔ 1010(10) et [[][]]↔ 110100(52). Tous les arrangements valides jusqu'à 15 crochets ouverts (30 crochets au total) sont couverts par des nombres jusqu'à 30 bits (en ignorant les zéros en tête), qui sont précisément les nombres inférieurs à 2 ³¹ .

La première boucle for donne l'inverse de cette bijection, convertissant un nombre en un arrangement de parenthèses, tout en vérifiant que l'arrangement est valide.

Les dispositions non valides sont remplacées dans l'instruction d'impression par de longues séquences de crochets pour éviter les collisions. Par exemple 11(3) ↔ [[n'est pas valide, nous concaténons donc 3 + 16 crochets à la place. Cela garantit que tous les arrangements sont uniques.

L'agencement résultant est placé dans une paire de crochets pour former un tableau imbriqué, de sorte que 1010(10) devient [[][]]et 110100(52) devient [[[][]]]. Le support supplémentaire ouvert signifie que nous avons maintenant couvert tous les tableaux avec 16 supports ouverts.

Le programme suivant peut être utilisé pour déterminer le numéro d'un tableau donné avec jusqu'à 16 crochets.

s=raw_input();o="";
for c in s[1:-1]:
 if c=="[":o+="1"
 if c=="]":o+="0"
print int(o,2)

Python, 153 128 octets

s=l=0;r="";n=input()
for d in bin(n)[2:]*(n>0):c=d<"1";l=[l,s>1][c];r+="]"*c+(1-l*c)*"[";s+=1-c-l*c
print"["+r+"["*l+"]"*(s+l+1)

Nous mappons un nombre n à une liste imbriquée en regardant ses chiffres binaires de gauche à droite. Cet algorithme fonctionne pour n'importe quel nombre, pas seulement en dessous de 2 ³² .

1. Si le chiffre binaire actuel est un 1, sortez [.
2. Sinon, si la séquence de parenthèses que nous avons sorties jusqu'à présent était équilibrée par une seule parenthèse fermante, la sortie ][.
3. Sinon, si c'est le dernier 0 du nombre binaire, sortez ][.
4. Sinon, sortie ].

Enfin, nous fermons tous les crochets ouverts.

Cuillère , 63 octets (501 bits)

000001001001001011001101001010011011111001010001000000101010
101101100110100101101001000101100010001000000100011000010000
000000000000001110111110010000001110110110010100100100100100
000110011010001000000110110000010000001010110011011011011001
000000011010010010010001000000111011011011101001001001000110
110110010100100101011001000100000011010001000000111011011001
010010010010010001101101101001000110110010110001101101101101
100100010001010010001010011011001000000011001101001001010010
000001100101001000111

Voici le programme brainfuck suivant converti en cuillère:

-[+[+<]>>+]<+++.[->+>+<<]>>++>>,[>-[<->-----]+<+++[-<+<<.>>>>-<]>[-<<-[->+<]<<<[-]>>>>[-<+<<<+>>>>]<<.>>+<[>-]>[-<+<<.>>>>]<<>>]<,]<<<<[>.>.<<[-]]>>>+[-<.>]+

Lit un entier en binaire sur stdin et affiche la liste imbriquée sur stdin. Nécessite 0 pour être entré comme chaîne vide (pas de chiffres) et nécessite un interpréteur brainfuck avec des cellules 8 bits. Même algorithme que ma réponse Python.

Version lisible:

-[+[+<]>>+]<+++.           push open bracket and print it
[->+>+<<]                  dup
>>++                       increment to close bracket

>>,[                       read input loop
    >-[<->-----]+<+++          subtract 48 and set up if/else
    [-                         if c == 1
        <+                         increment s
        <<.>>>                     output open bracket
    >-<]>[-<                   else
        <-[->+<]                   decrement and move s
        <<<[-]                     zero l
        >>>>[-<+<<<+>>>>]          l = s and restore s
        <<.>                       output close bracket
        >+<[>-]>[-                 if s == 0
            <+                         undo s decrement
            <<.                        output open bracket
        >>>>]<<
    >>]<
,]

<<<<[                      if l
    >.>.                   output pair
<<[-]]
>>>+[-<.>]                 output close bracket s+1 times

Gelée , 28 octets

ḃ2-*µSN;+\>-Ạ
1Ç#Ṫḃ2ṭ2;1ị⁾][

Cela itère sur toutes les chaînes de caractères [et ]qui commence par a [et se termine par a ], vérifie si les crochets correspondent et imprime la n ^ème correspondance.

Essayez-le en ligne!

Perl, 80 79 octets

Utilise à nouveau l'algorithme d' orlp , mais cette fois j'ai d'abord vérifié si cela fonctionne ...

Comprend +1 pour -p

Donner le numéro d'entrée sur STDIN

nest.pl <<< 8

nest.pl:

#!/usr/bin/perl -p
($_=sprintf"%b",$_).=2x(s^.^$&or++$n-pos&&/.0/g?++$n%1:$`&&21^eg-$n);y;102;();

La solution de Linus est de 64 octets en perl:

#!/usr/bin/perl -p
$_=sprintf"%b",/.+/g;$_=10x($&&&$&+16)if!/^(1(?1)*0)+$/;y;10;()

La solution de Dennis est de 59 octets en perl (de plus en plus lent pour les grands nombres):

#!/usr/bin/perl -p
1while$_-=(sprintf"%b",$n++)=~/^(1(?1)*0)+$/;$_=$&;y;10;()

Python 3, 120 114 octets

def f(n,k=0):
 while~n:
  k+=1
  try:r=eval(bin(k).translate({48:'],',49:'['})[3:-1])+[];n-=1
  except:0
 print(r)

Testez-le sur Ideone .

Comment ça marche

La fonction définie f prend l'entrée n et initialise k à 0 . Nous continuerons à incrémenter k jusqu'à ce que n + 1 valeurs de k donnent une sortie valide. Chaque fois que nous trouvons une telle valeur de k , n est décrémenté une fois qu'il atteint -1 , ~ndonne 0 , et la liste r qui correspond à la dernière valeur de k est imprimée.

Le mappage partiel des entiers positifs aux listes imbriquées (c'est-à-dire k ↦ r ) doit être bijectif, mais il n'y a pas d'autres contraintes. Celui utilisé dans cette réponse fonctionne comme suit.

1. Convertissez k en une représentation sous forme de chaîne binaire, en commençant par 0b .

   Par exemple, 44 ↦ "0b101100" .

2. Remplacez tous les 0 (point de code 48 ) dans la représentation sous forme de chaîne par la chaîne "]", et tous les 1 (point de code 49 ) par [ .

   Par exemple, "0b101100" ↦ "], b [], [[],]," .

3. Supprimez les trois premiers caractères (ils correspondent à "0b" ) et le caractère de fin (si tout va bien une virgule).

   Par exemple, "], b [], [[],]," ↦ "[], [[],]" .

4. Essayez d'évaluer le code généré. Si cela entraîne une erreur, k n'est mappé à aucune liste.

   Par exemple, "[], [[],]" ↦ ([], [[]]) .

5. Concatène le résultat (le cas échéant) avec la liste vide. Si cela entraîne une erreur, k n'est mappé à aucune liste.

   Par exemple, ([], [[]]) + [] erreurs car + ne peut pas concaténer des listes et des tuples.

Haskell, 71 octets

p 1=["[]"]
p n=['[':h++t|k<-[1..n-1],h<-p k,_:t<-p$n-k]
((p=<<[1..])!!)

La fonction principale de la dernière ligne indexe dans une liste de tous les tableaux imbriqués, triés par taille (nombre de crochets ouverts). Ainsi, tous les tableaux de taille au plus 16 sont répertoriés en premier.

Examinons d'abord le code plus agréable et plus court, mais le vérificateur de typographie de Haskell refuse d'accepter.

p 1=[[]]
p n=[h:t|k<-[1..n-1],h<-p k,t<-p$n-k]
((p=<<[1..])!!)

La fonction pen entrée ndonne une liste de tous les tableaux imbriqués de taille n(crochets ouverts). Cela se fait récursivement. Chacun de ces tableaux se compose d'une tête h(premier membre) de taille ket d'une queue t(autres membres) de taille n-k, les deux tailles étant différentes de zéro. Ou, c'est le tableau vide pour la taille n==1.

L'expression p=<<[1..]s'aplatit ensuite p(1), p(2), ...en une seule liste infinie de tous les tableaux triés par taille

[ [], [[]], [[],[]], [[[]]], [[],[],[]], [[],[[]]], [[[]],[]], [[[],[]]], ...

et la fonction principale y est indexée.

... Ou, si Haskell ne se plaignait pas de "construire [ing] le type infini: t ~ [t]". Haskell ne peut pas représenter la liste infinie ci-dessus dont les éléments sont des tableaux imbriqués arbitrairement. Tous ses éléments doivent avoir le même type, mais un type t ne peut pas être le même qu'une liste de t. En fait, la fonction pelle-même ne peut pas être affectée à un type cohérent sans typage dépendant, ce qui manque à Haskell.

Donc, à la place, nous travaillons sur des chaînes de crochets, simulant l'opération par contre en agissant sur [et sur les ]caractères. Cela prend 9 octets supplémentaires. Les dangers du golf dans un langage sûr.

Haskell, 87 82 octets

0#0=[""]
n#m=['[':x|n>0,x<-(n-1)#m]++[']':x|n<m,x<-n#(m-1)]
(([0..]>>= \y->y#y)!!)

Génère les éléments du tableau. Exemple d'utilisation: (([0..]>>= \y->y#y)!!) 3-> "[][]".

La fonction #crée tous les tableaux imbriqués sous forme de chaînes pour nles mcrochets ouverts et fermés, en gardant une trace du nombre de chacun qui reste. Commence toujours par n == m. La fonction principale appelle y # yfor every y <- [0,1,...]et sélectionne l'élément à l'index donné par l'entrée.

MATL , 31 octets

O`@BEqXJYs0&)0>w~hA+tG>~]x92J-c

Essayez-le en ligne! Ou vérifiez les premiers cas de test (cela prend quelques secondes).

La cartographie produite est:

0 -> []
1 -> [[]]
2 -> [[][]]
3 -> [[[]]]
4 -> [[][][]]
5 -> [[][[]]]
6 -> [[[]][]]
7 -> [[[][]]]
...

Explication

Le code continue de tester des nombres binaires croissants, le chiffre étant 0remplacé par -1; c'est-à-dire en utilisant 1et en -1tant que chiffres. Le chiffre 1représentera '['et -1représentera ']'.

Le programme compte jusqu'à ce que n +1 numéros valides aient été obtenus. Un numéro est valide si les deux conditions suivantes sont remplies:

1. La somme des chiffres est nulle (c'est-à-dire qu'il y a un nombre égal de 1et -1)
2. La somme cumulée des chiffres est toujours positive (c'est-à-dire que le nombre cumulé de 1chiffres dépasse toujours celui de -1) sauf à la fin (où il est nul par la condition 1).

Une fois que n +1 numéros valides ont été obtenus, le dernier est translittéré en changeant 1en [et -1en ], puis il est affiché.

Code:

O          % Push 0: initial count of valid numbers
`          % Do...while
  @        %   Push iteretation index k, starting at 1
  B        %   Convert to binary. For example, k=6 gives [1 1 0 0]
  Eq       %   Multiply by 2, subtract 1: transforms [1 1 0 0] into [1 1 -1 -1]
  XJ       %   Copy that to clipboard J, without popping it
  Ys       %   Cumulative sum: gives [1 2 1 0]
  0&)      %   Split array into its final element and the rest. Gives 0, [1 2 1]
  0>       %   Yields 1 for positive entries (condition 2). So in this case it
           %   gives [1 1 1]
  w        %   Swap: moves second-top element in the stack (0 in this case) to top
  ~        %   Negate: yields 1 if input is 0 (condition 1). Gives 1 in this case
  h        %   Concatenate horizontally. Gives [1 1 1 1]
  A        %   All: gives 1 if all elements are 1. Gives 1 in this case, meaning
           %   that this k is valid
  +        %   Add the result (0 or 1) to the count of valid numbers
  t        %   Duplicate
  G        %   Push input n
  >~       %   Loop condition: false (exit loop) if count exceeds input n
]          % End loop. At this point the result is in clipboard J, in 1/-1 format
x          % Delete count
92         % Push 92. Will be used to convert 1, -1 to '[', ']' (ASCII 91, 93)
J          % Push result in 1/-1 format
-          % Subtract: converts 1 to 91, -1 to 93
c          % Convert to char. Implicitly display