Secuencias de autorreferenciación tipo Kolakoski

19

Así es como se define la secuencia de Kolakoski (OEIS A000002 ):

La secuencia de Kolakoski es una secuencia que contiene 1y 2, y el nelemento th de la secuencia es la longitud del ngrupo th de elementos iguales (ejecución) en la secuencia misma. Los primeros 20 términos de la secuencia y las longitudes respectivas son:

1 2 2 1 1 2 1 2 2 1 2 2 1 1 2 1 1 2 2 1
- --- --- - - --- - --- --- - --- --- -
1  2   2  1 1  2  1  2   2  1  2   2  1

Esencialmente, la longitud de los grupos de elementos iguales de la secuencia de Kolakoski es la secuencia de Kolakoski misma.

Hasta ahora, todo bien, pero ¿por qué deberíamos restringirnos a 1y 2? ¡No vamos a hacerlo! Dadas dos entradas, una matriz de enteros positivos Ay un entero N, devuelven los primeros Ntérminos de la secuencia similar a Kolakoski definida por el ciclo A. Para comprenderlo mejor, aquí hay un ejemplo trabajado con las longitudes de los grupos recién agregados entre paréntesis:

A = [2, 3, 1]
N = 25

2: [[2], 2 ]
3: [ 2 ,[2], 3 , 3 ]
1: [ 2 , 2 ,[3], 3 , 1 , 1 , 1 ]
2: [ 2 , 2 , 3 ,[3], 1 , 1 , 1 , 2 , 2 , 2 ]
3: [ 2 , 2 , 3 , 3 ,[1], 1 , 1 , 2 , 2 , 2 , 3 ]
1: [ 2 , 2 , 3 , 3 , 1 ,[1], 1 , 2 , 2 , 2 , 3 , 1 ]
2: [ 2 , 2 , 3 , 3 , 1 , 1 ,[1], 2 , 2 , 2 , 3 , 1 , 2 ]
3: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 ,[2], 2 , 2 , 3 , 1 , 2 , 3 , 3 ]
1: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 ,[2], 2 , 3 , 1 , 2 , 3 , 3 , 1 , 1 ]
2: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 ,[2], 3 , 1 , 2 , 3 , 3 , 1 , 1 , 2 , 2 ]
3: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 , 2 ,[3], 1 , 2 , 3 , 3 , 1 , 1 , 2 , 2 , 3 , 3 , 3 ]
1: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 , 2 , 3 ,[1], 2 , 3 , 3 , 1 , 1 , 2 , 2 , 3 , 3 , 3 , 1 ]
2: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 1 ,[2], 3 , 3 , 1 , 1 , 2 , 2 , 3 , 3 , 3 , 1 , 2 , 2 ]
C: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 1 , 2 , 3 , 3 , 1 , 1 , 2 , 2 , 3 , 3 , 3 , 1 , 2 , 2 ]

Aquí hay otro ejemplo trabajado con un líder 1:

A = [1, 2, 3]
N = 10

1: [[1]]
2: [ 1 ,[2], 2 ]
3: [ 1 , 2 ,[2], 3 , 3 ]
1: [ 1 , 2 , 2 ,[3], 3 , 1 , 1 , 1 ]
2: [ 1 , 2 , 2 , 3 ,[3], 1 , 1 , 1 , 2 , 2 , 2 ]
C: [ 1 , 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 ]

Como puede ver arriba, el resultado final se cortó en N = 10elementos. El nelemento th debe ser la longitud del ngrupo de elementos iguales th, incluso si el elemento en sí pertenece al grupo al que se refiere. Como en el caso anterior, el primero se 1refiere al primer grupo, que es solo eso 1, y el primero se 2refiere al segundo grupo, que comienza con él.

Reglas

  • Puede suponer que Anunca tendrá dos o más elementos iguales consecutivos. Apuede contener un número entero más de una vez, pero el primer y el último elemento no serán iguales y Acontendrán al menos 2 elementos (por ejemplo [1, 2, 2, 3], [2, 4, 3, 1, 2]y [3]no se darán). Eso es porque si hubiera elementos iguales consecutivos, el resultado final habría sido un prefijo inválido para tal secuencia.
  • Puede suponer que Asolo contiene enteros positivos (ya que, de lo contrario, dicha secuencia no estaría definida).
  • Puede suponer que Nes un entero no negativo ( N >= 0).
  • No puede devolver más términos de los solicitados.
  • El uso de cualquiera de las lagunas estándar está estrictamente prohibido.
  • Puede usar cualquier método de E / S razonable .
  • Su respuesta no tiene que funcionar más allá de los límites del lenguaje natural, pero en teoría su algoritmo debería funcionar para entradas y números enteros arbitrariamente grandes .
  • Este es el , por lo que gana la respuesta más corta.

Casos de prueba

