El desafío es simple: escribir un programa o función que, cuando se le da un número entero no negativo finito, genera una matriz anidada.

Las normas

• Su código debe producir una matriz anidada válida única para cada número entero 0 ‌≤ n ‌ <2 ³¹ .
• Cada posible matriz anidada con hasta 16 paréntesis abiertos debe enviarse dentro de este rango. (Esto no significa que su código nunca pueda generar una matriz anidada con más de 16 paréntesis abiertos).
• Su código puede generar una representación de cadena de la matriz anidada en lugar de una matriz real (con o sin comas).

Un posible mapeo:

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

Tanteo

Este es el código de golf , por lo que gana el código más corto en bytes.

Python 2.7, 172149124118 bytes

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]+"]"

Explicación:

Defina una biyección por [↔ 1y ]↔ 0. Cualquier disposición de corchetes se puede escribir como un número binario y viceversa, por ejemplo [][]↔ 1010(10) y [[][]]↔ 110100(52). Todos los arreglos válidos de hasta 15 corchetes abiertos (30 corchetes en total) están cubiertos por números de hasta 30 bits (ignorando los ceros iniciales), que son precisamente los números menores que 2 ³¹ .

El primer bucle for da el inverso de esta biyección, convirtiendo un número en una disposición de corchetes, mientras verifica que la disposición sea válida.

Los arreglos no válidos se reemplazan dentro de la declaración de impresión por secuencias largas de corchetes para evitar colisiones. Por ejemplo 11(3) ↔ [[no es válido, por lo que concatenamos 3 + 16 corchetes. Esto asegura que todos los arreglos sean únicos.

La disposición resultante se coloca dentro de un par de soportes para hacer una matriz anidada, de modo que 1010(10) se convierte en [[][]]y 110100(52) se convierte [[[][]]]. El soporte abierto adicional significa que ahora hemos cubierto todos los arreglos con 16 soportes abiertos.

El siguiente programa se puede usar para calcular el número de una matriz dada con hasta 16 corchetes.

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

Python, 153128 bytes

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)

Asignamos un número n a una lista anidada mirando sus dígitos binarios de izquierda a derecha. Este algoritmo funciona para cualquier número, no solo por debajo de 2 ³² .

1. Si el dígito binario actual es un 1, salida [.
2. De lo contrario, si la secuencia de corchetes que hemos generado hasta ahora se equilibraría con un solo corchete de cierre, salida ][.
3. De lo contrario, si este es el último 0 en el número binario, salida ][.
4. De lo contrario salida ].

Finalmente, cerramos los corchetes abiertos.

Cuchara , 63 bytes (501 bits)

000001001001001011001101001010011011111001010001000000101010
101101100110100101101001000101100010001000000100011000010000
000000000000001110111110010000001110110110010100100100100100
000110011010001000000110110000010000001010110011011011011001
000000011010010010010001000000111011011011101001001001000110
110110010100100101011001000100000011010001000000111011011001
010010010010010001101101101001000110110010110001101101101101
100100010001010010001010011011001000000011001101001001010010
000001100101001000111

Este es el siguiente programa de brainfuck convertido en cuchara:

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

Lee un número entero en binario en stdin y genera la lista anidada en stdin. Requiere que se ingrese 0 como la cadena vacía (sin dígitos), y requiere un intérprete de brainfuck con celdas de 8 bits. Mismo algoritmo que mi respuesta de Python.

Versión legible:

-[+[+<]>>+]<+++.           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

Jalea , 28 bytes

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

Este itera sobre todas las cadenas de los personajes [y ]que se inician con una [y al final con una ], verifica si los soportes coinciden, e imprime el n ^º partido.

Pruébalo en línea!

Perl, 80 79 bytes

Nuevamente usa el algoritmo de orlp , pero esta vez primero comprobé si funciona ...

Incluye +1 para -p

Dar el número de entrada en 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 solución de Linus es de 64 bytes en perl:

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

La solución de Dennis es de 59 bytes en perl (cada vez más lenta para grandes números):

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

Python 3, 120 114 bytes

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)

Pruébalo en Ideone .

Cómo funciona

