54
\$\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.

\$\endgroup\$

40 Answers 40

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...

\$\endgroup\$
  • 1
    \$\begingroup\$ Why would you censor "brain" but not "fuck"... ? \$\endgroup\$ – Esolanging Fruit Mar 8 '18 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 '18 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.

\$\endgroup\$
1
\$\begingroup\$

CJam, 31 27 23 bytes

Prints the first n entries.

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

Try online

\$\endgroup\$
  • 1
    \$\begingroup\$ You can replace [1 2 2] with H3b (convert 17 to base 3). \$\endgroup\$ – Esolanging Fruit Mar 20 '18 at 5:27
  • \$\begingroup\$ Good catch! Answer updated. \$\endgroup\$ – Chiel ten Brinke Mar 20 '18 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 '18 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\$ – Chiel ten Brinke Mar 21 '18 at 14:27
  • \$\begingroup\$ I managed to golf the anwer without ee down to 24 bytes: l~_H3b\{_X2%)a\X)=*+}fX< \$\endgroup\$ – Chiel ten Brinke Mar 27 '18 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
\$\endgroup\$
  • \$\begingroup\$ 41 bytes (I think it's OK to simply return an infinite sequence. 47 bytes, otherwise.) \$\endgroup\$ – nwellnhof Oct 5 '18 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 '18 at 9:54
1
\$\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 ⍵
\$\endgroup\$
0
\$\begingroup\$

Jelly, 21 bytes

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

Try it online!

\$\endgroup\$
0
\$\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!

\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 59 bytes

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

Try it online!

\$\endgroup\$
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=',')
\$\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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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