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 x
y y
tal 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 a
y 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 s
de longitud lcm(a, b) + 1
( mcm representa el mínimo común múltiplo). Los caracteres de s
representan enteros de 0
a lcm(a, b)
. El carácter s[i]
es minúscula o
si i
es un múltiplo de a
o 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 o
en s
cuya 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 = 4
y b = 6
. Entonces tenemos gcd(a, b) = 2
y lcm(a, b) = 12
, entonces la longitud de s
será 13
. Los múltiplos de a
y b
se 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 o
s con la distancia dos, pero solo reemplazaremos los más a la izquierda con O
s, 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
.
,o
oO
.) O tiene que ser1
? O0
?Respuestas:
Jolf, 52 bytes
Dividiré este código en dos partes.
Pruébalo aquí!
fuente
Julia,
11111010710396 bytesEsta es una función que acepta dos enteros y devuelve una cadena.
Sin golf:
¡Ahorré un byte gracias a nimi!
fuente
Retina ,
112109999491 bytesNo 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.Esto antepone el LCM de
a
yb
a la cadena. Como ya tenemos un.
allí, terminaremos conlcm(a,b)+1
. Esto se logra al anteponer repetidamenteb
siemprea
que no divida este nuevo prefijo. Capturamosa
en un grupo uno y luego verificamos si podemos alcanzar el comienzo de la cadena haciendo coincidir esa captura al menos una vez.b
luego se inserta en la cadena a través del poco utilizado$'
que inserta todo después del partido en la sustitución.Éste coincide con los personajes en las posiciones divididas por
a
ob
. Se aprovecha el hecho de que el resultado es simétrico: ya quelcm(a,b)
se divide entre ambosa
y seb
va hacia la izquierda al restar instanciasa
o seb
obtiene el mismo patrón que al ir a la derecha0
al sumarlos. La primera búsqueda anticipada simplemente capturaa
yb
. La segunda búsqueda anticipada verifica que haya un múltiplo de cada unoa
ob
caracteres antes del primer espacio.Como se indica en Wikipedia, además de la identidad de Bézout también es cierto que
Esto implica que el GCD corresponderá al espacio más corto entre dos
o
s 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(\.*)o
coincide 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 yso
(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úsculaO
s (con el espacio intermedio), así como el resto de la cadena LCM, pero descarte todo comenzando desde el espacio, para eliminara
yb
del resultado final.fuente
(\.*)
=>(a*)
.
tarde, lo que cuesta cuatro bytes (y deshacerse de los escapes solo ahorra 3).𝔼𝕊𝕄𝕚𝕟, 50 caracteres / 90 bytes
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
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
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 reemplazaO[dots]O
utilizando una función toUpperCase.fuente
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.
Ejemplo
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).
fuente
Japt , 83 bytes
Todavía no está totalmente golfizado ... Y no quiere jugar golf: /
fuente
r
en lugar de$.replace($
?Javascript,
170164161153145141136 bytesEso es bastante lonnnggggg ...
Demo , variables definidas explícitamente porque el intérprete usa el modo estricto.
fuente
i%a<1||i%b<1?'o':'.'
coni%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')
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.)Python 2,
217200191 bytesEsto es un poco contundente, pero funciona. Se agradece cualquier consejo de golf,
especialmente si sabe cómo solucionar eltengo!s[i] = s[v] = "o"
problema que encontré, donde eso sobrescribiría "O". ¡LoSin golf:
fuente