Untuk menemukan kekerasan digital dari sebuah bilangan bulat, ambil representasi binernya, dan hitung berapa kali sebuah leading dan trailing
1
dapat dihilangkan sampai ia memulai atau diakhiri dengan a0
. Jumlah total bit yang dihapus adalah kekerasan digitalnya.
Itu penjelasan yang cukup bertele-tele - jadi mari kita uraikan dengan contoh yang berhasil.
Untuk contoh ini, kita akan menggunakan nomor 3167. Dalam biner, ini adalah:
110001011111
(Perhatikan bahwa, selama konversi ke biner, Anda harus memastikan untuk menghapus nol di depan)
Itu tidak dimulai atau diakhiri dengan 0
, jadi kami menghapus 1 pasang bit:
1 1000101111 1
Dan satu lagi:
11 00010111 11
Tapi sekarang ada 0 di awal, jadi kami tidak bisa menghapus 1
pasangan lagi . Secara total, 4 bit kami lepaskan, dan 4 adalah kekerasan digital 3167.
Namun, untuk angka yang dapat ditulis sebagai 2 n -1 untuk n positif (yaitu hanya berisi 1
dalam representasi biner), 0 tidak akan pernah tercapai, dan dengan demikian semua bit dapat dihapus. Ini berarti bahwa kekerasan hanyalah panjang bit bilangan bulat.
Tantangan
Tugas Anda adalah menulis program atau fungsi yang, diberi bilangan bulat non-negatif n >= 0
, menentukan kekerasan digitalnya.
Anda dapat mengirimkan program lengkap yang menjalankan I / O, atau fungsi yang mengembalikan hasilnya. Kiriman Anda harus berfungsi untuk nilai-nilai n
dalam rentang integer standar bahasa Anda.
Uji Kasus
Harap beri tahu saya jika ada yang salah, atau jika Anda ingin menyarankan case edge untuk ditambahkan.
0 -> 0
1 -> 1
8 -> 0
23 -> 2
31 -> 5
103 -> 4
127 -> 7
1877 -> 2
2015 -> 10
Inilah solusi Python yang tidak diklik yang saya gunakan untuk menghasilkan kasus uji ini (tidak dijamin bug-kurang):
def hardness(num) -> int:
binary = bin(num)[2:]
if binary.count('0') == 0:
return num.bit_length()
revbin = binary[::-1]
return min(revbin.find('0'), binary.find('0')) * 2
1
mengembalikan 1 ketika tidak ada0
di dalamnya sama sekali? Maksud saya, Anda tidak dapat menghapus cukup 1 dari string untuk memulai atau mengakhiri0
.Jawaban:
Jelly ,
1110 byteCobalah online!
Bagaimana itu bekerja
sumber
Python ,
76696863626057 byteCobalah online!
Bagaimana itu bekerja
Ini adalah solusi rekursif yang mengambil input n dan terus meningkatkan k - mulai dari 0 - sementara LSB k (n) (bit pada indeks k dari kanan) dan MSB k (n) (bit pada indeks k dari kiri) diatur. Setelah selesai, ia mengembalikan k jika semua bit n diatur dan 2k jika tidak.
Mari kita mulai dengan menulis ulang lambda f sebagai fungsi bernama F , dengan variabel bantu t .
Dalam setiap doa F , pertama-tama kita menggeser- n sejumlah k unit ke kanan dan menyimpan hasilnya dalam t . Dengan cara ini, LSB 0 (t) = LSB k (n) , jadi t aneh jika dan hanya jika LSB k (n) diatur.
Menentukan apakah MSB k (n) diatur sedikit lebih rumit; inilah yang
n & t > t >> 1
mencapai. Untuk menggambarkan cara kerjanya, mari kita pertimbangkan bilangan bulat n = 1αβγδεζη 2 dari bit-length 8 dan menganalisis panggilan fungsi F (n, 3) , yaitu, k = 3 .Kami mencoba menentukan apakah MSB 3 (n) = set diatur dengan memeriksa nilai kebenaran perbandingan (n & t> t >> 1) = (1αβγδεζη 2 & 1αβγδ 2 > 1αβγ 2 ) . Mari kita periksa bilangan bulat yang terlibat.
Kami mengklaim bahwa γ = 1 jika dan hanya jika n & t> t >> 1 .
Jika γ = 1 , maka n & t memiliki panjang bit 5 sedangkan t >> 1 memiliki panjang bit 4 , jadi n & t> t >> 1 .
Ini membuktikan bahwa γ = 1 menyiratkan n & t> t >> 1 .
Jika n & t> t >> 1 , ada dua opsi: baik γ = 1 atau γ = 0 . Dalam kasus pertama, tidak ada yang tersisa untuk dibuktikan.
Dalam kasus kedua, kita memiliki αβγδ 2 ≥ n & t> t >> 1 = 1αβγ 2 .
Karena αβγδ 2 > 1αβγ 2 , kita harus memiliki MSB 0 (αβγδ 2 ) ≥ MSB 0 (1αβγ 2 ) , artinya α = 1 .
Dengan cara ini, 1βγδ 2 > 11βγ 2 , jadi kita harus memiliki MSB 1 (1βγδ 2 ) ≥ MSB 1 (11βγ 2 ) , artinya β = 1 .
Pada gilirannya, ini menyiratkan bahwa 11γδ 2 > 111γ 2 . Mengingat bahwa γ = 0 dalam kasus kedua, kita mendapatkan ketimpangan 110δ 2 > 1110 2 , yang salah karena MSB 2 (110δ 2 ) = 0 <1 = MSB 2 (1110 2 ) .
Dengan demikian, hanya kasus pertama yang mungkin dan n & t> t >> 1 menyiratkan γ = 1 .
Ringkasnya, jika LSB k (n) dan MSB k (n) diatur, t akan menjadi aneh dan n & t> t >> 1 akan Benar , jadi t & (n & t> t >> 1) akan hasil 1 . Namun, jika LSB k (n) atau MSB k (n) tidak disetel (atau jika keduanya), t akan genap atau n & t> t >> 1 akan salah , jadi t & (n & t> t> > 1) akan menghasilkan 0 .
Memanggil F dengan argumen tunggal menginisialisasi k = 0 . Sementara kondisi yang telah kita bahas sebelumnya berlaku, kode setelah
and
dijalankan, yang (antara lain) secara rekursif memanggil F dengan k bertambah .Setelah LSB k (n) atau MSB k (n) tidak disetel, kondisi gagal dan F (n, k) mengembalikan 0 . Setiap panggilan fungsi k sebelumnya menambahkan (n & (n + 1)> 0) + 1 ke F (n, k) = 0 , jadi F (n) mengembalikan ((n & (n + 1)> 0) + 1) k .
Sekarang, jika semua bit n sama (yaitu, jika n adalah 0 atau semua bitnya ditetapkan), n +1 tidak akan memiliki bit yang sama dengan n , jadi n & (n +1) = 0 dan F (n) mengembalikan k . Namun, jika n memiliki bit set dan unset, n & (n + 1)> 0 dan F (n) mengembalikan 2k .
sumber
input()
,,while
danprint
sudah 17 byte ...MATL ,
1312 byteCobalah online! Atau verifikasi semua kasus uji .
Penjelasan
Kode ini mengulangi setiap digit biner, dan menghitung berapa kali dimungkinkan untuk menghapus dua digit luar.
sumber
Python, 82 byte
Saya merasa masih bisa bermain golf, tetapi saya menghabiskan beberapa waktu untuk mencoba metode yang berbeda dan ini adalah yang terpendek.
Cobalah online
Meskipun ini bekerja mirip dengan program Python OP, saya membuat ini sebelum pertanyaan diposting, setelah melihat pertanyaan di Sandbox, yang tidak mengandung program semacam itu.
sumber
Python 2, 66 byte
Pisahkan representasi biner dari input menjadi bilangan 1. Hitung angka 1 di bilangan kecil pertama dan terakhir, lalu gandakan, kecuali ada satu bidak yang akan dikalikan dua kali.
sumber
PowerShell ,
109106 byteCobalah online!
Mengambil input
$args[0]
, menggunakan panggilan .NET untukconvert
itutoString
dengan basis2
(yaitu, buatlah biner), lalu-split
s string itu di0
s, simpan yang ke dalam$a
. Penting untuk dicatat: panggilan .NET tidak menghasilkan nol di depan, jadi digit pertama selalu a1
.Jadi ada dua kemungkinan - string biner adalah semua, atau setidaknya ada satu nol. Kami membedakan antara mereka yang memiliki pseudo-ternary yang diindeks oleh
$a.count-eq1
. Jika biner memiliki setidaknya satu nol, case kiri, kami mengambil minimum dari panjang[0]
string pertama1
s dan[-1]
string terakhir (ditemukan oleh|sort
dan kemudian[0]
). Yang lebih pendek adalah pasangan terbanyak yang bisa kita hapus, jadi kita kalikan dengan2
. Perhatikan bahwa jika string biner asli berakhir dengan0
, seperti untuk input8
, maka[-1].length
juga akan menjadi0
(karena itu string kosong), yang ketika dikalikan dengan2
masih0
.Jika tidak, dengan semua string biner, kita hanya mengambil
$b
(yang sebelumnya ditetapkan sebagai panjang dari[0]
string pertama , dalam hal ini, keseluruhan dari string biner).Dalam situasi apa pun, hasil itu ditinggalkan di jalur pipa dan hasilnya tersirat.
sumber
JavaScript (ES6), 57 byte
Mengambil biner dan mencoba untuk mencocokkan semua
1s
atau gagal dalam jumlah yang sama dari memimpin dan mengikuti1s
.sumber
Retina , 48 byte
Cobalah online
Penjelasan:
sumber
C #, 133 byte
Fungsi yang mengembalikan kekerasan. Mengambil integer dari argumen.
Nah, hari ini saya temukan
'1' + '1' = 98
di C #.sumber
'1'
ASCII char 49, dan 49 + 49 = 98.1 + 1 = 2
tidak berhasil. @FlipTackC,
898885 byteDisimpan dua byte karena @FlipTack menunjukkan pernyataan yang tidak berguna.
Panggil
f()
dengan nomor untuk menguji, output dikembalikan dari fungsi.Cobalah di ideone .
sumber
JavaScript (ES6),
5958 byteUji kasus
Tampilkan cuplikan kode
sumber
Jelly , 14 byte
Cobalah online!
sumber
C,
1371321221191171149894928785 BytesSaatnya mulai bermain golf B-)
Inilah buktinya
dan hasilnya;
sumber
Java (OpenJDK) ,
181156150 byteCobalah online!
sumber
Mathematica,
6356 bytePenjelasan
Hasilkan representasi basis-2 input, dibungkus dengan a
List
. Simpan itu dil
Jika elemen min
l
adalah 1, output 1. Jika tidak, output 2. Kalikan ini dengan ...Dibagi
l
menjadi run.Ambil elemen pertama dan terakhir.
Ambil total keduanya.
Temukan yang lebih kecil di antara keduanya.
(Kalikan hasil pertama (1 atau 2) dengan hasil ini).
sumber
Oktaf,
5654 byteCobalah secara Online!
Penjelasan:
representasi biner dari
n
Ambil min kumulatif
d
dan min kumulatif dibalikd
lakukan perkalian matriks
kalikan dengan 2 jika semua digit adalah 1;
sumber
Pyth, 18 byte
Program yang mengambil input bilangan bulat dan mencetak hasilnya.
Suite uji (Baris pertama untuk pemformatan)
Bagaimana itu bekerja
sumber
APL, 26 byte
Kasus uji:
Penjelasan:
sumber
J, 22 byte
Ini didasarkan pada trik yang dipelajari dari tantangan ini .
Cobalah online!
Penjelasan
sumber
PHP,
8374 byte3 + 6 byte disimpan oleh Jörg
menerima input dari STDIN; jalankan bersama
-nR
.kerusakan
sumber
<?=~($s=decbin($argn))[$a=strspn($s,1)]?2*min($a,strspn(strrev($s),1)):$a;
JavaScript (ES6), 83 Bytes
Tidak Disatukan:
sumber
Mathematica, 62 byte
Fungsi murni di mana
#
merupakan argumen pertama.(h=0;...;h)&
seth=0
, melakukan banyak hal...
, lalu mengembalikanh
(kekerasan). Mari kita lihat banyak hal:Terima kasih kepada Greg Martin karena memperkenalkan saya pada trik ini .
sumber
Haskell ,
9492 byteCobalah online! Pemakaian:
Penjelasan:
b
mengonversi angka menjadi biner dan mengembalikan daftar nol dan angka dengan bit paling signifikan terlebih dahulu. Dalamh
, daftar ini dibalik dan elemen-bijaksana dikalikan dengan daftar asli, laluspan(>0)
terbelah setelah awal1
:Tupel yang dihasilkan adalah pola yang cocok dengan di
(c,_:_)
mana_:_
cocok dengan daftar yang tidak kosong, jadic = [1,1]
. Karena byte dihapus di depan dan belakang,c++c = [1,1,1,1]
dikembalikan dan akhirnya diringkas untuk menghasilkan kekerasan digital .Jika daftar kedua tuple kosong, maka representasi biner hanya berisi satu, dan jumlahnya adalah kekerasan digital. Dengan pencocokan pola gagal
h
mengembalikan sajan
, yang sekali lagi diringkas.sumber
Perl, 61 byte
Inti dari ini adalah regex di
/^(1+).*\1$/
mana 2 kali panjangnya$1
adalah jawabannya. Sisa kode adalah overhead dan berurusan dengan kasus khusus semua 1.sumber
sprintf
argumen. Juga, menggunakan-p
flag akan memungkinkan Anda untuk menulis program lengkap yang akan lebih pendek dari fungsi Anda karena Anda akan dapat menghilangkansub f{...}
(sebaliknya Anda harus mengakhiri dengan$_=...
tetapi itu masih merupakan peningkatan 4 byte). Akhirnya, alih-alih Andalength(...)
, Anda bisa melakukannya/0/&&s/^(1+).*\1$/$1$1/;$_=y///c
. Ini akan membuat Anda mencapai 51 byte.PHP, 65 Bytes
Versi Online
sumber
CJam, 14 byte
Penjelasan:
sumber