title: Compute the Kolakoski sequence

text:
# Question
Title: Compute the Kolakoski sequence
> 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 **1**s and **2**s and the sequence element **a(n)** describes the length of the **n**th run of **1**s or **2**s 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 **n**th 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 **n**th 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.

# Answer
> 20 votes
# 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 **k**th element **j** times, where **j** is the **k**th 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.

# Answer
> 16 votes
# Python 2, 42 bytes

```
x=y=-1
while 1:x=x/2^y;y<<=x%2;print x%2+1

```

Try it online!

Full disclosure - I didn't find the solution myself. I let my brute forcer do the heavy lifting for me and just watched the results roll in. At first, I didn't even try to understand the solution. I just assumed it was too complicated for me to wrap my head around. But then I realized that It's actually pretty simple.

# Answer
> 14 votes
# 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

```

# Answer
> 12 votes
## 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.

```

# Answer
> 11 votes
# Brachylog, ~~30 26 25 23 17~~ 16 bytes

```
~l{1|2}ᵐ.~lᵐ~ḅa₀

```

Outputs the first **n** values. Try it online!

This is *extremely* slow: **n = 6** takes over 30 seconds on TIO.

# Answer
> 9 votes
# Java 10, ~~155~~ ~~108~~ ~~105~~ ~~100~~ ~~97~~ 94 bytes

```
v->{var s="122";for(int i=1;;s+=(s.charAt(i)>49?11:1)<<i%2)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.
-3 bytes thanks to *@ceilingcat* with the binary left-shift trick.

**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:
         (s.charAt(i)>49?11:1)
                  //     Either once or twice depending on the digit at index `i`
          <<i%2)  //     With digits 2 or 1 by left-shifting with `i` modulo-2
    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`

```

The binary for 1 and 11 are `1` and `1011`. If we left-shift with `0` they'll remain the same, but if we left-shift with `1` they'll become `10` (binary for 2) and `10110` (binary for 22) respectively.

# Answer
> 9 votes
# 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]

```

# Answer
> 8 votes
# Python 2, 45 bytes

```
x=y=0
while 1:print 1+x%2;x^=~y&~-y;y=~-y&x/2

```

Try it online!

Based on this blog post, but golfed better. Has the bonus advantage of only using logarithmic space.

-1 thanks to xnor who realised we can invert and use `~x` and `~y` instead of `x` and `y` to avoid writing `x=y=-1` for the initial condition.

# Answer
> 7 votes
# Jelly, 10 bytes

```
’ß€+\<¹SḂ‘

```

Returns the **n**th 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.

```

# Answer
> 7 votes
# 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.

# Answer
> 7 votes
# , 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.

# Answer
> 7 votes
# 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!

```

# Answer
> 6 votes
# JavaScript, ~~67~~ ~~66~~ ~~60~~ ~~58~~ ~~52~~ ~~51~~ 50 bytes

Well, that made my brain itch more than it should have! Retruns the `n`th 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)

```

# Answer
> 6 votes
## 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.

```

# Answer
> 5 votes
# 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

```

# Answer
> 5 votes
# 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.

# Answer
> 5 votes
# \>\<\>, ~~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.

# Answer
> 5 votes
# 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 `1`s. `:~))~:~` 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.)

# Answer
> 4 votes
# 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 **n**th 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

```

# Answer
> 4 votes
# 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
]

```

# Answer
> 3 votes
# 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

```

# Answer
> 3 votes
# 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!

# Answer
> 3 votes
# 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!

# Answer
> 3 votes
# 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)

# Answer
> 3 votes
# R, 63 bytes or 61 bytes

**Implementation 1:** prints out the *n*th 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.

# Answer
> 3 votes
# 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

```

# Answer
> 2 votes
# 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>
```

# Answer
> 2 votes
# 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.

# Answer
> 2 votes
# 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.

# Answer
> 2 votes
# 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.

# Answer
> 2 votes
# 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 ⍵

```

# Answer
> 1 votes
# Jelly, 15 bytes

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

```

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

**Try it online!**

# Answer
> 1 votes
## 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 **i**th 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.

```

# Answer
> 1 votes
# Wolfram Language (Mathematica), 59 bytes

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

```

Try it online!

# Answer
> 1 votes
# 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

# Answer
> 1 votes
# 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.

# Answer
> 1 votes
# 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...

# Answer
> 1 votes
# CJam, 31 27 23 bytes

Prints the first n entries.

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

```

Try online

# Answer
> 1 votes
# 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

```

# Answer
> 1 votes
# 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 ⍵

```

# Answer
> 1 votes
# 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
]

```

# Answer
> 0 votes
# Jelly, 21 bytes

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

```

Try it online!

# Answer
> 0 votes
# 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=',')

```

# Answer
> 0 votes
# 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.

# Answer
> 0 votes
# 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!

# Answer
> 0 votes
# 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`

# Answer
> 0 votes
# 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.

---
Tags: code-golf, number, sequence
---


title: Is it a Frog List?

text:
# Question
Title: Is it a Frog List?
## Challenge:

A Frog List is defined by certain rules:

1. Each frog within a Frog List has an unique positive digit `[1-9]` as id (any `0` in a list is basically an empty spot, which can mostly be ignored).
2. A Frog List will always have *exactly one* Lazy Frog. A Lazy Frog will remain at its position.
3. Every other frog in a Frog List will jump at least once, and will always jump towards the right from its starting position.
4. When a frog jumps, the distance of its jump is always the same.
5. When a frog jumps, it will continue jumping until it's outside the list's right bound.
6. 0-1 jumping frogs can stand on top of a Lazy Frog, as long as their summed ids is still a single digit. (Jumping frogs cannot stand on top of one another! Which implicitly also means there cannot be two jumping frogs on a Lazy Frog simultaneously.)

Note that the frog-ids within a Frog List describe how a frog has already jumped *(past sense)*. Focusing on an individual frog-id within a Frog List shows how it has jumped, and at what positions within the Frog List it has landed, and jumped onward from - with the exception of the Lazy Frog, which hasn't moved.

Worked out explanation of the Frog List `[1,2,1,0,8,2]`:

1. The Lazy Frog has id \\$\color{green}{7}\\$ at position `~~~~7~`:

