11

Sudah terkenal, dalam bidang Matematika yang mempelajari ketidakterbatasan, bahwa produk Cartesian dari jumlah terbatas dari set yang dapat dihitung juga dapat dihitung .

Tugas Anda adalah menulis dua program untuk mengimplementasikan ini, satu untuk memetakan dari daftar ke integer, satu untuk memetakan dari integer ke daftar.

Fungsi Anda harus bijektif dan deterministik, artinya 1akan selalu memetakan ke daftar tertentu, dan 2akan selalu memetakan ke daftar tertentu lainnya, dll ...

Sebelumnya , kami memetakan bilangan bulat ke daftar yang hanya terdiri dari 0dan 1.

Namun, sekarang daftar akan terdiri dari angka-angka non-negatif.

Spesifikasi

Program / fungsi, format input / output yang masuk akal.
Apakah bilangan bulat yang dipetakan dimulai 1atau dimulai 0adalah pilihan Anda, artinya 0tidak harus (tetapi mungkin) memetakan apa pun.
Array kosong []harus dikodekan.
Input / output mungkin ada di pangkalan apa pun.
Kode berbagi antara dua fungsi diizinkan .

Mencetak gol

Ini adalah kode-golf . Skor terendah menang.

Skor adalah jumlah panjang (dalam byte) dari dua program / fungsi.

code-golf set-theory Biarawati Bocor
sumber

"Namun, sekarang daftar akan terdiri dari angka-angka non-negatif."

Leaky Nun

Jadi, agar lebih jelas, kita memetakan N^inf -> N?

Mego

@Mego N ^ inf tidak dapat dihitung. N ^ k dengan k adalah angka berhingga mana pun.

Leaky Nun

Kami telah mendiskusikan hal ini dalam obrolan.

Leaky Nun

Apakah itu mulai dari 1 atau mulai dari 0 adalah pilihan Anda. Apakah itu berlaku untuk bilangan bulat tunggal dan bilangan bulat dalam daftar.

Dennis

10

Jelly , 18 16 byte

Daftar ke bilangan bulat, 10 8 byte

TṪạL;³ÆẸ

Peta daftar bilangan bulat non-negatif ke bilangan bulat positif. Cobalah online!

Integer ke daftar, 8 byte

ÆE©Ḣ0ẋ®;

Memetakan bilangan bulat positif ke daftar bilangan bulat non-negatif. Cobalah online!

Latar Belakang

Biarkan p ₀ , p ₁ , p ₂ , ⋯ menjadi urutan bilangan prima dalam urutan menaik.

Untuk setiap daftar bilangan bulat non-negatif A: = [a ₁ , ⋯, a _n ] , kami memetakan A ke p ₀^{z (A)} p ₁^{a ₁} ⋯ p _n^{a _n} , di mana z (A) adalah jumlah membuntuti nol dari A .

Membalik peta di atas dengan mudah. Untuk bilangan bulat positif k , kami memfaktorkannya secara unik sebagai produk dari kekuatan prima berturut-turut n = p ₀^{α ₀} p ₁^{α ₁} ⋯ p _n^{α _n} , di mana α _n > 0 , kemudian merekonstruksi daftar tersebut sebagai [α ₁ , ⋯, α _n ] , menambahkan α ₀ nol.

Bagaimana itu bekerja

Daftar ke bilangan bulat

TṪạL;³ÆẸ  Main link. Argument: A (list of non-negative integers)

T         Yield all indices of A that correspond to truthy (i.e., non-zero) items.
 Ṫ        Tail; select the last truthy index.
          This returns 0 if the list is empty.
   L      Yield the length of A.
  ạ       Compute the absolute difference of the last truthy index and the length.
          This yields the amount of trailing zeroes of A.
    ;³    Prepend the difference to A.
      ÆẸ  Convert the list from prime exponents to integer.

Integer ke daftar

ÆE©Ḣ0ẋ®;  Main link. Input: k (positive integer)

ÆE        Convert k to the list of its prime exponents.
  ©       Save the list of prime exponents in the register.
   Ḣ      Head; pop the first exponent.
          If the list is empty, this yields 0.
    0ẋ    Construct a list of that many zeroes.
      ®;  Concatenate the popped list of exponents with the list of zeroes.

Contoh output

