Visualisasikan pembagi umum terbesar

28

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 xdan ysemacamnya 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 adan 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 spanjang lcm(a, b) + 1( lcm adalah singkatan untuk multiple umum terendah). Karakter smewakili integer dari 0ke lcm(a, b). Karakter s[i]adalah huruf kecil ojika imerupakan kelipatan dari aatau 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 odi syang jarak persis gcd(a, b). Pasangan yang paling kiri harus diganti oleh huruf besar O; ini adalah hasil akhir.

Contoh

Pertimbangkan input a = 4dan b = 6. Lalu kita punya gcd(a, b) = 2dan lcm(a, b) = 12, jadi panjangnya sakan 13. Kelipatan dari adan bdisorot sebagai berikut:

0  1  2  3  4  5  6  7  8  9 10 11 12
o  .  .  .  o  .  o  .  o  .  .  .  o

Ada dua pasang os dengan jarak dua, tetapi kami hanya akan mengganti yang paling kiri dengan Os, 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
Zgarb
sumber
1
Saat mengambil input yang tidak disorot, dapatkah kita memilih karakter apa saja? (Khususnya, bagaimana ., oatau O.) Atau haruskah demikian 1? Atau 0?
Martin Ender
1
@ MartinBüttner Dapat berupa karakter apa saja, selama Anda konsisten dan menggunakan format yang sama untuk kedua input.
Zgarb
2
Saya terkejut Anda tidak menggunakan 3 dan 5 sebagai salah satu kasus uji Anda.
Neil
Bisakah saya menggunakan buildin?
Akangka
@ChristianIrwan Ya, semua built-in diizinkan.
Zgarb

Jawaban:

7

Jolf, 52 byte

on*'.wm9jJΡR m*Yhm8jJDN?<*%Sj%SJ1'o'.}"'o%o"n"O%O"n

Saya akan membagi kode ini menjadi dua bagian.

on*'.wm9jJ
on         set n
  *'.       to a dot repeated
      m9jJ  the gcd of two numeric inputs

ΡR m*Yhm8jJDN?<*%Sj%SJ1'o'.}"'o%o"n"O%O"n
    *Y                                    multiply (repeat) Y (Y = [])
      hm8jJ                                by the lcm of two inputs + 1
  _m       DN              }              and map the array of that length
             ?<*%Sj%SJ1'o'.               "choose o if i%a*(i%b)<1; otherwise choose ."
 R                          "'            join by empty string
Ρ                            'o%o"n        replace once (capital Rho, 2 bytes): "o"+n+"o"
                                   "O%O"n   with "O"+n+"O"
                                          implicit printing

Coba di sini!

Conor O'Brien
sumber
Lebih pendek dari yang lainnya sejauh ini. : P
Rɪᴋᴇʀ
1
@RikerW Ya! Saya berharap Jolf akhirnya akan menang, sekali.
Conor O'Brien
10

Julia, 111 110 107 103 96 byte

f(a,b)=replace(join([i%a*(i%b)<1?"o":"."for i=0:lcm(a,b)]),"o$(d="."^(gcd(a,b)-1))o","O$(d)O",1)

Ini adalah fungsi yang menerima dua bilangan bulat dan mengembalikan string.

Tidak Terkumpul:

function f(a::Int, b::Int)
    # Construct an array of dots and o's
    x = [i % a * (i % b) < 1 ? "o" : "." for i = 0:lcm(a, b)]

    # Join it into a string
    j = join(x)

    # Replace the first pair with distance gcd(a, b) - 1
    replace(j, "o$(d = "."^(gcd(a, b) - 1))o", "O$(d)O", 1) 
end

Disimpan satu byte berkat nimi!

Alex A.
sumber
10

Retina , 112 109 99 94 91 byte

^
. 
+r`(?<!^\1+). (.+) 
$'$0
.(?=.* (.+) (.+))(?=\1* |\2* )
o
o(\.*)o((\1\.*o)*) .*
O$1O$2

Saya 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.

+r`(?<!^\1+). (.+) 
$'$0

Ini mengawali LCM dari adan bke string. Karena kita sudah punya di .sana, kita akan berakhir dengan lcm(a,b)+1. Ini dicapai dengan berulang kali membuat ulang bselama atidak membagi awalan baru ini. Kami menangkap ake dalam grup satu dan kemudian memeriksa apakah kami dapat mencapai awal string dengan mencocokkan penangkapan itu setidaknya sekali. bkemudian dimasukkan ke dalam string melalui yang jarang digunakan $'yang menyisipkan semuanya setelah pertandingan ke substitusi.

.(?=.* (.+) (.+))(?=\1* |\2* )
o

Ini cocok dengan karakter di posisi yang dibagi oleh aatau b. Itu memanfaatkan fakta bahwa hasilnya simetris: karena lcm(a,b)dibagi oleh keduanya adan bke kiri dengan mengurangkan contoh aatau bmenghasilkan pola yang sama dengan pergi dari 0dengan menambahkannya. Lookahead pertama hanya menangkap adan b. Lookahead kedua memeriksa bahwa ada kelipatan masing-masing aatau bkarakter sebelum spasi pertama.

o(\.*)o((\1\.*o)*) .*
O$1O$2

Seperti yang dinyatakan di Wikipedia, selain identitas Bézout juga benar

Pembagi umum terbesar dadalah bilangan bulat positif terkecil yang dapat ditulis sebagai ax + by.

