Latar Belakang
Pembagi umum terbesar ( singkatnya gcd ) adalah fungsi matematika yang praktis, karena memiliki banyak properti yang berguna. Salah satunya adalah identitas Bézout : jika d = gcd(a, b)
, maka ada bilangan bulat x
dan y
semacamnya d = x*a + y*b
. Dalam tantangan ini, tugas Anda adalah memvisualisasikan properti ini dengan seni ASCII sederhana.
Memasukkan
Input Anda adalah dua bilangan bulat positif a
dan b
, diberikan dalam format apa pun yang masuk akal. Anda juga dapat mengambil input unary (pengulangan satu karakter ASCII yang dapat dicetak pilihan Anda), tetapi Anda harus konsisten dan menggunakan format yang sama untuk kedua input. Masukan mungkin dalam urutan apa pun, dan mereka mungkin sama.
Keluaran
Output Anda adalah string s
panjang lcm(a, b) + 1
( lcm adalah singkatan untuk multiple umum terendah). Karakter s
mewakili integer dari 0
ke lcm(a, b)
. Karakter s[i]
adalah huruf kecil o
jika i
merupakan kelipatan dari a
atau b
, dan periode .
sebaliknya. Perhatikan bahwa nol adalah kelipatan dari setiap angka. Sekarang, karena identitas Bézout ini, akan ada setidaknya satu pasangan dari karakter o
di s
yang jarak persis gcd(a, b)
. Pasangan yang paling kiri harus diganti oleh huruf besar O
; ini adalah hasil akhir.
Contoh
Pertimbangkan input a = 4
dan b = 6
. Lalu kita punya gcd(a, b) = 2
dan lcm(a, b) = 12
, jadi panjangnya s
akan 13
. Kelipatan dari a
dan b
disorot sebagai berikut:
0 1 2 3 4 5 6 7 8 9 10 11 12
o . . . o . o . o . . . o
Ada dua pasang o
s dengan jarak dua, tetapi kami hanya akan mengganti yang paling kiri dengan O
s, sehingga hasil akhirnya adalah
o...O.O.o...o
Aturan dan penilaian
Anda dapat menulis program atau fungsi lengkap. Hitungan byte terendah menang, dan celah standar tidak diizinkan.
Uji kasus
1 1 -> OO
2 2 -> O.O
1 3 -> OOoo
4 1 -> OOooo
2 6 -> O.O.o.o
2 3 -> o.OOo.o
10 2 -> O.O.o.o.o.o
4 5 -> o...OO..o.o.o..oo...o
8 6 -> o.....O.O...o...o.o.....o
12 15 -> o...........O..O........o.....o.....o........o..o...........o
19 15 -> o..............o...o..........o.......o......o...........o..o..............OO.............o....o.........o........o.....o............o.o..............o.o............o.....o........o.........o....o.............oo..............o..o...........o......o.......o..........o...o..............o
.
,o
atauO
.) Atau haruskah demikian1
? Atau0
?Jawaban:
Jolf, 52 byte
Saya akan membagi kode ini menjadi dua bagian.
Coba di sini!
sumber
Julia,
11111010710396 byteIni adalah fungsi yang menerima dua bilangan bulat dan mengembalikan string.
Tidak Terkumpul:
Disimpan satu byte berkat nimi!
sumber
Retina ,
112109999491 byteSaya kira tidak terlalu kompetitif, tetapi teori bilangan di Retina selalu cukup menyenangkan. :)
Mengambil input sebagai angka unary menggunakan
.
sebagai digit unary.Cobalah online.
Penjelasan
Ini menyisipkan a
.
dan spasi di depan input. Ini pada akhirnya akan menjadi output.Ini mengawali LCM dari
a
danb
ke string. Karena kita sudah punya di.
sana, kita akan berakhir denganlcm(a,b)+1
. Ini dicapai dengan berulang kali membuat ulangb
selamaa
tidak membagi awalan baru ini. Kami menangkapa
ke dalam grup satu dan kemudian memeriksa apakah kami dapat mencapai awal string dengan mencocokkan penangkapan itu setidaknya sekali.b
kemudian dimasukkan ke dalam string melalui yang jarang digunakan$'
yang menyisipkan semuanya setelah pertandingan ke substitusi.Ini cocok dengan karakter di posisi yang dibagi oleh
a
ataub
. Itu memanfaatkan fakta bahwa hasilnya simetris: karenalcm(a,b)
dibagi oleh keduanyaa
danb
ke kiri dengan mengurangkan contoha
ataub
menghasilkan pola yang sama dengan pergi dari0
dengan menambahkannya. Lookahead pertama hanya menangkapa
danb
. Lookahead kedua memeriksa bahwa ada kelipatan masing-masinga
ataub
karakter sebelum spasi pertama.Seperti yang dinyatakan di Wikipedia, selain identitas Bézout juga benar
Ini menyiratkan bahwa GCD akan sesuai dengan kesenjangan terpendek antara dua
o
dalam output. Jadi kita tidak perlu repot menemukan GCD sama sekali. Sebagai gantinya kita hanya mencari contoh pertama dari celah terpendek.o(\.*)o
cocok dengan celah kandidat dan menangkap lebarnya ke dalam grup 1. Kemudian kami mencoba untuk mencapai ruang pertama dengan berganti-ganti antara backreference ke grup 1 dano
s (dengan tambahan opsional.
s). Jika ada celah yang lebih pendek di sebelah kanan, ini akan gagal untuk mencocokkan, karena kita tidak bisa melewati celah itu dengan referensi balik. Begitu semua kesenjangan lebih lanjut setidaknya selebar yang saat ini, ini cocok. Kami menangkap ujung LCM-string ke dalam grup 2 dan mencocokkan sisa string dengan.*
. Kami menulis kembali huruf besarO
s (dengan celah di antaranya) serta sisa string LCM, tetapi buang semuanya mulai dari spasi, untuk menghapusa
danb
dari hasil akhir.sumber
(\.*)
=>(a*)
.
nanti, yang biayanya empat byte (dan menyingkirkan lolos hanya menghemat 3).𝔼𝕊𝕄𝕚𝕟, 50 karakter / 90 byte
Try it here (Firefox only).
Pasti ada cara untuk bermain golf ini lebih jauh!
Penjelasan
Ini adalah algoritma dua fase dasar. Ini sebenarnya cukup sederhana.
Fase 1
Pertama, kami membuat rentang dari 0 hingga LCM + 1. Kemudian kami memetakannya, memeriksa apakah salah satu input merupakan faktor dari item saat ini dalam rentang. Jika demikian, kami mengganti item itu dengan
o
; jika tidak, kami menggantinya dengan a.
. Bergabung dengan itu memberi kita serangkaian titik dan titik yang bisa kita lewati untuk fase dua.Fase 2
Ini hanya satu fungsi ganti yang besar. Regex dibuat sebagai
o[dots]o
, di mana jumlah titik ditentukan oleh GCD-1. Karena regex ini bukan global, itu hanya akan cocok dengan kejadian pertama. Setelah itu, pertandingan diganti denganO[dots]O
menggunakan fungsi toUpperCase.sumber
MATL , 72 byte
Menggunakan versi 6.0.0 , yang lebih awal dari tantangan ini. Kode berjalan di Matlab dan dalam Oktaf.
Contoh
Penjelasan
Saya tidak tahu cara kerjanya. Saya baru saja mengetik karakter secara acak. Saya pikir ada beberapa konvolusi yang terlibat.
Sunting: Coba online! Kode dalam tautan telah sedikit dimodifikasi untuk menyesuaikan dengan perubahan dalam bahasa (per 2 Juni 2016).
sumber
Japt , 83 byte
Belum sepenuhnya bermain golf ... Dan tidak ingin bermain golf: /
sumber
r
di tempat$.replace($
?Javascript,
170164161153145141136 bytesItu cukup lonnnggggg ....
Demo , variabel yang didefinisikan secara eksplisit karena interpreter menggunakan mode ketat.
sumber
i%a<1||i%b<1?'o':'.'
dengani%a&&i%b?'.':'o'
[...Array((d=a*b/(c=(g=(a,b)=>b?g(b,a%b):a)(a,b)))+1).keys()].map(i=>i%a&&i%b?'.':'o')
menghemat dua byte. (Saya juga mencoba menggunakan pengindeksan string untuk membuat '.' Dan 'o' tetapi itu sebenarnya biaya dua byte.)Python 2,
217200191 byteIni sedikit tumpul, tetapi berhasil. Setiap kiat bermain golf dihargai,
terutama jika Anda tahu cara memperbaikiMengerti!s[i] = s[v] = "o"
masalah yang saya temui, di mana itu akan menimpa "O".Tidak Terkumpul:
sumber