La función definida f toma la entrada n e inicializa k a 0 . Seguiremos incrementando k hasta que n + 1 valores de k den como resultado una salida válida. Cada vez que encontramos dicho valor de k , n disminuye una vez que alcanza -1 , ~nproduce 0 y se imprime la lista r que corresponde al último valor de k .

La asignación parcial de los enteros positivos a las listas anidadas (es decir, k ↦ r ) tiene que ser biyectiva, pero no existen otras restricciones. El utilizado en esta respuesta funciona de la siguiente manera.

1. Convierta k en una representación de cadena binaria, mirando con 0b .

   Por ejemplo, 44 ↦ "0b101100" .

2. Reemplace todos los 0 '(punto de código 48 ) en la representación de cadena con la cadena "]," y todos los 1 ' (punto de código 49 ) con [ .

   Por ejemplo, "0b101100" ↦ "], b [], [[],]," .

3. Elimine los primeros tres caracteres (corresponden a "0b" ) y el carácter final (con suerte una coma).

   Por ejemplo, "], b [], [[],]," ↦ "[], [[],]" .

4. Intenta evaluar el código generado. Si esto resulta en un error, k no se asigna a ninguna lista.

   Por ejemplo, "[], [[],]" ↦ ([], [[]]) .

5. Concatene el resultado (si lo hay) con la lista vacía. Si esto resulta en un error, k no se asigna a ninguna lista.

   Por ejemplo, ([], [[]]) + [] errores ya que + no puede concatenar listas y tuplas.

Haskell, 71 bytes

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

La función principal en la última línea se indexa en una lista de todas las matrices anidadas, ordenadas por tamaño (número de paréntesis abiertos). Entonces, todas las matrices de tamaño como máximo 16 se enumeran primero.

Primero veamos el código que es más agradable y más corto, pero el comprobador de tipos de Haskell se niega a aceptar.

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

La función pen la entrada nproporciona una lista de todas las matrices anidadas de tamaño n(paréntesis abiertos). Esto se hace de forma recursiva. Cada conjunto de este tipo consiste en una cabeza h(primer miembro) de tamaño ky una cola t(otros miembros) de tamaño n-k, ambos tamaños distintos de cero. O es la matriz vacía para el tamaño n==1.

La expresión p=<<[1..]se aplana p(1), p(2), ...en una única lista infinita de todas las matrices ordenadas por tamaño.

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

y la función principal se indexa en él.

... O, lo haría, si Haskell no se quejara de "construir [ing] el tipo infinito: t ~ [t]". Haskell no puede representar la lista infinita arriba cuyos elementos son matrices anidadas arbitrariamente. Todos sus elementos deben tener el mismo tipo, pero un tipo t no puede ser lo mismo que una lista de t. De hecho, a la función en psí no se le puede asignar un tipo coherente sin un tipeo dependiente, del que carece Haskell.

Entonces, en su lugar, trabajamos en cadenas de corchetes, simulando la operación contras actuando sobre [y ]caracteres. Esto toma 9 bytes adicionales. Los peligros del golf en un lenguaje de tipo seguro.

Haskell, 87 82 bytes

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

Emite los elementos de la matriz. Ejemplo de uso: (([0..]>>= \y->y#y)!!) 3-> "[][]".

La función #construye todas las matrices anidadas como cadenas para nabrir y mcerrar paréntesis, al realizar un seguimiento de la cantidad restante de cada una. Siempre comienza con n == m. La función principal llama y # ya cada y <- [0,1,...]y elige el elemento en el índice dado por la entrada.

MATL , 31 bytes

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

Pruébalo en línea! O verifique los primeros casos de prueba (toma unos segundos).

El mapeo producido es:

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

Explicación

El código sigue probando números binarios crecientes, con dígitos 0reemplazados por -1; es decir, usando 1y -1como dígitos. Dígito 1representará '['y -1representará ']'.

El programa cuenta hasta que se hayan obtenido n +1 números válidos . Un número es válido si se cumplen las dos condiciones siguientes:

1. La suma de dígitos es cero (es decir, hay un número igual de 1y -1)
2. La suma acumulativa de dígitos siempre es positiva (es decir, el número acumulado de 1dígitos siempre excede el de -1) excepto al final (donde es cero por la condición 1).

Una vez que se han obtenido n +1 números válidos, el último se transcribe cambiando 1a [y -1dentro ], y luego se muestra.

Código:

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