The Hamming jarak antara dua string dengan panjang yang sama adalah jumlah posisi di mana yang sesuai simbol yang berbeda.
Membiarkan P
menjadi string biner panjang n
dan T
menjadi string biner panjang 2n-1
. Kita dapat menghitung n
jarak Hamming antara P
dan setiap n
substring T
dengan panjang dari kiri ke kanan dan menempatkannya ke dalam array (atau daftar).
Contoh urutan jarak Hamming
Biarkan P = 101
dan T = 01100
. Urutan jarak Hamming yang Anda dapatkan dari pasangan ini adalah 2,2,1
.
Tugas
Untuk meningkatkan n
mulai dari n=1
, pertimbangkan semua pasangan yang mungkin dari string biner P
panjang n
dan T
panjang 2n-1
. Ada 2**(n+2n-1)
pasangan seperti itu dan karenanya banyak urutan jarak Hamming. Namun banyak dari sekuens tersebut akan identik. Tugasnya adalah menemukan berapa banyak yang berbeda untuk masing-masing n
.
Kode Anda harus menampilkan satu nomor per nilai n
.
Skor
Skor Anda adalah tertinggi yang dicapai n
kode Anda di mesin saya dalam 5 menit. Waktunya adalah total waktu berjalan, bukan hanya waktu untuk itu n
.
Yang menang
Orang dengan skor tertinggi menang. Jika dua orang atau lebih berakhir dengan skor yang sama maka itu adalah jawaban pertama yang menang.
Contoh jawaban
Untuk n
dari 1
ke 8
jawaban optimal adalah 2, 9, 48, 297, 2040, 15425, 125232, 1070553
.
Bahasa dan perpustakaan
Anda dapat menggunakan bahasa dan perpustakaan yang tersedia yang Anda suka. Jika memungkinkan, alangkah baiknya untuk dapat menjalankan kode Anda, jadi harap sertakan penjelasan lengkap tentang cara menjalankan / mengkompilasi kode Anda di Linux jika memungkinkan.
Mesin Saya Pengaturan waktu akan dijalankan pada mesin 64-bit saya. Ini adalah instalasi ubuntu standar dengan RAM 8GB, Prosesor Delapan-Core AMD FX-8350 dan Radeon HD 4250. Ini juga berarti saya harus dapat menjalankan kode Anda.
Memimpin jawaban
- 11 dalam C ++ oleh feersum. 25 detik.
- 11 dalam C ++ oleh Andrew Epstein. 176 detik.
- 10 di Javascript oleh Neil. 54 detik.
- 9 di Haskell oleh nimi. 4 menit dan 59 detik.
- 8 di Javascript oleh fəˈnɛtɪk. 10 detik.
fastest-code
menyisakan lebih banyak ruang untuk optimasi melalui optimasi level kode dan algoritma yang baik. Jadi saya pikir itufaster-code
lebih baik daripadafaster-algorithm
.Jawaban:
C ++ 11 (harus mencapai 11 atau 12)
Saat ini single-threaded.
Untuk mengkompilasi:
sumber
feersum.cpp:111:61: warning: shifting a negative signed value is undefined [-Wshift-negative-value] int middle = int(s >> npre * MAX_N_BITS) & ~(~0 << MAX_N_BITS);
Haskell, skor 9
Kompilasi dengan
-O3
. Dibutuhkan 6min35s pada perangkat keras laptop saya yang berumur 6 tahun untuk menjalankannyan=9
, jadi mungkin itu di bawah 5 menit pada perangkat keras referensi.sumber
JavaScript, skor 10
Penjelasan: Menghitung
n=10
sulit karena ada lebih dari dua miliar pasangan dan lebih dari 26 miliar urutan potensial. Untuk mempercepat, saya membagi perhitungan menjadi 121 nampan. Karena urutannya tidak berubah di bawah komplemen bitwise, saya dapat mengasumsikan tanpa kehilangan keumuman bahwa bit tengahT
adalah nol. Ini berarti bahwa saya dapat menentukan elemen pertama dan terakhir dari urutan secara terpisah dari bit atasn-1
dan bawahn-1
T
. Setiap nampan sesuai dengan sepasang elemen pertama dan terakhir yang berbeda; Saya kemudian loop melalui semua set kemungkinan bit atas dan bawah yang sesuai dengan masing-masing bin dan menghitung elemen yang tersisa dari urutan, akhirnya menghitung urutan unik untuk setiap bin. Itu kemudian tetap total 121 sampah. Awalnya memakan waktu 45 jam, ini sekarang selesai dalam waktu kurang dari tiga setengah menit pada AMD FX-8120 saya. Sunting: Terima kasih kepada @ChristianSievers untuk kecepatan 50%. Output penuh:sumber
n
sebagai parameter. (Maaf untuk pilihan nama parameter yang salah di sana.)n=1
(tidak tahu mengapa hang).C ++, skor
1011Ini adalah terjemahan dari jawaban @ Neil ke dalam C ++, dengan beberapa paralelisasi sederhana.
n=9
selesai dalam 0,4 detik,n=10
dalam 4,5 detik, dann=11
dalam sekitar 1 menit pada 2015 Macbook Pro saya. Juga, terima kasih kepada @ChristianSievers. Karena komentarnya pada jawaban @ Neil, saya perhatikan beberapa simetri tambahan. Dari 121 ember asli (untukn=10
), hingga 66 ember saat menghitung pembalikan, saya turun menjadi hanya 21 ember.Gunakan skrip berikut untuk menjalankan kode:
Outputnya adalah sebagai berikut: (Formatnya adalah
M: result, seconds
)n=12
butuh 42 menit untuk menghitung pada utas tunggal, dan memberikan hasil 7368225813.sumber
sudo apt-get install libiomp-dev
.__builtin_popcount
.__builtin_popcount
dalam konteks constexpr. Saya bisa pergi dengan implementasi naif dan itu tidak akan mempengaruhi waktu berjalan.JavaScript 2,9,48,297,2040,15425,125232,1070553,9530752
Jalankan di konsol:
Cobalah online!
Atau sebagai Cuplikan Stack:
Tampilkan cuplikan kode
Kode menginisialisasi array untuk membuat menambahkan 1 ke array lebih cepat
Kode menemukan semua urutan jarak hamming dan memperlakukan mereka sebagai basis angka (input + 1), menggunakannya untuk menempatkan 1s dalam sebuah array. Sebagai hasilnya, ini menghasilkan array dengan n 1s di mana n adalah jumlah urutan jarak hamming yang unik. Akhirnya, jumlah 1s dihitung menggunakan array.reduce () untuk menjumlahkan semua nilai dalam array.
Kode ini tidak akan dapat berjalan untuk input 10 karena menyentuh batas memori
Kode ini berjalan dalam O (2 ^ 2n) waktu karena itulah berapa banyak elemen yang dihasilkannya.
sumber
n = 9
membutuhkan waktu 5 menit dan 30 detik untuk saya menggunakan node.js jadi terlalu lambat.n = 8
awalnya membutuhkan 24 detik pada PC saya, tetapi saya dapat mengoptimalkan kode sehinggan = 8
butuh 6 detik. Saya kemudian mencoban = 9
dan itu butuh 100 detik.