The period
string adalah terpendek non-zero pergeseran sehingga string cocok itu sendiri, mengabaikan semua bagian yang overhang. Jadi misalnya, abcabcab
ada titik 3
. Dengan konvensi kita katakan bahwa jika tidak ada pergeseran seperti itu maka string memiliki periode yang sama dengan panjangnya. Jadi periode abcde
is 5
dan periode a
is 1
.
Dalam istilah yang lebih formal, periode string S
adalah minimum i > 0
sehingga S[1,n-i] == S[i+1,n]
(pengindeksan dari 1
).
Untuk string S yang diberi kekuatan dua panjang, kami akan menghitung periode semua awalan kekuatan dua panjangnya. Sebagai contoh, pertimbangkan S = abcabcab
. Periode yang akan kami hitung adalah:
'a', 1
'ab', 2
'abca', 3
'abcabcab', 3
Kami sebenarnya hanya akan menampilkan array periode, yaitu [1, 2, 3, 3]
.
Untuk kekuatan positif yang diberikan dari dua n
, pertimbangkan semua string biner yang mungkin S
. Ingat bahwa string biner hanyalah string 1
s dan 0
s sehingga ada 2^n
string yang persis seperti itu (yaitu 2
untuk kekuatan n
). Untuk masing-masing kita dapat menghitung array periode ini.
Tantangannya adalah untuk menulis kode yang mengambil
n
(kekuatan dua) sebagai input dan menghitung berapa banyak array yang berbeda.
Jawabannya n = 1, 2, 4, 8, 16, 32, 64, 128
adalah:
1, 2, 6, 32, 320, 6025, 216854, 15128807
Rangkaian lengkap periode berbeda untuk n = 4
:
1, 1, 1
1, 1, 3
1, 1, 4
1, 2, 2
1, 2, 3
1, 2, 4
Skor
Saya akan menjalankan kode Anda di komputer saya yang menjalankan Ubuntu selama 10 menit. Skor Anda adalah yang terbesar n
untuk mana kode Anda berakhir pada waktu itu. Dalam kasus seri, jawaban yang melengkapi n
kemenangan tercepat bersama . Jika ada ikatan dalam waktu 1 detik pada timing, jawaban pertama yang diposting menang.
Bahasa dan perpustakaan
Anda dapat menggunakan bahasa dan perpustakaan yang tersedia yang Anda suka. Harap sertakan penjelasan lengkap tentang cara menjalankan / kompilasi kode Anda di Linux jika memungkinkan. `
Kode Anda sebenarnya harus menghitung jawaban dan tidak, misalnya, hanya menampilkan nilai yang telah dihitung.
Entri terkemuka
- 2 menit dan 21 detik untuk n = 128 dalam C # oleh Peter Taylor
- 9 detik untuk n = 32 di Rust oleh isaacg
n
, apakah Anda akan menerimanya? Tidak didefinisikan dengan baik di mana batas antara hardcoding dan komputasi aktual.abcab
. Semua kecuali 3 huruf terakhir adalahabcab
. Ini cocok, dan menghapus sejumlah kecil huruf tidak cocok.Jawaban:
C #, n = 128 dalam sekitar 2:40
Memperluas ke n = 256 akan membutuhkan peralihan ke
BigInteger
untuk topeng, yang mungkin membunuh kinerja terlalu banyak untuk n = 128 untuk dilewati tanpa ide-ide baru, apalagi n = 256.Di Linux, kompilasi dengan
mono-csc
dan jalankan denganmono
.Penjelasan dasar
Saya tidak akan melakukan pembedahan baris demi baris, hanya tinjauan umum konsep.
Sebagai aturan praktis, saya senang untuk mengulangi urutan 2 50 elemen dalam program kombinatorik brute-force. Untuk sampai ke n = 128 oleh karena itu perlu menggunakan pendekatan yang tidak menganalisis setiap bitstring. Jadi daripada bekerja maju dari string bit ke urutan periode, saya bekerja mundur: diberi urutan periode, apakah ada bitstring yang menyadarinya? Untuk n = 2 x ada batas atas yang mudah yaitu 2 x (x + 1) / 2 urutan periode (vs 2 2 x bitstring).
Beberapa argumen menggunakan string periodisitas string :
Wlog Saya akan menganggap bahwa semua bitstring yang dipertimbangkan mulai dengan
0
.Diberi urutan periode di mana periode awalan panjang 2 i ( selalu), ada beberapa pengamatan mudah tentang nilai-nilai yang mungkin dari :
[p1 p2 ... pk]
pi
p0 = 1
pk+1
pk+1 ≥ pk
karena periode stringS
juga merupakan periode awalanS
.pk+1 = pk
selalu merupakan ekstensi yang memungkinkan: cukup ulangi string primitif yang sama untuk karakter dua kali lebih banyak.2k < pk+1 ≤ 2k+1
selalu ada kemungkinan ekstensi. Cukup untuk menunjukkan ini karena string panjang aperiodik dapat diperluas ke string panjang aperiodik dengan menambahkan huruf apa pun yang bukan huruf pertama.pk+1 = 2k+1
L
L+1
Ambil string
Sx
dengan panjang 2 k yang periodenya dan perhatikan string dengan panjang 2 k + 1 . Jelas memiliki sebuah periode 2 k 1. Misalkan periodenya lebih kecil.pk
SxyS
SxyS
q
Maka demikian oleh lemma periodisitas juga merupakan periode , dan karena pembagi terbesar kurang dari atau sama dengan argumennya dan merupakan periode terkecil, kita perlu menjadi faktor yang tepat yaitu 2 k +1. Karena hasil bagi tidak boleh 2, kami punya .
2k+1 + q ≤ 2k+1+1 ≤ 2k+1 + gcd(2k+1, q)
gcd(2k+1, q)
SxyS
q
q
q ≤ (2k+1)/3
Sekarang, karena adalah periode maka harus periode . Tapi yang periode ini . Kami memiliki dua kasus:
q ≤ 2k
SxyS
Sx
Sx
pk
gcd(pk, q) = pk
, atau secara ekivalen membagi menjadi .pk
q
pk + q > 2k + gcd(pk, q)
sehingga lemma periodisitas tidak memaksa periode yang lebih kecil.Pertimbangkan dulu kasus kedua. , bertentangan dengan definisi sebagai periode . Oleh karena itu kita dipaksa ke kesimpulan yang merupakan faktor .
pk > 2k + gcd(pk, q) - q ≥ 2k+1 - q ≥ 2k+1 - (2k+1)/3 ≥ 2q
pk
Sx
pk
q
Tetapi karena
q
merupakan periodeSx
dan merupakan periode , awalan panjang hanyalah salinan awalan panjang , jadi kita melihat bahwa itu juga merupakan periode .pk
Sx
q
q/pk
pk
pk
SxyS
Oleh karena itu jangka waktunya
SxyS
adalah atau 2 k +1. Tapi kami punya dua pilihan untuk ! Paling banyak satu pilihan akan memberikan periode , jadi setidaknya satu akan memberikan periode 2 k +1. QED.pk
y
y
pk
Lemma periodisitas memungkinkan kami untuk menolak beberapa ekstensi yang tersisa.
Setiap ekstensi yang belum lulus tes penerimaan cepat atau penolakan cepat harus diuji secara konstruktif.
Konstruksi bitstring yang diberikan urutan periode pada dasarnya adalah masalah kepuasan, tetapi memiliki banyak struktur. Ada kendala kesetaraan sederhana yang tersirat oleh setiap periode awalan, jadi saya menggunakan struktur data kumpulan serikat untuk menggabungkan bit ke dalam kelompok independen. Ini cukup untuk mengatasi n = 64, tetapi untuk n = 128 itu perlu untuk melangkah lebih jauh. Saya menggunakan dua argumen yang bermanfaat:
2k - pk
M
adalah dan awalan panjang memiliki periode maka awalan panjang harus diakhiri . Ini paling kuat justru dalam kasus-kasus yang seharusnya memiliki kelompok paling independen, yang nyaman.01M-1
L > M
L
L
1M
M
adalah dan awalan panjang memiliki periode dengan dan berakhir di maka itu sebenarnya harus diakhiri dengan . Ini paling kuat pada ekstrim yang berlawanan, ketika urutan periode dimulai dengan banyak yang.0M
L > M
L - d
d < M
0d
10d
Jika kita tidak mendapatkan kontradiksi langsung dengan memaksa cluster dengan bit pertama (diasumsikan nol) menjadi satu maka kita brute force (dengan beberapa optimasi mikro) atas nilai-nilai yang mungkin untuk cluster paksa. Perhatikan bahwa urutannya dalam jumlah yang menurun karena jika bit
i
ke-1 adalah periode maka periode tidak dapati
dan kami ingin menghindari periode yang lebih pendek daripada yang sudah diberlakukan oleh pengelompokan. Turun meningkatkan kemungkinan menemukan tugas yang valid lebih awal.sumber
Rust, 32, 10s
11s29sdi laptop sayaSebut dengan bitsize sebagai argumen baris perintah.
Teknik pintar: mewakili bitstring langsung sebagai angka, gunakan bittwiddling untuk memeriksa siklus. Hanya mencari paruh pertama bitstring, yang dimulai dengan 0, karena array periode bitstring dan kebalikannya (0s ditukar dengan 1s) identik. Jika setiap kemungkinan untuk posisi akhir telah terjadi, saya tidak mencarinya.
Lebih banyak hal pintar:
Untuk mendupuplikasi setiap blok (string di mana bagian pertama bitnya sama) Saya menggunakan bitvector, yang jauh lebih cepat daripada hashset, karena panjang siklus akhir tidak perlu hashing.
Juga, saya melewatkan langkah pertama pemeriksaan siklus, karena saya tahu bahwa siklus akhir tidak bisa lebih pendek dari siklus kedua hingga terakhir.
Setelah banyak profil, sekarang saya dapat mengatakan bahwa hampir semua waktu digunakan secara produktif, jadi perbaikan algoritmik akan diperlukan untuk meningkatkan dari sini, saya pikir. Saya juga beralih ke integer 32 bit untuk menghemat lebih banyak waktu.
Masukkan
bit-vec = "0.4.4"
Cargo.toml AndaJika Anda ingin menjalankan ini, tiruan ini: github.com/isaacg1/cycle lalu
Cargo build --release
untuk membangun, laluCargo run --release 32
jalankan.sumber
time
memberikannya 27 detik pengguna di laptop saya.Rust , 16
Cobalah online!
Kompilasi:
rustc -O <name>.rs
String diimplementasikan sebagai vektor Bool.
The
next
fungsi iterate melalui kombinasi;The
find_period
mengambil sepotong Bool dan mengembalikan periode;The
compute_count_array
melakukan pekerjaan untuk setiap "kekuatan dua" subsequence setiap kombinasi dari bools.Secara teoritis, tidak ada overflow yang diharapkan sampai
2^n
melebihi nilai maksimum u64, yaitun > 64
. Batas ini dapat dijangkau dengan tes mahal pada s = [true, true, ..., true].Berita buruknya adalah: mengembalikan 317 untuk n = 16, tapi saya tidak tahu mengapa. Saya juga tidak tahu apakah itu akan membuatnya dalam sepuluh menit untuk n = 32, karena
Vec<bool>
tidak dioptimalkan untuk jenis komputasi ini.EDIT
Saya telah berhasil menghapus batas 64 untuk
n
. Sekarang, itu tidak akan crash sampain
lebih besar dari integer usize maks.Saya menemukan mengapa kode sebelumnya mengembalikan 317 untuk
n=32
. Saya menghitung set titik dan bukan susunan titik. Ada tiga array dengan elemen yang sama:Sekarang berhasil. Masih lambat tapi berhasil.
sumber
C - 16
Gagal pada nilai yang lebih besar dari 16 cuz overflow.
Saya tidak tahu seberapa cepat ini berjalan karena pada chromebook menjalankannya di repl.it.
Cukup terapkan pertanyaan saat dibaca, telusuri semua string bit, hitung array periode, dan periksa apakah sudah dihitung.
Kompilasi saja dengan gcc, dll.
sumber
16
saat itu ketika kode diubah sehingga keduamalloc
smalloc(...int*))
dan...**
masing - masing16
dicetakAnswer: 320
seperti yang diharapkan, namun32
dicetakAnswer: 0
(dan cukup cepat).n = 8
tetapi setelah hasilnya dicetak, yang berarti bahwa tumpukan rusak. Mungkin Anda berada di suatu tempat di luar blok memori yang dialokasikan.Haskell
Kompilasi dengan
ghc -O2
. Cobalah online!Berjalan dalam waktu kurang dari 0,1 detik pada perangkat keras laptop saya yang berumur 6 tahun untuk
n=16
.n=32
membutuhkan9992 menit, jadi saya faktor 9 atau 10 off. Saya sudah mencoba caching periode dalam tabel pencarian jadi saya tidak perlu menghitung ulang mereka berulang-ulang, tetapi ini dengan cepat kehabisan memori pada mesin 4GB saya.sumber
Python 2 (PyPy), 16
sumber
osboxes@osboxes:~/python$ python ascii_user.py 16 None
[C ++], 32, 4 menit
sumber