---
# System prepended metadata

title: Exploring the Kolakoski Sequence

---

## Draft

- TODO: Collapse for code? So you don't spoiler the solution.


---

# Exploring the Kolakoski Sequence

## Preface

I'm currently on an exchange semester and decided to take the course 'Functional Programming'. I also took a course about OCaml, so I was interested in seeing how it compares to Haskell (spoiler: it's quite similar). 

There's one big difference in the course though: The assignments are almost more math than programming. This was very frustrating in the beginning, because you need to understand each problem. But I learned to love these exercises and decided to share one of the assignments. 

TODO: Improve

TODO: 
- Exchange semester
- FP course -> Combining math and programming
- Banging head against desk

## What is it? 

Okay, what exactly is the Kolakosi sequence? It's an infinite sequence of 1s and 2s, which is the sequence of the length of it's own run-length-encoding. 

Sounds confusing? Well, I also didn't get it the first time. 

Let's take it step by step: What is run-length encoding? 

### Run-length encoding

It is a form of lossless compression, where you count the length of sequences and store them in a single value.

For example, the string "ABBCCCDDDD" would be encoded as "1A2B3C4D". 

### Defining the sequence

First, we need to define some rules of the sequence: 
- Sequence can only contain 1s and 2s
- They appear in a run of 1 or 2 (e.g. 1/2 or 11/22)
- Runs of the same number must not repeat (e.g. 111/222 is not allowed)

![](https://hackmd.io/_uploads/SybjgfQ-T.png)
TODO: Remake this image

TODO: Explain how it works

It's generated like this:
![](https://upload.wikimedia.org/wikipedia/commons/a/ac/Kolakoski_animated.gif)


## Naive solution

TODO: Show the one liner first and then explain how to get there? 



```haskell
selfrle :: [Int]
selfrle = 1 : 2 : (drop 2 $ selfrle' selfrle 1)
  where
    selfrle' [] _ = []
    selfrle' (n : xs) x
      | n == 1 = x : selfrle' xs (nextKey x)
      | n == 2 = x : x : selfrle' xs (nextKey x)

nextKey :: Int -> Int
nextKey n
  | n == 1 = 2
  | n == 2 = 1
```


TODO: Show Very naive solution
TODO: Break it down




## Optimized solution

```haskell
selfrle :: [Int]
selfrle = 1 : 2 : drop 2 (concat $ zipWith replicate selfrle $ cycle [1, 2])
```


## Resources

https://en.wikipedia.org/wiki/Kolakoski_sequence