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
9
adalah1001
dalam biner sehingga memiliki 21
bit.
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:
Sambil menambahkan nol ke ujung polinomial tidak mengubah nilainya:
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:
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 kode-golf sehingga jawaban akan dicetak dalam byte, dengan lebih sedikit byte yang lebih baik.
[]
atau[0]
input yang valid?Jawaban:
Jelly , 8 byte
Cobalah online!
Inversi kiri, 5 byte
Cobalah online!
Bagaimana itu bekerja
sumber
Bahasa Wolfram (Mathematica) ,
3620 byteCobalah 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:
sumber
Bahasa Wolfram (Mathematica) , 61 byte
Cobalah online!
Dua bilangan bulat positif dapat dipetakan ke bilangan bulat positif tunggal. Membiarkan
a, b
menjadi dua bilangan bulat positif. Kemudiana, b -> (2a - 1) 2^(b-1)
adalah bijection dari NxN ke N.Fungsi ini menemukan posisi semua
1
bit 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:
Fungsi terbalik (124 byte)
Inilah fungsi terbalik untuk menguji injeksi.
Cobalah online!
sumber
Python 2 ,
118117114103100 byte100 byte oleh Jonathan Frech:
Cobalah online!
103 byte dengan kemungkinan bermain golf 1
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 gantib
dengan2
.1 Saya bisa menyimpan 14 byte dengan mengubahnya menjadi nomor basis-12 sebagai gantinya, tetapi TIO kehabisan memori jadi saya memutuskan untuk menggunakan ini.
sumber
05AB1E , 14 byte
Cobalah online!
Menghasilkan hasil yang sama dengan larutan Dennis 'Jelly, namun tekniknya sedikit berbeda.
Bagaimana?
Mari kita coba inputnya
[1, 2, 3]
:sumber
Python 2 , 74 byte
Cobalah online!
sumber
JavaScript 6,
9683 Bytesmenghasilkan ekspresi biner
sumber
replace(/0|2/g,0)
tampaknya juga berfungsi, tetapi lebih sulit untuk memecahkan kodex=>(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