2. The first jumping frog has id \\$\color{red}{1}\\$ at positions `1~1~1~` with jump distance 2:

3. The second jumping frog has id \\$\color{blue}{2}\\$ at positions `~2~~~2` with jump distance 4:

All three frogs summed gives the Frog List `[1,2,1,0,8,2]`, so `[1,2,1,0,8,2]` would be truthy:

### All Test cases including explanation:

```
Input                 Explanation:

```

**Truthy:**

```
[1,2,1,0,8,2]         Lazy Frog 7 doesn't jump                ~~~~7~
                      frog 1 jumps (with jumping distance 2)  1~1~1~
                      frog 2 jumps (with jumping distance 4)  ~2~~~2

[1,0,0,0,0,1,2,7,2,2] Lazy Frog 5 doesn't jump                ~~~~~~~5~~
                      frog 1 jumps (with jumping distance 5)  1~~~~1~~~~
                      frog 2 jumps (with jumping distance 1)  ~~~~~~2222

[9,8,9,1]             Lazy Frog 7 doesn't jump                ~7~~
                      frog 1 jumps (with jumping distance 2)  ~1~1
                      frog 9 jumps (with jumping distance 2)  9~9~

[1,0,1,3,3,3,1]       Lazy Frog 2 doesn't jump                ~~~~2~~
                      frog 1 jumps (with jumping distance 2)  1~1~1~1
                      frog 3 jumps (with jumping distance 2)  ~~~3~3~
(Note that the 3 at ~~~~3~~ is Lazy Frog 2 and jumping frog 1 on top of one another,
 and not jumping frog 3!)

[7]                   A single Lazy Frog 7

[7,0,0,0]             A single Lazy Frog 7~~~

[8,1,1]               Lazy Frog 8 doesn't jump                8~~
                      frog 1 jumps (with jumping distance 1)  ~11
    OR alternatively:
                      Lazy Frog 7 doesn't jump                7~~
                      frog 1 jumps (with jumping distance 1)  111

```

**Falsey:**

```
[1,2,3,0,2,1,3]       (rule 2) there is no Lazy Frog: 1~~~~1~
                                                      ~2~~2~~
                                                      ~~3~~~3
[1,6,1,8,6,1]         (rule 4) frog 1 jumps irregular 1~1~~1 / 1~11~1
                                                      ~6~~6~ / ~6~~6~
                                                      ~~~8~~ / ~~~7~~
[2,8,2,8,0,9]         (rule 5) frog 2 stopped jumping 2~2~~~
                                                      ~~~~~1
                                                      ~8~8~8
[1,2,3,2,7]           (rule 6) two jumping frogs at the last position with: 1~~~1
                                                                            ~2~2~
                                                                            ~~3~3
                                                                      (Lazy)~~~~4
                                                                                ^
                      OR two jumping frogs at the third and last positions with: 1~1~1
                                                                                ~2222
                                                                           (Lazy)~~~~4
                                                                                ^ ^
[2,1]                 (rule 2+3) There are two Lazy Frogs without jumping frogs: ~1
                                                                                2~
                      OR (rule 1) The Lazy and jumping frog would both have id=1: 11
                                                                                1~

```

Here are all Frog Lists (as integers) of 3 or less digits:

```
[1,2,3,4,5,6,7,8,9,10,13,14,15,16,17,18,19,20,23,25,26,27,28,29,30,31,32,34,35,37,38,39,40,41,43,45,46,47,49,50,51,52,53,54,56,57,58,59,60,61,62,64,65,67,68,69,70,71,72,73,74,75,76,78,79,80,81,82,83,85,86,87,89,90,91,92,93,94,95,96,97,98,100,103,104,105,106,107,108,109,113,114,115,116,117,118,119,121,122,131,133,141,144,151,155,161,166,171,177,181,188,191,199,200,203,205,206,207,208,209,211,212,223,225,226,227,228,229,232,233,242,244,252,255,262,266,272,277,282,288,292,299,300,301,302,304,305,307,308,309,311,313,322,323,334,335,337,338,339,343,344,353,355,363,366,373,377,383,388,393,399,400,401,403,405,406,407,409,411,414,422,424,433,434,445,446,447,449,454,455,464,466,474,477,484,488,494,499,500,501,502,503,504,506,507,508,509,511,515,522,525,533,535,544,545,556,557,558,559,565,566,575,577,585,588,595,599,600,601,602,604,605,607,608,609,611,616,622,626,633,636,644,646,655,656,667,668,669,676,677,686,688,696,699,700,701,702,703,704,705,706,708,709,711,717,722,727,733,737,744,747,755,757,766,767,778,779,787,788,797,799,800,801,802,803,805,806,807,809,811,818,822,828,833,838,844,848,855,858,866,868,877,878,889,898,899,900,901,902,903,904,905,906,907,908,911,919,922,929,933,939,944,949,955,959,966,969,977,979,988,989]

```

## Challenge rules:

