Eine Leerenliste ist eine Liste, die auf keiner Ebene Nichtlistenobjekte enthält. Oder wenn Sie eine rekursive Definition bevorzugen

• Die leere Liste ist ungültig

• Eine Liste, die nur andere Leerlisten enthält, ist ungültig

Alle Leerlisten haben eine endliche Tiefe.

Hier einige Beispiele für Void-Listen (mit Python-Syntax):

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

Hier sind einige Beispiele für Dinge, die keine ungültigen Listen sind:

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

Aufgabe

Schreiben Sie zwei separate Funktionen (oder Programme, wenn Sie es vorziehen). Man sollte eine positive Ganzzahl als Argument nehmen (Sie können auch Null einschließen, wenn Sie dies wünschen) und eine leere Liste zurückgeben, der andere sollte eine leere Liste nehmen und eine ganze Zahl zurückgeben. Diese beiden Funktionen sollten immer gegensätzlich sein. Das heißt, wenn Sie die Ausgabe von fan übergeben g, sollten Sie die ursprüngliche Eingabe von fals Ergebnis von erhalten g. Dies bedeutet, dass das Mapping 1: 1 sein muss, dh für jede Ganzzahl darf nur genau eine Leerenliste existieren , für die gdiese Ganzzahl vorliegt , und für jede Leerenliste sollte genau eine Ganzzahl existieren, für die fdiese Leerenliste vorliegt.

Sie erstellen im Wesentlichen eine Bijektion

Sie können eine Zeichenfolgendarstellung einer leeren Liste (mit oder ohne Kommas und Leerzeichen) anstelle des systemeigenen Listentyps Ihrer Sprache verwenden.

Wertung

Ihre Kerbe ist die Länge Ihrer zwei Funktionen zusammen. Dies ist Codegolf, daher sollten Sie versuchen, diese Summe zu minimieren.

Pyth, 27 + 29 = 56 Bytes

f:

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

Testsuite

g:

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

Testsuite

Das System ist sehr einfach: Ich erstelle alle möglichen Listen mit nicht mehr als einer bestimmten Anzahl von [. Dann sortiere ich sie so, dass die Listen, die ich noch nicht erstellt habe, fast fertig sind. Dies alles erledigt die Funktion y, die in beiden Programmen identisch ist. Es ist geschrieben als

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

Dann indiziere ich in dieser Liste nach fund suche darin nachg .

Die Anzahl der von mir erstellten Listen ist so groß gewählt, dass ich alle möglichen Listen erstellt habe, die an oder vor dem gewünschten Ort in der unendlichen sortierten Liste erscheinen würden.

Die Programme erlauben / geben optional 0 zurück.

Python 2 , 96 Bytes

Probieren Sie es online! um die Bijektion zu testen.

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

Verschiebt leere Listen in nicht negative ganze Zahlen. 42 Bytes.

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

Nimmt nicht negative ganze Zahlen in leere Listen auf. 54 Bytes. Ein rekursiverer Versuch ergab die gleiche Länge.

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

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

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

Da die Methode gdie Methode verwendet f, um das Ergebnis zu berechnen, indem sie eine mögliche Leerenliste durchläuft, bis diejenige gefunden wird, die der eingegebenen entspricht, den Bytes vonf zweimal gezählt (da beide Methoden für diese Herausforderung ohne die andere ausgeführt werden sollten).

Erläuterung:

Im Allgemeinen fdurchläuft die Methode einfach alle binären String-Darstellungen von Ganzzahlen und erhöht einen Zähler jedes Mal, wenn ein gültiger gefunden wird. Gültige Binär-Strings für diese Challenge entsprechen den folgenden Regeln: Sie beginnen mit einem 1und enden mit einem 0; Sie haben die gleiche Anzahl von Einsen und Nullen. und jedes Mal , entfernen Sie das erste 1und 0und validieren , was wieder verlassen, werden diese beiden Regeln gelten weiterhin . Nachdem der Zähler der Eingabe entspricht, konvertiert er diesen Binär-String in eine String-Leerenliste, indem er all 1mit [und all 0mit ersetzt] .

Was die Methode betrifft g: Wir beginnen mit "[]"(Darstellung der Leerenliste 0) und verwenden die Methode dann weiter, fwährend eine Ganzzahl erhöht wird, bis sie mit der Eingabezeichenfolge übereinstimmt.

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`

Beispiel für Eingabe- und Ausgabefälle:

Probieren Sie es hier aus. (HINWEIS: In den letzten paar Testfällen ist es ziemlich langsam. Für alle dauert es ungefähr 10-15 Sekunden.)

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

Probieren Sie es online!

Verwendet die Formel aus dem Beispiel in Bijection: Baumähnliche Listen - natürliche Zahlen

JavaScript (Node.js) , 82 Byte

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

Probieren Sie es online!

Xnors Idee

Python 3 - Vorzeichen / Abs, 73 Bytes

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

Probieren Sie es online!

Einfache Implementierung, unterstützt negative Zahlen.

Ganzzahl iwird codiert [sign(i), abs(i)], wobei sign(i)=[] if i > 0 else [[]]undabs(i)=[[]] * i , dh eine Liste leerer Listen mit der Länge abs (i).

Python 3 - binär, 126 Bytes

Dies ist eine aufwändigere Version (und viel länger ...), bei der der absolute Wert in einer binären Listendarstellung codiert ist.

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)

Probieren Sie es online!

Stax , 33 Gesamtbytes

Diese Programme sind gegensätzlich. Sie konvertieren in und aus allen Leerenlisten und allen nicht-negativen Ganzzahlen, also einschließlich 0. Dies scheint eine berühmte Funktion aus einer Art Algebra zu sein, die ich nicht kenne. Um mich darum zu kümmern, habe ich die Programme zunächst als Funktionen in Python implementiert.

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

Die stax-Programme haben das gleiche Verhalten.

Nicht negative Ganzzahl → Leere Liste, 15 Bytes

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

Führen Sie es aus und debuggen Sie es

Ungültigkeitsliste → Nicht negative Ganzzahl, 18 Bytes

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

Führen Sie es aus und debuggen Sie es