Kolakoski sequence
The Kolakoski sequence is a sequence of 1's and 2's such that if you take the lengths of each run of the sequence, the result is the same as the original sequence. There are actually two sequences that fit this definition with their only difference being a 1 at the beginning. Its first 16 terms are:
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, ...
There are a few different ways to generate the sequence, such as iteratively making bigger copies of the sequence from smaller ones or using a growing queue.
Examples
1+
(1|1\":##[#1](2|11+\":##[#11+](1)))
><>
> >1}:n1-?!v1}v ^}2^!?-1n:}2< <
Bitdeque
In the deque, 1 is represented by a 1 bit, and 2 is represented by a 0 bit.
INVERT PUSH EJECT GOTO 6 INVERT PUSH INVERT PUSH EJECT GOTO 1 PUSH INVERT GOTO 1
Bitwise Cyclic Tag
In the data string, 1 is represented as 10 and 2 as 11. The initial data string is a single 2 (11), skipping the first 1, 2 of the sequence.
11100111001111011110
brainfuck
Uses two-pointers to work. It initializes the first 5 terms and adds the number that's different from the fast pointer value for slow pointer value times.
+++++++[>+++++++<-]>.+..-..[-] ; Print out "12211"
+>>>>++>>>>++>>>>+>+>>>+>>+<<<<<<<<<<<<<<<<<<< ; Store 1 2 2 1 1
; s^ f^
+[ ; Infinite loop
>>-[+>>>>-]+ ; Go to the slow pointer
<[
>>-[+>>>>-]+ ; Go to the fast pointer
>>[>>>>]+++ ; Set top value to 3
<<-[+<<<<-]+ ; Go back to the fast pointer
<<[>>>+>[>>>>]<<<<-<<-[+<<<<-]+<<-] ; Set top value to 3 minus fast pointer value
>>>[<<<+>>>-] ; Restore fast pointer value
<<<[>>>>]<<<++++++[<++++++++>-]<. ; Output top value as character
>++++++[<-------->-] ; Restore to number
-[+<<<<-]+<- ; Decrement slow pointer value
]
>>>[<<<+>>>-] ; Restore slow pointer value
<-[+>>>>-]+ ; Go to the fast pointer
[>>[>>>>]<<+<<<<-[+<<<<-]] ; Move fast pointer to top
<-[+<<<<-]+[>>>>+<<<<-] ; Move slow pointer to the next
>>-[+<<<<-]+ ; Move back to infinite loop flag
]
FALSE
This stores the queue as a pair of integers, one containing the actual data in bits, and the other being used as the "enqueue pointer".
[@$2*\@*@+]n: {enqueue}
[\2/\$2/\1&]d: {dequeue}
1 0 {initialize queue}
[0~][0n;!d;!$1+._[0n;!]?1n;!d;!$1+._[1n;!]?]#
This program instead stores the queue elements in the stack and uses ø to dequeue.
{queue is stored as <discarded elements>, <queue elements>, <queue length>}
[\1+]n: {enqueue}
[1-$1+ø]d: {dequeue}
0 {initialize queue}
[0 0=][1n;!d;!$.2=[1n;!]?2n;!d;!$.2=[2n;!]?]#
Python 3
def kolakoski():
q, p = [], 1
while True:
q.append(p)
yield (x := q.pop(0))
if x == 2:
q.append(p)
p = 3 - p