19
\$\begingroup\$

This is how the Kolakoski sequence (OEIS A000002) is defined:

The Kolakoski sequence is a sequence that contains 1 and 2, and the nth element of the sequence is the length of the nth group of equal elements (run) in the sequence itself. The first 20 terms of the sequence and the respective lengths are:

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

Essentially, the lengths of the groups of equal elements of the Kolakoski sequence is the Kolakoski sequence itself.

So far, so good, but that why should we restrict ourselves to 1 and 2? We're not going to! Given two inputs, an array of positive integers A and an integer N, return the first N terms of the Kolakoski-like sequence defined by cycling through A. To get the grasp of it better, here is a worked example with the lengths of the newly added groups in brackets:

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 ]

Here is another worked example with a leading 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 ]

As you can see above, the final result was cut to N = 10 elements. The nth element should be how long the nth equal-element group is, even if the element itself belongs in the group it refers to. As in the above case, the first 1 refers to the first such group which is just that 1, and the first 2 refers to the second such group, which starts with it.

Rules

  • You may assume that A will never have two or more consecutive equal elements. A may contain an integer more than once, but the first and last elements will not be equal, and A will contain at least 2 elements (e.g. [1, 2, 2, 3], [2, 4, 3, 1, 2] and [3] aren't going to be given). That's because if there were consecutive equal elements, the final result would've been an invalid prefix for such a sequence.
  • You may assume A only contains positive integers (as such a sequence would be otherwise undefined).
  • You may assume N is a non-negative integer (N >= 0).
  • You can't return more terms than requested.
  • Using any one of the standard loopholes is strictly forbidden.
  • You may use any reasonable I/O method.
  • Your answer doesn't have to work beyond natural language limits, but in theory your algorithm should work for arbitrarily large inputs and integers.
  • This is , so the shortest answer wins.

Test cases

[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]
\$\endgroup\$
9
\$\begingroup\$

Husk, 8 bytes

Ṡωȯ↑⁰`Ṙ¢

Takes first the length, then the list. Try it online!

Explanation

Ṡωȯ↑⁰`Ṙ¢  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.
\$\endgroup\$
8
\$\begingroup\$

Pyth, 14 bytes

u<s*V]M*QlGGvz

Try it online: Demonstration or Test suite

Explanation:

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
\$\endgroup\$
  • \$\begingroup\$ Interesting alternative: u&VSvzs*V]M*Ql \$\endgroup\$ – Jakube Sep 8 '17 at 12:54
  • 1
    \$\begingroup\$ This is a nice approach. \$\endgroup\$ – Erik the Outgolfer Sep 8 '17 at 12:56
5
\$\begingroup\$

Java 8, 151 + 19 119 115 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;}

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ You can reduce four bytes by getting rid of two parenthesis, changing && to & and removing a comma: 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) \$\endgroup\$ – Kevin Cruijssen Sep 11 '17 at 13:12
5
\$\begingroup\$

R, 120 114 108 bytes

-6 bytes thanks to 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]}

Try it online!

Anonymous function; successively inverts the RLE, replacing the lengths a[[1]] with the inverted RLE, and the values a[[2]] with A replicated to a length equal to that of a$l.

\$\endgroup\$
  • \$\begingroup\$ @plannapus ah, right! I did try that and crashed R because in assignment, it'll create a$l and a$v if they don't exist, but they won't affect the call to inverse.rle, causing an infinite loop. I think I can only use a$l in the while condition and the rep condition. \$\endgroup\$ – Giuseppe Sep 11 '17 at 14:02
5
\$\begingroup\$

Haskell, 68 bytes

Many thanks to Laikoni and flawr for their help in debugging and golfing this answer in the PPCG Haskell chatroom, Of Monads and Men. Golfing suggestions welcome! Try it online!

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

The first line is an anonymous function. The second line is the infinite list comprehension that produces our Kolakoski-like sequence.

Explanation

First, we define z as the head of a with a@(z:_). Then, we initialize the sequence with (z<$[1..z]).

Then, from 1 onwards, do i<-[1..], we append the following to the sequence: cycle a!!i<$[1..f a!!i], which is the i-th member of a (cycled indefinitely) appended f a!!i times.

Finally, the anonymous function simply takes the first n terms of our Kolaskoski-like sequence.

\$\endgroup\$
1
\$\begingroup\$

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]

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.