[5, 1, 2], 0 -> []
[2, 3, 1], 25 -> [2, 2, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 2, 2, 3, 3, 3, 1, 2, 2]
[1, 2, 3], 10 -> [1, 2, 2, 3, 3, 1, 1, 1, 2, 2]
[1, 2], 20 -> [1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1]
[1, 3], 20 -> [1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 1, 3, 3, 3, 1, 1, 1, 3]
[2, 3], 50 -> [2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3]
[7, 4], 99 -> [7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 7, 7, 7, 7, 4, 4, 4, 4, 7, 7, 7, 7, 4, 4, 4, 4, 7, 7, 7, 7, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7, 7, 4]
[1, 2, 3], 5 -> [1, 2, 2, 3, 3]
[2, 1, 3, 1], 2 -> [2, 2]
[1, 3, 5], 2 -> [1, 3]
[2, 3, 2, 4], 10 -> [2, 2, 3, 3, 2, 2, 2, 4, 4, 4]
Erik el Outgolfer
fuente
sandbox (2k + usuarios)
Erik the Outgolfer
Relacionado.
Martin Ender
@MartinEnder pensó que ya lo había vinculado
Erik the Outgolfer el

Respuestas:

9

Casco , 8 bytes

Ṡωȯ↑⁰`Ṙ¢

Primero toma la longitud, luego la lista. Pruébalo en línea!

Explicación

Ṡωȯ↑⁰`Ṙ¢  Inputs: n=9 and x=[2,1,3]
Ṡωȯ       Apply the following function to x until a fixed point is reached:
           Argument is a list, say y=[2,2,1,3,3,3]
       ¢   Cycle x: [2,1,3,2,1,3..
     `Ṙ    Replicate to lengths in y: [2,2,1,1,3,2,2,2,1,1,1,3,3,3]
   ↑⁰      Take first n elements: [2,2,1,1,3,2,2,2,1]
          Final result is [2,2,1,1,3,2,1,1,1], print implicitly.
Zgarb
fuente
8

Pyth, 14 bytes

u<s*V]M*QlGGvz

Pruébelo en línea: conjunto de demostración o prueba

Explicación:

u                 start with G = input array
       *QlG       repeat input array
     ]M           put every element into its own list
   *V      G      repeat every list vectorized by the counts in G
  s               flatten
 <          vz    take the first (second input line) numbers
                  and assign them to G until you reach fixed point
Jakube
fuente
Alternativa interesante:u&VSvzs*V]M*Ql
Jakube
1
Este es un buen enfoque.
Erik the Outgolfer
5

Java 8, 151 + 19119115 bytes

a->n->{int c=0,l[]=new int[n],i=0,j;for(;i<n;i++)for(j=0;j<(c==i?a[i]:l[i])&c<n;j++)l[c++]=a[i%a.length];return l;}

Pruébalo en línea!

Roberto Graham
fuente
1
Puede reducir cuatro bytes mediante la eliminación de dos paréntesis, cambiando &&a &y la eliminación de una coma: a->n->{int c=0,l[]=new int[n],i=0,j;for(;i<n;i++)for(j=0;j<(c==i?a[i]:l[i])&c<n;j++)l[c++]=a[i%a.length];return l;}( 115 bytes )
Kevin Cruijssen
Sugerir en (c==i?a:l)[i]lugar dec==i?a[i]:l[i]
ceilingcat
5

R , 120 114 108 bytes

-6 bytes gracias a plannapus

function(A,N){i=inverse.rle
w=length
a=rle(A)
while(w(a$l)<N){a[[1]]=i(a)
a[[2]]=rep(A,l=w(a$l))}
i(a)[0:N]}

Pruébalo en línea!

Función anónima; invierte sucesivamente el RLE, reemplazando las longitudes a[[1]]con el RLE invertido, y los valores a[[2]]con Areplicados a una longitud igual a la de a$l.

Giuseppe
fuente
@plannapus ah, cierto! Intenté eso y bloqueé R porque en la asignación, se creará a$ly a$vsi no existen, pero no afectarán la llamada a inverse.rle, causando un bucle infinito. Creo que solo puedo usar a$len la whilecondición y la repcondición.
Giuseppe
5

Haskell , 68 bytes

Muchas gracias a Laikoni y flawr por su ayuda en la depuración y el golf de esta respuesta en la sala de chat PPCG Haskell, Of Monads and Men . Sugerencias de golf bienvenidas! Pruébalo en línea!

(.f).take
f a@(z:_)=(z<$[1..z])++do i<-[1..];cycle a!!i<$[1..f a!!i]

La primera línea es una función anónima. La segunda línea es la comprensión de la lista infinita que produce nuestra secuencia tipo Kolakoski.

Explicación

Primero, definimos zcomo la cabeza de acon a@(z:_). Luego, inicializamos la secuencia con (z<$[1..z]).

Entonces, de en 1adelante,do i<-[1..] agregamos lo siguiente a la secuencia:, cycle a!!i<$[1..f a!!i]que es el imiembro número-en a(agregado de manera indefinida) en f a!!itiempos.

Finalmente, la función anónima simplemente toma los primeros ntérminos de nuestra secuencia similar a Kolaskoski.

Sherlock9
fuente
1

Python 2 , 123 bytes

x,y=input()
k=x[0]
t,j=[],0
if k==1:t,j=[k]+x[1]*[x[1]],2
while len(t)<y:t+=(j and t[j]or k)*[x[j%len(x)]];j+=1
print t[:y]

Pruébalo en línea!

officialaimm
fuente