Visualiza el máximo divisor común

28

Fondo

El máximo común divisor ( mcd para abreviar) es una función matemática conveniente, ya que tiene muchas propiedades útiles. Una de ellas es la identidad de Bézout : si d = gcd(a, b), entonces existen enteros xy ytal d = x*a + y*b. En este desafío, su tarea es visualizar esta propiedad con un simple arte ASCII.

Entrada

Sus entradas son dos enteros positivos ay b, dados en cualquier formato razonable. También puede tomar entradas unarias (repeticiones de un solo carácter ASCII imprimible de su elección), pero debe ser coherente y usar el mismo formato para ambas entradas. Las entradas pueden estar en cualquier orden, y pueden ser iguales.

Salida

Su salida es una cadena sde longitud lcm(a, b) + 1( mcm representa el mínimo común múltiplo). Los caracteres de srepresentan enteros de 0a lcm(a, b). El carácter s[i]es minúscula osi ies un múltiplo de ao b, y un punto en .caso contrario. Tenga en cuenta que cero es un múltiplo de cada número. Ahora, debido a la identidad de Bézout, habrá al menos un par de personajes oen scuya distancia es exactamente gcd(a, b). El par más a la izquierda debe ser reemplazado por mayúsculas O; Este es el resultado final.

Ejemplo

Considere las entradas a = 4y b = 6. Entonces tenemos gcd(a, b) = 2y lcm(a, b) = 12, entonces la longitud de sserá 13. Los múltiplos de ay bse resaltan de la siguiente manera:

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

Hay dos pares de os con la distancia dos, pero solo reemplazaremos los más a la izquierda con Os, por lo que la salida final es

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

Reglas y puntaje

Puede escribir un programa completo o una función. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten.

Casos de prueba

 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
fuente
1
Al tomar una entrada unaria, ¿podemos elegir cualquier personaje? (En particular, ¿qué tal ., oo O.) O tiene que ser 1? O 0?
Martin Ender
1
@ MartinBüttner Puede ser cualquier personaje, siempre y cuando sea coherente y use el mismo formato para ambas entradas.
Zgarb
2
Me sorprende que no haya usado 3 y 5 como uno de sus casos de prueba.
Neil
¿Puedo usar buildin?
Akangka
@ChristianIrwan Sí, todos los elementos integrados están permitidos.
Zgarb

Respuestas:

7

Jolf, 52 bytes

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

Dividiré este código en dos partes.

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

Pruébalo aquí!

Conor O'Brien
fuente
Más corto que todo lo demás hasta ahora. : P
Rɪᴋᴇʀ
1
@RikerW ¡Sí! Espero que Jolf finalmente gane, una vez.
Conor O'Brien el
10

Julia, 111 110 107 103 96 bytes

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)

Esta es una función que acepta dos enteros y devuelve una cadena.

Sin 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

¡Ahorré un byte gracias a nimi!

Alex A.
fuente
10

Retina , 112 109 99 94 91 bytes

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

No es muy competitivo, creo, pero la teoría de números en Retina siempre es bastante divertida. :)

Toma la entrada como números unarios utilizando .como dígito unario.

Pruébalo en línea.

Explicación

^
. 

Esto inserta ay un .espacio delante de la entrada. Esto finalmente se convertirá en la salida.

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

Esto antepone el LCM de ay ba la cadena. Como ya tenemos un .allí, terminaremos con lcm(a,b)+1. Esto se logra al anteponer repetidamente bsiempre aque no divida este nuevo prefijo. Capturamos aen un grupo uno y luego verificamos si podemos alcanzar el comienzo de la cadena haciendo coincidir esa captura al menos una vez. bluego se inserta en la cadena a través del poco utilizado $'que inserta todo después del partido en la sustitución.

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

Éste coincide con los personajes en las posiciones divididas por ao b. Se aprovecha el hecho de que el resultado es simétrico: ya que lcm(a,b)se divide entre ambos ay se bva hacia la izquierda al restar instancias ao se bobtiene el mismo patrón que al ir a la derecha 0al sumarlos. La primera búsqueda anticipada simplemente captura ay b. La segunda búsqueda anticipada verifica que haya un múltiplo de cada uno ao bcaracteres antes del primer espacio.

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

Como se indica en Wikipedia, además de la identidad de Bézout también es cierto que

El máximo común divisor des el menor entero positivo que se puede escribir como ax + by.

