Idenya di sini adalah untuk menghasilkan pola yang hampir berulang. Artinya, urutan yang sedang dibangun berubah pada saat terakhir untuk menghindari pengulangan dari beberapa berikutnya. Selanjutnya tipe AA dan ABA harus dihindari (di mana B tidak lebih dari A).
Contoh:
Saya akan melanjutkan dan mulai dengan mendaftar semua contoh kecil untuk membuat deskripsi saya lebih jelas. Mari kita mulai dengan 0.
Valid: 0 Tidak valid: 00 (pola AA) Berlaku: 01 Tidak valid: 010 (pola ABA) Tidak valid: 011 (pola AA) Berlaku: 012 Berlaku: 0120 Tidak valid: 0121 (pola ABA) Tidak valid: 0122 (pola AA) Tidak valid: 01200 (pola AA) Tidak valid: 01201 (pola ABA; 01-2-01) Tidak valid: 01202 (pola ABA) Berlaku: 01203
Sekarang, saya sangat percaya bahwa a 4
tidak pernah diperlukan, meskipun saya tidak punya bukti, karena saya telah dengan mudah menemukan urutan ratusan karakter yang hanya digunakan 0123
. (Ini mungkin terkait erat dengan bagaimana hanya tiga karakter diperlukan untuk memiliki string tanpa batas yang tidak memiliki pola AA. Ada halaman Wikipedia tentang ini.)
Input output
Input adalah bilangan bulat tunggal, positif, tidak nol n
. Anda mungkin menganggap itu n <= 1000
.
Output adalah n
urutan -character tanpa urutan yang cocok dengan pola yang dilarang (AA atau ABA).
Input dan output sampel
>>> 1 0 >>> 2 01 >>> 3 012 >>> 4 0120 >>> 5 01203 >>> 50 01203102130123103201302103120132102301203102132012
Aturan
- Hanya karakter
0123
yang diizinkan. - B adalah tidak lebih dari A. Hal ini untuk menghindari situasi di mana
012345
telah diikuti oleh6
karena0123451
memiliki ini:1-2345-1
. Dengan kata lain, urutannya akan sepele dan tidak menarik. n
dapat dimasukkan melalui metode apa pun yang diinginkan, kecuali hard-coding.- Output dapat berupa daftar atau string, tergantung mana yang lebih mudah.
- Tidak ada kekuatan kasar ; waktu menjalankan harus dalam urutan menit, paling banyak satu jam pada mesin yang sangat lambat, untuk
n=1000
. (Ini dimaksudkan untuk mendiskualifikasi solusi yang hanya mengulangin
permutasi semua- panjang{0,1,2,3}
, sehingga trik dan trik serupa tidak diizinkan.) - Celah standar tidak diizinkan, seperti biasa.
- Skor dalam byte. Ini adalah kode-golf , sehingga entri terpendek menang (mungkin - lihat bonus).
- Bonus: pilih angka terendah yang diizinkan pada setiap langkah. Jika
1
dan3
merupakan pilihan yang memungkinkan untuk digit berikutnya dalam urutan, pilih1
. Kurangi 5 byte dari skor Anda. Namun, perhatikan catatan di bawah ini.
Catatan!
Jalan buntu adalah mungkin. Program atau fungsi Anda harus menghindari ini. Ini sebuah contoh:
Stump: 012031021301231032013021031201321023012031021320123021031201302310320123021320310230120321021230132033030302030303030303030303030303030 Tunggul: 01203102130123103201302103120132102301203102132012302103120130231032012302132031023012032102123013203303030203030303030303030303030303030 Tunggul: 01203102130123103201302103120132102301203102132012302103120130231032012302132031023012032102123013203303030202030303030303030303030 Stump: 0120310213012310320130210312013210230120310213201230210312013023103201230213203102301203210230303020303030303030303030303030303030303030
Setiap urutan ini tidak dapat diperpanjang lebih jauh (tanpa menggunakan a 4
). Tetapi juga perhatikan bahwa ada perbedaan penting antara dua yang pertama dan yang kedua. Saya akan mengganti awal awal bersama dengan X
untuk membuat ini lebih jelas.
Tunggul: X2130120 Tunggul: X2130123 Tunggul: X320 Tunggul: X321301203102130
Dua digit terakhir X
adalah 10
, jadi satu-satunya pilihan yang mungkin untuk digit berikutnya adalah 2
dan 3
. Memilih 2
mengarah ke situasi di mana urutan harus diakhiri. Algoritma serakah tidak akan berfungsi di sini. (Lagi pula, bukan tanpa mundur.)
sumber
n
? Jika seseorang memberikan algoritma semi-rakus heuristik, bagaimana Anda memeriksa bahwa itu tidak mengalami masalah untuk panjang yang sangat besar? Masalah umum adalah masalah yang menarik, dan saya belum dapat menemukan apa pun tentang penghindaran pola di mana kita membatasi panjang bagian dari pola tersebut. Jika seseorang dapat membuat resep umum, saya berharap itu menjadi pendekatan terbaik.n
, tetapi mengingat bahwa tunggul yang ditemukan program saya cenderung menjadi lebih lama dengan rata-rata 10 digit setiap kali, saya sangat yakin bahwa ada urutan yang tak terbatas. Saya tidak yakin bagaimana algoritma semi-serakah dapat diuji untuk urutan besar yang sewenang-wenang. Saya bisa membatasi persyaratan untukn
= 1000 dan tidak perlu khawatir tentang lebih tinggin
.AA
benar-benar mengetik diABA
manaB
kosong. Ini mungkin dapat membantu merampingkan beberapa solusi.Jawaban:
Retina , 86 byte - 5 = 81
Dimana
<empty>
mewakili garis trailing kosong. Anda dapat menjalankan kode di atas dari satu file dengan-s
bendera.Masukan harus diberikan secara unary , mis
111111
. Saya belum mengujinya untuk output pada urutan ribuan - dua regex mungkin agak lambat setelah beberapa saat - tetapi ia dapat dengan mudah menangani beberapa ratus dalam beberapa detik.Penjelasan
Ini adalah solusi backtracking sederhana.
0
.3
.Mundur ini diimplementasikan oleh loop penggantian regex yang dibatalkan setelah string tetap tidak berubah melalui satu iterasi.
Ini menambahkan a
_
ke input, yang digunakan untuk memisahkan input unary dari urutan yang kita buat.Ini adalah subtitusi pertama dalam loop (ditunjukkan oleh yang terkemuka
(
). Regex cocok jika a) ada karakter kata (yaitu digit) di akhir string (yang berarti string valid - kita akan melihat di bawah bahwa urutan yang tidak valid ditandai dengan trailing#
) dan b) setidaknya ada sebanyak karakter dalam urutan seperti pada input (ini diperiksa menggunakan kelompok penyeimbang ). Jika itu masalahnya, kami menghapus input dan menambahkan a!
. Ini!
berfungsi untuk membuat semua regex dalam loop gagal, sehingga berakhir.Jika ada karakter kata di akhir (yaitu urutannya valid, dan loop tidak diakhiri oleh langkah sebelumnya), tambahkan a
0
.Jika (sebagai gantinya) urutan telah ditandai tidak valid dan diakhiri
3
, kami menghapusnya3
(tapi biarkan urutan tersebut tidak valid, karena tidak ada kelanjutan yang mungkin untuk awalan saat ini ... sehingga karakter selanjutnya perlu ditinjau kembali juga).Jika urutan ditandai tidak valid dan angka apa pun selain
3
di akhir, kami menambah digit dan menghapus penanda.Substitusi terakhir dalam loop (seperti yang ditunjukkan oleh
)
). Ia memeriksa apakah string berakhirABA
( di manaB
tidak lebih dariA
tetapi berpotensi kosong). Panjang relatifA
danB
lagi-lagi diperiksa menggunakan kelompok penyeimbang, dan pengulanganA
dicentang dengan backreference sederhana.Jika regex ini cocok, kami menandai urutan tidak valid dengan menambahkan
#
.Setelah loop berakhir, yang perlu kita lakukan adalah menghapus
!
dan kemudian dibiarkan dengan output yang diinginkan.sumber
Python 2, 175 - 5 = 170 byte
Ini adalah algoritma serakah dengan mundur. Saya berharap itu lebih pendek. Saya harap itu benar (lihat di bawah).
Itu membangun string satu digit pada suatu waktu. Dengan serangkaian
d
digit yang telah ditemukannya, ia mencoba untuk menambahkan a0
sebagai(d+1)
digit pertama. Jika itu tidak berhasil, maka dicoba a1
, lalu a2
, lalu a3
. Jika tidak ada yang berhasil, maka kembali ked
digit ke th dan menambahkannya (jika kurang dari3
) atau menghilangkannya (jika sama dengan3
, dalam hal ini menambah yang sebelumnya, dll).Pemeriksaan untuk validitas adalah garis
.find
di dalamnya. Jika ada yang memutuskan untuk membaca kode saya, saya harus mengatakan bahwa program ini benar-benar menyimpan string ke belakang, artinya menambahkan angka ke depan . Jadi cek melibatkan mencari tempat-tempat di mana digit pertamac
muncul lagi di string (di mana saja setelah yang pertamac
digit ), dan jika ada tempat-tempat seperti itu, apakah panjang intervensi paling banyakc
.(Tentu saja membalikkan string sebelum mencetak.)
Bisa juga dengan cepat menjadi lebih cepat; Saya awalnya sudah keluar berbagai loop awal untuk efisiensi, tetapi biaya byte yang berharga. Masih OK dalam kisaran
n=1000
, meskipun.Bagaimanapun, program ini tampaknya menunjukkan preferensi untuk digit yang lebih kecil, tetapi itu bukan preferensi yang sangat kuat. Misalnya, menjalankannya dengan
n=2000
memberi saya string dengan523
nol,502
satu,497
dua dan478
tiga, berakhir dengan30210312013021
. Jadi, jika ada orang lain yang bekerja pada algoritma serakah, mungkin mereka dapat mengkonfirmasi hasil ini. Atau dengann=1000
saya mendapat[263, 251, 248, 238]
hitungan dengan digit.Akhirnya, saya akan menyebutkan bahwa penghitungan ini adalah semacam sugestif simetri, hampir (meskipun tidak persis) seolah-olah kita telah memulai dengan distribusi yang seragam dan kemudian mengkonversi beberapa
3
's ke0
' s dan beberapa2
's ke1
' s. Namun yang jelas itu bisa saja kebetulan. Saya tidak punya ide!sumber
Haskell, 115 (120 byte - 5 bonus)
Jalankan online di Ideone
Contoh dijalankan:
sumber