¿Sabías que el algoritmo euclidiano es capaz de generar ritmos musicales tradicionales ? Veremos cómo funciona esto describiendo un algoritmo similar, pero ligeramente diferente al del documento.

Elija un número entero positivo n, el número total de latidos y un número entero positivo k, el número de latidos que suenan (notas). Podemos pensar en el ritmo como una secuencia de nbits, kde los cuales son 1s. La idea del algoritmo es distribuir los 1 lo más uniformemente posible entre los 0.

Por ejemplo, con n = 8y k = 5, comenzamos con 5 unos y 3 ceros, cada uno en su propia secuencia:

[1] [1] [1] [1] [1] [0] [0] [0]

En cualquier momento tendremos dos tipos de secuencias: las que están al principio son las secuencias "centrales" y las que están al final son las secuencias "restantes". Aquí los núcleos son [1]sy los restos son [0]s. Siempre que tengamos más de una secuencia restante, las distribuiremos entre los núcleos:

[1 0] [1 0] [1 0] [1] [1]

Ahora el núcleo es [1 0]y el resto es [1], y distribuimos nuevamente:

[1 0 1] [1 0 1] [1 0]

Ahora el núcleo es [1 0 1]y el resto es [1 0]. Como solo tenemos una secuencia restante, nos detenemos y obtenemos la cadena

10110110

Esto es lo que parece, repetido 4 veces:

Aquí hay otro ejemplo, con n = 16y k = 6:

[1] [1] [1] [1] [1] [1] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0]
[1 0] [1 0] [1 0] [1 0] [1 0] [1 0] [0] [0] [0] [0]
[1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0] [1 0]
[1 0 0 1 0] [1 0 0 1 0] [1 0 0] [1 0 0]
[1 0 0 1 0 1 0 0] [1 0 0 1 0 1 0 0]
1001010010010100

Observe cómo terminamos en el último paso con dos secuencias centrales y sin secuencias restantes. Aquí está, repetido dos veces:

Entrada

Puede escribir una función o un programa completo leyendo desde STDIN, línea de comando o similar. La entrada será dos enteros positivos ny k <= n, que puede suponer que está en cualquier orden.

Salida

Su tarea es generar el ritmo generado como una ncadena larga de caracteres. Puede elegir cualquiera de los dos caracteres ASCII imprimibles distintos (0x20 a 0x7E) para representar notas y descansos.

Casos de prueba

Los siguientes casos de prueba se utilizan xpara representar notas .ys para representar descansos. La entrada se da en el orden n, entonces k.

1 1    ->  x
3 2    ->  xx.
5 5    ->  xxxxx
8 2    ->  x...x...
8 5    ->  x.xx.xx.
8 7    ->  xxxxxxx.
10 1   ->  x.........
11 5   ->  x.x.x.x.x..
12 7   ->  x.xx.x.xx.x.
16 6   ->  x..x.x..x..x.x..
34 21  ->  x.xx.x.xx.xx.x.xx.x.xx.xx.x.xx.x.x
42 13  ->  x...x..x..x..x...x..x..x..x...x..x..x..x..
42 18  ->  x..x.x.x..x.x.x..x.x.x..x.x.x..x.x.x..x.x.

Puntuación

Este es el código de golf, por lo que gana el código en la menor cantidad de bytes.

CJam, 37 34 30 27 24 bytes

3 bytes guardados por el usuario 23013.

q~,f>{_(a-W<}{e`:a:e~z}w

Esto toma la entrada como kprimero, nsegundo. Utiliza 1y 0para indicar notas y descansos, respectivamente.

Pruébalo aquí. Alternativamente, aquí hay un arnés de prueba que ejecuta todos los casos de prueba dados (intercambiando el orden de entrada) y también formatea la salida para usar xy .para una comparación más fácil con las soluciones de referencia. (Los resultados que aparecen en la entrada del arnés de prueba se descartan antes de ejecutar el código. Se pueden eliminar de forma segura sin afectar el programa).

Explicación

q~                       e# Read and eval the input, dumping k and n on the stack.
  ,                      e# Create a range [0 .. n-1]
   f>                    e# For each of them, check if it's less than k.
                         e# This gives k 1s and n-k 0s.
     {      }{        }w e# While the first block yields a truthy result, execute
                         e# the second block.
      _                  e# Duplicate the array.
       (a-               e# Remove all instances of core sequences.
          W<             e# Remove one remainder sequence if there is one. This
                         e# gives an empty array (falsy) whenever there are less
                         e# than two remainder sequences.
              e`         e# Run-length encode. I.e. this turns an array into a list
                         e# of pairs of run-length and element.
                :a:e~    e# Wrap each RLE pair in an array and RLD it. This
                         e# partitions the array into cores and remainders.
                     z   e# Zip the two parts, interleaving cores and remainders.

Este proceso arraiga matrices muy anidadas, pero la parte importante es que todos los núcleos (y todos los restos) siempre tienen la misma estructura anidada, por lo que siguen siendo iguales entre sí. CJam imprime automáticamente el contenido de la pila al final del programa y omite los delimitadores de matriz por completo, por lo tanto, esta estructura tampoco afecta la salida.

Haskell, 125 bytes

r=replicate
g z(a:b)(c:d)=g((a++c):z)b d
g z x y=(z,x++y)
f(x,y)|length y>1=f$g[]x y|1<2=concat$x++y
n#k=f(r k "x",r(n-k)".")

Ejemplo de uso: 42 # 13-> x...x..x..x..x...x..x..x..x...x..x..x..x...

ftoma dos parámetros: núcleo y lista de resto. Comprime ambas listas (vía g) y se llama a sí mismo nuevamente o se detiene si el resto es demasiado corto. La función principal #crea las listas de inicio y las llamadas f.

Python, 85

f=lambda n,k,a='1',b='0':n-k<2and a*k+b*(n-k)or[f(n-k,k,a+b,b),f(k,n-k,a+b,a)][2*k>n]

La solución recursiva natural. Los parámetros (n,k,a,b)representan un núcleo de k a's seguido de un resto de n-k b's.

Esta solución es ineficiente porque fse evalúan ambas llamadas recursivas , lo que provoca un número exponencial de llamadas.

Traté de comprimir la invocación condicional de flike

f(max(n-k,k),min(n-k,k),a+b,[a,b][2*k<n])
f(*[n-k,k,k,n-k,b,a][2*k>n::2]+[a+b])

pero ninguno resultó más corto.