Esto implica que el GCD corresponderá al espacio más corto entre dos os en la salida. Por lo tanto, no tenemos que molestarnos en encontrar el MCD. En cambio, solo buscamos la primera instancia de la brecha más corta. o(\.*)ocoincide con un espacio candidato y captura su ancho en el grupo 1. Luego intentamos alcanzar el primer espacio alternando entre una referencia al grupo 1 ys o(con .s adicionales opcionales ). Si hay un espacio más corto más a la derecha, esto no coincidirá, porque no podemos superar ese espacio con la referencia inversa. Tan pronto como todos los huecos adicionales sean al menos tan anchos como el actual, esto coincide. Capturamos el final de la cadena LCM en el grupo 2 y hacemos coincidir el resto de la cadena con .*. Escribimos en mayúsculaOs (con el espacio intermedio), así como el resto de la cadena LCM, pero descarte todo comenzando desde el espacio, para eliminar ay bdel resultado final.

Martin Ender
fuente
No sé mucho sobre la teoría de números de Retina, pero ¿no establecería el carácter de entrada en algo que no requiera escapar de bytes de guardado? Es decir (\.*)=>(a*)
Conor O'Brien el
@ CᴏɴᴏʀO'Bʀɪᴇɴ Sí, pero tendría que reemplazarlo más .tarde, lo que cuesta cuatro bytes (y deshacerse de los escapes solo ahorra 3).
Martin Ender
Ohh ¡Guay! Muy interesante respuesta.
Conor O'Brien el
5

𝔼𝕊𝕄𝕚𝕟, 50 caracteres / 90 bytes

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

Try it here (Firefox only).

¡Debe haber una manera de jugar golf más allá!

Explicación

Este es un algoritmo básico de dos fases. En realidad es bastante simple.

Fase 1

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

Primero, creamos un rango de 0 a LCM + 1. Luego lo mapeamos, verificando si alguna de las entradas es un factor del elemento actual en el rango. Si es así, reemplazamos ese elemento con un o; de lo contrario, lo reemplazamos con a .. Unirse a él nos da una serie de puntos y o que podemos pasar a la fase dos.

Fase 2

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

Esta es solo una gran función de reemplazo. Se crea una expresión regular como o[dots]o, donde la cantidad de puntos está determinada por el GCD-1. Dado que esta expresión regular no es global, solo coincidirá con la primera aparición. Después, la coincidencia se reemplaza O[dots]Outilizando una función toUpperCase.

Mama Fun Roll
fuente
3

MATL , 72 bytes

Utiliza la versión 6.0.0 , que es anterior a este desafío. El código se ejecuta en Matlab y en Octave.

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

Ejemplo

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

Explicación

No tengo idea de cómo funciona. Acabo de escribir caracteres al azar. Creo que hay alguna convolución involucrada.

Editar: ¡ Pruébelo en línea! El código en el enlace se ha modificado ligeramente para adaptarse a los cambios en el idioma (a partir del 2 de junio de 2016).

Luis Mendo
fuente
No puede escribir un programa de 72 bytes al azar. Calculará la probabilidad más tarde (después de dormir y ACTUAR durante un tiempo)
CalculatorFeline
2

Japt , 83 bytes

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

Todavía no está totalmente golfizado ... Y no quiere jugar golf: /

nicael
fuente
¿No se puede usar ren lugar de $.replace($?
ETHproductions
@Eth No he descubierto cómo reemplazar sin la bandera g, así que no, no puedo.
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`)

Eso es bastante lonnnggggg ...

Demo , variables definidas explícitamente porque el intérprete usa el modo estricto.

nicael
fuente
Intente reemplazar i%a<1||i%b<1?'o':'.'coni%a&&i%b?'.':'o'
Mama Fun Roll
Oh sí, creo que puedes unirte a un alias.
Mama Fun Roll
@ ן nɟuɐɯɹɐ ן oɯ gracias, también reemplazando matrices con una simple repetición.
nicael
Ah, entonces, en ese caso, probablemente no deberías unirte alias a menos que tengas 3 veces.
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')te ahorra dos bytes. (También traté de usar la indexación de cadenas para crear '.' Y 'o' pero eso en realidad cuesta dos bytes.)
Neil
1

Python 2, 217 200 191 bytes

Esto es un poco contundente, pero funciona. Se agradece cualquier consejo de golf, especialmente si sabe cómo solucionar el s[i] = s[v] = "o"problema que encontré, donde eso sobrescribiría "O". ¡Lo tengo!

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)

Sin 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)
Sherlock9
fuente