Contexte

Le plus grand diviseur commun ( gcd pour faire court) est une fonction mathématique pratique, car elle possède de nombreuses propriétés utiles. L'un d'eux est l'identité de Bézout : si d = gcd(a, b), alors il existe des entiers xet ytels que d = x*a + y*b. Dans ce défi, votre tâche consiste à visualiser cette propriété avec un art ASCII simple.

Contribution

Vos entrées sont deux entiers positifs aet b, donnés dans n'importe quel format raisonnable. Vous pouvez également prendre des entrées unaires (répétitions d'un seul caractère ASCII imprimable de votre choix), mais vous devez être cohérent et utiliser le même format pour les deux entrées. Les entrées peuvent être dans n'importe quel ordre et elles peuvent être égales.

Sortie

Votre sortie est une chaîne sde longueur lcm(a, b) + 1( lcm représente le plus petit commun multiple). Les caractères de sreprésentent des entiers de 0à lcm(a, b). Le caractère s[i]est en minuscule osi iest un multiple de aou b, et un point .sinon. Notez que zéro est un multiple de chaque nombre. Maintenant, en raison de l'identité de Bézout, il y aura au moins une paire de personnages oà sdistance exacte gcd(a, b). La paire la plus à gauche doit être remplacée par des majuscules O; c'est la sortie finale.

Exemple

Considérez les entrées a = 4et b = 6. Ensuite, nous avons gcd(a, b) = 2et lcm(a, b) = 12, donc la longueur de ssera 13. Les multiples de aet bsont mis en évidence comme suit:

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

Il y a deux paires de os avec une distance de deux, mais nous ne remplacerons que les plus à gauche par Os, donc la sortie finale est

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

Règles et notation

Vous pouvez écrire un programme complet ou une fonction. Le nombre d'octets le plus bas l'emporte et les failles standard sont interdites.

Cas de test

 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 octets

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

Je vais diviser ce code en deux parties.

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

Essayez-le ici!

Julia, 111 110 107 103 96 octets

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)

Il s'agit d'une fonction qui accepte deux entiers et renvoie une chaîne.

Non golfé:

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

Un octet sauvé grâce à nimi!

Retina , 112 109 99 94 91 octets

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

Pas très compétitif, je pense, mais la théorie des nombres dans la rétine est toujours assez amusante. :)

Prend la saisie comme des nombres unaires en utilisant .comme chiffre unaire.

Essayez-le en ligne.

Explication

^
. 

Cela insère un .et un espace devant l'entrée. Cela deviendra finalement la sortie.

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

Cela ajoute le LCM de aet bà la chaîne. Puisque nous en avons déjà un ., nous nous retrouverons avec lcm(a,b)+1. Ceci est accompli en ajoutant plusieurs fois btant que ane divise pas ce nouveau préfixe. Nous capturons adans un groupe puis vérifions si nous pouvons atteindre le début de la chaîne en faisant correspondre cette capture au moins une fois. best ensuite inséré dans la chaîne via le rarement utilisé $'qui insère tout après la correspondance dans la substitution.

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

Celui-ci fait correspondre les caractères à des positions divisées par aou b. Il utilise le fait que le résultat est symétrique: puisque lcm(a,b)est divisé par les deux aet bva à gauche en soustrayant les instances de aou bdonne le même motif que d'aller à droite 0en les ajoutant. Le premier lookahead capture simplement aet b. Le deuxième lookahead vérifie qu'il y a un multiple de chacun aou des bcaractères avant le premier espace.

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

Comme indiqué sur Wikipédia, outre l'identité de Bézout, il est également vrai que

Le plus grand diviseur commun dest le plus petit entier positif qui puisse s'écrire ax + by.

Cela implique que le GCD correspondra à l'écart le plus court entre deux os dans la sortie. Nous n'avons donc pas du tout besoin de trouver le GCD. Au lieu de cela, nous recherchons simplement la première instance de l'écart le plus court. o(\.*)ocorrespond à un espace candidat et capture sa largeur dans le groupe 1. Ensuite, nous essayons d'atteindre le premier espace en alternant entre une référence arrière au groupe 1 et os (avec des .s supplémentaires facultatifs ). S'il y a un écart plus court plus à droite, cela ne correspondra pas, car nous ne pouvons pas dépasser cet écart avec la référence arrière. Dès que tous les autres écarts sont au moins aussi larges que l'actuel, cela correspond. Nous capturons la fin de la chaîne LCM dans le groupe 2 et faisons correspondre le reste de la chaîne avec .*. Nous réécrivons les majusculesOs (avec l'espace entre les deux) ainsi que le reste de la chaîne LCM, mais jetez tout à partir de l'espace, pour supprimer aet bdu résultat final.

𝔼𝕊𝕄𝕚𝕟, 50 caractères / 90 octets

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

Try it here (Firefox only).

Il doit y avoir un moyen de jouer au golf plus loin!

Explication

Il s'agit d'un algorithme de base à deux phases. C'est en fait assez simple.

La phase 1

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

Tout d'abord, nous créons une plage de 0 à LCM + 1. Ensuite, nous le cartographions, vérifiant si l'une des entrées est un facteur de l'élément actuel dans la plage. Si oui, nous remplaçons cet article par un o; sinon, nous le remplaçons par un .. Le rejoindre nous donne une série de o et de points que nous pouvons passer à la phase deux.

Phase 2

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

Ce n'est qu'une grande fonction de remplacement. Une expression régulière est créée en tant que o[dots]o, où la quantité de points est déterminée par le GCD-1. Puisque cette expression régulière n'est pas globale, elle ne correspondra qu'à la première occurrence. Après, la correspondance est remplacée à l' O[dots]Oaide d'une fonction toUpperCase.

MATL , 72 octets

Utilise la version 6.0.0 , antérieure à ce défi. Le code s'exécute dans Matlab et dans Octave.

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

Exemple

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

Explication

Je ne sais pas comment ça marche. Je viens de taper des caractères au hasard. Je pense qu'il y a une certaine convolution.

Edit: Essayez-le en ligne! Le code du lien a été légèrement modifié pour se conformer aux changements de langue (au 2 juin 2016).

Japt , 83 octets

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

Pas encore entièrement golfé ... Et ne veut pas être golfé: /

Javascript, 170 164 161 153 145 145 141 136 octets

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

C'est tout à fait lonnnggggg ....

Démo , variables définies explicitement car l'interpréteur utilise le mode strict.

Python 2, 217 200 191 octets

C'est un peu brutal, mais ça marche. Tous les conseils de golf sont appréciés, surtout si vous savez comment résoudre le s[i] = s[v] = "o"problème que j'ai rencontré, où cela remplacerait "O" .

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)

Non golfé:

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)