started at . submit by
we made it! let's celebrate: give me 100 terms of the kolakoski sequence. submissions may be written in any language.
ever dipped your toes in the field of compression? there's a basic concept there known as run-length encoding. you've probably heard of it. it makes it more efficient to store repeated symbols: to store "aaaaa", instead of keeping 5 copies of the character 'a', you can just remember "there are 5 'a's" here, right? so instead of just storing each character, you store them along with a "run length" that tells you how many times it's repeated. "apple" becomes "1a2p1l1e". simple, right?
let's forget about strings for a second. in fact, let's forget about what the runs consist of at all. let's remember "apple" as "1211", just the length of the runs. we'll define a function f that turns a string into a series of run lengths, so that f("apple") = "1211". I could repeat the operation to get f("1211") = "112"... this iteration reminds me of the look-and-say sequence, but it's a little different. because we don't keep the content of the runs, only their lengths, the string doesn't grow infinitely. if I keep going, I get "21", then "11", then "2". unlike look and say, it isn't growing to infinity. it in fact turns out that this operation has fixed points: infinite sequences x such that f(x) = x. the sequence is equal to its own sequence of run lengths!
the Kolakoski sequence is the unique such sequence that consists of only 1 and 2 and starts with 1. let's look at it:
1 2 2 1 1 2 1 2 2 1 2 2 1 1 2 1 1 2 2 1 2 1 1 2 1 2 2 1 1
- --- --- - - --- - --- --- - --- --- - - --- - - --- ---
1 2 2 1 1 2 1 2 2 1 2 2 1 1 2 1 1 2 2
above are the terms of the sequence and below the runs and their lengths are shown. for the infinite Kolakoski sequence, these two sequences are one and the same.
ordinarily, I'd let you generate as many terms of this sequence as you liked in any way that you liked. but this is round 100, so your challenge is to give me exactly 100 terms of the kolakoski sequence. as any language is allowed, there is no fixed API.
3 entries have been received so far.