* The integers in the input-list are guaranteed to be \\$0\leq n\leq9\\$ (aka single digits).
* Any single-value inputs are Frog List, since they'll contain a single Lazy Frog and no jumping frogs.
* I/O is flexible. You may take the input as a list/array/stream of digits, an integer, a string, etc. You may output any two values or type of values (not necessarily distinct) to indicate truthy/falsey respectively.
* You can assume a Frog List will never start with a `0` (doesn't matter too much for list I/O, but can be for integer I/O).

## General Rules:

* This is , so the shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code (e.g. TIO).
* Also, adding an explanation for your answer is highly recommended.

# Answer
> 2 votes
# Jelly, ~~39~~ 35 bytes

```
Ḷ⁹¦Ẏ€ŒpɗⱮTẎḟƑ_ƒ¥ƇSẹⱮ¹ƇfƑJmÐƤ`ẎIƇƲƲƇ

```

Try it online!

Takes an integer list as input, and outputs a list of all valid ways to ignore the Lazy Frog--falsy if empty.

Generate every candidate:

```
Ḷ⁹¦Ẏ€ŒpɗⱮTẎḟƑ_ƒ¥ƇS
       ɗⱮT            For every index with any frogs:
Ḷ⁹¦                   Replace the frog(s) at that index with [0 .. id),
   Ẏ€                 wrap all other elements in singleton lists,
     Œp               and compute the Cartesian product of all of them.
          Ẏ           Join the results into a single list of candidates.
                Ƈ     Filter the candidates to those which
           ḟƑ         do not contain
             _ƒ¥      the difference between their sum and
                 S    the input's sum
             _ƒ¥ S    (i.e., the Lazy Frog's ID).

```

Filter (`ƲƇ`) to those with valid jumping frogs:

```
ẹⱮ¹ƇfƑJmÐƤ`ẎIƇƲ
      J ÐƤ         For every suffix of [1 .. len(input)],
       m           drop all but every n'th element, where n is
      J   `        each of [1 .. len(input)].
           Ẏ       Join the results,
            IƇ     and filter to those with multiple elements.
 Ɱ¹Ƈ               For every frog in the candidate,
ẹ                  get the list of all of its indices in the candidate.
    fƑ        Ʋ    Is every element of that list an element of the other list?

```

This took me an hour and a half to write on my phone and it didn't even work lmao

# Answer
> 4 votes
# Haskell \+ hgl, 141 bytes

```
g k(x:y)=lq x<>mL1 x<>k?<fo y
f x=or[fo[ay(g k<tx<fue(dW(k/=)y)<sA)$dpH y|k<-y,k>0]|y<-[i++q:k|(i,j:k)<-fsA**<dph$x,q<-e0$j-1,(j-q)?<x||1>q]]

```

Attempt This Online!

*Euch*, this seems *long*. There's probably a better way to do this, and there's probably a lot of little things here I could tweak to improve it. But the spec turned out to be a lot more intricate and have a lot more edge cases than I had thought and I'm just glad to be done.

# Explanation

First we find all the ways to split the list into two chunks

```
(i,j:k)<-fsA**<dph$x

```

We filter out cases where the element we are splitting is `0`

```
j>0

```

Then we get all number strictly less than `j`. This will give us the id number for the lazy frog.

```
q<-e0$j-1

```

Now we replace the lazy frog with `q`.

```
i++q:k

```

Now we confirm that one of the possible combinations of lazy frog and replacement yields a solution. To check solutions we are going to check that every frog in the list can jump to the right.

So we enumerate every frog in the list:

```
k<-y,k>0

```

This has duplicates, but I don't care. For each frog we drop everything off the front of the list until that frog is at the front itself.

```
dW(k/=)y

```

Then for each number \\$n\\$ from one to the length of the list, we split the trimmed list into chunks of size \\$n\\$.

```
fue(dW(k/=)y)<sA)$dpH y

```

Now we transpose the list with `tx`. With the transposed list we want to check the following conditions:

* The first piece contains only one type of element (must be the frog we are looking at since it is the first element of the trimmed list) `lq x`
* The first piece contains at least two elements (so the frog jumps at least twice) `mL1 x`
* The frog cannot occur in other pieces `k?<fo y`

If the split list satisfies these conditions for any way to divide it, then that frog is good. If all frogs in the modified list satisfy this then the substitution is good. If any substitution of the lazy frog for a non-lazy frog is good, then the whole list is valid.

# Reflection

There are a lot of things here that could be improved. A few come to mind immediately but I will probably add to this list as I ruminate on this.

* I shouldn't have to do `ic[j]`. I really thought I had already made a function which intercalates elements with lists. But it seems either I didn't or I can't find it.
* There should be a way to replace every instance of one element with another element.
* I could swear there used to be a "is x a prefix of y" function. But I cannot find it. It would be useful here
* There should be a way to get all partitions of a specific size. *And* there should be a function which gives all ways to split a list in two (as tuples).
* `tx` could be a pattern here. It would be one of the rare times in which a pattern would actually save bytes
* There should be a built in for breaking a list into chunks of a certain size. `uue<sA` is short, but it could be much shorter.
* I discovered `eL` is broken. I didn't need to use it but it should be fixed. Also there should be some pre-composed functions here with `eL2`, `eL3` etc.

# Answer
> 4 votes
# Python3, 498 bytes:

```
E=enumerate
def V(x,l):r=len(K:=set({x[i+1]-a for i,a in E(x)if i+1<len(x)}));return r==1and max(x)+max(K)>=len(l)
T=lambda x:[*filter(None,x)]
P=sorted
def f(l):
 if len(T(l))==1:return 1
 q=[(l,T({*l[:i]+l[i+1:]}),i,a,[])for i,a in E(l)if a>1]
 while q:
  L,s,I,o,C=q.pop(0)
  if[]==s and o-sum(C)not in l and o-sum(C)and C:return 1
  if[]==s:continue
  S,*s=s
  U=[i for i,a in E(l)if a==S and i!=I]
  if len(U)>1and V(P(U),l):q+=[(L,s,I,o,C)]
  if V(P(U+[I]),l)and len(C)<1:q+=[(L,s,I,o,C+[S])]

```

Try it online!

# Answer
> 1 votes
# 05AB1E, ~~68~~ 67 bytes

```
εLã€êDOyQÏ}JÅ»â€˜}θ€€SʒU9LεXQ€à0ÛDVεYNÅ0«Ćƶ0K¥Ë}à}þ`y˜0KD¢ΘOy€g2¢!P

```

Twice as long as the Jelly answer, but figured I'd post my own (now mostly golfed) reference implementation. A different approach is likely much shorter, though.

-1 byte by including duplicates in the truthy outputs.

Input as an integer; output as a list of list of ids for truthy cases (may contain duplicates) and an empty list for falsey cases.

Try it online or verify all test cases.

**Explanation:**

Step 1: Convert each digit of the input to a list of potential 1 or 2 frogs:

```
ε                  # Map over each digit of the (implicit) input-integer:
 L                 #  Convert it to a list in the range [1,digit]
  ã                #  Get the cartesian power of itself to create pairs
   €               #  Inner map over each pair:
    ê              #   Uniquify and sort each pair
     D             #  Duplicate this list
      O            #  Sum each inner list
       yQ          #  Check which are equal to the current digit
     D   Ï         #  Keep the singulars/pairs which sum to the digit
}                  # Close the map

```

