Uma lista de nulos é uma lista que em nenhum nível contém objetos que não sejam da lista. Ou se você preferir uma definição recursiva

• A lista vazia é nula

• Uma lista contendo apenas outras listas de cancelamentos é cancelada.

Todas as listas de nulos têm uma profundidade finita.

Aqui estão alguns exemplos de listas de nulos (usando a sintaxe python):

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

Aqui estão alguns exemplos de coisas que não são listas nulas:

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

Tarefa

Escreva duas funções separadas (ou programas, se preferir). Um deve usar um número inteiro positivo (você também pode incluir zero, se desejar) como argumento e retornar uma lista de nulos; o outro deve usar uma lista de nulos e retornar um número inteiro. Essas duas funções devem sempre ser inversas uma da outra. Ou seja, se você passar a saída para fdentro, gdeverá obter a entrada original fcomo resultado de g. Isso significa que o mapeamento deve ser 1: 1, ou seja, para todo número inteiro, pode existir apenas exatamente uma lista de nulos para a qual gesse número inteiro e para cada lista de nulos deve haver exatamente um número inteiro para o qualf fornece essa lista de nulos.

Você está essencialmente criando uma Bijeção

Você pode optar por usar uma representação de seqüência de caracteres de uma lista de nulos (com ou sem vírgulas e espaços) em vez do tipo de lista nativa do seu idioma.

Pontuação

Sua pontuação será o comprimento de suas duas funções juntas. Isso é código-golfe, então você deve tentar minimizar essa soma.

Pitão, 27 + 29 = 56 bytes

f:

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

Suíte de teste

g:

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

Suíte de teste

O sistema é muito simples: eu gero todas as listas possíveis com não mais que um certo número de ['s. Em seguida, classifico-as de maneira que as listas que ainda não geraram estejam próximas do fim. Tudo isso é feito pela função y, idêntica nos dois programas. Está escrito como

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

Então, indexo nesta lista fe pesquiso nelag .

O número de listas que eu gero é escolhido para ser grande o suficiente para que eu tenha gerado todas as listas possíveis que apareceriam no local ou antes do local desejado na lista de classificação infinita.

Os programas permitem / retornam 0 como uma opção.

Python 2 , 96 bytes

Experimente online! para testar a bijeção.

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

Leva listas nulas a números inteiros não negativos. 42 bytes.

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

Leva números inteiros não negativos para listas nulas. 54 bytes. Uma tentativa mais recursiva deu o mesmo comprimento.

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 o método gusa o método fpara calcular o resultado, percorre a lista de vazios possível até encontrar o igual ao que foi inserido, os bytes de fsão contados duas vezes (já que os dois métodos devem ser capazes de executar sem o outro para esse desafio).

Explicação:

Em geral, o método fsimplesmente percorre todas as representações binárias de números inteiros e aumenta um contador toda vez que um válido é encontrado. As strings binárias válidas para esse desafio estão em conformidade com as seguintes regras: Elas começam com a 1e terminam com a 0; eles têm um número igual de 1s e 0s; e toda vez que você remove o primeiro 1e 0valida o que resta novamente, essas duas regras ainda se aplicam. Depois que o contador é igual à entrada, ele converte a String binária em uma lista de vozes da String, substituindo todas 1por[ e all 0with ].

Quanto ao método g: Começamos com "[]"(representando void-list 0) e depois continuamos usando o método fenquanto aumentamos um número inteiro, até que ele corresponda à string 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`

Exemplos de casos de entrada e saída:

Experimente aqui. (OBSERVAÇÃO: é muito lento para os últimos casos de teste. Levará de 10 a 15 segundos para todos eles.)

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;()]}

Experimente online!

usa a fórmula do exemplo em Bijeção: listas semelhantes a árvores - números naturais

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

Experimente online!

ideia de xnor

Python 3 - sinal / abs, 73 bytes

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

Experimente online!

Implementação direta, suporta números negativos.

O número inteiro ié codificado [sign(i), abs(i)], onde sign(i)=[] if i > 0 else [[]]e abs(i)=[[]] * i, ou seja, uma lista de listas vazias com comprimento abs (i).

Python 3 - binário, 126 bytes

Esta é uma versão mais elaborada (e muito mais longa ...), onde o valor absoluto é codificado em uma representação de lista binária.

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)

Experimente online!

Stax , 33 bytes totais

Esses programas são inversos um do outro. Eles convertem para e de todas as listas de nulos e todos os números inteiros não negativos, de modo que inclui 0. Isso parece ser talvez uma função famosa de algum tipo de álgebra que eu não conheço. Para entender melhor, primeiro implementei os programas como funções em 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

Os programas stax têm o mesmo comportamento.

Inteiro não negativo → Lista de nulos, 15 bytes

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

Execute e depure

Lista de nulos → Número inteiro não negativo, 18 bytes

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

Execute e depure