Seratus bilangan bulat positif pertama memetakan ke daftar berikut.

  1: []
  2: [0]
  3: [1]
  4: [0, 0]
  5: [0, 1]
  6: [1, 0]
  7: [0, 0, 1]
  8: [0, 0, 0]
  9: [2]
 10: [0, 1, 0]
 11: [0, 0, 0, 1]
 12: [1, 0, 0]
 13: [0, 0, 0, 0, 1]
 14: [0, 0, 1, 0]
 15: [1, 1]
 16: [0, 0, 0, 0]
 17: [0, 0, 0, 0, 0, 1]
 18: [2, 0]
 19: [0, 0, 0, 0, 0, 0, 1]
 20: [0, 1, 0, 0]
 21: [1, 0, 1]
 22: [0, 0, 0, 1, 0]
 23: [0, 0, 0, 0, 0, 0, 0, 1]
 24: [1, 0, 0, 0]
 25: [0, 2]
 26: [0, 0, 0, 0, 1, 0]
 27: [3]
 28: [0, 0, 1, 0, 0]
 29: [0, 0, 0, 0, 0, 0, 0, 0, 1]
 30: [1, 1, 0]
 31: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 32: [0, 0, 0, 0, 0]
 33: [1, 0, 0, 1]
 34: [0, 0, 0, 0, 0, 1, 0]
 35: [0, 1, 1]
 36: [2, 0, 0]
 37: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 38: [0, 0, 0, 0, 0, 0, 1, 0]
 39: [1, 0, 0, 0, 1]
 40: [0, 1, 0, 0, 0]
 41: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 42: [1, 0, 1, 0]
 43: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 44: [0, 0, 0, 1, 0, 0]
 45: [2, 1]
 46: [0, 0, 0, 0, 0, 0, 0, 1, 0]
 47: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 48: [1, 0, 0, 0, 0]
 49: [0, 0, 2]
 50: [0, 2, 0]
 51: [1, 0, 0, 0, 0, 1]
 52: [0, 0, 0, 0, 1, 0, 0]
 53: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 54: [3, 0]
 55: [0, 1, 0, 1]
 56: [0, 0, 1, 0, 0, 0]
 57: [1, 0, 0, 0, 0, 0, 1]
 58: [0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 59: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 60: [1, 1, 0, 0]
 61: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 62: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 63: [2, 0, 1]
 64: [0, 0, 0, 0, 0, 0]
 65: [0, 1, 0, 0, 1]
 66: [1, 0, 0, 1, 0]
 67: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 68: [0, 0, 0, 0, 0, 1, 0, 0]
 69: [1, 0, 0, 0, 0, 0, 0, 1]
 70: [0, 1, 1, 0]
 71: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 72: [2, 0, 0, 0]
 73: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 74: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 75: [1, 2]
 76: [0, 0, 0, 0, 0, 0, 1, 0, 0]
 77: [0, 0, 1, 1]
 78: [1, 0, 0, 0, 1, 0]
 79: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 80: [0, 1, 0, 0, 0, 0]
 81: [4]
 82: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 83: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 84: [1, 0, 1, 0, 0]
 85: [0, 1, 0, 0, 0, 1]
 86: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 87: [1, 0, 0, 0, 0, 0, 0, 0, 1]
 88: [0, 0, 0, 1, 0, 0, 0]
 89: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 90: [2, 1, 0]
 91: [0, 0, 1, 0, 1]
 92: [0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
 93: [1, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 94: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
 95: [0, 1, 0, 0, 0, 0, 1]
 96: [1, 0, 0, 0, 0, 0]
 97: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
 98: [0, 0, 2, 0]
 99: [2, 0, 0, 1]
100: [0, 2, 0, 0]

Dennis
sumber

Ini brilian.

Leaky Nun

3

Python 2, 88 byte

d=lambda n:map(len,bin(n).split('1')[1:])
e=lambda l:int('1'.join(a*'0'for a in[2]+l),2)

Demo:

>>> for i in range(33):
...     print e(d(i)), d(i)
... 
0 []
1 [0]
2 [1]
3 [0, 0]
4 [2]
5 [1, 0]
6 [0, 1]
7 [0, 0, 0]
8 [3]
9 [2, 0]
10 [1, 1]
11 [1, 0, 0]
12 [0, 2]
13 [0, 1, 0]
14 [0, 0, 1]
15 [0, 0, 0, 0]
16 [4]
17 [3, 0]
18 [2, 1]
19 [2, 0, 0]
20 [1, 2]
21 [1, 1, 0]
22 [1, 0, 1]
23 [1, 0, 0, 0]
24 [0, 3]
25 [0, 2, 0]
26 [0, 1, 1]
27 [0, 1, 0, 0]
28 [0, 0, 2]
29 [0, 0, 1, 0]
30 [0, 0, 0, 1]
31 [0, 0, 0, 0, 0]
32 [5]

Python 2, 130 byte

Berikut adalah solusi yang lebih "efisien" di mana bit-panjang output linear dalam bit-panjang input daripada eksponensial.

def d(n):m=-(n^-n);return d(n/m/m)+[n/m%m+m-2]if n else[]
e=lambda l:int('0'+''.join(bin(2*a+5<<len(bin(a+2))-4)[3:]for a in l),2)

Anders Kaseorg
sumber

Menggunakan algoritme yang sama dengan solusi saya :)

Leaky Nun

@ KennyLau: Saya belum melihat solusi Anda. Mereka terlihat serupa tetapi tidak identik (0s dan 1s ditukar). Dan daftar gagal Anda bolak-balik daftar kosong.

Anders Kaseorg

Begitu ya, terima kasih sudah mengingatkan.

Leaky Nun

Ngomong-ngomong, saya katakan outputnya bisa di pangkalan apa saja .

Leaky Nun

Sejak berbagi kode antara fungsi diperbolehkan, sepertinya Anda hanya dapat membangun emenjadi terbalik untuk d: e=lambda l,i=0:l!=d(i)and-~e(l,i+1).

xnor

1

Python 2, 204 202 byte

p=lambda x,y:(2*y+1<<x)-1
u=lambda n,x=0:-~n%2<1and u(-~n//2-1,x+1)or[x,n//2]
e=lambda l:l and-~reduce(p,l,len(l)-1)or 0
def d(n):
 if n<1:return[]
 r=[];n,l=u(n-1);exec"n,e=u(n);r=[e]+r;"*l;return[n]+r

Bekerja dengan berulang kali menerapkan Z + x Z + <-> Z + bijection, didahului oleh panjang daftar.

0: []
1: [0]
2: [1]
3: [0, 0]
4: [2]
5: [0, 0, 0]
6: [1, 0]
7: [0, 0, 0, 0]
8: [3]
9: [0, 0, 0, 0, 0]
10: [1, 0, 0]
11: [0, 0, 0, 0, 0, 0]
12: [0, 1]
13: [0, 0, 0, 0, 0, 0, 0]
14: [1, 0, 0, 0]
15: [0, 0, 0, 0, 0, 0, 0, 0]
16: [4]
17: [0, 0, 0, 0, 0, 0, 0, 0, 0]
18: [1, 0, 0, 0, 0]
19: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
20: [0, 0, 1]
21: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
22: [1, 0, 0, 0, 0, 0]
23: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
24: [2, 0]
25: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
26: [1, 0, 0, 0, 0, 0, 0]
27: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
28: [0, 0, 0, 1]
29: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
30: [1, 0, 0, 0, 0, 0, 0, 0]
31: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

orlp
sumber

Satu pertanyaan: fungsi mana yang merupakan fungsi "list to integer", dan yang merupakan fungsi "integer to list"?

user48538

@ zyabin101 eadalah list to integer, dadalah integer to list (encode / decode).

orlp

Saya suka solusi ini.

Leaky Nun

0

Retina, 17 + 23 = 40 byte

Dari daftar ke integer:

\d+
$&$*0
^
1

1

Cobalah online!

Dari integer ke daftar:

^1

S`1
m`^(0*)
$.1
¶
<space>

Cobalah online!

Menggunakan Algoritma Kaseorg .

Biarawati Bocor
sumber

Petakan daftar ukuran yang tidak terbatas ke suatu angka!

Spesifikasi

Mencetak gol

Jawaban:

Jelly , 18 16 byte

Daftar ke bilangan bulat, 10 8 byte

Integer ke daftar, 8 byte

Latar Belakang

Bagaimana itu bekerja

Daftar ke bilangan bulat

Integer ke daftar

Contoh output

Python 2, 88 byte

Python 2, 130 byte

Python 2, 204 202 byte

Retina, 17 + 23 = 40 byte