Tujuan
Tulis sebuah fungsi atau program, urutkan array bilangan bulat dalam urutan menurun dengan jumlah 1 yang ada dalam representasi biner mereka. Tidak diperlukan kondisi penyortiran sekunder.
Contoh daftar yang diurutkan
(menggunakan bilangan bulat 16-bit)
Dec Bin 1's
16375 0011111111110111 13
15342 0011101111101110 11
32425 0111111010101001 10
11746 0010110111100010 8
28436 0000110111110100 8
19944 0100110111101000 8
28943 0000011100011111 8
3944 0000011111101000 7
15752 0011110110001000 7
825 0000000011111001 6
21826 0101010101000010 6
Memasukkan
Array bilangan bulat 32-bit.
Keluaran
Array bilangan bulat yang sama diurutkan seperti yang dijelaskan.
Mencetak gol
Ini adalah kode golf untuk jumlah byte terkecil yang akan dipilih dalam waktu satu minggu.
Jawaban:
J (11)
Ini adalah fungsi yang mengambil daftar:
Jika Anda ingin memberi nama, biayanya satu karakter tambahan:
Penjelasan:
\:
: ke bawah semacam+/
: jumlah dari"1
: setiap baris#:
: representasi binersumber
\:1#.#:
yang menyimpan beberapa byte.JavaScript, 39
Pembaruan: Sekarang lebih pendek dari Ruby.
40
Penjelasan:
q adalah fungsi rekursif. Jika x atau y adalah 0, ia mengembalikan
x-y
(angka negatif jika x adalah nol atau angka positif jika y adalah nol). Kalau tidak, ia akan menghapus bit terendah (x&x-1
) dari x dan y dan berulang.Versi sebelumnya (42)
sumber
~y
bekerja-!y
?!x|-!y
menjadi tidak nol.~
tidak cocok karena ini bukan nol untuk banyak input (termasuk nol)Ruby 41
Uji:
sumber
Python 3 (44):
sumber
Common Lisp, 35
logcount
mengembalikan jumlah 'on'-bit dalam suatu angka. Untuk daftarl
, kami memiliki:Sebagai fungsi mandiri, dan berdasarkan apa byte akan digunakan:
sumber
Python 3,
90777267 karakter.Solusi kami mengambil input dari baris perintah, dan mencetak nomor dalam urutan menurun (67 karakter), atau naik (66).
Urutan menurun
Terima kasih kepada @daniero , untuk saran menggunakan minus pada hitungan 1 untuk membalikkannya, daripada menggunakan slice untuk membalikkan array pada akhirnya! Ini secara efektif menyimpan 5 karakter.
Hanya demi mempostingnya, versi urutan naik (yang pertama kali kami buat) akan mengurangi satu karakter.
Urutan naik :
Terima kasih kepada @ Bakuriu untuk saran kunci = lambda x… . ; D
sumber
0
akan selalu menjadi bagian dari output Anda kemudian; Itu tidak benar.raw_input()
dan menjatuhkan beberapa karakter saja?[]
dalamnyasorted
. Juga output dari program ini adalah jumlah 1s dalam angka-angka dalam input diurutkan, tetapi Anda harus menampilkan nomor yang Anda terima dalam input, diurutkan menggunakan jumlah1
s. Sesuatu seperti:print(sorted(input().split(), key=lambda x:bin(int(x)).count('1')))
akan benar.JavaScript [76 byte]
di mana
a
input array angka.Uji:
sumber
..
kerjanya? Pemahaman saya adalah bahwa jikax = 5
kemudianeval(x + r)
menjadieval(5..toString(2).match(/1/g).length)
yang saya kira tidak valid. Terima kasih.'string'.length
atau[1,2,3].pop()
. Dalam hal angka Anda dapat melakukan hal yang sama tetapi Anda harus ingat bahwa setelah satu titik parser akan mencari bagian fraksional dari angka yang mengharapkan nilai float (seperti dalam123.45
). Jika Anda menggunakan integer Anda harus "kirim" parser bahwa sebagian pecahan kosong, menetapkan dot ekstra sebelum menangani properti:123..method()
.match(/1/g).length
denganreplace(/0/g,"")
.a.sort(function(x,y){r='..toString(2).match(/1/g).length';return eval(y+r+-x+r)})
Mathematica 30
Pemakaian:
sumber
k [15 Karakter]
Contoh 1
Contoh 2 (semua angka 2 ^ n -1)
sumber
Mathematica 39
IntegerDigits[#,2]
mengonversi nomor basis 10 ke daftar 1 dan 0.Tr
menjumlahkan digit.Kasus cobaan
sumber
Java 8 -
87/11381/11160/8060/74/48 karakterIni bukan program java yang lengkap, ini hanya sebuah fungsi (metode, tepatnya).
Diasumsikan bahwa
java.util.List
danjava.lang.Long.bitCount
diimpor, dan memiliki 60 karakter:Jika tidak ada barang pra-impor diizinkan, ini dia dengan 74 karakter:
Tambahkan lebih dari 7 karakter jika diperlukan
static
.[4 tahun kemudian] Atau jika Anda mau, itu bisa berupa lambda (terima kasih @KevinCruijssen untuk sarannya), dengan 48 byte:
sumber
Integer.bitCount(x)<Integer.bitCount(y)?-1:1;
? Apakah Anda memerlukan-1,0,1
perilaku itu?<Integer>
dengan ruang?Long
, yang menghemat ruang :)a.sort((x,y)->Long.bitCount(x)-Long.bitCount(y));
Python 2.x - 65 karakter (byte)
Itu sebenarnya 66 karakter, 65 jika kita membuatnya berfungsi (maka Anda perlu sesuatu untuk memanggilnya yang ingin ditampilkan).
Demo di Bash / CMD:
sumber
sum(int(d)for d in bin(x)[2:])
kesum(map(int,bin(x)[2:]))
print sorted(input(),key=lambda x:-bin(x).count('1'))
Matlab, 34
Masukkan 'a'
Berfungsi untuk nomor non-negatif.
sumber
C - 85 byte (
108106 byte)Versi portabel pada GCC / Dentang / di mana pun
__builtin_popcount
tersedia (106 byte):Versi MSVC-satunya ultra-kondensasi, non-portabel, hampir tidak berfungsi (85 byte):
Baris pertama pertama dimasukkan dalam hitungan byte karena
#define
, yang lain tidak diperlukan.Fungsi untuk menelepon
s(array, length)
sesuai dengan spesifikasi.Dapat meng-hardcode
sizeof
dalam versi portabel untuk menyimpan 7 karakter lainnya, seperti beberapa jawaban C lainnya. Saya tidak yakin yang mana yang paling layak dalam hal rasio kegunaan-panjang, Anda memutuskan.sumber
sizeof l
menghemat satu byte. Yang jelek#define p-__builtin_popcount(
bisa membantu menyelamatkan yang lain.PowerShell v3,
615853ScriptBlock untuk
Sort-Object
cmdlet mengembalikan array 1 untuk setiap 1 dalam representasi biner dari angka tersebut.Sort-Object
mengurutkan daftar berdasarkan panjang array yang dikembalikan untuk setiap nomor.Untuk mengeksekusi:
sumber
$f={
berlebihan,while
->for
,-band1
->%2
,-des
->-d
dan trik golf lainnya. Itu sudah jelas. Bisakah Anda menjelaskan cara kerjanya$args|sort{@(1,1,...,1)}
? Ini berhasil! Bagaimana cara membandingkan array tanpa eksplisit.Count
? di mana membaca tentang itu? Terima kasih!help Sort-Object -Parameter property
Saya tidak tahu di mana properti penyortiran default untuk tipe didefinisikan, tetapi untuk array adalah Count atau Panjang.$args|sort{while($_){if($_-band1){$_};$_=$_-shr1}}-des
memberikan hasil yang salah. Karena itu tidakCount
. Itu sangat menarik. Terima kasih lagi.ECMASkrip 6, 61
Asumsikan
z
adalah inputUji data
Terima kasih, sikat gigi untuk solusi yang lebih singkat.
sumber
z.sort((a,b)=>{c=d=e=0;while(++c<32)d+=a>>c&1,e+=b>>c&1},e-d)
(dan terima kasih atas suaranya).R ,
1329694888475735351 byte-20 Berkat implementasi J.oe -2 Lebih banyak terima kasih kepada Giuseppe
Posting asli saya:
Cobalah online!
Saya mencoba beberapa metode yang berbeda sebelum saya sampai pada hasil ini.
Metode Matriks: Membuat matriks dua kolom, satu kolom dengan vektor input, salah satu dari jumlah representasi biner, lalu saya urutkan berdasarkan jumlah biner.
Non-Matriks: Menyadari bahwa saya dapat membuang fungsi matriks dan sebagai gantinya membuat vektor nilai-nilai biner, menjumlahkannya, memesannya, lalu menggunakan nilai yang diurutkan untuk menyusun ulang vektor input.
Perubahan kecil
Lebih Banyak Perubahan Kecil Mengubah seluruh hal menjadi satu baris kode alih-alih dipisahkan oleh tanda titik koma.
Metode Sum Alih-alih menambahkan kolom dengan
colSums
matriks biner yang dibuat olehsapply
, saya menambahkan elemen dalam kolom sebelumsapply
"selesai."Penurunan untuk Rev Aku benar-benar ingin mempersingkat menurun, tetapi R squawks pada saya jika saya mencoba untuk mempersingkat
decreasing
dalamorder
fungsi, yang diperlukan untuk mendapatkan pesanan yang diinginkan sebagaiorder
default untuk meningkat, maka saya teringatrev
fungsi untuk membalikkan vektor. EUREKA !!! Perubahan terakhir dalam solusi akhir adalahfunction
untukpryr::f
menyelamatkan 2 byte lagisumber
Haskell, 123C
Ini adalah cara pertama yang saya pikirkan untuk menyelesaikan ini, tapi saya yakin ada cara yang lebih baik untuk melakukannya. Juga, jika ada yang tahu tentang cara golf Haskell impor, saya akan sangat tertarik untuk mendengarnya.
Contoh
Versi tidak digabungkan (dengan penjelasan)
sumber
mod
,n`mod`2
? Ia memiliki prioritas yang sama dengan perkalian dan pembagian.CoffeeScript (94)
Kode yang dapat dibaca (212):
Dioptimalkan (213):
Mengaburkan (147):
Operator ternary terlalu panjang (129):
Terlalu lama, hentikan casting (121):
Final (94):
sumber
Smalltalk (Smalltalk / X), 36 (atau mungkin 24)
masukan dalam; secara destruktif memilah:
versi fungsional: mengembalikan array yang diurutkan baru:
bahkan ada varian yang lebih pendek (lewat nama atau fungsi sebagai argumen) dalam 24 karakter. Tapi (menghela napas) itu akan mengurutkan tertinggi terakhir. Seperti yang saya pahami, ini tidak diminta, jadi saya tidak menganggapnya sebagai skor golf:
sumber
PHP 5.4+ 131
Saya bahkan tidak tahu mengapa saya repot-repot dengan PHP, dalam hal ini:
Pemakaian:
sumber
Scala, 58
sumber
DFSORT (produk penyortiran Mainframe IBM) 288 (setiap baris sumber adalah 72 karakter, harus memiliki ruang di posisi satu)
Hanya untuk bersenang-senang, dan tanpa matematika.
Mengambil file (dapat dieksekusi dari program yang menggunakan "array") dengan integer. Sebelum mengurutkan, ia menerjemahkan bilangan bulat ke bit (dalam bidang 16 karakter). Kemudian mengubah 0s dalam bit menjadi nol. SORT Turun pada hasil bit yang diubah. Membuat file yang diurutkan hanya dengan integer.
sumber
C
sumber
C #,
8889Edit: urutan menurun menambahkan karakter.
sumber
Javascript 84
Terinspirasi oleh jawaban javascript lainnya, tetapi tanpa eval dan regex.
sumber
Javascript (82)
sumber
Catatan tambahan, 126
Karena daftar nilai yang digunakan untuk mengurutkan dikenal sebelumnya dan sangat terbatas (32), tugas ini dapat dengan mudah dilakukan bahkan jika tidak ada bawaan untuk menyortir, dengan memilih nilai yang cocok untuk 1..32. (Apakah itu O (32n)? Mungkin).
Prosedur mengharapkan array pada stack dan mengembalikan array yang 'diurutkan'.
Atau, ruang putih dilucuti secara ritual dan mudah dibaca:
Kemudian, jika disimpan
bits.ps
dapat digunakan seperti ini:Saya pikir ini efektif sama dengan Perl ini (belum ada Perl di sini juga):
Meskipun demikian , tidak seperti Postscript, dapat dengan mudah dipasangkan:
sumber
C -
124111Diimplementasikan sebagai metode dan menggunakan perpustakaan standar untuk penyortiran. Pointer ke array dan ukuran harus dilewatkan sebagai parameter. Ini hanya akan bekerja pada sistem dengan pointer 32-bit. Pada sistem 64-bit, beberapa karakter harus dihabiskan menentukan definisi pointer.
Lekukan untuk keterbacaan
Contoh panggilan:
sumber
Jawa 8: 144
Dalam bentuk yang diperluas:
Seperti yang Anda lihat, ini berfungsi dengan mengonversikan
args
ke aStream<String>
, lalu mengonversikan keStream<Integer>
dengan denganInteger::decode
referensi fungsi (lebih pendek dariparseInt
atauvalueOf
), lalu menyortir denganInteger::bitCount
, lalu memasukkannya ke dalam array, dan mencetaknya.Streaming membuat segalanya lebih mudah.
sumber