68
\$\begingroup\$

This is a repost of an old challenge, in order to adjust the I/O requirements to our recent standards. This is done in an effort to allow more languages to participate in a challenge about this popular sequence. See this meta post for a discussion of the repost.

The Kolakoski sequence is a fun self-referential sequence, which has the honour of being OEIS sequence A000002 (and it's much easier to understand and implement than A000001). The sequence starts with 1, consists only of 1s and 2s and the sequence element a(n) describes the length of the nth run of 1s or 2s in the sequence. This uniquely defines the sequence to be (with a visualisation of the runs underneath):

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,2,1,1,2,...
= === === = = === = === === = === === = = === = = === === = === =
1, 2,  2, 1,1, 2, 1, 2,  2, 1, 2,  2, 1,1, 2, 1,1, 2,  2, 1, 2, 1,...

Your task is, of course, to implement this sequence. You may choose one of three formats to do so:

  1. Take an input n and output the nth term of the sequence, where n starts either from 0 or 1.
  2. Take an input n and output the terms up to and including the nth term of the sequence, where n starts either from 0 or 1 (i.e. either print the first n or the first n+1 terms).
  3. Output values from the sequence indefinitely.

In the second and third case, you may choose any reasonable, unambiguous list format. It's fine if there is no separator between the elements, since they're always a single digit by definition.

In the third case, if your submission is a function, you can also return an infinite list or a generator in languages that support them.

You may write a program or a function and use any of our standard methods of receiving input and providing output. Note that these loopholes are forbidden by default.

This is , so the shortest valid answer – measured in bytes – wins.

Improve this question
\$\endgroup\$
3

47 Answers 47

Reset to default
1
2
2
\$\begingroup\$

APL (Dyalog Unicode), 34 bytes

1{⎕←⍺⌷⍵⋄(1+⍺)∇⍵,⍵[2+⍺]⍴2-2|⍺}1 2 2

Try it online!

I'm flabbergasted that there was no APL answer to this challenge yet. This is a full program that outputs the sequence indefinitely.

Thanks to @dzaima for -3 bytes.

How

1{⎕←⍺⌷⍵⋄(1+⍺)∇⍵,⍵[2+⍺]⍴2-2|⍺}1 2 2 ⍝ Full program. Inputs ⍺=1, ⍵=1 2 2
  ⎕←                                ⍝ Print
    ⍺⌷⍵                             ⍝ the ⍺th element of ⍵
       ⋄                            ⍝ Then
        (1+⍺)∇                      ⍝ Recurse with ⍺=⍺+1 and ⍵=
              ⍵,                    ⍝ append to ⍵
                       2-2|⍺        ⍝ 2 minus ⍺ modulo 2
                      ⍴             ⍝ reshape (repeats right arg, left arg times)
                ⍵[2+⍺]              ⍝ using the (2+⍺)th element of ⍵
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ {⍵{⍺↑⍵/⍺⍴⍳2}⍣⍵⍴⍨⍵} (port of the jelly answer) \$\endgroup\$
    – rak1507
    Jan 14, 2021 at 21:20
1
\$\begingroup\$

Jelly, 15 bytes

R€a"JḂ$Fo2
2Ç¡ḣ

A monadic link accepting an integer n which yields the first n terms.

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 59 bytes

Nest[Flatten@*MapIndexed[Mod[#2,2,1]~Table~#&],{2},#][[#]]&

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

axo, 13 bytes

[:|[1+{#;1;-_

Try it online!

Explanation

This started out as a port of an alternative solution in my Wumpus answer:

2%)[=]&=[O00.

This resulted in 18 bytes. I ended up golfing it down to the 13 bytes you see above to adjust it more to the way axo works. This 13-byte version then ended up inspiring the improvement down to 11 bytes in Wumpus, so now it's actually closer to that version.

As in Wumpus, in iteration i, the bottom of the stack holds a(i)-1 and the top holds the first element of the ith run, but we're working with 0 and 1 throughout, except for printing.

[:    Store a copy of the top of the stack in register A.
|     Pull up a(i)-1 from the bottom of the stack.
[1+{  Print a(i).
#;    If a(i)-1 is 1, push the value in register A.
1;-   Push another copy of that value and subtract it from 1 to swap
      0 and 1 for the next run.
_     Jump back to the beginning of the program.
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Ruby, 45 39 bytes

a=*i=0;loop{a+=[k=1+i%2]*p(a[i+=1]||k)}

prints indefinitely

Try it online!

Try it with an overloaded print function that allows you to pick a separator and the number of elements printed

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Br**nfuck, 96 bytes

+.+..<<+.[.[[>>]<+<[<<]>>-]>>[>>]<[>[>>]+++<<[<]>>-]<[<+>>+<-]>[>->>[-<]<<[<]>-]<<[>+<-]>[<<]>>]

Try it online!

This prints terms indefinitely.

Explanation

+.+..<<+.[                       Initialize the tape with {1, 0, 2} (printing the first four terms). Start an infinite loop.
  .[ [>>] <+< [<<] >>- ]           Print the first value and move it to the end. Let's call it n.
  >> [>>]                          Move to the end of the filled part of the tape.
  <[                               n times:
    > [>>] +++<< [<] >>-             Make a three on the end.
  ]
  < [<+>>+<-]                      Copy the last sequence value calculated, k.
  >[>->>[-<]<<[<]>-]               Subtract k from all the 3s made earlier.
  <<[>+<-]>                        Move the copied k back into place.
  [<<]>>                           Return to the start of the tape.
]                                End loop.

I've been trying to save some bytes by including no empty cells between terms. No luck so far, but maybe someday soon...

Pastebin of the (naïvely) transpiled .java file. Outputs as base-10 numbers, each on a line. Come to think of it, unary is probably the way to go for this challenge...

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Why would you censor "brain" but not "fuck"... ? \$\endgroup\$
    – Esolanging Fruit
    Mar 8, 2018 at 5:56
  • \$\begingroup\$ @EsolangingFruit It seems to be a variant of one of the name variants of BF \$\endgroup\$
    – Conor O'Brien
    Mar 8, 2018 at 18:18
1
\$\begingroup\$

Ruby, 44 43 37 bytes

b=*a=2;loop{b+=[a^=3]*p(b[$.+=1]||a)}

Try it online!

Prints an infinite sequence of numbers separated by newlines. -1 byte thanks to Martin Ender.

Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

CJam, 31 27 23 bytes

Prints the first n entries.

l~H3b{ee{(2%)+}%e~}2$*<

Try online

Improve this answer
\$\endgroup\$
5
  • 1
    \$\begingroup\$ You can replace [1 2 2] with H3b (convert 17 to base 3). \$\endgroup\$
    – Esolanging Fruit
    Mar 20, 2018 at 5:27
  • \$\begingroup\$ Good catch! Answer updated. \$\endgroup\$
    – chtenb
    Mar 20, 2018 at 10:01
  • \$\begingroup\$ A simple byte save would be ~4+ --> 3^, but you can actually do several bytes better by making use of run-length decoding: l~H3b{ee{(2%)+}%e~}2$*< (I also changed = to < because it's the same byte count but makes it easier to verify the correctness of the solution.) \$\endgroup\$
    – Martin Ender
    Mar 20, 2018 at 20:18
  • \$\begingroup\$ I'm quite new to code golfing and I hadn't looked into these compression mechanisms like base conversion and runlength encoding yet. Gotta read up I guess :) \$\endgroup\$
    – chtenb
    Mar 21, 2018 at 14:27
  • \$\begingroup\$ I managed to golf the anwer without ee down to 24 bytes: l~_H3b\{_X2%)a\X)=*+}fX< \$\endgroup\$
    – chtenb
    Mar 27, 2018 at 16:05
1
\$\begingroup\$

Perl 6, 53 41 bytes

-12 bytes thanks to nwellnhof!

{1,2,2,{$/=$++%2+1;|($/xx@_[2+$++])}...*}

Try it online!

Anonymous code block that returns a lazy infinite sequence of values.

Explanation:

{                                       }  # Anonymous code block
 1,2,2,     #Hard-code the self-referential elements
       {                           }...*   # Get the next element based on the previous elements
        $/=$++%2+1;    # Swap the variable keeping track of 1 or 2
                     $/xx   # Repeat that variable
                         @_[2+$++]   # From the next element in the sequence
                   |(             )  # And add those elements to the sequence
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ 41 bytes (I think it's OK to simply return an infinite sequence. 47 bytes, otherwise.) \$\endgroup\$
    – nwellnhof
    Oct 5, 2018 at 9:42
  • \$\begingroup\$ @nwellnhof Neat. I didn't know you could add more than one element to the list at a time, thanks! \$\endgroup\$
    – Jo King ♦
    Oct 5, 2018 at 9:54
  • 1
    \$\begingroup\$ -1 byte, avoiding $/: Try it online! \$\endgroup\$
    – naffetS
    Dec 17, 2022 at 23:23
1
\$\begingroup\$

APL (Dyalog Extended), 13 bytes

{⍺↑2-2|⍸⍵}⍣≡⍨

Try it online!

Basically a port of 13-byte J code at the bottom of algorithmshark's J answer ($1+2|I.)^:_~.

Takes an integer n and gives first n terms.

How it works

{⍺↑2-2|⍸⍵}⍣≡⍨  ⍝ Input: n
{        }     ⍝ At each step,
       ⍸⍵      ⍝   For each item a_i at index i, give a_i copies of i
   2-2|        ⍝   Modulo 2 then subtract from 2;
               ⍝   convert 1 2 3 4 5 .. to 1 2 1 2 1 ..
 ⍺↑            ⍝   Take first n items
          ⍣≡   ⍝ Repeat until the result does not change
            ⍨  ⍝   using n as both the fixed ⍺ and the starting ⍵
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Factor, 75 bytes

[ { 1 2 } over [ [ 2 mod 1 + <array> ] map-index concat ] times swap head ]

Try it online!

Somewhat ended up like the J solution, just more bloaty.

Since Factor is stack-based, it is shorter to hardcode the starting array than to copy the input and create an array out of it.

[                      ! anonymous lambda, taking input n from stack
  { 1 2 } over         ! ( n arr n )
  [ ... ] times        ! run lambda n times to the array { 1 2 } ...
    [ ... ] map-index  !   given an array, map each with index...
      2 mod 1 +        !     ( item idx%2+1 )
      <array>          !     an array of length `item`, filled with idx%2+1
    concat             !   concat the elements of nested arrays
  swap head            ! take first n items from the result
]
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Jelly, 21 bytes

3_ṪẋŒgL‘ịƲ⁸;
2Rx`Ç⁸¡ḣ

Try it online!

Improve this answer
\$\endgroup\$
0
0
\$\begingroup\$

MIPS, 128 124 108 88 bytes

Changelog:

  • Mar 24: Fix mod
  • Mar 25: Simplify algorithm (no need to push n)
  • Mar 26: Simpler algorithm using stack 

 Address    Code        Basic                     Source

0x00400000  0x24020001  addiu $2,$0,0x00000001    8         li      $v0, 1          # print first 3 vals
0x00400004  0x2404007a  addiu $4,$0,0x0000007a    9         li      $a0, 122        
0x00400008  0x0000000c  syscall                   10        syscall
0x0040000c  0x24180002  addiu $24,$0,0x0000000    12        li      $t8, 2          # const 2
0x00400010  0xafb8fff4  sw $24,0xfffffff4($29)    13        sw      $t8, -12($sp)   # l[3] = 2
0x00400014  0x24080003  addiu $8,$0,0x00000003    14        li      $t0, 3          # n = 3
0x00400018  0x23a9fff4  addi $9,$29,0xfffffff4    15        addi    $t1, $sp, -12   # i = l + 3
0x0040001c  0x23abfff4  addi $11,$29,0xfffffff    16        addi    $t3, $sp, -12   # ln = l + 3
0x00400020  0x31040001  andi $4,$8,0x00000001     19        andi    $a0, $t0, 1     # n%2 
0x00400024  0x03042022  sub $4,$24,$4             20        sub     $a0, $t8, $a0   # x = 2 - n%2
0x00400028  0xad24fffc  sw $4,0xfffffffc($9)      21        sw      $a0, -4($t1)    # *(i+1) = x
0x0040002c  0x0000000c  syscall                   24        syscall                 # print x
0x00400030  0x8d6c0000  lw $12,0x00000000($11)    26        lw      $t4, ($t3)      # temp = *ln
0x00400034  0x20010002  addi $1,$0,0x00000002     27        bne     $t4, 2, kol2    # if temp == 2
0x00400038  0x142c0003  bne $1,$12,0x00000003          
0x0040003c  0xad24fff8  sw $4,0xfffffff8($9)      29        sw      $a0, -8($t1)    # *(i+2) = x
0x00400040  0x0000000c  syscall                   32        syscall                 # print x
0x00400044  0x2129fffc  addi $9,$9,0xfffffffc     34        addi    $t1, $t1, -4    # i += 1
0x00400048  0x2129fffc  addi $9,$9,0xfffffffc     37        addi    $t1, $t1, -4    # i += 1
0x0040004c  0x21080001  addi $8,$8,0x00000001     38        addi    $t0, $t0, 1     # n += 1
0x00400050  0x216bfffc  addi $11,$11,0xfffffff    39        addi    $t3, $t3, -4    # ln += 1
0x00400054  0x08100008  j 0x00400020              40        j       koll

Old solution

 Address    Code        Basic                     Source

0x00400040  0x23bdfff4  addi $29,$29,0xfffffff    32        addi    $sp, $sp, -12           # allocate 3 ints
0x00400044  0xafbf0000  sw $31,0x00000000($29)    33        sw      $ra, ($sp)              # push $ra
0x00400048  0x20010001  addi $1,$0,0x00000001     34        bne     $a0, 1, kol1            # if n == 1
0x0040004c  0x14240002  bne $1,$4,0x00000002           
0x00400050  0x00041021  addu $2,$0,$4             35        move    $v0, $a0                # return n
0x00400054  0x08100026  j 0x00400098              36        j       kolret
0x00400058  0x24100001  addiu $16,$0,0x0000000    39        li      $s0, 1                  # k = 1
0x0040005c  0x00048821  addu $17,$0,$4            40        move    $s1, $a0                # x = n
0x00400060  0xafb00004  sw $16,0x00000004($29)    43        sw      $s0, 4($sp)             # push k
0x00400064  0xafb10008  sw $17,0x00000008($29)    44        sw      $s1, 8($sp)             # push x
0x00400068  0x00102021  addu $4,$0,$16            45        move    $a0, $s0                # arg1 = k
0x0040006c  0x0c100010  jal 0x00400040            46        jal     kol                     # f(k)
0x00400070  0x8fb00004  lw $16,0x00000004($29)    48        lw      $s0, 4($sp)             # pop k
0x00400074  0x8fb10008  lw $17,0x00000008($29)    49        lw      $s1, 8($sp)             # pop x
0x00400078  0x02228822  sub $17,$17,$2            51        sub     $s1, $s1, $v0           # x -= f(k)
0x0040007c  0x20010001  addi $1,$0,0x00000001     52        bgt     $s1, 1, kol4            # if x <= 1
0x00400080  0x0031082a  slt $1,$1,$17                  
0x00400084  0x14200007  bne $1,$0,0x00000007           
0x00400088  0x02301020  add $2,$17,$16            53        add     $v0, $s1, $s0           # r = x + k
0x0040008c  0x20420001  addi $2,$2,0x00000001     54        addi    $v0, $v0, 1             # r = x + i + 1
0x00400090  0x30420001  andi $2,$2,0x00000001     55        andi    $v0, $v0, 1             # r = (x + k + 1) % 2
0x00400094  0x20420001  addi $2,$2,0x00000001     56        addi    $v0, $v0, 1             # ret (x+k+1)%2 + 1
0x00400098  0x8fbf0000  lw $31,0x00000000($29)    59        lw      $ra, ($sp)              # pop $ra
0x0040009c  0x23bd000c  addi $29,$29,0x0000000    60        addi    $sp, $sp, 12            # free stack memory
0x004000a0  0x03e00008  jr $31                    61        jr      $ra
0x004000a4  0x22100001  addi $16,$16,0x0000000    64        addi    $s0, $s0, 1             # k += 1
0x004000a8  0x08100018  j 0x00400060              65        j       kolw

Assembly-friendly algorithm I came up with, based on Benoit Cloitre's OEIS formula:

def f(n):
    if n == 1: return n
    k = 1
    x = n
    while True:
        x -= f(k)

        if x <= 1:
            return (x + k + 1)%2 + 1 

        k += 1

for n in range(1, 10):
    print(f(n), end=',')
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

PHP, 61 bytes

for($v=2;$n<$argn;$s.=$v^=3,$x>1&&$s.=$v)echo$x=$s[$n++]?:$n;

prints the first \$n\$ elements without a separator. Run as pipe with -nr or try it online.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Momema, 64 bytes

02 1 3-8 1j0+1*0+1-**00+1*0-8+1**1 1+1*1j+-1*+-1*1+1*0**00+1*0j1

Explanation

The idea is to gradually fill up the tape with the decremented values of the sequence. We use index 0 for the write head and index 1 for the read head.

0  2            #  w = 2
1  3            #  r = 3
-8 1            #  print(1)
j  0            #  do {
  +1*0  +1-**0  #    tape[1 + w] = 1 - tape[w]
  0     +1*0    #    w = 1 + w
  -8    +1**1   #    print(1 + tape[r])
  1     +1*1    #    r = 1 + r
j  +-1*+-1*1    #    if (tape[r - 1] - 1) continue
  +1*0  **0     #    tape[1 + w] = tape[w]
  0     +1*0    #    w = 1 + w
j  1            # } while (1)

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

dirt -v, 48 bytes

"122,11"|.*`,(1',.*(1'2|2'1)|2',.*(1"22"|2"11"))

Continuously outputs longer and longer Kolakoski sequences, with a , in the middle that moves right as the sequence is generated:

122,11
1221,12
12211,21
122112,122
1221121,221
12211212,2122
122112122,12211
1221121221,22112
12211212212,211211
122112122122,1121122
1221121221221,1211221
12211212212211,2112212
122112122122112,11221211
1221121221221121,12212112
12211212212211211,22121121
122112122122112112,212112122
1221121221221121122,1211212211
12211212212211211221,2112122112

Run as dirt kolakoski.dirt -v -i "", or by feeding it an empty file dirt kolakoski.dirt -v < empty.txt

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Unlambda, 419 bytes

```c`.1.2``s``s`ks``s`kd``s`kk``sii`k``s``s``s``si`kk`k``s``s``s``si`k`ki`k``s`k.1``s``s`ks``s`k`si``s`kk`s``s`ks``s`kk``s`ksk`k`k`ki`k``s`k.1``s``s`ks``s`k`si``s`kk`s`k`s``s`ksk`k`kk``si`kk`k``s``s``s``si`k`ki`k``s`k.2``s``s`ks``s`k`si``s`kk``s`k`s``s`ks``s`kk``s`ksk`s``s`ks``s`kk``s`ksk`k`k`ki`k``s`k.2``s``s`ks``s`k`si``s`kk``s`k`s`k`s``s`ksk`s`k`s``s`ksk`k`kk``si`kk``s`k`s``si`k`k`ki``s`kk``si`k`ki``s``si`k`ki`kk

Try it online!

No way this could be a contender for the shortest solution, but oh well. Prints indefinitely.

Improve this answer
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.