Une liste vide est une liste qui, à aucun niveau, ne contient aucun objet non-liste. Ou si vous préférez une définition récursive

• La liste vide est nulle

• Une liste ne contenant que d'autres listes nulles est nulle

Toutes les listes de vides ont une profondeur finie.

Voici quelques exemples de listes de vides (en utilisant la syntaxe python):

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

Voici quelques exemples de choses qui ne sont pas des listes nulles:

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

Tâche

Écrivez deux fonctions distinctes (ou programmes si vous préférez). L'un doit prendre un entier positif (vous pouvez également inclure zéro si vous le souhaitez) comme argument et renvoyer une liste vide, l'autre doit prendre une liste vide et lui retourner un entier. Ces deux fonctions doivent toujours être inverses l'une de l'autre. C'est-à-dire que si vous passez la sortie de fdans, gvous devriez obtenir l'entrée d'origine de fcomme résultat de g. Cela signifie que le mappage doit être de 1: 1, c'est-à-dire que pour chaque entier, il ne peut exister qu'une seule liste de vides pour laquelle gdonne cet entier et pour chaque liste de vides, il devrait y avoir exactement un entier pour qui fdonne cette liste de vides.

Vous créez essentiellement une Bijection

Vous pouvez choisir d'utiliser une représentation sous forme de chaîne d'une liste vide (avec ou sans virgules et espaces) au lieu du type de liste native de votre langue.

Notation

Votre score sera la longueur de vos deux fonctions ensemble. Il s'agit de code-golf , vous devez donc essayer de minimiser cette somme.

Pyth, 27 + 29 = 56 octets

f:

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

Suite de tests

g:

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

Suite de tests

Le système est très simple: je génère toutes les listes possibles avec pas plus d'un certain nombre de [. Ensuite, je les trie de manière à ce que les listes que je n'ai pas encore générées soient presque terminées. Tout cela se fait par la fonction y, identique dans les deux programmes. Il est écrit comme

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

Ensuite, je l'indexe dans cette liste fet la recherche g.

Le nombre de listes que je génère est choisi pour être suffisamment grand pour que j'ai généré toutes les listes possibles qui apparaîtront à ou avant l'emplacement souhaité dans la liste triée infinie.

Les programmes autorisent / renvoient 0 en option.

Python 2 , 96 octets

Essayez-le en ligne! pour tester la bijection.

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

Prend des listes vides à des entiers non négatifs. 42 octets.

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

Prend des entiers non négatifs pour annuler les listes. 54 octets. Une tentative plus récursive a donné la même longueur.

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

Java 7, 725 octets

f(int)( 325 octets ):

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 octets ):

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

Étant donné que la méthode gutilise la méthode fpour calculer son résultat en bouclant sur la liste de vides possible jusqu'à ce qu'elle trouve celui égal à celui entré, les octets de fsont comptés deux fois (car les deux méthodes devraient pouvoir s'exécuter sans l'autre pour ce défi).

Explication:

En général, la méthode fait fsimplement une boucle sur toutes les représentations binaires de chaînes d'entiers et augmente un compteur chaque fois qu'une valeur valide est trouvée. Les chaînes binaires valides pour ce défi sont conformes aux règles suivantes: elles commencent par un 1et se terminent par un 0; ils ont un nombre égal de 1 et de 0; et chaque fois que vous supprimez le premier 1et 0que vous validez ce qui reste, ces deux règles s'appliquent toujours. Une fois que le compteur est égal à l'entrée, il convertit cette chaîne binaire en une liste vide de chaînes, en remplaçant all 1with [et all 0with ].

Quant à la méthode g: nous commençons par "[]"(représentant void-list 0), puis continuons à utiliser la méthode ftout en augmentant un entier, jusqu'à ce qu'il corresponde à la chaîne d'entrée.

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`

Exemples de cas d'entrée et de sortie:

Essayez-le ici. (REMARQUE: C'est assez lent pour les derniers cas de test. Cela prendra environ 10 à 15 secondes pour chacun d'eux.)

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

K (ngn / k) , 49 octets

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

Essayez-le en ligne!

utilise la formule de l'exemple dans Bijection: listes arborescentes - nombres naturels

JavaScript (Node.js) , 82 octets

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

Essayez-le en ligne!

L'idée de xnor

Python 3 - signe / abs, 73 octets

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

Essayez-le en ligne!

Implémentation simple, prend en charge les nombres négatifs.

L'entier iest codé [sign(i), abs(i)], où sign(i)=[] if i > 0 else [[]]et abs(i)=[[]] * i, c'est-à-dire une liste de listes vides de longueur abs (i).

Python 3 - binaire, 126 octets

Il s'agit d'une version plus élaborée (et beaucoup plus longue ...), où la valeur absolue est codée dans une représentation de liste binaire.

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)

Essayez-le en ligne!

Stax , 33 octets au total

Ces programmes sont inverses les uns des autres. Ils se convertissent vers et depuis toutes les listes de vides et tous les entiers non négatifs, donc cela inclut 0. Cela semble être peut-être une fonction célèbre d'une sorte d'algèbre que je ne connais pas. Afin d'envelopper ma tête autour de lui, j'ai d'abord implémenté les programmes en tant que fonctions 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

Les programmes stax ont le même comportement.

Entier non négatif → Liste vide, 15 octets

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

Exécuter et déboguer

Liste des vides → Entier non négatif, 18 octets

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

Exécuter et déboguer