Lista nieważnych jest listą, która na żadnym poziomie nie zawiera żadnych obiektów nie będących listami. Lub jeśli wolisz definicję rekurencyjną

• Pusta lista jest nieważna

• Lista zawierająca tylko inne listy nieważnych jest nieważna

Wszystkie listy pustek mają skończoną głębokość.

Oto kilka przykładów pustych list (przy użyciu składni python):

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

Oto kilka przykładów rzeczy, które nie są pustymi listami:

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

Zadanie

Napisz dwie oddzielne funkcje (lub programy, jeśli wolisz). Jedna powinna przyjąć dodatnią liczbę całkowitą (możesz również podać zero, jeśli chcesz) jako argument i zwrócić listę nieważnych, druga powinna wziąć listę nieważnych i zwrócić ją jako liczbę całkowitą. Te dwie funkcje powinny zawsze być odwrotnymi względem siebie. To znaczy, jeśli przekazujesz wyjście fdo g, powinieneś otrzymać oryginalne wejście fw wyniku g. Oznacza to, że mapowanie musi wynosić 1: 1, tzn. Dla każdej liczby całkowitej może istnieć tylko jedna lista nieważności, dla której gta liczba całkowita jest określona, ​​a dla każdej listy nieważności powinna istnieć dokładnie jedna liczba całkowita, dla której fta lista nieważności.

Zasadniczo tworzysz Bijection

Możesz wybrać ciąg znaków reprezentujący pustą listę (z przecinkami lub spacjami lub bez nich) zamiast rodzimego typu listy języków.

Punktacja

Twój wynik będzie równy długości twoich dwóch funkcji razem. To jest golf golfowy, więc powinieneś dążyć do zminimalizowania tej sumy.

Pyth, 27 + 29 = 56 bajtów

f:

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

Zestaw testowy

g:

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

Zestaw testowy

System jest bardzo prosty: generuję wszystkie możliwe listy z nie więcej niż określoną liczbą [. Następnie sortuję je w taki sposób, aby listy, których jeszcze nie wygenerowałem, były blisko końca. Wszystko to wykonuje funkcja yidentyczna w obu programach. Jest napisane jako

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

Następnie indeksuję tę listę fi wyszukuję ją g.

Liczba generowanych przeze mnie list jest tak duża, że ​​wygenerowałem wszystkie możliwe listy, które pojawią się w lub przed żądaną lokalizacją na nieskończonej posortowanej liście.

Programy dopuszczają / zwracają 0 jako opcję.

Python 2 , 96 bajtów

Wypróbuj online! przetestować bijection.

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

Usuwa listy nieujemnych liczb całkowitych. 42 bajty.

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

Bierze nieujemne liczby całkowite do unieważnienia list. 54 bajty. Bardziej rekurencyjna próba dała tę samą długość.

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

Java 7, 725 bajtów

f(int)( 325 bajtów ):

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 bajtów ):

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

Ponieważ metoda gużywa metody fdo obliczenia wyniku, zapętlając nad możliwą listą pustek, aż znajdzie jeden równy wprowadzonemu, bajty z fsą liczone dwukrotnie (ponieważ obie metody powinny być w stanie działać bez drugiej dla tego wyzwania).

Wyjaśnienie:

Ogólnie metoda fpo prostu zapętla wszystkie binarne reprezentacje ciągu liczb całkowitych i zwiększa licznik za każdym razem, gdy zostanie znaleziona poprawna. Prawidłowe ciągi binarne dla tego wyzwania są zgodne z następującymi zasadami: zaczynają się na 1, a kończą na 0; mają taką samą liczbę 1 i 0; i za każdym razem, gdy usuniesz pierwszy 1i 0ponownie zweryfikujesz to, co zostało, te dwie reguły nadal obowiązują. Po licznik jest równy wkład, to zamienia to binarny string na ciąg pustych liście, zastępując wszystko 1z [a wszystko 0z ].

Jeśli chodzi o metodę g: zaczynamy od "[]"(reprezentuje listę pustek 0), a następnie kontynuujemy używanie metody f, zwiększając liczbę całkowitą, aż do dopasowania ciągu wejściowego.

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`

Przykładowe przypadki wejścia i wyjścia:

Wypróbuj tutaj. (UWAGA: w ostatnich kilku przypadkach testowych jest dość wolny. Dla wszystkich zajmie to około 10-15 sekund.)

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

K (ngn / k) , 49 bajtów

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

Wypróbuj online!

używa wzoru z przykładu w Bijection: listy drzewiaste - liczby naturalne

JavaScript (Node.js) , 82 bajty

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

Wypróbuj online!

pomysł xnora

Python 3 - znak / abs, 73 bajty

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

Wypróbuj online!

Prosta implementacja, obsługuje liczby ujemne.

Liczba całkowita ijest zakodowana [sign(i), abs(i)], gdzie sign(i)=[] if i > 0 else [[]]i abs(i)=[[]] * itj. Lista pustych list o długości abs (i).

Python 3 - binarny, 126 bajtów

Jest to bardziej rozbudowana wersja (i znacznie dłużej ...), w której wartość bezwzględna jest zakodowana w reprezentacji listy binarnej.

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)

Wypróbuj online!

Stax , 33 bajtów ogółem

Te programy są odwrócone względem siebie. Konwertują do i ze wszystkich pustych list i wszystkich nieujemnych liczb całkowitych, więc zawiera 0. Wygląda na to, że jest to może znana funkcja z jakiejś algebry, której nie znam. Aby owinąć głowę, najpierw zaimplementowałem programy jako funkcje w Pythonie.

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

Programy stax mają takie samo zachowanie.

Nieujemna liczba całkowita → Lista pustych, 15 bajtów

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

Uruchom i debuguj

Lista pustek → Nieujemna liczba całkowita, 18 bajtów

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

Uruchom i debuguj