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

17
\$\begingroup\$

Jelly, 7 bytes

2Rṁxṁµ¡

This is a full program that prints the first n terms.

Try it online!

How it works

2Rṁxṁµ¡  Main link. Argument: n (integer)

     µ   Combine the preceding links into a monadic chain.
      ¡  Set t = n.  Call the chain n times, updating t with the return value after
         each call. Yield the last value of t.
2R           Set the return value to 2 and take its range. Yields [1, 2].
  ṁ          Mold; cyclically repeat 1 and 2 to match t's length.
             In the first run, ṁ promotes t = n to [1, ..., n].
   x         Repeat the k-th element of the result t[k] times.
             In the first run, x repeats each element t = n times.
    ṁ        Mold; truncate the result to match the length of t.
             In the first run, ṁ promotes t = n to [1, ..., n].                 

Example run

Let n = 5.

The first invocation of the chain repeats 1, 2 cyclically to reach length 5, then each element 5 times, and finally truncates the result to length 5.

  1         2         1         2         1
x 5         5         5         5         5
---------------------------------------------------
  1 1 1 1 1 2 2 2 2 2 1 1 1 1 1 2 2 2 2 2 1 1 1 1 1

  1 1 1 1 1

This yields a list of length 5. The first element is the first element of the Kolakoski sequence.

The second invocation of the chain repeats 1, 2 cyclically to reach length 5, then repeats the kth element j times, where j is the kth element of the previous list, and finally truncates the result to length 5.

   1 2 1 2 1
x  1 1 1 1 1
------------
   1 2 1 2 1

   1 2 1 2 1

This yields another list of length 5. The first two elements are the first two elements of the Kolakoski sequence.

The process continues for three more iterations.

   1 2   1 2   1
x  1 2   1 2   1
----------------
   1 2 2 1 2 2 1

   1 2 2 1 2
   1 2   1   2 1
x  1 2   2   1 2
------------------
   1 2 2 1 1 2 1 1

   1 2 2 1 1
   1 2   1   2 1
x  1 2   2   1 1
----------------
   1 2 2 1 1 2 1

   1 2 2 1 1

These are the first five elements of the Kolakoski sequence.

\$\endgroup\$
12
\$\begingroup\$

Python 2, 51 bytes

l=[2]
print 1,2,
for x in l:print x,;l+=x*[l[-1]^3]

Prints indefinitely. Builds the list l as it's being iterated through. For each entry x of l, appends x copies of 1 or 2, whichever is opposite the current last element.

The main difficulty is dealing with the initial self-referential fragment [1,2,2]. This code just prints the initial 1,2 and proceeds from there. The extra printing costs 12 bytes. Without that:

39 bytes, missing first two entries:

l=[2]
for x in l:print x;l+=x*[l[-1]^3]

Another approach is to specially initialize the first two entries. We initialize l as [0,0,2] so that the first two entries don't cause appending, but print x or n makes them be printed as n.

51 bytes

l=[0,0,2]
n=1
for x in l:print x or n;l+=x*[n];n^=3

Another fix is to initialize l=[1], track the alternation manually in n, and correct the printing:

51 bytes

n,=l=[1]
for x in l:print(l==[1,1])+x;l+=x*[n];n^=3

Without the (l==[1,1])+, everything works except the printed sequences starts 1,1,2 instead of 1,2,2. There has to be a better way to recognize we're at this second step.

And another weird fix, also somehow the same byte count:

51 bytes

l=[1];q=2
for x in l:print x;l+=x*[l[-1]^3]*q;q=q<2
\$\endgroup\$
12
\$\begingroup\$

Wumpus, 13 11 bytes

=[=)O?=!00.

Try it online!

Prints the sequence indefinitely without separators.

I am genuinely surprised by how short this is.

Explanation

The basic idea is to keep the sequence on the stack and repeatedly use the bottom-most element to generate another run and then print it. We're effectively abusing the stack as a queue here. We can also save a couple of bytes by working 0 and 1 (incrementing only for output) instead of 1 and 2, because this way we don't need to explicitly initialise the stack with a 1 and we can use logical negation to toggle between the two values.

     The entire program is run in a loop.
     At the beginning of loop iteration i, a(i)-1 will be at the bottom of the
     stack and the first element of the ith run of values will be on top.
     The caveat is that on the first iteration, the stack is empty, but
     popping from an empty stack produces an implicit zero.
=    Duplicate the top of the stack. Since this is defined as "pop x, push
     x, push x" this will result in 2 zeros when the stack is empty.
     After this we've got two copies of the ith run's value on top of the stack.
[    Pull up a(i)-1 from the bottom of the stack.
=)O  Duplicate, increment to a(i) and print it.
?=   If a(i)-1 is 1 (as opposed to 0), make another copy of the top of the
     stack. We've now got a(i)+1 copies, so one more than the run should be 
     long, but that's great because we can use the additional copy to get 
     the start of the next run.
!    Logical negation which swaps 0 and 1.
00.  Jump back to the beginning of the program.
\$\endgroup\$
10
\$\begingroup\$

Brachylog, 30 26 25 23 17 16 14 bytes

~a₀{1|2}ᵐḅlᵐ?l

Outputs the first n values. Uses the "output variable" . for input, and outputs to the "input variable" ?. Try it online!

Explanation

I'm pretty happy with how declarative this turned out: the program is basically a high-level description of the output list and its relation to the input.

~a₀{1|2}ᵐḅlᵐ?l  Input is a number N.
                Output is a term that I'll call T.
