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< <
Binary lambda calculus
A 0 bit corresponds to 1, and a 1 bit corresponds to 2.
0 000 010 1 1 000 0 011 001 0 11 0 0 00 01 0 01 0 1 01 0 001 101 0 0 000 0 001 000 0 0 1 0 1 1 0 1 1 0 0 101 011 111 101 111 100 001 011 111 100 1 0 1 1 1 1 0 0 0 0 1 0 1 1 01111 101100001 011011111 00001 01101 111110111 00000 1 0 0 101 111 0 0 000 1 00 0 0 01 10 0 10 1 110 001 0 0 000 1 1 0 0 0 0 0 0 101 100 000 101 100 000 110
Below is a breakdown of the expression.
ONE = λfirst. λsecond. first
TWO = λfirst. λsecond. second
INVERT item = item TWO ONE
CONS head tail = λf. f head tail
GENERATE = λqueue. λnext. (
λhead. CONS head (
GENERATE (
λenqueue. queue (
head (CONS next enqueue) (CONS next (CONS next enqueue))
) TWO
) (INVERT next)
)
) (queue (λx. x) ONE)
MAIN = λ_. CONS ONE (CONS TWO (GENERATE (λenqueue. CONS TWO enqueue) ONE))
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
]
Another by User:Jan jelo:
cells:tmp|flag|tmp|tmp|tmp|term|preflag|lastflag|tmp|tmp|term|preflag|lastflag|tmp|tmp…
>+>>>>
+>+>+>>>
++>+>+>>>
++
[
>
[<<<<<]
<<<<<<<<
++++++[->++++++++<]
<<<[->>>>+<<<<]
>>>>.
<++++++[->--------<]
>[-<<<<+>>>>]
>>>>>>
[->>>+>+<<<<]
>>>>[-<<<<+>>>>]
<[-<<<[<<<<<]>>+>>>>[>>>>>]>>]
<<<[<<<<<]
>>[
-
<[->>+>+<<<]
>>[-<<+>>]
>[->>>[>>>>>]>>>+[<<<<<]>>>>]
>>>[>>>>>]+>>>>+<[<<<<<]
>>
]
+++<[->-<]
>[-<+>]
>>>>[>>>>>]+>>>>>-
>>>>
]
And another 176-bytes one by User:Blashyrkh, with o(log n) memory consumption. Generation of first 26 million terms of the sequence uses only 132 memory cells and 6.12 billion operations. Here's the stripped version. Version with comments is available at User:Blashyrkh/Kolakoski-brainfuck.
>+++++++[->+++++++<]>.->++>++>>++>++[<<<]>[>[-<+<+>>]<.<[->->+<<]>>>-[>]+>>>[<<+++<-<[->>-<<]>>[-<<+>>]>>-[>]+>>>]>++>[<--<]++>[<-->>>]<<<<<<-<<<<<[>>>[-<+<+>>]<[->+<]<<<<<]>>]
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;!]?]#
This interpreter has a handful more commands, but the roll n command "®" is quite helpful here.
1q:{current}
0h:{height}
[0 0=][
q;{push}
h;1+®{pop bottom}
$.", "{output}
2={popped == 2?}
[
q;{push another}
h;1+h:{increment h}
]?
3q;-q:{3 - q -> q}
]#{do forever!}
Kawa
Raw text version at Kawa/Raw programs#Kolakoski sequence
Lazy K
`k```s`s````ssi`s`k`s``s`ks``s``s`ks``s`k`s`k``s``s`ks``s`k`si``s`s`kk`k`sk``s`si`kk````ssi`s`k`s``s`ks``s``s``s`s`k`s`s`ks`k`k`k`k`sk`kk`k``s`k`s``ss`k`k`skk``s`k`s``s`ks``s`s`k``s```sik```ss`ss`kk``s`ks``s`k`sik`kk``s``s`ks``s`s`kki`k``si`k`sk`k``s`k`s`k``s```sss`ks`kk``s``s`ks``s`k`s`k``s`ks`s`k``s`ks``s`k`sik``s``s`ks``s`k`s`k``s`ks``s`k`sik``s`k`s````ssi`s`k`s``s`ks``s``s``s`s`k`s`s`ks`k`k`k`k`sk`kk`k``s`k`s``ss`k`k`skk``s`k`s``s`ks``s`s`k``s```sik```ss`ss`kk``s`ks``s`k`sik`kk``s``s`ks``s`s`kki`k``si`k`skk`kk```ss``ss``ss`s``si`k`sk`kk``s`kk``s`kk``s`s`k`s`k`s`k``s`k``s`k`s``s`k``s`ks``s`k`sik``s``si`k```si``si``s`s``s`k``s`ksk``s``sski```sski`s``s`ksk`k```si``s`s``s`k``s`ksk``s``sski```sski`s``s`kskkkiki
This is the result of "compilation" of the following lambda calculus code (preamble with definition of car/cdr/nil/etc... is omitted):
pushpop = lambda q p . (lambda q f . f (cdr q) (car q)) (append q p) onestep = lambda q p . pushpop q p (lambda q x f . f (x (append q p) q) (not p) x) kolakoski = (lambda f input . f f nil false) lambda self q p . onestep q p (lambda q p x . cons (x 50 49) (self self q p))
One can see that it's just the python example (see below) rewritten in functional paradigm.
MoreMathRPN
"p 1 "do "q.append(p) >> 0 "x = q.pop(0) # -> ]0 del 1 "yield x >> 0 outputV outputS ", " "if x == 2 -3 * 7 + jmp ]0 del 0 "q.append(p) >> 0 jmp 2 del 0 "p = 3 - p 3 -> 1 - "while true jmp -19
Muriel
S:"@\"S:\\\"\"+|S+\"\\\";\\nK:\\\"\"+K+$f+(%$f,0,(2=#(%K,i+2,i+3)))+\"\\\";\\nf:\"+$(3-f)+\";i:\"+$(i+1)+\";\\n.%K,i,i+1;\\n\"+S"; K:"122"; f:1;i:0; .%K,i,i+1; @"S:\""+|S+"\";\nK:\""+K+$f+(%$f,0,(2=#(%K,i+2,i+3)))+"\";\nf:"+$(3-f)+";i:"+$(i+1)+";\n.%K,i,i+1;\n"+S
Post correspondence problem
These two are listed in the OEIS entry (they're mentioned as fixed points of substitutions, which are equivalent):
11 12 12 122 21 112 22 1122
This one skips the first 1:
11 21 12 211 21 221 22 2211
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
Another one:
k=[1,2,2] i=2 while True: print(k[i-2]) k+=[3-k[-1]]*k[i] i+=1
Tag system
Here, 1 is encoded as abc and 2 is encoded as ababc. The initial word is a single 2, skipping the first 1, 2 of the sequence.
Tag system
m: 2
A: {a,b,c}
P:
a --> abc
b --> ababc
c -->
Computation
Initial word: ababc
abcabc
cabcabc
bcabc
abcababc
cababcabc
...
Thue
[1>]1::=1[1>] [1>]2::=2[1>] [1>]*1::=[<1]1*[a1>] [1>]*2::=[<1]2*[a1>][a1>] (1)::=~1 (2)::=~2 1[<1]::=[<1]1 2[<1]::=[<1]2 >[<1]1::=1>[2>](1) >[<1]2::=2>[2>](2) [a1>]1::=1[a1>] [a1>]2::=2[a1>] [a1>]|::=1| [2>]1::=1[2>] [2>]2::=2[2>] [2>]*1::=[<2]1*[a2>] [2>]*2::=[<2]2*[a2>][a2>] 1[<2]::=[<2]1 2[<2]::=[<2]2 >[<2]1::=1>[1>](1) >[<2]2::=2>[1>](2) [a2>]1::=1[a2>] [a2>]2::=2[a2>] [a2>]|::=2| ::= |>[1>]12*2|
Uiua
⍢(↘1⊂:↙:⊂.⊂[]-:3⊣,⊡2.&pf⊢.|1)[1 2 2]