tło

Największy wspólny dzielnik ( w skrócie gcd ) jest wygodną funkcją matematyczną, ponieważ ma wiele przydatnych właściwości. Jednym z nich jest tożsamość Bézouta : jeśli d = gcd(a, b), to istnieją liczby całkowite xi ytakie tam d = x*a + y*b. W tym wyzwaniu Twoim zadaniem jest wizualizacja tej właściwości za pomocą prostej grafiki ASCII.

Wkład

Twoje wejścia są dwie dodatnie liczby całkowite ai b, biorąc pod uwagę w każdym rozsądnym formacie. Możesz również przyjmować jednoargumentowe dane wejściowe (powtórzenia jednego wybranego znaku ASCII do wydrukowania), ale musisz być spójny i używać tego samego formatu dla obu danych wejściowych. Dane wejściowe mogą być w dowolnej kolejności i mogą być równe.

Wydajność

Twój wynik jest ciągiem sdługości lcm(a, b) + 1( lcm oznacza najniższą wspólną wielokrotność). Znaki sreprezentują liczby całkowite od 0do lcm(a, b). Znak s[i]jest małą literą, ojeśli ijest wielokrotnością alub b, a kropką w .innym przypadku. Zauważ, że zero jest wielokrotnością każdej liczby. Teraz, ze względu na tożsamość Bézouta, będzie co najmniej jedna para znaków, ow sktórych odległości jest dokładnie gcd(a, b). Najbardziej z lewej taka para ma zostać zastąpiona wielkimi literami Os; to jest końcowy wynik.

Przykład

Rozważ dane wejściowe a = 4i b = 6. Mamy więc, gcd(a, b) = 2a lcm(a, b) = 12więc długość sbędzie 13. Wielokrotności ai bsą podświetlone w następujący sposób:

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

Istnieją dwie pary os z odległością 2, ale zamienimy tylko te lewe z lewej na Os, więc końcowy wynik to

o...O.O.o...o

Zasady i punktacja

Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.

Przypadki testowe

 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

Jolf, 52 bajty

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

Podzielę ten kod na dwie części.

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

Wypróbuj tutaj!

Julia, 111 110 107 103 96 bajtów

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)

Jest to funkcja, która akceptuje dwie liczby całkowite i zwraca ciąg znaków.

Nie golfowany:

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

Zapisałem bajt dzięki nim!

Retina , 112 109 99 94 91 bajtów

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

Myślę, że niezbyt konkurencyjny, ale teoria liczb w Retinie zawsze jest całkiem fajna. :)

Pobiera dane wejściowe jako liczby jednoargumentowe za pomocą .cyfry jednoargumentowej.

Wypróbuj online.

Wyjaśnienie

^
. 

To wstawia a .i spację przed wejściem. To ostatecznie stanie się rezultatem.

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

To dodaje LCM do ai bdo łańcucha. Ponieważ już .tam mamy, skończymy lcm(a,b)+1. Dokonuje się tego poprzez wielokrotne przygotowywanie, bo ile anie dzieli tego nowego prefiksu. Przechwytujemy ado grupy, a następnie sprawdzamy, czy możemy osiągnąć początek ciągu, dopasowując to przechwytywanie przynajmniej raz. bjest następnie wstawiany do ciągu za pomocą rzadko używanego, $'który wstawia wszystko po dopasowaniu do podstawienia.

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

Ten dopasowuje znaki na pozycjach, które są podzielone przez alub b. Wykorzystuje fakt, że wynik jest symetryczny: ponieważ lcm(a,b)jest dzielony przez oba ai bprzechodzenie w lewo przez odejmowanie wystąpień alub bdaje ten sam wzorzec, jak przechodzenie w prawo 0przez dodawanie ich. Pierwszy lookahead po prostu rejestruje ai b. Drugi lookahead sprawdza, aczy bprzed pierwszą spacją jest wielokrotność każdego lub znaków.

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

Jak stwierdzono na Wikipedii, oprócz tożsamości Bézouta prawdą jest również to

Największym wspólnym dzielnikiem djest najmniejsza dodatnia liczba całkowita, którą można zapisać jako ax + by.

Oznacza to, że GCD będzie odpowiadać najkrótszej szczelinie między dwoma os na wyjściu. Więc wcale nie musimy zawracać sobie głowy znalezieniem GCD. Zamiast tego szukamy tylko pierwszego wystąpienia najkrótszej luki. o(\.*)odopasowuje przerwę kandydata i przechwytuje jej szerokość do grupy 1. Następnie próbujemy dotrzeć do pierwszej spacji, zmieniając odniesienie do grupy 1 i os (z opcjonalnymi dodatkowymi .s). Jeśli po prawej stronie znajduje się krótsza luka, nie będzie to zgodne, ponieważ nie możemy przekroczyć tej luki z odniesieniem wstecznym. Gdy tylko wszystkie dalsze luki będą co najmniej tak duże jak bieżące, to się dopasowuje. Przechwytujemy koniec łańcucha LCM do grupy 2 i dopasowujemy pozostałą część ciągu .*. Odpisujemy wielkie literyOs (z odstępem pomiędzy), a także pozostałą część łańcucha LCM, ale odrzuć wszystko, zaczynając od spacji, aby usunąć ai bod końcowego wyniku.

𝔼𝕊𝕄𝕚𝕟, 50 znaków / 90 bajtów

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

Try it here (Firefox only).

Musi być jeszcze jakiś sposób na grę w golfa!

Wyjaśnienie

Jest to podstawowy algorytm dwufazowy. To jest właściwie dość proste.

Faza 1

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

Najpierw tworzymy zakres od 0 do LCM + 1. Następnie odwzorowujemy to, sprawdzając, czy którekolwiek z danych wejściowych jest czynnikiem bieżącego elementu w zakresie. Jeśli tak, zamieniamy ten element na o; w przeciwnym razie zamieniamy go na .. Łączenie go daje nam serię kropek i kropek, które możemy przejść do drugiej fazy.

Faza 2

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

To tylko jedna duża funkcja zamiany. Wyrażenie regularne jest tworzone jako o[dots]o, gdzie liczba kropek jest określana przez GCD-1. Ponieważ wyrażenie regularne nie jest globalne, będzie pasować tylko do pierwszego wystąpienia. Następnie dopasowanie jest zastępowane za O[dots]Opomocą funkcji toUpperCase.

MATL , 72 bajty

Używa wersji 6.0.0 , która jest wcześniejsza niż to wyzwanie. Kod działa w Matlabie i Octave.

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

Przykład

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

Wyjaśnienie

Nie mam pojęcia jak to działa. Właśnie wpisałem znaki losowo. Myślę, że w grę wchodzi pewien splot.

Edycja: Wypróbuj online! Kod w łączu został nieznacznie zmodyfikowany w celu dostosowania do zmian w języku (od 2 czerwca 2016 r.).

Japt , 83 bajty

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

Jeszcze nie w pełni golfa ... I nie chcę grać w golfa: /

JavaScript, 170 164 161 153 145 141 136 136 bajtów

(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`)

To dość lonnnggggg ....

Demo , zmienne jawnie zdefiniowane, ponieważ interpreter używa trybu ścisłego.

Python 2, 217 200 191 bajtów

To trochę tępe, ale działa. Wszelkie wskazówki dotyczące gry w golfa są mile widziane, zwłaszcza jeśli wiesz, jak rozwiązać s[i] = s[v] = "o"napotkany problem, który zastąpiłby „O”, rozumiem !

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)

Nie golfowany:

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)