Una lista vacía es una lista que en ningún nivel contiene objetos que no sean de la lista. O si prefieres una definición recursiva

• La lista vacía es nula

• Una lista que contiene solo otras listas nulas es nula

Todas las listas vacías tienen una profundidad finita.

Aquí hay algunos ejemplos de listas vacías (usando la sintaxis de Python):

[]
[[]]
[[],[]]
[[[]]]
[[[]],[]]
[[],[[]]]

Aquí hay algunos ejemplos de cosas que no son listas nulas:

["a"]
[[...]]
[1]
2
[[],([],[])]

Tarea

Escriba dos funciones separadas (o programas si lo prefiere). Uno debe tomar un entero positivo (también puede incluir cero si lo desea) como argumento y devolver una lista vacía, el otro debe tomar una lista vacía y devolverlo un entero. Estas dos funciones siempre deben ser inversas entre sí. Esto es, si se pasa la salida fen gque debe recibir la entrada original de fcomo resultado de g. Esto significa que la asignación debe ser 1: 1, es decir, para cada número entero, solo puede existir exactamente una lista vacía para la que se gobtiene ese número entero y para cada lista vacía debe haber exactamente un número entero para el que se fobtiene esa lista vacía.

Básicamente estás creando una Biyección

Puede elegir utilizar una representación de cadena de una lista vacía (con o sin comas y espacios) en lugar del tipo de lista nativa de su idioma.

Tanteo

Su puntaje será la duración de sus dos funciones juntas. Este es el código de golf, por lo que debe intentar minimizar esta suma.

Pyth, 27 + 29 = 56 bytes

f:

L?bol`NS{sm[d+d]Y]d)ytb]Y@y

Banco de pruebas

g:

L?bol`NS{sm[d+d]Y]d)ytb]Yxyl`

Banco de pruebas

El sistema es muy simple: genero todas las listas posibles con no más de un cierto número de ['s. Luego, los clasifico de tal manera que las listas que aún no he generado estarían cerca del final. Todo esto lo hace la función y, idéntica en ambos programas. Está escrito como

L?bol`NS{sm[d+d]Y]d)ytb]Y

Luego, indico en esta lista para f y busco en ella g.

El número de listas que genero se elige para que sea lo suficientemente grande como para haber generado todas las listas posibles que aparecerían en o antes de la ubicación deseada en la lista ordenada infinita.

Los programas permiten / devuelven 0 como opción.

Python 2 , 96 bytes

Pruébalo en línea! para probar la biyección.

f=lambda l:len(l)and f(l[0])*2+1<<f(l[1:])

Lleva las listas nulas a enteros no negativos. 42 bytes.

g=lambda n:n*[g]and[g(n/(n&-n)/2)]+g(len(bin(n&-n))-3)

Toma enteros no negativos para anular listas. 54 bytes. Un intento más recursivo dio la misma duración.

g=lambda n,i=0:n*[g]and[g(n/2,i+1),[g(n/2)]+g(i)][n%2]

Java 7, 725 bytes

f(int)( 325 bytes ):

String f(int i){String s="";for(int j=0,e=0;e<i;e+=v(s))s=Integer.toBinaryString(j++);return"["+s.replace("1","[").replace("0","]")+"]";}int v(String s){for(;!s.isEmpty();s=s.replaceFirst("1","").replaceFirst("0",""))if(s.replace("1","").length()!=s.replace("0","").length()|s.charAt(0)<49|s.endsWith("1"))return 0;return 1;}

g(String)( 75 + 325 bytes ):

int g(String s){int r=0;for(String i="10";!i.equals(s);i=f(++r));return r;}

Como el método gusa el método fpara calcular su resultado, recorre la posible lista vacía hasta que encuentra el igual al ingresado, los bytes def se cuentan dos veces (ya que ambos métodos deberían poder ejecutarse sin el otro para este desafío).

Explicación:

En general, el método fsimplemente recorre todas las representaciones de cadenas binarias de enteros y aumenta un contador cada vez que se encuentra uno válido. Las cadenas binarias válidas para este desafío cumplen con las siguientes reglas: comienzan con a 1y terminan con a 0; tienen el mismo número de 1s y 0s; y cada vez que elimine el primero 1y 0valide lo que queda nuevamente, estas dos reglas aún se aplican. Después de que el contador es igual a la entrada, convierte esa cadena binaria en una lista vacía de cadena, reemplazando todas 1con [y todas 0con ].

En cuanto al método g: comenzamos con "[]"(que representa la lista vacía 0), y luego continuamos usando el método fmientras aumentamos un entero, hasta que coincida con la cadena de entrada.

