# Overview

Some of you might be aware of the Kolakoski Sequence (A000002), a well know self-referential sequence that has the following property:

It is a sequence containing only 1's and 2's, and for each group of 1's and twos, if you add up the length of runs, it equals itself, only half the length. In other words, the Kolakoski sequence describes the length of runs in the sequence itself. It is the only sequence that does this except for the same sequence with the initial 1 deleted. (This is only true if you limit yourself to sequences made up of 1s and 2s - Martin Ender)

# The Challenge

The challenge is, given a list of integers:

• Output -1 if the list is NOT a working prefix of the Kolakoski sequence.
• Output the number of iterations before the sequence becomes [2].

# The Worked Out Example

Using the provided image as an example:

[1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1] # Iteration 0 (the input).
[1,2,2,1,1,2,1,2,2,1,2]             # Iteration 1.
[1,2,2,1,1,2,1,1]                   # Iteration 2.
[1,2,2,1,2]                         # Iteration 3.
[1,2,1,1]                           # Iteration 4.
[1,1,2]                             # Iteration 5.
[2,1]                               # Iteration 6.
[1,1]                               # Iteration 7.
[2]                                 # Iteration 8.

Therefore, the resultant number is 8 for an input of [1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1].

9 is also fine if you are 1-indexing.

# The Test Suite (You can test with sub-iterations too)

------------------------------------------+---------
Truthy Scenarios                          | Output
------------------------------------------+---------
[1,1]                                     | 1 or 2
[1,2,2,1,1,2,1,2,2,1]                     | 6 or 7
[1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1]       | 8 or 9
[1,2]                                     | 2 or 3
------------------------------------------+---------
Falsy Scenarios                           | Output
------------------------------------------+---------
[4,2,-2,1,0,3928,102904]                  | -1 or a unique falsy output.
[1,1,1]                                   | -1
[2,2,1,1,2,1,2] (Results in [2,3] @ i3)   | -1 (Trickiest example)
[]                                        | -1
[1]                                       | -1

If you're confused:

Truthy: It will eventually reach two without any intermediate step having any elements other than 1 and 2. – Einkorn Enchanter 20 hours ago

Falsy: Ending value is not [2]. Intermediate terms contain something other than something of the set [1,2]. A couple other things, see examples.

This is , lowest byte-count will be the victor.

• Can we use any falsey value instead of just -1? – mbomb007 Jun 28 '17 at 20:05
• What do you mean by "NOT a working prefix of the Kolakoski sequence"? I had assumed you meant the list does not eventually reach [2] until I saw the [2,2,1,1,2,1,2] test case. – ngenisis Jun 28 '17 at 21:42
• @ngenisis It will eventually reach two without any intermediate step having any elements other than 1 and 2. – Ad Hoc Garf Hunter Jun 29 '17 at 0:27
• Might be a good idea to add [1] as a test case. – Emigna Jun 29 '17 at 9:54
• @mbomb007 any distinct value is fine. A positive integer is not fine. If you're 1-indexing 0 is fine. "False" is fine. Erroring is fine. Any non-positive return value is fine, even -129.42910. – Magic Octopus Urn Jun 29 '17 at 15:33

39 bytes saved thanks to Ørjan Johansen

import Data.List
f[2]=0

Try it online!

# Python 2, 122 bytes

def f(s,c=2,j=0):
w=[1]
for i in s[1:]:w+=[1]*(i!=s[j]);w[-1]+=i==s[j];j+=1
return(w==[2])*c-({1,2}!=set(s))or f(w,c+1)

Try it online!

# Python 3, 120 bytes

def f(s,c=2,j=0):
w=[1]
for i in s[1:]:w+=[1]*(i!=s[j]);w[-1]+=i==s[j];j+=1
return(w==[2])*c-({1,2}!={*s})or f(w,c+1)

Try it online!

# Explanation

A new sequence (w) is initialized to store the next iteration of the reduction. A counter (c) is initalized to keep track of the number of iterations.

Every item in the original sequence (s) is compared to the previous value. If they are the same, the value of the last item of (w) is increased with 1. If they are different, the sequence (w) is extended with [1].

If w==[2], the counter (c) is returned. Else, if the original sequence (s) contains other items than 1 and 2, a value -1 is returned. If neither is the case, the function is called recursively with the new sequence (w) as (s) and the counter (c) increased by 1.

• To save a byte, I'm trying to combine the first two lines into def f(s,c=2,j=0,w=[1]):, but that gives a different result. Could anybody explain why that is? – Jitse Jul 24 '19 at 8:14
• Mutable default arguments will stay mutated – Jo King Jul 24 '19 at 11:02
• @JoKing That makes perfect sense, thanks! – Jitse Jul 24 '19 at 11:05

# R, 122 bytes

a=scan()
i=0
f=function(x)if(!all(x%in%c(1,2)))stop()
while(length(a)>1){f(a)
a=rle(a)$l f(a) i=i+1} if(a==2)i else stop() Passes all test cases. Throws one or more errors otherwise. I hate validity checks; this code could have been so golfed if the inputs were nice; it would be shorter even in case the input were a sequence of 1’s and 2’s, not necessarily a prefix of the Kolakoski sequence. Here, we have to check both the initial vector (otherwise the test case [-2,1]) would have passed) and the resulting vector (otherwise [1,1,1] would have passed). # Ruby, 81 77 bytes f=->a,i=1{a[1]&&a-[1,2]==[]?f[a.chunk{|x|x}.map{|x,y|y.size},i+1]:a==[2]?i:0} Try it online! Edit: Saved 4 bytes by converting to recursive lambda. Returns 1-indexed number of iterations or 0 as falsey. Makes use of Ruby enumerable's chunk method, which does exactly what we need - grouping together consecutive runs of identical numbers. The lengths of the runs constitute the array for the next iteration. Keeps iterating while the array is longer than 1 element and no numbers other than 1 and 2 have been encountered. # Pyth, 45 bytes L?||qb]1!lb-{b,1 2_1?q]2b1Z.V0IKy~QhMrQ8*KhbB Try it online! This is probably still golfable. It's definitely golfable if .? worked the way I hoped it would (being an else for the innermost structure instead of the outermost) L?||qb]1!lb-{b,1 2_1?q]2b1Z # A lambda function for testing an iteration of the shortening L # y=lambda b: ? # if qb]1 # b == [1] | !lb # or !len(b) | {b # or b.deduplicate() - ,1 2 # .difference([1,2]): _1 # return -1 ?q]2b1Z # else: return 1 if [2] == b else Z (=0) .V0 # for b in range(0,infinity): IKy~Q # if K:=y(Q := (applies y to old value of Q) hM # map(_[0], rQ8 # run_length_encode(Q)): *Khb # print(K*(b+1)) B # break # Perl 5-p, 71 bytes$_.=$";s/(. )\1*/$&=~y|12||.$"/ge&$.++while/^([12] ){2,}$/;$_=/^2 $/*$.

Try it online!

1-indexed. Outputs 0 for falsy.