É assim que a sequência de Kolakoski (OEIS A000002 ) é definida:
A sequência de Kolakoski é uma sequência que contém
1
e2
, e on
th elemento da sequência é o comprimento don
th grupo de elementos iguais (execução) na própria sequência. Os primeiros 20 termos da sequência e os respectivos comprimentos são: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
Essencialmente, os comprimentos dos grupos de elementos iguais da sequência Kolakoski é a própria sequência Kolakoski.
Tão longe, tão bom, mas que por que devemos nos restringir 1
e 2
? Nós não vamos! Dadas duas entradas, uma matriz de números inteiros positivos A
e um número inteiro N
, retornam os primeiros N
termos da sequência tipo Kolakoski definida por meio de ciclo A
. Para entender melhor, aqui está um exemplo trabalhado com os comprimentos dos grupos recém-adicionados entre colchetes:
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 ]
Aqui está outro exemplo trabalhado com um 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 você pode ver acima, o resultado final foi cortado em N = 10
elementos. O n
elemento th deve ter a duração do grupo n
th de elementos iguais, mesmo que o próprio elemento pertença ao grupo ao qual se refere. Como no caso acima, o primeiro 1
se refere ao primeiro grupo desse tipo que é exatamente isso 1
, e o primeiro 2
se refere ao segundo grupo desse tipo, que começa com ele.
Regras
- Você pode assumir que
A
nunca terá dois ou mais elementos iguais consecutivos.A
pode conter um número inteiro mais de uma vez, mas o primeiro e o último elementos não serão iguais eA
conterão pelo menos 2 elementos (por exemplo[1, 2, 2, 3]
,[2, 4, 3, 1, 2]
e[3]
não serão fornecidos). Isso porque se houvesse elementos iguais consecutivos, o resultado final teria sido um prefixo inválido para essa sequência. - Você pode presumir que
A
contém apenas números inteiros positivos (pois, de outra forma, uma sequência não seria definida). - Você pode assumir que
N
é um número inteiro não negativo (N >= 0
). - Você não pode retornar mais termos do que o solicitado.
- É estritamente proibido usar qualquer uma das brechas padrão .
- Você pode usar qualquer método de I / O razoável .
- Sua resposta não precisa ir além dos limites da linguagem natural, mas em teoria seu algoritmo deve funcionar para entradas e números arbitrariamente grandes .
- Isso é código-golfe , então a resposta mais curta vence.
Casos de teste
[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]
fonte
Respostas:
Casca , 8 bytes
Toma primeiro o comprimento, depois a lista. Experimente online!
Explicação
fonte
Pitão, 14 bytes
Experimente online: demonstração ou teste
Explicação:
fonte
u&VSvzs*V]M*Ql
Java 8,
151 + 19119115 bytesExperimente online!
fonte
&&
a&
e removendo uma vírgula: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 )(c==i?a:l)[i]
vez dec==i?a[i]:l[i]
R ,
120114108 bytes-6 bytes graças ao plannapus
Experimente online!
Função anônima; sucessivamente inverte a RLE, substituindo os comprimentos
a[[1]]
com o RLE invertido, e os valoresa[[2]]
comA
replicados para um comprimento igual ao daa$l
.fonte
a$l
e,a$v
se não existirem, mas não afetarão a chamadainverse.rle
, causando um loop infinito. Eu acho que só posso usara$l
nawhile
condição e narep
condição.Haskell , 68 bytes
Muito obrigado a Laikoni e flawr por sua ajuda na depuração e golfe desta resposta na sala de chat do PPCG Haskell, Of Monads and Men . Sugestões de golfe são bem-vindas! Experimente online!
A primeira linha é uma função anônima. A segunda linha é a compreensão infinita da lista que produz nossa sequência tipo Kolakoski.
Explicação
Primeiro, definimos
z
como o chefe dea
coma@(z:_)
. Em seguida, inicializamos a sequência com(z<$[1..z])
.A partir
1
de então,do i<-[1..]
anexamos o seguinte à sequência :,cycle a!!i<$[1..f a!!i]
que é oi
-ésimo membro dos temposa
anexados (ciclados indefinidamente)f a!!i
.Por fim, a função anônima simplesmente aceita os primeiros
n
termos de nossa sequência semelhante a Kolaskoski.fonte
Python 2 , 123 bytes
Experimente online!
fonte