Hotel biner Hilbert

18

Dalam tantangan ini, Anda akan diminta untuk mengimplementasikan fungsi apa pun (atau program lengkap) yang memenuhi dua properti. Properti itu adalah:

  • Fungsi Anda harus berupa fungsi injektif (reversibel) dari polinomial dengan koefisien bilangan bulat non-negatif ke bilangan bulat non-negatif. Ini berarti tidak ada dua input yang tidak sama dapat memetakan ke output yang sama.

  • Fungsi Anda harus mempertahankan jumlah total "pada bit" dari input ke outputnya. Ini berarti jika Anda menghitung 1 bit dari setiap koefisien polinomial, jumlah mereka harus sama dengan jumlah 1 bit dalam representasi biner dari output. Misalnya 9adalah 1001dalam biner sehingga memiliki 2 1bit.


IO

Polinomial integer non-negatif sama dengan daftar tak terbatas dari integer non-negatif sehingga setelah titik tertentu semua bilangan bulat adalah nol. Dengan demikian, polinomial dapat direpresentasikan baik oleh daftar yang tidak terbatas (walaupun ini mungkin tidak diinginkan) atau oleh daftar terbatas dengan nol implisit setelah akhir daftar.

Perbedaan utama antara polinomial dan daftar terbatas adalah menambahkan nol di akhir daftar akan mengubah daftar:

Daftar

Sambil menambahkan nol ke ujung polinomial tidak mengubah nilainya:

Polinomial

Jadi, jika fungsi Anda mengambil daftar terbatas yang merepresentasikan polinomial sebagai input, menambahkan nol tidak boleh mengubah hasilnya.

Saat merepresentasikan polinomial sebagai daftar, Anda dapat merepresentasikannya dengan entri pertama atau terakhir yang mewakili istilah konstan. Misalnya, Anda dapat memiliki salah satu dari kemungkinan berikut ini:

Maju atau mundur

Dalam kasus pertama, menambahkan nol ke akhir daftar tidak boleh mengubah hasilnya; dalam kasus kedua, menambahkan nol di bagian depan daftar tidak boleh mengubah hasilnya.

Tentu saja jika bahasa Anda mendukung polinomial, Anda dapat mengambilnya sebagai masukan.

Output harus berupa output integer non-negatif melalui metode standar apa pun.


Ini adalah sehingga jawaban akan dicetak dalam byte, dengan lebih sedikit byte yang lebih baik.

Wisaya Gandum
sumber
Apakah []atau [0]input yang valid?
JungHwan Min
1
@JungHwanMin Ya, keduanya, mereka adalah nol polinomial.
Wheat Wizard
Saya tahu Anda bermaksud menempatkan 1 untuk membagi nol, tetapi beberapa cara mungkin berhasil dan tampaknya tidak begitu bagus ...
l4m2
1
@ l4m2 Maaf, tapi saya tidak mengerti salah satu dari komentar Anda. Sejauh pertanyaan Anda, memimpin nol pada apa? Polinomial, koefisiennya? Saya juga tidak yakin apa yang Anda maksud dengan "nol tidak tertulis".
Wheat Wizard
1
Apakah gambar benar-benar diperlukan (yaitu mereka tidak dapat direpresentasikan menggunakan teks kaya) ??? Karena orang tanpa kemampuan untuk melihat gambar tidak dapat melihat tantangan Anda secara keseluruhan.
Mindwin

Jawaban:

6

Jelly , 8 byte

BFṢḄæ«ÆẸ

Cobalah online!

Inversi kiri, 5 byte

Bċ0ÆE

Cobalah online!

Bagaimana itu bekerja

BFṢḄæ«ÆẸ  Main link. Argument: A (array)

B         Binary; convert each integer in A to base 2.
 F        Flatten; concatenate the resulting binary arrays.
  Ṣ       Sort the resulting bit array.
   Ḅ      Convert from base 2 to integer, yielding an integer x with as much set
          bits as there are set bits in A.
      ÆẸ  Unexponents; convert A = [a1, a2, ...] to y = (p1**a1 + p2**a2 + ...),
          where pn is the n-th prime number.
          By the fundamental theorem of arithmetic, the resulting integer is unique
          for each array A without trailing zeroes.
    æ«    Bitshift left; compute x * 2**y.
Dennis
sumber
6

Bahasa Wolfram (Mathematica) , 36 20 byte

x#/.x->2^(#/.x->2)!&

Cobalah online!

Mengambil polinom f (x) sebagai input. Mengevaluasi y * f (y), di mana y = 2 ^ (f (2)!). Sayangnya, ini berarti bahwa output menjadi cukup besar.

Mengevaluasi y * f (y) akan mempertahankan jumlah 1-bit setiap kali y adalah kekuatan 2 lebih besar dari koefisien apa pun, yang berlaku untuk nilai yang dipilih di atas. Kami memilih y = 2 ^ (f (2)!) Untuk membuat hasil injeksi:

  • Dua input berbeda dengan nilai y yang sama akan memberikan output yang berbeda karena pada dasarnya kita membaca dua angka berbeda pada basis y.
  • Jika kita memperbaiki k = f (2) dan oleh karena itu y, nilai terkecil dari y * f (y) dicapai ketika input polinomial konstan sama dengan k dan nilai terbesar dicapai ketika input polinomial memberikan basis -2 ekspansi k. Dalam kasus pertama, y ​​* f (y) = 2 ^ (k!) * K, dan dalam kasus kedua, y * f (y) <2 ^ (k! * Ceil (lg k)), yang kurang dari 2 ^ ((k + 1)!) * (k + 1).
  • Akibatnya, untuk dua polinomial f dan g dengan f (2) <g (2), bilangan bulat yang kita dapatkan dari f akan lebih kecil dari bilangan bulat yang kita dapatkan dari g.