~a₀             T is a prefix of a list L.
   {   }ᵐ       Each element of L
    1|2         is either 1 or 2.
         ḅ      If you cut L into blocks of equal elements
          lᵐ    and take the length of each block,
            ?   the result is T.
             l  The length of T is N.

Because {1|2}ᵐ tries out lists in lexicographic order, the output will begin with 1.

\$\endgroup\$
9
\$\begingroup\$

Husk, 10 bytes

Ṡωo↑⁰`Ṙ¢ḣ2

Returns the first n values. Try it online!

Explanation

Ṡωo↑⁰`Ṙ¢ḣ2  Input is an integer N.
        ḣ2  The range [1,2]
       ¢    Cycle: C = [1,2,1,2,1,2...
 ω          Iterate until fixed point is found:
Ṡ    `Ṙ      Replicate the list C element-wise according to the current list,
  o↑⁰        then take first N elements.

For input 20, the process goes like this:

[1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2...
[1,2,2,1,2,2,1,2,2,1,2,2,1,2,2,1,2,2,1,2]
[1,2,2,1,1,2,1,1,2,2,1,2,2,1,1,2,1,1,2,2]
[1,2,2,1,1,2,1,2,2,1,2,1,1,2,2,1,2,2,1,1]
[1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,1,2]
[1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1]
[1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1]
\$\endgroup\$
  • 1
    \$\begingroup\$ Here's a variation printing the sequence indefinitely, same byte count but maybe you'll see some golfing opportunities I didn't Try it online! \$\endgroup\$ – Leo Mar 7 '18 at 0:57
9
\$\begingroup\$

Java 10, 155 108 105 100 97 bytes

v->{var s="122";for(int i=1;;s+=(1+i%2)*(s.charAt(i)>49?11:1))System.out.print(s.charAt(++i-2));}

Prints indefinitely without delimiter.

-3 bytes after an indirect tip from @Neil.
-5 bytes thanks to @MartinEnder.
-3 bytes converting Java 8 to Java 10.

Explanation:

Try it online (times out after 60 sec on TIO).

v->{              // Method with empty unused parameter and no return-type
  var s="122";    //  String, starting at "122"
  for(int i=1;;   //  Loop `i` from 1 upwards indefinitely
      s+=         //    After every iteration: Append the String with:
         (1+i%2)  //     1+`i`modulo-2
         *(s.charAt(i)>49?11:1))
                  //     either once or twice depending on the digit at index `i`
    System.out.print(s.charAt(++i-2));}
                  //   Print the character at index `i-2` of the String
                  //   After we've first increased `i` by 1 with `++i`
\$\endgroup\$
  • 1
    \$\begingroup\$ I like how you have made this look so simple. \$\endgroup\$ – Erik the Outgolfer Mar 6 '18 at 12:52
  • \$\begingroup\$ @EriktheOutgolfer Thanks! :) When I read the challenge I wasn't sure how to even start, but then it hit me (using a list with the initial [1,2,2] and go from there) and I wrote the 155 byte answer (which is now golfed by using a String instead of List). \$\endgroup\$ – Kevin Cruijssen Mar 6 '18 at 12:55
  • \$\begingroup\$ Why not use (3-i) instead of (1+i%2)? \$\endgroup\$ – Erik the Outgolfer Mar 6 '18 at 12:58
  • 1
    \$\begingroup\$ @EriktheOutgolfer because i isn't 1 or 2, it's the string index. \$\endgroup\$ – Martin Ender Mar 6 '18 at 12:59
7
\$\begingroup\$

Jelly, 10 bytes

’߀+\<¹SḂ‘

Returns the nth term.

Try it online!

How it works

’߀+\<¹SḂ‘  Main link. Argument: n (positive integer)

’           Decrement; yield n-1.
 ߀         Recursively map the main link over [1, ..., n-1].
   +\       Take the cumulative sum.
            The k-th sum is the combined length of the first k runs.
     <¹     Compare each sum with n.
       S    Sum the Booleans.
            This counts the number of runs that occur before the n-th term.
            If there's an even number (including 0) of runs, the n-th term is 1.
            If there's an odd number of runs, the n-th term is 2.
        Ḃ   Extract the least significant bit of the count.
         ‘  Increment.
\$\endgroup\$
7
\$\begingroup\$

Haskell, 33 bytes

r=r%1
~(x:t)%n=n:[n|x>1]++t%(3-n)

Try it online!

Ørjan Johansen saved 7 bytes using an irrefutable pattern to force the prefix.

\$\endgroup\$
  • 5
    \$\begingroup\$ You can save 7 bytes by making it lazier. Try it online! \$\endgroup\$ – Ørjan Johansen Mar 8 '18 at 2:01
  • \$\begingroup\$ @ØrjanJohansen That's amazing and the lazy pattern is magic to me. Want to post your own answer? \$\endgroup\$ – xnor Mar 8 '18 at 3:43
  • \$\begingroup\$ Nah you were most of the way there. By using n: at the start of the expression you don't need to know the x is there to produce the first n. But you need the pattern to be lazy in order to avoid the function checking it before getting to the n:. \$\endgroup\$ – Ørjan Johansen Mar 8 '18 at 3:59
6
\$\begingroup\$

Gol><>, 8 7 bytes

:{:PnKz

Try it online!

Explanation

This is a port of my Wumpus answer. Gol><> is basically the language that has all the necessary features to port the Wumpus answer (specifically, implicit zeros at the bottom of stack, "duplicate" implemented "pop, push, push", and a stack rotation command), but:

  • It has a toroidal grid, which means we don't need the explicit 00. to jump back to the beginning.
  • It has K, which is "pop N, then duplicate the next element N times", which can replace ?=, saving another byte.

So the mapping from Wumpus to Gol><> becomes:

Wumpus   Gol><>
=        :
[        {
=        :
)        P
O        n
?=       K
!        z
00.
\$\endgroup\$
6
\$\begingroup\$

Shakespeare Programming Language, 594 583 572 bytes

Thanks to Ed Wynn for -10 bytes!

,.Ford,.Puck,.Act I:.Scene I:.[Enter Ford and Puck]Ford:You cat!Open heart!You big cat!Open heart!Puck:Remember you!Remember me!Scene V:.Ford:You is the sum ofI a cat!Puck:Recall!Open heart!Ford:Remember a pig!Is I nicer a cat?If notyou be the sum ofyou a big pig!Scene X:.Puck:Recall!Ford:Is I nicer zero?If soremember I!If solet usScene X!Puck:Is I nicer zero?You is the sum ofI a big cat!If soyou is I!Remember zero!Remember I!Remember you!You be the difference betweena big cat you!Scene L:.Ford:Recall!Is you worse I?If so,let usScene V!Puck:Remember I!Let usScene L!

Try it online!

This is a golfed version of Ed Wynn's ungolfed solution, starting from the 828 byte solution he linked in the comments and going a little nuts from there.

Explanation:

,.Ford,.Puck,.Act I:.Scene I:.[Enter Ford and Puck]    Boilerplate, introducing the characters
Ford:You cat!Open heart!You big cat!Open heart!  Print 1,2 as the first two terms of the sequence

Puck:Remember you!Remember me!  Initialise stack as 0, 2
                                Ford's value is currently 0, representing the value to be pushed to the stack

Scene V:.     Start infinite loop
  Ford:You is the sum ofI a cat!         
  Puck:Recall!Open heart!                 Pop the next value in the stack and print it
  Ford:Remember a pig!                    Push -1 as the end of the stack
  Is I nicer a cat?                       If Ford's value is 2
  If notyou be the sum ofyou a big pig! Subtract 2 from Puck's value to represent making 2 only one copy

        #Reverse the stack until it reaches the terminator value 0 or -1
  Scene X:.Puck:Recall!Ford:Is I nicer zero?If soremember I!If solet usScene X!

  Puck:Is I nicer zero?                          Check if the Puck's value is bigger than 0 (only making one copy)
  You is the sum of Ia big cat!                 Set Ford's value to Puck+2 to counter the change
  If soyou is I!                                But undo it if making one copies
  Remember zero!                                 Push 0 as the stack terminator
  Remember I!                                    Push Ford's value, which is 0 or -1 if this is a single copy, or 1 or 2 for a double copy
  Remember you!                                  Push one copy of Puck's value
  You be the difference betweena big cat you!   Map Ford's value from 1,2 to 1,0

  Scene L:.   #Reverse the stack until it reaches the terminator 0 
     Ford:Recall!Is you worse I?If solet us Scene V!
     Puck:Remember I!Let usScene L!
\$\endgroup\$
  • \$\begingroup\$ Nice! You can save 7 bytes by making the single child be (-1 or 0) instead of the twins. This costs you 1 byte just before Scene X (when "If so" becomes "If not"), and another byte just after the Scene X loop (when "Is I nicer you" becomes "Is I nicer zero"). The saving is that you can replace the "If not,remember you!" with simply "Remember I!" one line earlier. We insert either a second child or a spare terminator. (This is why you need to change the finely-balanced "Is I nicer you?" -- you can no longer rely on Ford==0 after Scene X.) Here is TIO, 587 bytes: tinyurl.com/yb9zg4gp \$\endgroup\$ – Ed Wynn May 8 '18 at 17:50
  • \$\begingroup\$ You can remove the first "If so," in Scene L and move the command to the start of Scene V. This saves you only 1 byte, because you need a new "Ford:". But you save a couple of bytes in Scene I, so long as you can rely on Ford being automatically zero-initialised. You have no right to rely on this, but it might work: here is TIO, 584 bytes: tinyurl.com/y9f6vy7u \$\endgroup\$ – Ed Wynn May 8 '18 at 17:55
5
\$\begingroup\$

><>, 13 12 bytes

0:{:1+n?:0=!

Try it online!

A port of Martin Ender's Wumpus answer. Unfortunately, ><> doesn't have an increment or an invert command nor does it have implicit 0s on the bottom of the stack, so this ends up being a bit longer.

\$\endgroup\$
  • 1
    \$\begingroup\$ Yep, this is what I had before remembering Gol><>. :) \$\endgroup\$ – Martin Ender Mar 7 '18 at 7:48
5
\$\begingroup\$

JavaScript, 67 66 60 58 52 51 50 bytes

Well, that made my brain itch more than it should have! Retruns the nth term, 0-indexed.

s=`122`
x=1
f=n=>s[n]||f(n,s+=s[++x%2]*(s[x]+0-9))

5+1 bytes saved thanks to tsh scratching my itchy brain!


Test it

The snippet below will output the first 50 terms.

s=`122`
x=1
f=n=>s[n]||f(n,s+=s[++x%2]*(s[x]+0-9))
o.innerText=[...Array(50).keys()].map(f).join`, `
<pre id=o></pre>


Explanation

This is one of those rare occasions when we can declare some variables outside the scope of our function, modify them within the function and still be able to reuse them on subsequent calls of the function.

s=`122`       :Initialise variable s as the string "122"
x=1           :Initialise variable x as integer 1
f=n=>         :Named function f taking input as an argument through parameter n
 s[n]         :If s has a character at index n, return it and exit
 ||           :Or
 f(n          :Call f with n again
  ,s+=        :At the same time, append to s
  s[++x%2]    :  Increment x, modulo by 2 and get the character at that index in s
  *           :  Multiplied by (the above gets cast to an integer)
  (s[x]+0-9)  :  Append a 0 to the xth character of s and subtract 9
 )            :  (The above gives "1"+0-9="10"-9=1 or "2"+0-9="20"-9=11)
\$\endgroup\$
  • \$\begingroup\$ What about n=>(g=s=>s[n]||g(s+(++x%2+1)*(10*s[x]-9)))('122',x=1) \$\endgroup\$ – tsh Mar 7 '18 at 7:00
  • \$\begingroup\$ Btw, is s='122',x=1,g=n=>s[n]||g(n,s+=(++x%2+1)*(10*s[x]-9)) considered a valid submission? \$\endgroup\$ – tsh Mar 7 '18 at 7:06
  • \$\begingroup\$ Thanks, @tsh. s[n]|| was a clear case of not seeing the wood for the trees! Your second suggestion wouldn't be valid ,though, as the function could only be called once; s & x need to be initialised with each call. \$\endgroup\$ – Shaggy Mar 7 '18 at 9:12
  • \$\begingroup\$ the second one does be reusable, as long as s and x not touched by other codes between each invokes (which is by default). \$\endgroup\$ – tsh Mar 7 '18 at 11:42
  • 1
    \$\begingroup\$ Nice! s[x]+0-9 is a pretty neat trick \$\endgroup\$ – JollyJoker Mar 7 '18 at 13:46
4
\$\begingroup\$

Python (2 and 3), 65 60 bytes

f=lambda n:sum([f(i)*[i%2+1]for i in range(2,n)],[1,2,2])[n]

Returns the nth entry, 0-indexed.

Alternative (65 bytes):

f=lambda n:n>1and sum([f(i)*[i%2+1]for i in range(n)],[])[n]or-~n
\$\endgroup\$
  • 3
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – Martin Ender Mar 6 '18 at 15:45
  • 1
    \$\begingroup\$ You can (probably, I didn't tested though) save 5 bytes in the alternative version by using [1,2,2] as starting value in the sum \$\endgroup\$ – Rod Mar 6 '18 at 16:06
4
\$\begingroup\$

Haskell, 48 bytes

-1 byte thanks to nimi. -2 bytes thanks to Lynn.

c=1:2:c
l=1:2:drop 2(id=<<zipWith replicate l c)

Try it online!

Repeat every element its position mod 2 + 1 times.

\$\endgroup\$
  • \$\begingroup\$ You can save two more by defining c=1:2:c \$\endgroup\$ – Lynn Mar 6 '18 at 20:45
4
\$\begingroup\$

brainfuck, 61 bytes

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

Try it online!

Prints numbers as char codes indefinitely. For clarity, here's a version that prints in numbers (except for the first two elements, which are easy enough to verify).

How It Works:

+.+. Prints the first two elements. These are the self-referential elements
     This also intitialises the tape with the third element, 2
[ Start infinite loop
   . Print current lowest element
   [>]>+++>+++ Move to end of tape and create two 3s
   <<<[->+>->-<<<] Subtract the last element of the tape from these 3s
   <[[->+<]<]>> Move to the beginning of the tape
   --  Subtract two from the first element
       This leaves 2 as 0 and 1 as -1
   [ If the number was 1
     [>]<,  Delete the excess element from the end of the tape
     <[<]>+ Remove the -1
   ]
   > Move to the next element of the list
]
\$\endgroup\$
4
\$\begingroup\$

05AB1E, 12 9 bytes

Saved 3 bytes thanks to Grimy

Prints the first n items.

Δ2LÞsÅΓI∍

Try it online!

Explanation

Δ           # repeat until ToS doesn't change
 2LÞ        # push [1,2,1,2 ...]               
    sÅΓ     # run-length encode with previous value (initially input)
       I∍   # extend/shorten to the length specified by input
\$\endgroup\$
  • \$\begingroup\$ Run-length decoding is now a built-in, so this can simply be 2L[2LÞsÅΓ. \$\endgroup\$ – Grimmy Jun 13 at 13:30
  • \$\begingroup\$ Or even better: ∞[2LÞsÅΓ. \$\endgroup\$ – Grimmy Jun 13 at 13:35
  • \$\begingroup\$ Or Δ2LÞsÅΓI∍ for a version that prints the first n items given input n. \$\endgroup\$ – Grimmy Jun 13 at 13:47
  • \$\begingroup\$ @Grimy: Thanks! I like the first n version since it actually terminates :) \$\endgroup\$ – Emigna Jun 14 at 15:26
3
\$\begingroup\$

05AB1E, 15 bytes

ƵLS[DNÌ©èF®É>¸«

Try it online! or with an iteration limit

Explanation

ƵLS               # push our initial list [1,2,2]
   [              # for every N in [0 ...
    D             # duplicate current list of numbers
     NÌ©è         # get the N+2'th element from the list
         F        # that many times do
          ®É>     # push ((N+2)%2==1)+1
             ¸«   # append to current list
\$\endgroup\$
  • \$\begingroup\$ Instead of ¸«, = would print them for 2 bytes saved. ƵLS[NÌ©èF®É>=, no need to dupe if you're not consuming. \$\endgroup\$ – Magic Octopus Urn Mar 6 '18 at 15:52
  • \$\begingroup\$ @MagicOctopusUrn: I don't produce the first 3 items though, so printing unfortunately doesn't work \$\endgroup\$ – Emigna Mar 6 '18 at 17:12
3
\$\begingroup\$

Python 3, 55 54 bytes

n=h=1;l=[]
while n:print(h);n^=3;h,*l=l+[n]*(l+[2])[0]

Try it online!

\$\endgroup\$
3
\$\begingroup\$

J, 12 bytes

Single-argument function taking n and producing the first n terms. Try it online!

$(1+2|I.)^:]

Just sprucing up my old answer to the old question.

I. is a verb which takes an array of numbers and spits out a list of indices, so that if the k-th item in the array is n, then the index k appears n times. We'll use it to bootstrap the Kolakowski sequence up from an initial seed. Each step will proceed as follows:

1 2   2   1 1 2   1 2   2   1   (some prefix)
0 1 1 2 2 3 4 5 5 6 7 7 8 8 9   (use I.)
0 1 1 0 0 1 0 1 1 0 1 1 0 0 1   (mod 2)
1 2 2 1 1 2 1 2 2 1 2 2 1 1 2   (add 1) 

If we perform this operation (1+2|I.) over and over starting from 10, it looks something like this:

10
1 1 1 1 1 1 1 1 1 1
1 2 1 2 1 2 1 2 1 2
1 2 2 1 2 2 1 2 2 1 2 2 1 2 2
1 2 2 1 1 2 1 1 2 2 1 2 2 1 1 ...
1 2 2 1 1 2 1 2 2 1 2 1 1 2 2 ...
1 2 2 1 1 2 1 2 2 1 2 2 1 1 2 ...

Notice how we get more and more correct terms each time, and after a while the first n terms are fixed. The number of iterations it takes to settle down is hard to describe precisely, but it looks to be roughly logarithmic in n, so if we just run it n times (^:]) it should be fine. (Check out these other OEIS sequences for more info: generation lengths, partial sums.)

Once we're done that, all we have to do is take the first n terms using $. The construction $v for any verb v is an example of a hook, and giving it n as argument will execute n $ (v n).

Here is the old 13-byte version which is far less wasteful of time and space: ($1+2|I.)^:_~. It truncates the input at every step, so we can run exactly as many times as is needed to settle, instead of linearly many times.

\$\endgroup\$
  • \$\begingroup\$ Oh this works perfectly with I.. I've always wanted to see the copy feature of it used in some golf. \$\endgroup\$ – miles Mar 11 '18 at 7:38
3
\$\begingroup\$

Fueue, 30 bytes

Fueue is a queue-based esolang in which the running program and its data are both in the same queue, the execution goes around the queue in cycles, and programming requires lots of synchronizing to keep anything from executing at the wrong time.

1)2:[[2:])~)~:~[[1]:~))~:~~]~]

Try it online!

The above prints an unending list of digits as control codes. For 34 bytes it can print actual digits:

49)50:[[50:])~)~:~[[49]:~))~:~~]~]

Try it online!

The rest of the explanation uses the latter version.

Summary of Fueue elements

The Fueue queue can contain the following kind of elements:

  • Integers, which print their Unicode codepoint when executed,
  • Square-bracket delimited subprogram blocks, which are mercifully inactive (just moving to the end of the queue) unless the ) function deblocks them, and
  • Single-character functions, which execute if they are followed by the right type of arguments and remain inactive otherwise.
    • The only functions used in this program are ~ (swap two following elements), : (duplicate next element), and ) (deblock following block).

High level overview

During the main loop of the program, the queue consists of:

  • a chain of blocks representing digits to be iterated through;
    • A digit 1 or 2 is represented by the blocks [49] and [50:], respectively.
  • a self-replicating main loop section that traverses the digit blocks and puts alternating 1s and 2s after them, then deblocks them.
    • An deblocked digit block prints its own digit d, and then creates d copies of the following block, thus creating the digits for the run it describes.

Low level trace of first 10 commands

Cmds   Explanation              Queue
49     Print '1'.               )50:[[50:])~)~:~[[49]:~))~:~~]~]
)      Inactive, move to end.   50:[[50:])~)~:~[[49]:~))~:~~]~])
50     Print '2'.               :[[50:])~)~:~[[49]:~))~:~~]~])
:[...] Duplicate block.         )[[50:])~)~:~[[49]:~))~:~~]~][[50:])~)~:~[[49]:~))~:~~]~]
)[...] Deblock (rmv. brackets). [[50:])~)~:~[[49]:~))~:~~]~][50:])~)~:~[[49]:~))~:~~]~
[...]  Inactive.                [50:])~)~:~[[49]:~))~:~~]~[[50:])~)~:~[[49]:~))~:~~]~]
[50:]  Inactive.                )~)~:~[[49]:~))~:~~]~[[50:])~)~:~[[49]:~))~:~~]~][50:]
)      Inactive.                ~)~:~[[49]:~))~:~~]~[[50:])~)~:~[[49]:~))~:~~]~][50:])
~)~    Swap ) and ~.            :~[[49]:~))~:~~]~[[50:])~)~:~[[49]:~))~:~~]~][50:])~)
:~     Duplicate ~.             [[49]:~))~:~~]~[[50:])~)~:~[[49]:~))~:~~]~][50:])~)~~

Walkthrough of a full main loop iteration

Optional whitespace has been inserted to separate commands.

49 ) 50 :[[50:])~)~:~[[49]:~))~:~~]~]

Cycle 1: 49 prints 1. ) is inactive, waiting to be brought together with the main loop block. 50 prints 2. : duplicates the main loop block (which needs a copy for self-replication.)

) [[50:])~)~:~[[49]:~))~:~~]~] [[50:])~)~:~[[49]:~))~:~~]~]

Cycle 2: ) deblocks the first main loop block, making it start executing next cycle.

[50:] ) ~)~ :~ [[49]:~))~:~~] ~[[50:])~)~:~[[49]:~))~:~~]~]

Cycle 3: [50:] represents the first digit produced in the chain, a 2 not yet deblocked. The following ) will eventually do so after the rest of the main loop has traversed it. ~)~:~ is a golfed (using a swap and a copy) one-cycle delay of ~)~~. [[49]:~))~:~~] is inactive. ~ swaps the following main loop block past the [50:] digit block.

) ~)~ ~[[49]:~))~:~~][50:] [[50:])~)~:~[[49]:~))~:~~]~]

Cycle 4: ) still waits, ~)~ produces ~), ~ swaps [[49]:~))~:~~] past the [50:] digit block.

) ~)[50:] [[49]:~))~:~~] [[50:])~)~:~[[49]:~))~:~~]~]

Cycle 5: ~ swaps ) past the [50:] digit block.

)[50:] )[[49]:~))~:~~] [[50:])~)~:~[[49]:~))~:~~]~]

Cycle 6: The first ) now deblocks the [50:] digit block, the next ) deblocks the subprogram [[49]:~))~:~~].

50 :[49] :~ ) ) ~:~ ~[[50:])~)~:~[[49]:~))~:~~]~]

Cycle 7: 50 prints 2, : duplicates the just produced [49] digit block, creating a run of two 1s. :~))~:~ is a one-cycle delay of ~~))~:. ~ swaps the remaining main loop block past the first [49].

[49] ~~) ) ~:[49] [[50:])~)~:~[[49]:~))~:~~]~]

Cycle 8: ~~)) is a one-cycle delay of )~). ~ swaps : past the currently traversed [49].

[49] ) ~)[49] :[[50:])~)~:~[[49]:~))~:~~]~]

Cycle 9: ~ swaps ) past [49]. : duplicates the main loop block.

[49] )[49] )[[50:])~)~:~[[49]:~))~:~~]~] [[50:])~)~:~[[49]:~))~:~~]~]

Cycle 10: The first ) deblocks the [49] digit block just traversed, the second ) restarts the main loop to traverse the next one (above shown at the beginning of the queue.)

\$\endgroup\$
  • \$\begingroup\$ Nice work! The reason I learned some Fueue and answered the HW challenge because I actually looked into it for this challenge, but ended up being too intimidated by the queue-based nature. That's a really great score for Fueue! :) \$\endgroup\$ – Martin Ender Mar 20 '18 at 19:40
3
\$\begingroup\$

x86, 41 37 35 33 28 bytes

I had a lot of fun messing around with different x86 instructions, as this is my first "non-trivial" x86 answer. I actually learned x86-64 first, and I saved many bytes just by converting my program to 32-bit.

It turns out the algorithm I used from OEIS pushes values to an array, which makes it amenable to x86 and storing values on the stack (note MIPS doesn't have stack instructions).

Currently the program takes N values as input in ecx and returns an address in ebp of an array with the nth element representing the nth value in the sequence. I assume returning on the stack and computing extra values is valid (we consider what's beyond the array as garbage anyway).

Changelog

  • -4 bytes by computing x = 2 - n%2 with xor every iteration

  • -2 bytes by using do-while instead of while loop.

  • -2 bytes by pushing initial values 1, 2, 2 using eax

  • -5 bytes by not storing n explicitly and instead running loop N times

.section .text
.globl main
main:
        mov     $10, %ecx           # N = 10 

start:
        mov     %esp, %ebp          # Save sp
        push    $1
        push    $2                  # x = 2
        pop     %eax       
        push    %eax                # push 2
        push    %eax                # push 2
        mov     %esp, %esi          # sn = stack+3 addr

loop:                               
        xor     $3, %al             # flip x between 1 <-> 2 
        push    %eax                # push x      
                                    # maybe use jump by parity?
        cmp     $2, (%esi)          # if *sn == 2 
        jne     loop1
        push    %eax                # push x

loop1: 
        sub     $4, %esi            # sn += 1
        loop    loop                # --N, do while (N)
end:
        mov     %ebp, %esp          # Restore sp
        ret

Objdump:

00000005 <start>:
   5:   89 e5                   mov    %esp,%ebp
   7:   6a 01                   push   $0x1
   9:   6a 02                   push   $0x2
   b:   58                      pop    %eax
   c:   50                      push   %eax
   d:   50                      push   %eax
   e:   89 e6                   mov    %esp,%esi

00000010 <loop>:
  10:   34 03                   xor    $0x3,%al
  12:   50                      push   %eax
  13:   83 3e 02                cmpl   $0x2,(%esi)
  16:   75 01                   jne    19 <loop1>
  18:   50                      push   %eax

00000019 <loop1>:
  19:   83 ee 04                sub    $0x4,%esi
  1c:   e2 f2                   loop   10 <loop>

0000001e <end>:
  1e:   89 ec                   mov    %ebp,%esp
  20:   c3                      ret 
\$\endgroup\$
3
\$\begingroup\$

C (gcc), 72 71 65 64 62 bytes

-9 bytes thanks to @ceilingcat

x,y;f(z){for(x=y=-1;putchar(49-~x%2);y=-~y|z&x/2)x^=z=y&~-~y;}

Try it online!

Generates values of the sequence indefinitely (option 3 from the challenge)

\$\endgroup\$
  • \$\begingroup\$ Explanation please! I have no idea how this works. There is no array! And the numbers stay too small to contain one as bits. \$\endgroup\$ – Ørjan Johansen Apr 19 '18 at 18:37
  • \$\begingroup\$ @ØrjanJohansen I have to admit, I have no idea how this works either! :) I took the python implementation from OEIS A000002, ported it to C and golfed it :) \$\endgroup\$ – vazt Apr 19 '18 at 19:07
  • \$\begingroup\$ Ah I thought it might have been something there, but didn't look far enough down that page to find the Python. There's a link to an explanation, but it was a bit buried in the link section. This method definitely fits C at least as well. \$\endgroup\$ – Ørjan Johansen Apr 20 '18 at 0:00
  • \$\begingroup\$ 1) 56 bytes in PHP: for($x=$y=-1;;$y=$y+1|$f&.5*$x^=$f=$y&-$y-2)echo$x&1?:2;. 2) 50-x%2 should save one byte for you. 3) I tried to get it running with x=y=1; but couldn´t get the operations right so far. Can you? \$\endgroup\$ – Titus Oct 5 '18 at 20:24
2
\$\begingroup\$

Perl 5, 36 bytes

Still a trivial modification of the classic TPR(0,3) solution:

Outputs the series from 0 to n

#!/usr/bin/perl
use 5.10.0;
say$_=($n+=!--$_[$n])%2+1for@_=0..<>

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Javascript ES6 - 71 70 68 bytes

(_="122")=>{for(x=1;;_+=(1+x%2)*(_[x]>1?11:1))console.log(_[++x-2])}

1 bit saved thanks to Neil

Tanks to Shaggy for correcting my mistake, also for saving 1 bit.

f = (_="122") => {
  for(x=1;x<20;_+=(1+x%2)*(_[x]>1?11:1))
    document.getElementById('content').innerHTML += '   ' + _[++x-2]
}
f()
<div id="content"></div>

\$\endgroup\$
  • \$\begingroup\$ This looks like a port of my Java 8 answer (except for x=0 instead of x=1), but @Shaggy is indeed right: this doesn't work in its current form (I added the ,i=100;i-->0 temporarily to just see the first 100 items, instead of having to wait 60 sec before seeing an output). No idea why it doesn't work, though. JS is not my thing. \$\endgroup\$ – Kevin Cruijssen Mar 6 '18 at 16:19
  • \$\begingroup\$ The problems are: 1. initiating x to 0 instead of 1 (as @KevinCruijssen mentioned) and 2. checking if the xth character in the string, which can only ever be 1 or 2, is greater than 49. \$\endgroup\$ – Shaggy Mar 6 '18 at 17:23
  • 2
    \$\begingroup\$ Here's a golfed down (but not fully tested) version of the fixed solution: tio.run/… \$\endgroup\$ – Shaggy Mar 6 '18 at 17:24
  • \$\begingroup\$ (_[x]*10-9) than (_[x]>1?11:1) \$\endgroup\$ – l4m2 Mar 31 '18 at 13:48
2
\$\begingroup\$

Appleseed, 89 bytes

(def K(lambda()(concat(q(1 2))(drop 2(flatten(zip-with repeat-val(cycle(q(1 2)))(K)))))))

Defines a function K that takes no arguments and returns the Kolakoski sequence as an infinite list. Try it online!

This approach was inspired by totallyhuman's Haskell answer. My original approach was longer and was probably O(2^n). :^P

Ungolfed

(def kolakoski
 (lambda ()
  (concat (list 1 2)
   (drop 2
    (flatten
     (zip-with repeat-val
      (cycle (list 1 2))
      (kolakoski)))))))

The return list begins with (1 2). After that, to generate the rest of it (reading from the inside out):

  • Recursively call (kolakoski) to get the Kolakoski sequence list (due to lazy evaluation, it doesn't matter that the list hasn't been fully generated yet)
  • (cycle (list 1 2)) creates an infinite list (1 2 1 2 1 2 ...)
  • Zip the two infinite lists together using the function repeat-val. This will repeat the 1 or 2 from the cycle list either one or two times depending on the associated value in the Kolakoski list. Result: ((1) (2 2) (1 1) ...)
  • flatten that list into (1 2 2 1 1 ...)
  • We've already got the first two terms from (concat (list 1 2), so we drop the first two from the generated list to avoid duplication.
\$\endgroup\$
2
\$\begingroup\$

Stax, 12 bytes

╦╥2Bïß▄n»-[╒

Run and debug it

This is the ascii representation of the same program.

G@}2R;D{|;^]*m$

It expands the sequence x times where x is the input. Then it outputs the xth element, 0-indexed.

G }             G jumps to trailing } and returns when done
 @              get xth element in array
   2R           [1, 2]
     ;D         repeat the rest x times
       {     m  map array using block
        |;^]    produces [1] and [2] alternately
            *   repeat array specified number of times
              $ flatten array

Here's a bonus 12-byte solution that produces output as an infinite stream. Press Run to start.

\$\endgroup\$
2
\$\begingroup\$

R, 63 bytes or 61 bytes

Implementation 1: prints out the nth term of the sequence.

x=scan()
a=c(1,2,2)
for(n in 3:x)a=c(a,rep(2-n%%2,a[n]))
a[x]

Implementation 2: prints out the first n terms of the sequence.

x=scan()
a=c(1,2,2)
for(n in 3:x)a=c(a,rep(2-n%%2,a[n]))
a[1:x]

(The difference is only in the last line.)

Yes, yes, you may complain that my solution is inefficient, that it computes really more terms than needed, but still...

Update: Thanks to @Giuseppe for shaving off 9 bytes.

\$\endgroup\$
  • 1
    \$\begingroup\$ use a=c(a,rep(2-n%%2,a[n])) instead of the second for loop to shave off some bytes. \$\endgroup\$ – Giuseppe Mar 23 '18 at 17:24
  • \$\begingroup\$ @Giuseppe Implemented, thanks! \$\endgroup\$ – Andreï Kostyrka Mar 23 '18 at 17:43
  • \$\begingroup\$ We don't mind inefficient for golfing solutions here. In fact using a more inefficient algorithm is one of the tips in the code-golf tag wiki. \$\endgroup\$ – Ørjan Johansen Mar 25 '18 at 1:37
2
\$\begingroup\$

Shakespeare Programming Language, 575 bytes (but defective), or 653 or 623 bytes

,.Puck,.Ford,.Act I:.Scene X:.[Enter Puck and Ford]Ford:You big cat!Scene L:.Ford:Is I nicer zero?If so,let us Scene V.Is you nicer a big cat?If so,you is the sum of you a big lie.If so,open heart!Open heart!Scene M:.Puck:Remember you!Is I nicer a cat?You big cat.If so,you cat.Ford:Recall!Is you nicer zero?If not,let us Scene X.Is you nicer a big cat?If not,let us Scene M.You is the sum of you a big lie.Scene V:.Ford:Remember you!Is you worse a big big cat?If not, you big cat.Is you as big as a big cat?If not,you zero.You is the sum of I you.Puck:Recall!Let us Scene L.

In the hotly contested SPL category, this would beat Jo King's current entry (583 bytes), except that it is defective: First, it does not run in the TIO version (implementing the SPL website) -- but it does run in the Perl version, so maybe that is not a serious defect. Second, though, it does not print the first two digits. If we allowed that defect in Jo King's solution, then that defective solution would be 553 bytes, beating my defective solution.

My solution fails on TIO for two reasons: we try to rely on an empty stack returning zero when popped; and we goto the first scene, with "[Enter Ford and Puck]" even though nobody has left the stage. These are merely warnings in the Perl version. If I fix these errors and put in the first two digits, I reach 653 bytes:

 ,.Puck,.Ford,.Act I:.Scene I:.[Enter Puck and Ford]Ford:You cat!Open heart!You big cat!Open heart!You zero!Scene X:.Ford:Remember you!You big cat!Scene L:.Ford:Is I nicer zero?If so,let us Scene V.Is you nicer a big cat?If so,you is the sum of you a big lie.If so,open heart!Open heart!Scene M:.Puck:Remember you!Is I nicer a cat?You big cat.If so,you cat.Ford:Recall!Is you nicer zero?If not,let us Scene X.Is you nicer a big cat?If not,let us Scene M.You is the sum of you a big lie.Scene V:.Ford:Remember you!Is you worse a big big cat?If not, you big cat.Is you as big as a big cat?If not,you zero.You is the sum of I you.Puck:Recall!Let us Scene L.

Try it online!

I can generate the full sequence in the Perl implementation using 623 bytes:

,.Puck,.Ford,.Act I:.Scene I:.[Enter Puck and Ford]Ford:You cat!Open heart!You big cat!Open heart!Scene L:.Ford:Is I nicer zero?If so,let us Scene V.Is you nicer a big cat?If so,you is the sum of you a big lie.If so,open heart!Open heart!Scene M:.Puck:Remember you!Is I nicer a cat?You big cat.If so,you cat.Ford:Recall!Is you worse a cat?If so,you big cat!If so,let us Scene L.Is you nicer a big cat?If not,let us Scene M.You is the sum of you a big lie.Scene V:.Ford:Remember you!Is you worse a big big cat?If not, you big cat.Is you as big as a big cat?If not,you zero.You is the sum of I you.Puck:Recall!Let us Scene L.

However, I would point out that this solution is fast compared to many other solutions, and uses logarithmic amounts of memory rather than storing the whole list. (This is similar to vazt's C solution, to which it is distantly related.) This makes no difference for golf, but I'm pleased with it even so. You can generate a million digits in about a minute in Perl (for example if you pipe to sed and wc to get a digit count), where the other solution might give you a few thousand digits.

Explanation

We store a sequence of variables in order: Puck's stack (bottom to top), Puck's value, Ford's value, Ford's stack (top to bottom). Apart from zero values at the ends (with the zero on the left maybe from popping an empty stack), each value is the digit generated next at that generation, with 2 added if the next generation needs to have another child from that parent. When we have N non-zero values in the sequence, we generate all the children up to and including the N-th generation, in a kind of depth-first tree traversal. We print values only from the N-th generation. When the N-th generation has been completely generated, the stored values are in fact the starting values for generations 2 to (N+1), so we append a 2 at the left and start again, this time generating the (N+1)-th generation.

So, an outline: Scene X: When we reach here, this the start of a new traversal. Puck==0. We optionally push that zero onto Puck's stack, and set Puck=2. Scene L: If Ford==0, we have reached the printing generation. If not, goto V. For printing, if the value in Puck has had 2 added, remove the 2 and print it twice; if not, print it once. Scene M: This is a loop where we repeatedly toggle the value of Puck and go back through the sequence. We repeat until either we reach the end (Puck==0), in which case goto X, or we reach a value that needs another child (Puck>2), in which case subtract the extra 2 and go forwards in V. Scene V: Here we go forwards. If Puck is 2 or 4, the next generation will contain two children from the current parent, so Ford+=2. Step forwards through the sequence. Goto L to check for termination.

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

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