Ini menyiratkan bahwa GCD akan sesuai dengan kesenjangan terpendek antara dua odalam output. Jadi kita tidak perlu repot menemukan GCD sama sekali. Sebagai gantinya kita hanya mencari contoh pertama dari celah terpendek. o(\.*)ococok 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 dan os (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 besarOs (dengan celah di antaranya) serta sisa string LCM, tetapi buang semuanya mulai dari spasi, untuk menghapus adan bdari hasil akhir.

Martin Ender
sumber
Saya tidak tahu banyak tentang teori bilangan Retina, tetapi tidak akan mengatur karakter input ke sesuatu yang tidak perlu melarikan diri menyelamatkan byte? Yaitu (\.*)=>(a*)
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ Ya, tapi kemudian saya harus menggantinya .nanti, yang biayanya empat byte (dan menyingkirkan lolos hanya menghemat 3).
Martin Ender
Ohh Keren! Jawaban yang sangat menarik.
Conor O'Brien
5

𝔼𝕊𝕄𝕚𝕟, 50 karakter / 90 byte

⩥Мū⁽îí+1)ⓜ$%î⅋$%í?⍘.:⍘o)⨝ċɼ(`o⦃⍘.ĘМũ⁽îí-1)}o”,↪$ú⬮

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

⩥Мū⁽îí+1)ⓜ$%î⅋$%í?⍘.:⍘o)⨝

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

ċɼ(`o⦃⍘.ĘМũ⁽îí-1)}o”,↪$ú⬮

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 dengan O[dots]Omenggunakan fungsi toUpperCase.

Mama Fun Roll
sumber
3

MATL , 72 byte

Menggunakan versi 6.0.0 , yang lebih awal dari tantangan ini. Kode berjalan di Matlab dan dalam Oktaf.

2$tZm1+:1-bbvtbw\A~otbZ}ZdXK1+ltb(3X53$X+1K2$lh*t2=f1)tK+hwg1+Ib('.oO'w)

Contoh

>> matl
 > 2$tZm1+:1-bbvtbw\A~otbZ}ZdXK1+ltb(3X53$X+1K2$lh*t2=f1)tK+hwg1+Ib('.oO'w)
 > 
> 1
> 1
OO

>> matl
 > 2$tZm1+:1-bbvtbw\A~otbZ}ZdXK1+ltb(3X53$X+1K2$lh*t2=f1)tK+hwg1+Ib('.oO'w)
 > 
> 2
> 3
o.OOo.o

>> matl
 > 2$tZm1+:1-bbvtbw\A~otbZ}ZdXK1+ltb(3X53$X+1K2$lh*t2=f1)tK+hwg1+Ib('.oO'w)
 > 
> 12
> 15
o...........O..O........o.....o.....o........o..o...........o

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).

Luis Mendo
sumber
Anda tidak dapat mengetik program 72 byte secara acak. Akan menghitung probabilitas nanti (setelah tidur dan BERTINDAK sebentar)
CalculatorFeline
2

Japt , 83 byte

'.pD=U*V/(C=(G=@Y?G$($YX%Y :X} $($UV)+1 £Y%U©Y%V?".:o"} $.replace($E=`o{'.pC-1}o`Eu

Belum sepenuhnya bermain golf ... Dan tidak ingin bermain golf: /

nicael
sumber
Dapatkah Anda tidak menggunakan rdi tempat $.replace($?
ETHproduk
@Eth saya belum menemukan cara mengganti tanpa g flag, jadi tidak, saya tidak bisa.
nicael
2

Javascript, 170 164 161 153 145 141 136 bytes

(a,b)=>[...Array(a*b/(c=(g=(a,b)=>b?g(b,a%b):a)(a,b))+1)].map((x,i)=>i%a&&i%b?'.':'o').join``.replace(`o${e='.'.repeat(c-1)}o`,`O${e}O`)

Itu cukup lonnnggggg ....

Demo , variabel yang didefinisikan secara eksplisit karena interpreter menggunakan mode ketat.

nicael
sumber
Coba ganti i%a<1||i%b<1?'o':'.'dengani%a&&i%b?'.':'o'
Mama Fun Roll
Oh iya, kupikir kamu bisa alias gabung.
Mama Fun Roll
@ ן nɟuɐɯɹɐ ן oɯ terima kasih, juga mengganti array dengan pengulangan sederhana.
nicael
Oh, kalau begitu, Anda mungkin tidak boleh alias bergabung kecuali jika Anda memiliki 3 kejadian itu.
Mama Fun Roll
[...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.)
Neil
1

Python 2, 217 200 191 byte

Ini sedikit tumpul, tetapi berhasil. Setiap kiat bermain golf dihargai, terutama jika Anda tahu cara memperbaiki s[i] = s[v] = "o"masalah yang saya temui, di mana itu akan menimpa "O". Mengerti!

g=lambda a,b:b and g(b,a%b)or a
def f(a,b):
 h=g(a,b);x=1+a*b/h;s=["."]*x;v=k=0
 for i in range(x):
    if(i%a)*(i%b)<1:
     if k:s[i]="o"
     else:k=i==h+v;s[i]=s[v]="oO"[k]
     v=i
 return''.join(s)

Tidak Terkumpul:

def gcd(a,b):                           # recursive gcd function
    if b:
        return g(b,a%b)
    else:
        return a
def f(a,b):
    h = gcd(a,b)
    x = 1 + a*b/h                       # 1 + lcm(a,b)
    s = ["."] * x
    v = 0
    k = 0
    for i in range(x):
        if i%a == 0 and i % b == 0:
            if k == 0:
                k = (i == h+v)          # correct distance apart?
                if k:                   # if "O" just found
                    s[i] = s[v] = "O"
                else:
                    s[i] = s[v] = "o"
            else:
                s[i] = "o"              # if "O" already found, always "o"
            v = i                       # If we found an "o" or an "O", i is the new v
    return ''.join(s)
Sherlock9
sumber