Dobrze wiadomo, w dziedzinie matematyki badającej nieskończoność, że iloczyn kartezjański dowolnej skończonej liczby zbiorów policzalnych jest również policzalny .
Twoim zadaniem jest napisanie dwóch programów, które to zaimplementują, jednego do mapowania z listy na liczbę całkowitą, jednego do mapowania z liczby całkowitej na listę.
Twoja funkcja musi być bijectywna i deterministyczna, co oznacza, że 1
zawsze będzie mapowana na określoną listę i 2
zawsze będzie mapowana na inną określoną listę itp.
Wcześniej zamapowaliśmy liczby całkowite na listę składającą się wyłącznie z 0
i 1
.
Jednak teraz lista będzie się składać z liczb nieujemnych.
Okular
- Program / funkcja, rozsądny format wejścia / wyjścia.
- Niezależnie od tego, czy zmapowane liczby całkowite zaczynają się,
1
czy zaczynają od0
ciebie, zależy od ciebie, co oznacza, że0
nie musisz (ale może) mapować do niczego. - Pusta tablica
[]
musi być zakodowana. - Wejście / wyjście może być w dowolnej bazie.
- Udostępnianie kodu między dwiema funkcjami jest dozwolone .
Punktacja
To jest golf golfowy . Najniższy wynik wygrywa.
Wynik jest sumą długości (w bajtach) dwóch programów / funkcji.
źródło
N^inf -> N
?Odpowiedzi:
Galaretka ,
1816 bajtówLista do liczb całkowitych,
108 bajtówOdwzorowuje listy liczb całkowitych nieujemnych na liczby całkowite dodatnie. Wypróbuj online!
Liczba całkowita do listy, 8 bajtów
Mapuje dodatnie liczby całkowite na listy liczb całkowitych nieujemnych. Wypróbuj online!
tło
Niech p 0 , p 1 , p 2 , ⋯ będą ciągiem liczb pierwszych w porządku rosnącym.
Dla każdej listy liczb całkowitych nieujemnych A: = [a 1 , ⋯, a n ] , odwzorowujemy A na p 0 z (A) p 1 a 1 ⋯ p n a n , gdzie z (A) jest liczbą końcowe zera z A .
Odwrócenie powyższej mapy w prosty sposób. Dla dodatniej liczby całkowitej k rozkładamy ją jednoznacznie jako iloczyn kolejnych sił pierwszych n = p 0 α 0 p 1 α 1 ⋯ p n α n , gdzie α n > 0 , a następnie rekonstruujemy listę jako [α 1 , ⋯, α n ] , dodanie α 0 zerami.
Jak to działa
Lista do liczby całkowitej
Liczba całkowita do listy
Przykładowe dane wyjściowe
Pierwsze sto dodatnich liczb całkowitych mapuje na następujące listy.
źródło
Python 2, 88 bajtów
Próbny:
Python 2, 130 bajtów
Oto bardziej „wydajne” rozwiązanie, w którym długość bitu wyjścia jest liniowa na długości bitu wejścia, a nie wykładnicza.
źródło
e
się odwrotność dlad
:e=lambda l,i=0:l!=d(i)and-~e(l,i+1)
.Python 2,
204202 bajtyDziała poprzez wielokrotne stosowanie bijectcji Z + x Z + <-> Z +, poprzedzone długością listy.
źródło
e
jest listą do liczby całkowitej,d
jest liczbą całkowitą do listy (kodowanie / dekodowanie).Siatkówka, 17 + 23 = 40 bajtów
Z listy do liczby całkowitej:
Wypróbuj online!
Od liczby całkowitej do listy:
Wypróbuj online!
Wykorzystuje algorytm Kaseorga .
źródło