String f(int i){         // Method `f` with integer parameter and String return-type
  String s="";           //  Start with an empty String
  for(int j=0,e=0;e<i;   //  Loop as long as `e` does not equal the input
      e+=v(s))           //    And append increase integer `e` if String `s` is valid
    s=Integer.toBinaryString(j++);
                         //   Change `s` to the next byte-String of integer `j`
                         //  End of loop (implicit / single-line body)
  return"["+             //  Return the result String encapsulated in "[" and "]"
    s.replace("1","[").replace("0","]")+"]";
                         //  after we've replaced all 1s with "[" and all 0s with "]"
}                        // End of method `f`

int v(String s){         // Separate method with String parameter and integer return-type
  for(;!s.isEmpty();     //  Loop as long as String `s` isn't empty
      s=s.replaceFirst("1","").replaceFirst("0",""))
                         //    After each iteration: Remove the first "1" and "0"
    if(s.replace("1","").length()!=s.replace("0","").length()
                         //   If there isn't an equal amount of 1s and 0s
       |s.charAt(0)<49   //   or the String doesn't start with a 1
       |s.endsWith("1")) //   or the String doesn't end with a 0
      return 0;          //    Return 0 (String is not valid)
                         //  End of loop (implicit / single-line body)
  return 1;              //  Return 1 (String is valid)
}                        // End of separate method

int g(String s){         // Method `g` with String parameter and integer return-type
  int r=0;               // Result integer
  for(String i="[]";!i.equals(s);
                         //  Loop as long as `i` does not equal the input String
      i=f(++r));         //   After each iteration: Set `i` to the next String in line
  return r;              //  Return the result integer
}                        // End of method `g`

Ejemplos de casos de entrada y salida:

Pruébalo aquí (NOTA: es bastante lento para los últimos casos de prueba. Tomará alrededor de 10-15 segundos para todos ellos).

0   <-> []
1   <-> [[]]
2   <-> [[][]]
3   <-> [[[]]]
4   <-> [[][][]]
5   <-> [[][[]]]
6   <-> [[[]][]]
7   <-> [[[][]]]
8   <-> [[[[]]]]
9   <-> [[][][][]]
10  <-> [[][][[]]]
11  <-> [[][[]][]]
12  <-> [[][[][]]]
13  <-> [[][[[]]]]
14  <-> [[[]][][]]
50  <-> [[[][[[]]]]]
383 <-> [[[][]][[[][]]]]

K (ngn / k) , 49 bytes

{$[#x;2/,/1,'&:'o'x;0]}
{$[x;o'|-1+-1-':&|2\x;()]}

Pruébalo en línea!

usa la fórmula del ejemplo en Bijection: listas tipo árbol - números naturales

JavaScript (Node.js) , 82 bytes

f=(n,i)=>n?n&1<<i?[f(i),...f(n>>-~i)]:f(n,-~i):[]
g=([a,...b])=>a?g(b)*2+1<<g(a):0

Pruébalo en línea!

idea de xnor

Python 3 - signo / abs, 73 bytes

f=lambda n:[[[]]*(n<0),[[]]*abs(n)]
g=lambda l:[-1,1][not l[0]]*len(l[1])

Pruébalo en línea!

Implementación directa, admite números negativos.

El número entero iestá codificado [sign(i), abs(i)], donde sign(i)=[] if i > 0 else [[]]y abs(i)=[[]] * i, es decir, una lista de listas vacías con longitud abs (i).

Python 3 - binario, 126 bytes

Esta es una versión más elaborada (y mucho más larga ...), donde el valor absoluto se codifica en una representación de lista binaria.

f=lambda n:[[[]]*(n<0),[[[]]*int(i)for i in f"{n:+b}"[1:]]]
g=lambda l:[-1,1][not l[0]]*int(''.join(map(str,map(len,l[1]))),2)

Pruébalo en línea!

Stax , 33 bytes totales

Estos programas son inversos entre sí. Se convierten desde y hacia todas las listas vacías y todos los enteros no negativos, por lo que eso incluye 0. Esto parece ser una función famosa de algún tipo de álgebra que no conozco. Para entenderlo, primero implementé los programas como funciones en python.

def convert_to_void(n):
    lst = []
    while n > 0:
        n -= 1
        choices = len(lst) + 1
        choice = n % choices
        cutpoint = len(lst) - choice
        n //= choices
        newgroup = lst[cutpoint:]
        del lst[cutpoint:]
        lst.append(newgroup)
    return lst

def convert_from_void(lst):
    n = 0
    while lst != []:
        newgroup = lst.pop()
        n *= len(lst) + len(newgroup) + 1
        n += len(newgroup) + 1
        lst.extend(newgroup)
    return n

Los programas stax tienen el mismo comportamiento.

Entero no negativo → Lista vacía, 15 bytes

ƒâ₧~└3BI─¿-rÅ;ì

Ejecutar y depurarlo

Lista vacía → Entero no negativo, 18 bytes

Çäê[!σ`c↑Ö§░NR╥ç=Æ

Ejecutar y depurarlo