Tugas Anda adalah, mengingat bilangan bulat yang tidak ditandatangani n
, menemukan angka terbesar yang dapat dibuat dengan menghapus satu byte (8 bit berturut-turut) data.
Contoh
Diberi nomor tersebut 7831
, pertama-tama kita mengonversinya menjadi biner (menghapus sembarang nol terkemuka):
1111010010111
Kami kemudian menemukan grup 8 bit berturut-turut yang, ketika dihapus, akan menghasilkan hasil baru terbesar. Dalam hal ini, ada 3 solusi, yang ditunjukkan di bawah ini
1111010010111
^ ^
^ ^
^ ^
Menghapus salah satu dari hasil ini 11111
, yang kemudian kami konversi kembali ke nilai desimal 31
untuk jawabannya.
Uji Kasus
256 -> 1
999 -> 3
7831 -> 31
131585 -> 515
7854621 -> 31261
4294967295 -> 16777215 (if your language can handle 32 bit integers)
Aturan
- Dijamin bahwa panjang bit
n
akan lebih besar dari 8. - Solusi Anda secara teoritis harus bekerja untuk setiap bit
n
lebih besar dari 8, tetapi dalam praktiknya, hanya perlu bekerja untuk bilangan bulat 255 <n <2 16 - Input / Output harus dalam desimal.
- Anda dapat mengirimkan program atau fungsi lengkap.
- Ini adalah kode-golf , jadi program terpendek (dalam byte) menang!
Jawaban:
Jelly , 6 byte
Tautan monadik yang mengambil nomor dan mengembalikan nomor.
Cobalah online!
Bagaimana?
Menggunakan bagus cepat ,
Ƥ
yang dikembangkan oleh mil ...sumber
J , 12 byte
Cobalah online!
sumber
&.
; ini adalah jenis masalah yang sempurna untuk itu.Python 2 , 41 byte
Cobalah online!
sumber
JavaScript (ES6), 54 byte
Bekerja hingga 2 ** 31-1. Karena seseorang meminta jawaban yang agak membingungkan ...
sumber
Pyth , 21 byte
Ini adalah fungsi rekursif (harus dipanggil dengan
y
, atau lihat tautannya).Coba di sini!
sumber
Mathematica, 69 byte
Cobalah online!
Solusi ini berfungsi untuk jumlah besar. Coba online!
-3 byte dari KellyLowder
sumber
Max[c=#~RealDigits~2;Array[Drop[c[[1]],#;;#+7]~FromDigits~2&,Last@c-7]]&
Python 3 ,
686660 byte-2 byte terima kasih kepada Tn. Xcoder!
-4 bytes terima kasih kepada ovs!
-2 byte terima kasih kepada Erik the Outgolfer!
Cobalah online!
sumber
n.bit_length()-8
setara denganlen(bin(n))-10
.Bahasa Wolfram (Mathematica) , 46 byte
Cobalah online!
Versi ini hanya dapat menangani input hingga 2 518 -1, jika tidak kita akan memasuki batas ukuran tumpukan Mathematica. (Batasnya dapat bervariasi antara instalasi Mathematica.) Solusi kedua dalam jawaban ini menghindari itu.
Bagaimana itu bekerja
Pendekatan rekursif berdasarkan logika berikut:
0
untuk setiap input yang kurang dari256
, karena mengeluarkan byte dari angka memakan seluruh angka. Ini adalah kasus dasar kami, itulah sebabnya mengapa disertakan meskipun spesifikasi menjanjikan kami bahwa kami tidak perlu menangani input seperti itu.Max
dua opsi: makan byte terendah (memberi kita input dibagi dengan256
) atau memotong bit terendah, berulang pada integer yang tersisa, dan menambahkan bit terendah kembali ketika kita selesai.Bahasa Wolfram (Mathematica) , 55 byte
Cobalah online!
Versi alternatif yang membangun tabel alih-alih rekursi, sehingga berfungsi untuk angka dengan ukuran berapa pun yang dapat ditangani oleh Mathematica.
sumber
Retina ,
716764 byteCobalah online! Tautan hanya mencakup test case yang lebih cepat, sehingga tidak terlalu membebani server Dennis. Sunting: Disimpan 3 byte berkat @MartinEnder. Penjelasan:
Konversi dari desimal ke biner.
Buat daftar string yang diperoleh dengan menghapus 8 digit berurutan dengan semua cara yang mungkin.
Sortir dalam urutan terbalik dan ambil yang pertama (terbesar).
Konversi kembali ke desimal. (Lihat penjelasan @ MartinEnder .)
sumber
Java (OpenJDK 8) ,
138134 byteCobalah online!
sumber
i.toBinaryString(i)
bisai.toString(i,2)
.ReRegex ,
294275 byteDisimpan 19 byte dengan menggunakan definisi 'fungsi' yang lebih baik
Saya akan mengatakan ini cukup baik untuk bahasa Regex saja.
Lib dasar memang memungkinkan untuk konversi antara Unary dan Desimal (Yang diperlukan sebagai spec tantangan secara eksplisit menyatakan desimal), tetapi tidak mendukung Binary; Jadi saya harus menulis itu sebagai bagian dari skrip yang menambahkan 120 byte ke dalamnya.
Cobalah online!
Dengan Regex Individual.
Tangga
Pertama, kami mengimpor perpustakaan 'basis', yang memberikan dua regex. Yang dikonversi
u<numbers>
menjadi unary. Dan yang bertobatd<unary_underlines>
kembali menjadi desimal. Ini karena tantangannya membutuhkan IO di base10.Kemudian kita mendefinisikan beberapa regex yang mengubah unary menjadi biner.
Yang pertama dari ini,
b(\d*):(_*)\2_b/b1$1:$2b/
mencarib
, secara opsional diikuti oleh beberapa digit biner, lalu a:
, Kemudian jumlah garis bawah, diikuti oleh jumlah garis bawah yang sama persis ditambah satu, dan akhirnya yang lainb
.Kami kemudian menggantinya dengan
b1
diikuti oleh angka-angka biner dari sebelumnya:
,, dan hanya setengah dari garis bawah, dan akhirnya yang terakhirb
.Jadi ini memeriksa jika unary tidak dapat dibagi dua, dan jika demikian, menambahkan 1 ke angka binernya, kemudian membaginya menjadi minus satu per dua.
Yang kedua,
b(\d*):(_+)\2b/b0$1:$2b/
hampir idendis, namun tidak memeriksa untuk tambahan_
, artinya hanya cocok jika dapat dibagi dua, dan dalam hal ini0
sebaliknya menambahkan .Yang ketiga memeriksa apakah kita kehabisan digit unary, dan jika demikian, lepaskan bantalan untuk meninggalkan digit biner.
Yang terakhir memeriksa apakah tidak pernah ada digit biner yang disediakan, dan dalam kasus itu hanya pergi
0
.Kelompok Regex berikutnya yang kami definisikan adalah untuk mengubah biner kembali menjadi unary, dan sedikit lebih sederhana.
Yang pertama dari kelompok ini,
B(_*):1/B$1$1_:/
seperti halnya antitesisnya, mendeteksi aB
, diikuti oleh sejumlah digit Unary, kemudian:1
. Itu tidak memeriksa kecocokanB
dalam kasus ini, karena hanya mencari satu digit pada suatu waktu. Jika ini cocok, itu menggandakan jumlah digit unary yang sebelumnya cocok dan menambahkan satu, lalu menghapus satu.Yang kedua,,
B(_*):0/B$1$1:/
hampir idendisikal dengan yang pertama, kecuali cocok dengan yang0
bukan1
, dan tidak menambahkan digit unary tambahan.Yang terakhir ini,,
B(_*):B/$1/
periksa apakah tidak ada lagi angka biner, dan jika demikian membuka bungkusan yang unary. Tidak seperti antitesisnya, ini tidak memerlukan 0 kasus khusus.Selanjutnya kita mendefinisikan
j
regex, yang bertindak sebagai fungsi pemisahan.Yang pertama,
j(\d*),\1(\d)(\d{7})(\d*):/j$1$2,$1$2$3$4:,B:$1$4B/
lakukan sebagian besar angkat berat. Ia mencarij
, secara opsional diikuti oleh digit biner yang merupakan "incrementer", kemudian koma diikuti oleh incrementer kemudian tepat 8 digit biner diikuti oleh sisa nomor biner, kemudian a:
. Yang pertama dari 8 digit ditambahkan ke incrementer, sehingga menambahnya, lalu semuanya kecuali 8 digit dari input biner ditambahkan setelah:
berikut ini a,
. Jadi (Jika kita menggunakan 2 digit, bukan 8)j,1001:
akan menjadij1:1001:,01
ituj10:1001,01,11
. Selain itu, elemen array yang ditambahkan dibungkus denganB
s, untuk mengubahnya kembali menjadi unary.Yang lain,
j(\d*),\1\d{0,7}:,?(.*)/,$2,/
memeriksa apakah ada kurang dari 8 digit biner yang tersisa untuk memeriksa setelah incrementer, dan jika demikian, menghapus segala sesuatu selain array yang dibungkus dengan,
s. Misalnya.,_,___,
Selama dan setelah pembuatan array, kami mendefinisikan regex perbandingan.
Yang pertama,
,((_+)_+),(\2),/,$1,/
periksa koma diikuti oleh sejumlah garis bawah, lalu beberapa lagi, diikuti oleh koma, lalu jumlah garis bawah pertama, daripada koma. Kemudian menggantinya dengan jumlah total garis bawah pada elemen pertama yang dikelilingi oleh,
s.Yang terakhir,,
,(_+),(\1_*),/,$2,/
memeriksa koma diikuti oleh sejumlah garis bawah diikuti oleh koma lain, kemudian jumlah yang sama atau lebih garis bawah, dan koma terakhir. Ini sebagai gantinya akan meninggalkan elemen yang tepat.Akhirnya, ketika ada pada elemen yang tersisa sehingga cocok
^,(_*),$
, kami menghapus koma sekitarnya dan mengkonversi kembali ke desimal viad<>
. Maka tidak ada lagi regex yang dapat diaktifkan dan hasilnya ditampilkan.Input awalnya ditempatkan ke dalam template
j,b:u<(?#input)>b:
, yang pertama-tama mengubah input desimal menjadi unary, misalnya5
->j,b:_____b:
, kemudian unary yang dihasilkan ke biner,j,101:
Kemudian membelah biner (yang tidak berfungsi misalnya), mendapatkan elemen terbesar, mengkonversi kembali ke desimal, dan selesai.sumber
C (gcc),
91byte-23 byte dari Colera Su
Mendukung hingga
2**31-1
Cobalah online!
Mulai dengan 8 bit rendah
(j=0)
, lalu naik, mengubah output jika jumlah dengan bit yang[j,j+8)
dipotong lebih besar dari arus kita, dan berlanjut sampai x tidak memiliki bit di atasj+8
sumber
x>>j+8
danx>>j+8<<j|x%(1<<j)
dalam variabel (tanda kurung dihapus) akan menguranginya menjadi 68 byte .Jelly , 12 byte
Cobalah online!
Bytes yang disimpan berkat Jonathan Allan !
sumber
JavaScript (ES6),
9491 byte-3 byte terima kasih kepada Justin Mariner
Hanya membuang solusi berbasis string JavaScript, tapi saya berharap seseorang akan memposting solusi berbasis bitwise yang terpisah sehingga saya dapat belajar sesuatu.
Solusi saya secara rekursif mengambil potongan 8-bit dari string, mengambil nilai maksimum yang ditemukan.
Tampilkan cuplikan kode
sumber
+(...)
yang mengkonversi'0b'+c[1]+c[2]
ke nomor, karenaMath.max
sudah melakukannya. Cobalah online! ( spec untuk referensi di masa mendatang )C # (.NET Core) ,
122 + 13 = 135120 + 13 = 133 byteCobalah online!
+13 untuk
using System;
Saya membayangkan ada cara melakukan ini tanpa menggunakan
Convert
. Either way, saya yakin ini bisa dikurangi.Ucapan Terima Kasih
-2 byte terima kasih kepada Kevin Cruijssen
Tidak disatukan
sumber
while
tofor
dan meletakkannyavar b
di dalamnya:for(var b=Convert.ToString(n,2);i<b.Length-7;)
,t
dan tidak menggunakanMath.Max
, tetapi sebagai gantinya memeriksa manual:n=>{int m=0,i=0,t;for(var b=Convert.ToString(n,2);i<b.Length-7;m=t>m?t:m)t=Convert.ToInt32(b.Remove(i++,8),2);return m;}
( 120 + 13 byte )PHP, 67 +1 byte
Jalankan sebagai pipa dengan
-nR
atau coba online .sumber
Pyth, 19 byte
Jawaban alternatif:
Penjelasan:
Jawaban lainnya menggunakan pendekatan yang sama, kecuali bahwa itu berputar pertama kali, dan mendapatkan semua bit kecuali 8 terakhir.
sumber
MATL ,
2321 byteCobalah online!
Sayangnya,
Bn8-:8:!+q&)
hanya menghasilkan irisan yang akan dihapus, bukan sisanya yang ingin kita simpan.sumber
Bn8-:"GB[]@8:q+(XBvX>
(tetapkan[]
dengan(
alih - alih menggunakan&)
, dan ganti&:
dengan:
dan penambahan)Java (OpenJDK 8) , 73 byte
Cobalah online!
sumber
Oktaf ,
8180 byteCobalah online!
Ini adalah solusi berbeda untuk upaya awal saya, menghemat 14 byte lebih lanjut.
Kode dipecah sebagai berikut:
Pada baris keenam jumlah kelompok dihitung dengan menemukan eksponen kekuatan berikutnya dari dua yang lebih besar dari input (jumlah bit dalam jumlah input), dan mengurangi 7 karena kami menghapus 8 bit dari masing-masing kelompok - jumlah yang dihasilkan adalah disimpan di
b
untuk nanti.Kami kemudian menghitung array kekuatan dua di baris kelima yang cukup besar untuk semua grup yang mungkin dapat dihapus. Kami menyimpan ini dalam variabel
c
untuk nanti.Pada baris berikutnya ke atas (baris keempat), kita mengalikan input dengan larik pangkat dua (pada dasarnya bit menggeser setiap nomor ke atas), dan mengonversi hasilnya menjadi biner. Jika kita mengambil contoh 7831, ini menghasilkan array 2D yang berisi:
Jika kemudian kita memotong pusat 8 bit, itu sama dengan menghapus masing-masing kelompok 8 bit. Ini dilakukan oleh baris ketiga.
Array yang dihasilkan dikonversi kembali ke desimal pada baris kedua. Kita juga harus membaginya
c
untuk membatalkan penskalaan yang dilakukan untuk masing-masing kelompok pada awalnya.Akhirnya pada baris pertama fungsi anonim dideklarasikan, dan nilai maksimum dari semua grup dihitung.
nextpow2(x+1)
daripadannz(bin2dec(x))
Upaya asli -
120 9895 byteCobalah online!
Kode ini dibagi sebagai berikut:
Pada dasarnya ia menghitung matriks yang berisi kelompok nilai-nilai yang mungkin dapat dihapus, dan kemudian bekerja yang akhirnya memberikan jumlah terbesar.
Bekerja baris demi baris, baris kelima menghitung kelompok yang bisa dihapus. Misalnya, ambil 7831. Ini adalah angka 13bit, memberikan grup:
Hasil dari baris kelima adalah array logis 2D yang dapat digunakan untuk pengindeksan.
Baris keempat dari kode mengubah input ke array bit (diwakili sebagai karakter '0' dan '1'), dan kemudian mereplikasi
n
-7 kali (n
di mana dalam jumlah bit) memberikan satu baris untuk setiap pengelompokan yang mungkin. Topeng grup di atas digunakan untuk menghapus masing-masing grup yang mungkin.Pada baris ketiga, hasilnya kemudian dibentuk kembali untuk membatalkan perataan yang tidak diinginkan yang dihasilkan dari penerapan topeng grup. Baris kedua mengkonversi kembali ke array angka desimal yang dihasilkan. Dan baris pertama mendefinisikan fungsi anonim menjadi nilai maksimum array dari grup yang mungkin.
sumber
Perl 5 , 78 + 1 (
-p
) = 79 byteCobalah online!
sumber
Ruby , 55 byte
Cobalah online!
sumber
Perl, 53 byte
(itu
use 5.10.1
untuk membawa perl ke level bahasa 5.10.1 gratis)Berikan nomor input pada STDIN. Akan kehabisan memori untuk nomor besar, tetapi nomor 32-bit dalam input belum menjadi masalah
sumber