Try just the first step.

Step 2: Reduce it by the cartesian product to create all possible result-lists (for which 05AB1E unfortunately lacks a builtin):

```
J                  # Join each inner singular/pair together
 Å»                # Left-reduce it by (unfortunately keeping all intermediate results)
   â               #  Take the cartesian product of the current two lists to create pairs
    €˜             #  Flatten each inner list
      }θ           # After the reduce (with intermediate results), keep the last
        €          # Map over each inner list:
         €         #  Inner map over each integer:
          S        #   Convert it back to a singular digit/pair of digits

```

Try the first two steps.

Step 3: Filter and output the result:

```
ʒ                  # Start filtering this list by:

```

Step 3a: Verify rules 4 (the jump distance of jumping frogs is always the same) and 5 (will go outside the list's right bound):

```
 U                 #  Pop and store the current list in variable `X`
 9L                #  Push a list in the range [1,9]
   ε               #  Map over this list of potential frog-ids:
    X              #   Push list `X`
     Q             #   Check which inner digits are equal to the current potential frog-id
      €à           #   Any on each (for the pairs)
        0Û         #   Trim all leading 0s
    DVεY           #   Duplicate this list its length amount of times as list
      ε            #   Inner map over each of these lists:
        NÅ0        #    Push a list with the 0-based index amount of 0s
           «       #    Append it to the list
            Ć      #    Enclose; append its own head
             ƶ     #    Multiply each inner 0/1 by its 1-based index
              0K   #    Remove all 0s
                ¥  #    Get the deltas/forward-differences
                 Ë #    Check if all of them are equal
       }à          #   After the inner map: check if any was truthy
    }þ             #  After the outer map: remove all empty strings (for the non-occurring frog-ids)
      `            #  Pop and push all checks to the stack

```

Step 3b: Verify rule 2 (there is exactly one Lazy Frog):

```
 y                 #  Push the current list we're filtering again
  ˜                #  Flatten it to a single list of digits
   0K              #  Remove all 0s
     D¢            #  For each digit, count how many times it occurs
       Θ           #  Check for each count whether it's equal to 1
        O          #  Sum them together to get the amount of Lazy Frogs

```

Step 3c: Verify rule 6 (there cannot be two jumping frogs on top of one another):

```
 y                 #  Push the current list we're filtering for a third time
  €g               #  Get the length of each inner list
    2¢             #  Count the amount of 2s (amount of pairs of frog-ids)
      !            #  Faculty to check it's either 0 or 1

```

Step 3d: Combine all checks, and output the result:

```
 P                 #  Get the product of all values on the stack
                   #  (note: only 1 is truthy in 05AB1E)
                   # (output the filtered result)

```

---
Tags: code-golf, number, decision-problem, integer
---


title: Implement Bogosort

text:
# Question
Title: Implement Bogosort
Is solving Sudoku too hard? Even the brute force version? Here's a coding exercise that's a little easier. I hope. :-P

Write the shortest function to implement bogosort. In specific, your function should:

* Take an array (or your language's equivalent) as input
* Check if its elements are in sorted order; if so, return the array
* If not, shuffle the elements, and start again

The shortest entry wins. In the case of a tie, a function that supports a custom comparator (and/or pseudorandom number generator) is favoured. Any remaining ties are resolved by favouring the earlier submission.

---

**Clarifications:** You can use any element type you want, as long as there's some way to order them, of course. Also, the shuffling has to be uniform; none of this "I'll just quicksort it and call it shuffled" business. :-)

# Answer
## APL(Dyalog), 20

```
{⍵≡⍵[⍋⍵]:⍵⋄∇⍵[?⍨⍴⍵]}

```

**Explanation**

is the (right) argument
`⍵≡⍵[⍋⍵]`: Checks if  sorted equals  itself
`:⍵`: If yes, then return
`∇⍵[?⍨⍴⍵]`: Else, generate an array of 1 to `⍴⍵` (length of ) in random order, reorder  according to that (`⍵[...]`), and apply the function to it ()

---

Suddenly revisiting this problem and...

## APL(Dyalog), 19

```
{∧/2≤/⍵:⍵⋄∇⍵[?⍨⍴⍵]}

```

Was just thinking about sorting an array in the check makes it kind of pointless (not saying that Bogosort is meaningful), a more accurate implementation would be `∧/2≤/⍵`, and that happens to lower the char count.
> 8 votes

# Answer
## Perl 6: 23 chars

```
@s.=pick(*)until[<=] @s

```
> 17 votes

# Answer
## Ruby - 33 characters

```
g=->l{l.shuffle!!=l.sort ?redo:l}

```
> 7 votes

# Answer
### APL (22)

```
{(⍳X←⍴⍵)≡⍋⍵:⍵⋄∇⍵[X?X]}

```

Usage:

```
    {(⍳X←⍴⍵)≡⍋⍵:⍵⋄∇⍵[X?X]} 3 2 1
1 2 3

```

Explanation:

* `⍋⍵`: returns the *indexes* of the items in sorted order, so `⍋30 10 20` gives `2 1 3`
* `(⍳X←⍴⍵)≡⍋⍵:⍵` Store the length of input list in X. If range `[1..X]` is equal to the sorted index order, the list is sorted, so return it.
* `⋄∇⍵[X?X]`: if this is not the case, recurse with shuffled array.
> 7 votes

# Answer
### *Mathematica*, ~~40~~ 37

```
NestWhile[RandomSample,#,Sort@#!=#&]&

```

With whitespace:

```
NestWhile[RandomSample, #, Sort@# != # &] &

```
> 6 votes

# Answer
## J - 34 27

```
f=:({~?~@#)^:(1-(-:/:~))^:_

```

eg:

```
f 5 4 1 3 2
1 2 3 4 5

f 'hello'
ehllo

```

The **{~ ?~@#** part shuffles the input:

```
({~ ?~@#) 1 9 8 4
4 8 9 1
({~ ?~@#) 'abcd'
bdca

```
> 5 votes

# Answer
## Python 61

Sorts in place.

```
import random
def f(l):
 while l!=sorted(l):random.shuffle(l)

```
> 4 votes

# Answer
# K, 31 25

`{while[~x~x@<x;x:x@(-#x)?#x];x}`

```
{x@(-#x)?#x}/[{~x~x@<x};]

```

.

```
k){x@(-#x)?#x}/[{~x~x@<x};] 3 9 5 6 7 9 1
`s#1 3 5 6 7 9 9

```

.

```
k){x@(-#x)?#x}/[{~x~x@<x};] "ascsasd"
`s#"aacdsss"

```
> 3 votes

# Answer
# Python 94

```
from itertools import*
def f(a):return [x for x in permutations(a) if x==tuple(sorted(a))][0]

```

Other python answers use random.shuffle(). The documentation of the python random module states:

> Note that for even rather small len(x), the total number of permutations of x is larger than the period of most random number generators; this implies that most permutations of a long sequence can never be generated.
> 3 votes

# Answer
## Python - 61 chars

Recursive

```
from random import*;f=lambda l:l==sorted(l)or shuffle(l)>f(l)

```
> 2 votes

# Answer
## Python (69 chars)

```
from random import*
def f(a):
 while a>sorted(a):shuffle(a)
 return a

```

Sorts integers in increasing numeric order. Note that recursive solutions, like

`from random import*;f=lambda a:a>sorted(a)and(shuffle(a)or f(a))or a`

will fail due to stack overflow for even small inputs (say N\>5), because Python does not do tail-call optimisation.
> 2 votes

# Answer
# D without custom comparator: 59 Characters

```
R f(R)(R r){while(!isSorted(r))r.randomShuffle();return r;}

```

More Legibly:

```
R f(R)(R r)
{
    while(!r.isSorted)
        r.randomShuffle();

    return r;
}

```

# D with custom comparator: 69 Characters

```
R f(alias p,R)(R r){while(!isSorted!p(r))r.randomShuffle();return r;}

```

More Legibly:

```
R f(alias p, R)(R r)
{
    while(!isSorted!p(r))
        r.randomShuffle();

    return r;
}

```
> 2 votes

# Answer
### Scala 73:

```
def s(l:Seq[Int]):Seq[Int]=if(l==l.sorted)l else s(util.Random.shuffle l)

```

In Scala, we can check whether the compiler did a tail-call optimization:

```
@annotation.tailrec
def s(l:Seq[Int]):Seq[Int]=if(l==l.sorted)l else s(util.Random shuffle l)

```

and yes, it did. However, for a short List of 100 values:

```
val rList = (1 to 100).map(x=>r.nextInt (500))
s(rList)

```

took nearly 4 months to complete. ;)
> 2 votes

# Answer
**C# (184 chars)**

```
T[]S<T>(T[]i)where T:IComparable<T>{T l=default(T);while(!i.All(e=>{var r=e.CompareTo(l)>=0;l=e;return r;})){i=i.OrderBy(a=>Guid.NewGuid()).ToArray();l=default(T);}return i.ToArray();}

```

It's not really nice to do this in C#. You have to support generics to support both value and reference types. There is no array shuffle function or function to check if something is sorted.

Does anybody got any tips to make this better?

Edit Version that only sorts int (134 chars):

```
int[]S(int[]i){var l=0;while(!i.All(e=>{var r=e>=l;l=e;return r;})){i=i.OrderBy(a=>Guid.NewGuid()).ToArray();l=0;}return i.ToArray();}

```
> 2 votes

# Answer
# GNU/BASH 65

```
b(){ IFS=$'\n';echo "$*"|sort -C&&echo "$*"||b $(shuf -e "$@");}

```
> 2 votes

# Answer
## C++11, 150 characters

```
#include<deque>
#include<algorithm>
void B(std::deque &A){while(!std::is_sorted(A.begin(),A.end())std::random_shuffle(myvector.begin(),myvector.end());}

```

Just.. made for fun.
> 2 votes

# Answer
# C++14, 158 bytes

```
#include <algorithm>
#include <random>
[](int*a,int s){std::random_device r;for(std::knuth_b g(r());!std::is_sorted(a,a+s);std::shuffle(a,a+s,g));return a;};

```
> 2 votes

# Answer
# PowerShell, ~~85~~ ~~82~~ ~~56~~ ~~55~~ 52 bytes

-26 bytes thanks to mazzy's suggestions
-1 byte thanks to AdmBorkBork
-3 bytes thanks to mazzy

```
for($l=$args;"$l"-ne($l|sort)){$l=$l|sort{random}}$l

```

Try it online!

PowerShell does have a relatively cheap array comparison by casting them to strings and comparing that.
> 2 votes

# Answer
# JavaScript, ~~98~~ 92 chars

More precisely ECMAScript 2015 (ES6)

**Minified:**

```
let b=r=>{for(;!r.every((o,t)=>o==[...r].sort()[t]);)r.sort(()=>Math.random()-.5);return r};

```

**Invocation:** `console.log(b([3, 2, 1, 5, 67, 4, 6, 5, 6, 4]))`

**Not minified:**

```
let bogoSort = (myArray) => {
  while (!myArray.every((v, i) => v == [...myArray].sort()[i])) {
    myArray.sort(() => Math.random() -0.5)
  }
  return myArray
}

```

**Explanation:**

* `myArray.every()` is an element-wise compare function. Comparing shuffled with sorted array
* `someArray.sort()` sorts in place so saving assignments, but also needs cloning for the sorted array
* `[...myArray]` clones the array (array destructuring)
* `() => (Math.random() > .5) ? 1 : -1` is a custom compare function. Coin flip whether to order an element in front or behind
> 2 votes

# Answer
# Go 1.20+, 95 bytes

```
import(."math/rand";."sort")
func f[T Interface](I T){for!IsSorted(I){Shuffle(I.Len(),I.Swap)}}

```

Attempt This Online!

Expects input to implement `sort.Interface`, which wants:

* `Len() int`: gets the number of elements.
* `Less(i, j int) bool`: checks whether the element at index `i` is less than the element at index `j`.
* `Swap(i, j int)`: swaps elements at indexes `i` and `j`.

Why is this `1.20+`? See below.

### Go, 158 bytes, seeded ints (pre-1.20)

```
import(."math/rand";."sort";."time")
func f(I[]int)[]int{Seed(Now().Unix())
for!IntsAreSorted(I){Shuffle(len(I),func(i,j int){I[i],I[j]=I[j],I[i]})}
return I}

```

Attempt This Online!

### Go, 131 bytes, unseeded ints (pre-1.20), truly random (post-1.20)

```
import(."math/rand";."sort")
func f(I[]int)[]int{for!IntsAreSorted(I){Shuffle(len(I),func(i,j int){I[i],I[j]=I[j],I[i]})}
return I}

```

Attempt This Online!

This solution is marked as both "unseeded" and "truly random" due to a change in Go v1.20 that changed the global, default random number generator to be seeded "randomly" rather than be default, deterministic `rand.Seed(1)` in pre-1.20 versions.
> 2 votes

# Answer
# Javascript 291 characters

min

```
function f(e){var t=[].concat(e).sort();t.e=function(e){var n=true;t.forEach(function(t,r){if(t!=e[r])n=false});return n};while(!t.e(e.sort(function(){return Math.floor(Math.random()*2)?1:-1}))){console.log(e)}return e}

```

un-min

```
function f(a) {
var b = [].concat(a).sort();
b.e = function (z) {
    var l = true;
    b.forEach(function (v, i) {
        if (v != z[i]) l = false;
    });
    return l
};
while (!b.e(a.sort(function () {
    return Math.floor(Math.random() * 2) ? 1 : -1;
}))) {
    console.log(a);
}
return a;
}

```
> 1 votes

# Answer
# Python, 71 characters

```
from random import*
def b(l):
 while l!=sorted(l):shuffle(l)
 return(l)

```

Not the shortest one, but it works.

Ungolfed:

```
from random import *
def bogosort(list):
    while list != sorted(list):
        shuffle(list)

    return(list)

```

**Usage:**

Input: `b([1, 7, 3, 9, 2])`

Output: `[1, 2, 3, 7, 9]`
> 1 votes

# Answer
# Matlab, 59 bytes

Relatively straight forward approach:

```
x=input('');while~issorted(x);x=x(randperm(numel(x)));end;x

```
> 1 votes

# Answer
# J, 22 bytes

```
$:@({~?~@#)`]@.(-:/:~)

```

This is a recursive, tacit monad using an agenda. Here's how it works:

Let `y` be our list. First, the verb on the right of the agenda is `-:/:~`. This a verb graciously provided by Leaky Nun. It matches (`-:`) whether or not the input is sorted (`/:~`) using a monadic hook. (`(f g) y = y f (g y)`) This returns a one or a zero accordingly. The left hand side of the agenda is a gerund of two verbs: on the right is the identity verb `]`, and on the left is where the recursion takes place. The agenda selects either the identity verb at position `1` if the list *is* sorted, and the longer verb at position `0` if the list *isn't* sorted.

`$:@({~?~@#)` calls `$:` (the longest verb it is contained in) atop the result of `{~?~@#` on `y`. This shuffles the list, as `?~@#` takes the permutations of the length of `y`, being randomly-sorted indices of `y`. `{~`, in a monadic hook, returns a list from `y` whose indices are the right arg. This shuffled list is then called again with the agenda, and repeats until it is sorted.
> 1 votes

# Answer
# Pushy, 8 bytes

```
[oSog?_i

```

**Try it online!**

Alternatively, run this version to see it print each shuffle as it goes along! The code works like this:

```
[          \ Infinitely:
 oS        \   Shuffle the stack
   og?     \   If it's sorted (ascendingly):
      _i   \     Print and terminate

```

If you want to sort descendingly, just replace `og` with `oG`.
> 1 votes

# Answer
# 05AB1E, 8 bytes

```
[Ð{Q#.r

```

Try it online!

Explanation:

```
[        # Infinite Loop start
 Ð       # Push input
  {Q#    # If input is sorted, break loop
     .r  # Otherwise, shuffle

```
> 1 votes

# Answer
# Jelly, 6 bytes, language postdates challenge

```
ẊŒ¿’$¿

```

Try it online!

## Explanation

```
ẊŒ¿’$¿
     ¿  While
 Œ¿’$     the input is not in its earliest possible permutation (i.e. sorted)
Ẋ       shuffle it

```

`Œ¿` assigns a number to each permutation of a list; 1 is sorted, 2 has the last two elements exchanged, etc., up to the factorial of the list length (which is the list in reverse order). So for a sorted list, this has the value 1, and we can decrement it using  in order to produce a "not sorted" test that's usable as a Boolean in a while loop condition. The `$` is to cause the condition to parse as a group.
> 1 votes

# Answer
# Brachylog (v2), 5 bytes

```
≤₁|ṣ↰

```

Try it online!

Function submission. (The TIO link uses a command-line argument that automatically wraps a function into a full program.)

## Explanation

```
≤₁|ṣ↰
≤₁      Assert that {the input} is (nonstrictly) sorted in ascending order
  |     Output it
  |     Exception handler: if an assertion fails:
   ṣ      Randomly shuffle {the input}
    ↰     and run this function recursively on it, {outputting its output}

```

Prolog (the language that Brachylog compiles into) is tail-recursive, so this function ends up being compiled into a tight loop.
> 1 votes

# Answer
# C++, 166 bytes

Meh.

```
#import<algorithm>
#import<random>
#define r b.begin(),b.end()
template<class v>
v f(v b){auto a=std::mt19937();while(!std::is_sorted(r))std::shuffle(r,a);return b;}

```

This should work on all STL containers that have `begin()` and `end()`.

Ungolfed:

```
#include <algorithm>
#include <random>
template <class v>
v f(v b) {
    auto a = std::mt19937();
    while (!std::is_sorted(b.begin(),b.end()))
        std::shuffle(b.begin(),b.end(),a);

    return b;
}

```
> 1 votes

# Answer
# APL (Dyalog Extended), 15 bytes

```
(?⍨∘≢⊇⊢)⍣{⍺≡∧⍺}

```

Try it online!
> 1 votes

# Answer
# Brachylog, 5 bytes

```
∈&ṣ≤₁

```

Try it online!

When I first saw ais523's Brachylog answer (as opposed to his Jelly answer, because if I'm not mistaken user62131 was also him), I wondered, what if it used backtracking instead of recursion? So at first, I tried `ṣ≤₁`. Turns out, since choosing something at random doesn't produce multiple outputs so much as it just produces one output nondeterministically, the shuffle predicate  can't be backtracked to, so running that will simply fail unless you're lucky enough to shuffle it right on the first try. After that, I tried `pṣ≤₁`, which worked most of the time, but since a finitely long list has finitely many permutations, it still failed at random sometimes. After having abandoned the goal of achieving length reduction, I finally came up with this:

```
         The input
∈        is an element of
         an unused implicit variable,
 &       and the input
  ṣ      shuffled randomly
   ≤₁    which is increasing
         is the output.

```

(Demonstration of randomness)

Although it actually can be a bit shorter if we take some liberties with I/O...

# Brachylog, 4 bytes

```
⊆ṣ≤₁

```

Try it online!

In order for the output to be useful, the input must not contain any duplicate elements, because in addition to sorting the input, this bogosort predicate adds in a random number of duplicate elements and zeroes. (Hypothetically, it could add in anything, but it just kind of doesn't.) Ordinarily I wouldn't bother mentioning something so far from correctly functioning, but I feel it's in the spirit of the challenge.

```
⊆        An ordered superset of the input
 ṣ       shuffled randomly
  ≤₁     which is increasing
         is the output.

```
> 1 votes

# Answer
# Japt, ~~11~~ 9 bytes

```
_eZñ}a@öx

```

Try it

```
_eZñ}a@öx     :Implicit input of array U
_             :Function taking an array as argument via parameter Z
 e            :  Test Z for equality with
  Zñ          :  Z sorted
    }         :End function
     a        :Repeat and return the first result that returns true
      @       :Run this function each time and pass the result to the first function
       öx     :  Random permutation of U

```
> 1 votes

# Answer
# Perl 6, 28 bytes

```
{({.pick(*)}...~.sort).tail}

```

Try it online!

Anonymous code block that shuffles the list until it is sorted. Note that it sorts the list at least once, which is allowed. And no, the `{.pick(*)}` can't be replaced with `*.pick(*)`
> 1 votes

# Answer
# Pyth, 11 bytes

```
Wn=Q.SQSQ;Q

```

Pretty happy with this, probably can be golfed a bit more

# Explanation

```

Wn=Q.SQSQ;Q
W    While
  =Q.SQ    Variable Q (input variable) shuffled
 n  Does not equal
       SQ    Variable Q sorted
             ;  Do nothing (loop ends)
              Q    And output variable Q

```

Try it online!
> 1 votes

# Answer
# Java, 252

Requires java 10 as the `var`keyword is used.

```
import java.util.*;interface B{static int c(List<String>a,int i){return i>0?Math.max(a.get(i-1).compareTo(a.get(i)),c(a,i-1)):-1;}
static void main(String[]p){var a=Arrays.asList(p);while(c(a,a.size()-1)>0)Collections.shuffle(a);System.out.print(a);}}

```

## Explained

```
import java.util.*;                              // you don't get a lot for free in java
interface B{
  static int c(List<String>a,int i){             // recursive comparator method, i is index to compare a[i-1] with a[i]
    return i>0?                                  // still not at the first element?
           Math.max(                             // return the max of...
             a.get(i-1).compareTo(a.get(i)),     // - string comparison of a[i-1] and a[i]
             c(a,i-1))                           // - recursive call c for i-1
           :-1;                                  // i=0 -> return -1
  }
  static void main(String[]p){                   // entry point
    var a=Arrays.asList(p);                      // convert the input array in a List (so we can use Collections functions)
    while(c(a,a.size()-1)>0)                     // as long as c()>0, at least one element is not in correct order
      Collections.shuffle(a);                    // shuffle the list
    System.out.print(a);                         // print the ordered list
  }
}

```

Try it online
> 1 votes

# Answer
# Vyxal, 8 bytes

```
{ÞṠ¬|Þ℅:

```

Try it Online!

#### Explanation

```
{ÞṠ¬|Þ℅:  # Implicit input
{   |     # While loop
 ÞṠ       # (Condition): Is sorted?
   ¬      #              Logical NOT
     Þ℅   # (Body): Randomly shuffle
       :  #         Duplicate
          # Implicit output

```
> 1 votes

# Answer
## C (203 chars, no input loop: only the func)

```
#include <stdio.h>
#define P (int*a,int n){
#define F for(i=0;i<n;i++){
int i,j,v;s P F if(a[i]>a[i+1])return 0;}return 1;}void h P F v=a[i];a[i]=a[j=rand()%n];a[j]=v;}}void b P while(!s(a,n-1))h(a,n);}

```

This is the same as the following, where we also read the array from stdin and write out the sorted array. Since the Q asked for the function and not a whole program...

## C (296 chars)

```
#include <stdio.h>
#define P (int*a,int n){
#define F for(i=0;i<n;i++){
int i,j,n,v,x[999];s P F if(a[i]>a[i+1])return 0;}return 1;}void h P F j=rand()%n;v=a[i];a[i]=a[j];a[j]=v;}}void b P while(!s(a,n-1))h(a,n);}main(){while(scanf("%d",&v)==1)x[n++]=v;if(!s(x,n))b(x,n);F printf("%d\n",x[i]);}}

```

Compiling may give warning (implicit declarations). Hardencoded array size limit of 999 elements. Fragile.

if there's no need to pre-check if the array is sorted, it can be done in 284.

## C (251 chars, was 284)

```
#include <stdio.h>
#define F for(i=0;i<n;i++){
int i,j,n,v,a[999];s(int n){F if(a[i]>a[i+1])return 0;}return 1;}void h(){F v=a[i];a[i]=a[j=rand()%n];a[j]=v;}}void b(){while(!s(n-1))h();}main(){while(scanf("%d",&a[n++])>0);b();F printf("%d\n",a[i]);}}

```

(using globals instead of function args).
> 0 votes

# Answer
## R, 82 characters

Since I wrote it for this question I thought I'll add it there as well. Slightly modified here to accomodate question criteria.

```
b=function(a){while(any(apply(embed(a,2),1,function(x)x[1]<x[2]))){a=sample(a)};a}

```
> 0 votes

# Answer
## JavaScript (using Array.sort()): 91

Utilising Array.sort():

```
function s(a){while((a=a.sort(function(){return 2-Math.random()*4|0}))!=a.sort());return a}

```

## JavaScript (avoiding Array.sort()): 186

Not using the built-in .sort() method (randomising method stolen from here):

```
function s(a){while(function(b,c,d){for(;c<b.length-1;){d&=b[c]<=b[++c]}return!d}(function(t,n,i){i=a.length;while(i--){n=Math.random()*i|0,t=a[i],a[i]=a[n],a[n]=t}}()||a,0,1));return a}

```
> 0 votes

# Answer
# Java - 207 bytes

```
boolean sorted(Integer[] n,int i){while(i-->1)if(n[i]<n[i-1])return false;return true;}void bogo(Integer[] n){List<Integer>l=Arrays.asList(n);while(!sorted(n,n.length)){Collections.shuffle(l);l.toArray(n);}}

```

**Ungolfed** try online

```
boolean sorted(Integer[] n,int i)
{
    while(i --> 1) // i..1
        if(n[i] < n[i-1]) // ascending order
            return false;

    return true;
}

void bogo(Integer[] n)
{
    List<Integer>l = Arrays.asList(n);

    while(!sorted(n, n.length))
    {
        Collections.shuffle(l); // shuffle
        l.toArray(n); // re-fill the array
    }
}

```
> 0 votes

# Answer
# Java, 147 bytes

```
import java.util.*;void A(List<Long>b){for(;;){for(int B=1;B++<b.toArray().length;){if(b.get(B-1)>b.get(B))break;return;}Collections.shuffle(b);}}

```

This sorts in ascending order, To make it sort in descending order, simply replace `b.get(B-1)>b.get(B)` with `b.get(B-1)<b.get(B)`.

Ungolfed:

```
import java.util.*;

void A(List<Long> b) {
    for (;;) {
        for (int B = 1; B++ < b.toArray().length;) {
            if (b.get(B - 1) > b.get(B))
                break;
            return;
        }
        Collections.shuffle(b);
    }
}

```

Making this function compilable costs 9 bytes, resulting in a 156-byte program:

```
import java.util.*;class a{void A(List<Long>b){for(;;){for(int B=1;B++<b.toArray().length;){if(b.get(B-1)>b.get(B))break;return;}Collections.shuffle(b);}}}

```

---

# Java (lambda expression), 111 bytes

```
(b,B)->{for(;;){for(B=1;B++<b.toArray().length;){if(b.get(B-1)>b.get(B))break;return;}Collections.shuffle(b);}}

```

This is a `java.util.function.BiConsumer<java.util.List<Long>, Integer>`.
> 0 votes

# Answer
# C, 111 bytes

This answer takes bogus sort one step further: It doesn't shuffle the entire array before rechecking, it just makes a singe random swap before rechecking. For extra measure, that single random swap always swaps with the first entry, so the general random swap actually takes two iterations. Inefficient, yes, but hey, it's bogus sort, and it saves one call to `rand()`!

```
#include<stdlib.h>
t,r;b(int*d,int s){r=rand()%s;t=*d;*d=d[r];d[r]=t;for(r=s-1;r--;)d[r]>d[r+1]&&(b(d,s),r=0);}

```

Note that since the mixing loop is implemented via recursion, this will crash for larger input arrays (= more than eight elements on my machine) due to stack exhaustion.

Ungolfed:

```
void b(int*data,int size){
    //First, swap random element with the first element.
    int randomIndex = rand()%size;
    int temp = *data;
    *data = data[randomIndex];
    data[randomIndex] = temp;

    //Check if array is sorted
    for(int i = size-1;i--;) {
        if(data[i]>data[i+1]) {
            //array is not sorted, start over
            b(data,size);
            i = 0;  //don't resume loop on return
        }
    }
}

```

Test with

```
int main(){
    int data[] = {8, 7, 6, 5, 4, 3, 2, 1};
    int size = sizeof(data)/sizeof(*data);
    for(int i = 0; i < size; i++) printf("%d ", data[i]);
    printf("\n");

    b(data, size);

    for(i = 0; i < size; i++) printf("%d ", data[i]);
    printf("\n");
}

```
> 0 votes

# Answer
# SmileBASIC, ~~104~~ 81 bytes

```
DEF B A@D
SWAP A[0],A[RND(LEN(A))]FOR I=0TO LEN(A)-2IF A[I]<A[I+1]GOTO@D
NEXT
END

```
> 0 votes

# Answer
# 05AB1E, 6 bytes

```
œ.ΔD{Q

```

Try it online!

**Explanation**

```
œ       Create list with all permutations
 .Δ     Return the first element that satisfies the followng:
   D{Q  Check if element is sorted.

```
> 0 votes

# Answer
# Pyth, ~~13~~ 11 bytes

```
WnSQKO.pQ;K

```

*Previous Solution*

```
L?n.SbSbybb
y

```

Try it online!

```
WnSQKO.pQ;K
      .pQ    Generate a list of all permutations of input
    KO.pQ    K = random permutation in the list
WnSQK    ;   While(sorted(input) != K): do nothing
          K  print K

```

*Previous Solution:*
Compiled to python:

```
assign('Q',eval_input())
@memoized
def subsets(b):
 return (subsets(b) if ne(shuffle(b),Psorted(b)) else b)
imp_print(subsets(Q))

```

Basically:
*Shuffle the list, if it isn't equal to the sorted list:*
recursively call.
*Else:*
Return it
> 0 votes

# Answer
# Husk, 8 bytes

```
ΩS=O§!←P

```

Try it online!

Husk does not have random numbers, so this uses the array itself to get a permutation. I genuinely don't know whether this would complete.

## Explanation

```
ΩS=O§!←P
Ω        Until
 S=O     the argument is ordered
       P take it's permutations
      ←  take its first element
    §!   return that permutation

```
> 0 votes

# Answer
# CJam, 14 bytes

```
{{__$=!}{mr}w}

```

Try it online!
> 0 votes

---
Tags: code-golf, random, sorting
---