Daftar kosong adalah daftar yang pada level mana pun tidak berisi objek yang tidak ada dalam daftar. Atau jika Anda lebih suka definisi rekursif

• Daftar kosong tidak valid

• Daftar yang hanya berisi daftar kosong lainnya tidak berlaku

Semua daftar kosong memiliki kedalaman yang terbatas.

Berikut ini beberapa contoh daftar kosong (menggunakan sintaksis python):

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

Berikut adalah beberapa contoh hal-hal yang bukan daftar batal:

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

Tugas

Tulis dua fungsi terpisah (atau program jika Anda mau). Satu harus mengambil bilangan bulat positif (Anda juga dapat memasukkan nol jika Anda mau) sebagai argumen dan mengembalikan daftar kosong yang lain harus mengambil daftar kosong dan mengembalikannya bilangan bulat. Dua fungsi ini harus selalu menjadi invers satu sama lain. Itu adalah jika Anda melewatkan output fke gAnda harus mendapatkan input asli fsebagai hasil g. Ini berarti pemetaan harus 1: 1, yaitu untuk setiap bilangan bulat, mungkin hanya ada tepat satu daftar kosong yang gmemberikan bilangan bulat itu dan untuk setiap daftar batal harus ada tepat satu bilangan bulat yang fmemberikan daftar batal itu.

Anda pada dasarnya menciptakan sebuah Bijection

Anda dapat memilih untuk menggunakan representasi string dari daftar kosong (dengan atau tanpa koma dan spasi) daripada jenis daftar asli bahasa Anda.

Mencetak gol

Skor Anda akan menjadi panjang dari dua fungsi Anda bersama-sama. Ini adalah kode-golf sehingga Anda harus berusaha meminimalkan jumlah ini.

Pyth, 27 + 29 = 56 byte

f:

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

Suite uji

g:

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

Suite uji

Sistem ini sangat sederhana: Saya menghasilkan semua daftar yang mungkin dengan tidak lebih dari jumlah tertentu [. Kemudian, saya mengurutkannya sedemikian rupa sehingga daftar yang belum saya buat akan mendekati akhir. Ini semua dilakukan oleh fungsi y, identik di kedua program. Itu ditulis sebagai

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

Kemudian, saya mengindeks ke dalam daftar ini untuk f, dan mencari melalui itu g.

Jumlah daftar yang saya hasilkan dipilih untuk menjadi cukup besar sehingga saya telah menghasilkan semua daftar yang mungkin muncul pada atau sebelum lokasi yang diinginkan dalam daftar diurutkan tak terhingga.

Program memungkinkan / mengembalikan 0 sebagai opsi.

Python 2 , 96 byte

Cobalah online! untuk menguji bijection.

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

Membawa daftar batal ke bilangan bulat non-negatif. 42 byte

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

Membawa bilangan bulat tidak negatif ke daftar batal 54 byte Upaya yang lebih rekursif memberi panjang yang sama.

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

Java 7, 725 byte

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;}

Karena metode gmenggunakan metode funtuk menghitung hasilnya dengan mengulangi daftar kosong yang mungkin sampai menemukan yang sama dengan yang diinput, byte fdihitung dua kali (karena kedua metode harus dapat berjalan tanpa yang lain untuk tantangan ini).

Penjelasan:

Secara umum, metode fhanya mengulangi semua representasi String biner dari bilangan bulat, dan menambah penghitung setiap kali ditemukan valid. String biner yang valid untuk tantangan ini mematuhi aturan berikut: Mereka mulai dengan a 1, dan diakhiri dengan a 0; mereka memiliki jumlah 1s dan 0s yang sama; dan setiap kali Anda menghapus pertama 1dan 0dan memvalidasi apa yang tersisa lagi, dua aturan ini masih berlaku. Setelah penghitung sama dengan input, itu mengkonversi biner-String ke daftar string-kosong, dengan mengganti semua 1dengan [dan semua 0dengan ].

Adapun metode g: Kita mulai dengan "[]"(mewakili void-list 0), dan kemudian melanjutkan menggunakan metode fsambil meningkatkan integer, sampai cocok dengan input-String.

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`

Contoh input & output kasus:

Coba di sini. (CATATAN: Cukup lambat untuk beberapa kasus uji terakhir. Akan memakan waktu sekitar 10-15 detik untuk semuanya).

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

K (ngn / k) , 49 byte

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

Cobalah online!

menggunakan rumus dari contoh di Bijection: daftar mirip pohon - bilangan asli

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

Cobalah online!

Gagasan utama

Python 3 - masuk / abs, 73 byte

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

Cobalah online!

Implementasi lurus ke depan, mendukung angka negatif.

Integer idikodekan [sign(i), abs(i)], di mana sign(i)=[] if i > 0 else [[]]dan abs(i)=[[]] * i, yaitu daftar daftar kosong dengan panjang abs (i).

Python 3 - biner, 126 byte

Ini adalah versi yang lebih rumit (dan lebih lama ...), di mana nilai absolut dikodekan dalam representasi daftar biner.

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)

Cobalah online!

Stax , total 33 byte

Program-program ini adalah kebalikan dari satu sama lain. Mereka mengonversi ke dan dari semua daftar kosong dan semua bilangan bulat non-negatif, sehingga termasuk 0. Ini sepertinya merupakan fungsi yang terkenal dari beberapa jenis aljabar yang saya tidak tahu. Untuk membungkus kepala saya, saya pertama kali mengimplementasikan program sebagai fungsi dalam 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

Program stax memiliki perilaku yang sama.

Integer non-negatif → Daftar kosong, 15 byte

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

Jalankan dan debug itu

Daftar kosong → Bilangan bulat non-negatif, 18 byte

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

Jalankan dan debug itu