Misha Lavrov
sumber
5

Bahasa Wolfram (Mathematica) , 61 byte

Tr[2^((2#2-1)2^#)&@@@Position[Reverse/@#~IntegerDigits~2,1]]&

Cobalah online!

Dua bilangan bulat positif dapat dipetakan ke bilangan bulat positif tunggal. Membiarkan a, bmenjadi dua bilangan bulat positif. Kemudian a, b -> (2a - 1) 2^(b-1)adalah bijection dari NxN ke N.

Fungsi ini menemukan posisi semua 1bit dalam input (dari tempat 1s), dan menerapkan varian hanya suntik dari peta di atas untuk setiap posisi. Kemudian, setiap angka yang dihasilkan dinaikkan menjadi kekuatan dua, dan semua angka ditambahkan bersama-sama (yang tidak apa-apa karena kami menerapkan NxN injeksi -> N peta).

Sebagai contoh:

{1, 2, 3}
{{1}, {1, 0}, {1, 1}}             (* Convert to binary *)
{{1}, {0, 1}, {1, 1}}             (* Reverse each *)
{{1, 1}, {2, 2}, {3, 1}, {3, 2}}  (* Position of 1s *)
{2, 12, 8, 24}                    (* Inject to N *)
{4, 4096, 256, 16777216}          (* Raise to the power of 2 *)
16781572                          (* Add *)

Fungsi terbalik (124 byte)

##+#&~Fold~#&@*Reverse/@Normal@SparseArray[{Log2[j=#~BitAnd~-#],(#/j+1)/2}->1&@@@(Reverse[#~IntegerDigits~2]~Position~1-1)]&

Inilah fungsi terbalik untuk menguji injeksi.

Cobalah online!

JungHwan Min
sumber
5

Python 2 , 118 117 114 103 100 byte

100 byte oleh Jonathan Frech:

a=input()
while a[0]<1:a.pop(0)
y="".join("2"+bin(v)[2:]for v in a)
print~-2**y.count("1")<<int(y,3)

Cobalah online!

103 byte dengan kemungkinan bermain golf 1

a=input()
while a[0]<1:a.pop(0)
x="".join(map(bin,a))
print~-(1<<x.count("1"))<<int(x.replace(*"b2"),3)

Cobalah online!

-15 byte terima kasih kepada Jonathan Frech

Ini menciptakan angka yang pertama berisi "pada bit" dan kemudian representasi unary dari array yang ditafsirkan sebagai angka trinary.

Nomor trinary dibuat dengan mengonversi angka ke string biner ( 0bNNN), lalu ganti bdengan 2.

1 Saya bisa menyimpan 14 byte dengan mengubahnya menjadi nomor basis-12 sebagai gantinya, tetapi TIO kehabisan memori jadi saya memutuskan untuk menggunakan ini.

fergusq
sumber
@JonathanFrech Terima kasih banyak :)
fergusq
1

05AB1E , 14 byte

gÅpImPoIbS{2β*

Cobalah online!

Menghasilkan hasil yang sama dengan larutan Dennis 'Jelly, namun tekniknya sedikit berbeda.

Bagaimana?

Mari kita coba inputnya [1, 2, 3] :

gÅpImPoIbS{2β* | Full program.
               | STACK: [[1, 2, 3]]
               |
g              | Push the length.
               | STACK: [3]
 Åp            | Generate the first N primes.
               | STACK: [[2, 3, 5]]
   Im          | Push the input, and apply pairwise exponentiation.
               | STACK: [2, 9, 125]
     P         | Push the product.
               | STACK: 2250
      o        | Push 2 ** N.
               | STACK: 2 ** 2250 (way too large)
       Ib      | Push the input and convert to binary.
               | STACK: [2 ** 2250, ['1', '10', '11']].
         S{    | Sort all the characters.
               | STACK: [2 ** 2250, ['0', '1', '1', '1', '1']]
           2β  | Convert from binary.
               | STACK: [2 ** 2250, 15]
             * | Multiplication.
               | STACK: [2 ** 2250 * 15]
               | Implicitly print the top of the stack (2 ** 2250 * 15).
Tuan Xcoder
sumber
1

Python 2 , 74 byte

r='print 0';s='<<'
for n in input():r+=oct(n)[:0:-1];s+='0'+'1'*n
exec r+s

Cobalah online!

Dennis
sumber
0

JavaScript 6, 96 83 Bytes

x=>(t=x.map(k=>(x[0]+=k)&&2+k.toString(2)).join``).replace(/0|2/g,'')+'0'.repeat(t)

menghasilkan ekspresi biner

([1,2]) => 3*2^21210(Decimal)
([0,1,2]) => 3*2^21210
([1,2,0]) => 3*2^2121020
([1,2,3,4]) => 31*2^212102112100(Threotically)
l4m2
sumber
nol akan mengarah ke string kosong yang mewakili nol
l4m2
replace(/0|2/g,0)tampaknya juga berfungsi, tetapi lebih sulit untuk memecahkan kode
l4m2
Tidak yakin tentang itu x=>(t=x.map(k=>(x[0]+=k)&&2+k.toString(2)).join``).replace(/2/g,'0'.repeat(t)). Merasa baik-baik saja tetapi tidak dapat membuktikan
l4m2