title: Fractal Smoke Sequence

text:
# Question
Title: Fractal Smoke Sequence
## Introduction

A229037 has a quite intriguing plot (at least for the first few terms):

There is the conjecture, that it might indeed have some kind of fractal property.

### How is this sequence constructed?

Define `a(1) = 1, a(2) = 1` then for each `n>2` find a minimal positive integer `a(n)` such that for every arithmetic 3 term sequence `n,n+k,n+2k` of indices, the corresponding values of the sequence `a(n),a(n+k),a(n+2k)` is *not* an arithmetic sequence.

## Challenge

Given a positive integer `n` as an input, output the first `n` terms `a(1), ... , a(n)` of this sequence. (With any reasonable formatting. Possible leading/trainling characters/strings are irrelevant.)

There are snippets for generating this sequence available, but I think other approaches might be more golfable/more suitable for certain languages.

Please let us know how your progrm works. If you come a cross a particularly efficient algorithm you might want to mention that too, as it would allow to plot more terms of the sequence in shorter time.

### First few test cases:

```
1, 1, 2, 1, 1, 2, 2, 4, 4, 1, 1, 2, 1, 1, 2, 2, 4, 4, 2, 4, 4, 5, 5, 8, 5, 5, 9, 1, 1, 2, 1, 1, 2, 2, 4, 4, 1, 1, 2, 1, 1, 2, 2, 4, 4, 2, 4, 4, 5, 5, 8, 5, 5, 9, 9, 4, 4, 5, 5, 10, 5, 5, 10, 2, 10, 13, 11, 10, 8, 11, 13, 10, 12, 10, 10, 12, 10, 11, 14, 20, 13

```

### More testcases:

```
  a(100)  =   4
  a(500)  =   5
 a(1000)  =  55
 a(5000)  =  15
a(10000)  = 585

```

All terms up to `n=100000` are available here: https://oeis.org/A229037/b229037.txt

Thanks @MartinBüttner for the help and encouragement.

# Answer
## Python 2, 95 bytes

```
l=[];n=input()
exec"a=min(set(range(n))-{2*b-c for b,c in zip(l,l[1::2])});print-~a;l=[a]+l;"*n

```

The main trick is in generating the numbers the new value must avoid. Keeping the reversed sequence so far in `l`, let's look at what elements might form a three-term arithmetic progression with the value we're about to add.

```
? 4 2 2 1 1 2 1 1   a b c
^ ^ ^               ? 4 2
^   ^   ^           ? 2 1
^     ^     ^       ? 2 2
^       ^       ^   ? 1 1

```

The other numbers are the paired members of `l` and every second element of `l`, so `zip(l,l[1::2])`. If this pair is `(b,c)` then the arithmetic progression `(a,b,c)` happens for `a=2*b-c`. After generating the set of `a`'s to avoid, the code takes the minimum of the complement, prints it, and prepends it to the list. (Actually, the computation is done with numbers decreased by 1, and printed 1 higher, to let `range(n)` serve as a universe of candidates.)
> 13 votes

# Answer
## Mathematica, 95 bytes

```
For[n_~s~k_=0;n=0,n<#,For[i=n,--i>0,s[2n-i,2f@n-f@i]=1];For[++n;i=1,n~s~i>0,++i];Print[f@n=i]]&

```

Certainly not the golfiest approach, but this is actually fairly efficient, compared to the algorithms I tried from the OEIS page.

As opposed to checking all the forbidden values for each *s(n)* when we get there I'm using a sieve-based approach. When we find a new value *s(n)* we check immediately which values this forbids for *m \> n*. Then we just solve the *s(n+1)* by looking for the first value that wasn't forbidden.

This can be made even more efficient by changing the conditional `--i>0` to `2n-#<=--i>0`. In that case, we avoid checking forbidden values for *n* greater than the input.

For a somewhat more readable version, I started with this code, which stores the results up to `max` in a function `f`, and then golfed it to the above one-line pure function:

```
 max = 1000;
 ClearAll[sieve, f];
 sieve[n_, k_] = False;
 For[n = 0, n < max,
  temp = f[n];
  For[i = n - 1, i > 0 && 2 n - i <= max, --i,
   sieve[2 n - i, 2 temp - f[i]] = True;
   ];
  ++n;
  i = 1;
  While[sieve[n, i], ++i];
  f@n = i;
  ]

```
> 9 votes

# Answer
# Haskell, ~~90~~, ~~89~~, ~~84~~, 83 bytes

Can probably be golfed more, but this is still a decent ~~first~~ attempt:

```
a n|n<1=0|n<3=1|1<2=[x|x<-[1..],and[x/=2*a(n-k)-a(n-k-k)||a(n-k-k)<1|k<-[1..n]]]!!0

```

Ungolfed:

```
a n | n<1        = 0
    | n<3        = 1
    | otherwise  = head (goods n)

goods n = [x | x <- [1..], isGood x n]

isGood x n = and [ x - a(n-k) /= a(n-k) - a(n-k-k) || a(n-k-k) == 0 | k <- [1..n] ]

```

This is a simple implementation which returns '0' for out of bounds. Then, for each possible value, it checks that for all k \<= n and in bounds, \[x, a(x-k), a(x-2k)\] is not an arithmetic sequence.

Upper bound on time complexity (using the fact from the OEIS page that a(n) \<= (n+1)/2:

```
t n <= sum[ sum[2*t(n-k) + 2*t(n-k-k) | k <- [1..n]] | x <- [1..(n+1)/2]]
    <= sum[ sum[4*t(n-1)              | k <- [1..n]] | x <- [1..(n+1)/2]]
    <= sum[     4*t(n-1)*n                         ] | x <- [1..(n+1)/2]]
    <=          4*t(n-1)*n*(n+1)/2
    ->
O(t(n)) == O(2^(n-2) * n! * (n+1)!)

```

I'm not sure how good this bound is because calculating the first 1k values of 't' and using a linear model on the logs of the values gave appx. O(22^n), with p-value \< 10^(-1291), in case it matters.

On an implementation level, compiling with '-O2', it took ~35 min to calculate the first 20 values.
> 4 votes

# Answer
# Brachylog, ~~33~~ 31 bytes

```
;Ė{~b.hℕ₁≜∧.¬{ġh₃hᵐs₂ᶠ-ᵐ=}∧}ⁱ⁽↔

```

Try it online!

*In case it matters: The 2-byte golf was possible thanks to a feature I requested after working on this challenge.*

### Explanation

We iteratively generate the sequence as a list in reverse order, e.g. `[2,2,1,1,2,1,1]`, and reverse it at the end.

There are a couple of nested predicates here. Let's look at them from the inside out. The first one, `ġh₃hᵐs₂ᶠ-ᵐ=`, takes a candidate subsequence `a(n),a(n-1),...,a(0)` and determines whether `a(n),a(n-k),a(n-2k)` is an arithmetic sequence for some `k`.

```
ġ            Group the list into equal-length sublists (with the possible exception of
             the last sublist, which might be shorter)
 h₃          Get the first 3 sublists from that list
   hᵐ        and get the head of each of those 3 sublists
             We now have a list containing a(n),a(n-k),a(n-2k) for some k
     s₂ᶠ     Find all 2-element sublists of that list: [a(n),a(n-k)] and [a(n-k),a(n-2k)]
        -ᵐ   Find the difference of each pair
          =  Assert that the two pairwise differences are equal

```

For example, with input of `[1,2,1,1,2,1,1]`:

```
ġ has possible outputs of
    [[1],[2],[1],[1],[2],[1],[1]]
    [[1,2],[1,1],[2,1],[1]]
    [[1,2,1],[1,2,1],[1]]
    [[1,2,1,1],[2,1,1]]
    [[1,2,1,1,2],[1,1]]
    [[1,2,1,1,2,1],[1]]
    [[1,2,1,1,2,1,1]]
h₃ has possible outputs of
    [[1],[2],[1]]
    [[1,2],[1,1],[2,1]]
    [[1,2,1],[1,2,1],[1]]
hᵐ has possible outputs of
    [1,2,1]
    [1,1,2]
    [1,1,1]
s₂ᶠ has possible outputs of
    [[1,2],[2,1]]
    [[1,1],[1,2]]
    [[1,1],[1,1]]
-ᵐ has possible outputs of
    [-1,1]
    [0,-1]
    [0,0]
= is satisfied by the last of these, so the predicate succeeds.

```

The next predicate outwards, `~b.hℕ₁≜∧.¬{...}∧`, inputs a subsequence `a(n-1),a(n-2),...,a(0)` and outputs the next bigger subsequence `a(n),a(n-1),a(n-2),...,a(0)`.

```
~b.hℕ₁≜∧.¬{...}∧
~b.                 The input is the result of beheading the output; i.e., the output is
                    the input with some value prepended
  .h                The head of the output
    ℕ₁              is a natural number >= 1
      ≜             Force a choice as to which number (I'm not sure why this is necessary,
                    but the code doesn't work without it)
        ∧           Also,
         .          the output
          ¬{...}    does not satisfy the nested predicate (see above)
                    I.e. there is no k such that a(n),a(n-k),a(n-2k) is an arithmetic sequence
                ∧   Break unification with the output

```

Finally, the main predicate `;Ė{...}ⁱ⁽↔` takes an input number and outputs that many terms of the sequence.

```
;Ė{...}ⁱ⁽↔
;           Pair the input number with
 Ė          the empty list
  {...}ⁱ⁽   Using the first element of the pair as the iteration count and the second
            element as the initial value, iterate the nested predicate (see above)
         ↔  Reverse, putting the sequence in the proper order

```
> 4 votes

# Answer
# APL (Dyalog Extended), 37 bytesSBCS

Many thanks to Adám for his help in writing and golfing this answer in The APL Orchard, a great place to learn the APL language. Try it online!

**Edit:** -6 bytes thanks to Adám

```
⌽{⍵,⍨⊃(⍳1+≢⍵)~-¯2⊥⍵[2×⍀⍥⍳⌊2÷⍨≢⍵]}⍣⎕,⍬

```

**Explanation**

```
{⍵,⍨⊃(⍳1+≢⍵)~-¯2⊥⍵[2×⍀⍥⍳⌊2÷⍨≢⍵]}  ⍵ is our right argument, the sequence S

                        ⌊2÷⍨≢⍵    We start by calculating X = ⌊len(S)÷2⌋
                       ⍳          Get a range [1, X]
                   2×⍀⍥           With that we can get S[:X] and S[:X×2:2]
                                  or S up to halfway and every 2nd element of S
             -¯2⊥⍵[           ]   And with that we can get 2*S[:X] - S[:X×2:2]
                                  Which is C=2*B-A of a progression A B C
     (⍳1+≢⍵)~                     We remove these Cs from our possible a(n)s
                                  I use range [1, len(S)+1]
    ⊃                             Get the first result, which is the minimum
 ⍵,⍨                              And then prepend that to S

⌽{...}⍣⎕,⍬

 {...}⍣⎕    We iterate an "input" ⎕ times
        ,⍬  with an empty list ⍬ as the initial S
⌽           and reversing S at the end as we have built it backwards

```

# APL (Dyalog Unicode), ~~43~~ ~~39~~ 38 bytesSBCS

Here is a faster but less golfy solution that can calculate `⍺(10000)` in a few seconds.

```
⌽{⍵,⍨⊃(⍳1+≢⍵)~-⌿⍵[1 2 1∘.×⍳⌊2÷⍨≢⍵]}⍣⎕,⍬

```

Try it online!
> 4 votes

# Answer
# Jelly, ~~24~~ 19 bytes

This is my first Jelly answer in quite a while. Glad to be back.

This is a port of my APL answer which itself is an adaptation of many of the algorithms used here. The main difference is that this is 0-indexed.

**Edit:** -5 bytes thanks to Jonathan Allan.

Try it online!

```
Ḋm2ɓṁḤ_
ŻJḟÇṂ;
1Ç¡U

```

**Explanation**

```
Ḋm2ɓṁḤ_  First link. Takes our current sequence S as our left argument.

         We are trying to calculate, of an arithmetic progression A B C,
           the C using the formula, C = 2*B - A
Ḋ        Remove the first element of S.
 m2      Get every element at indices 0, 2, 4, ...
           This is equivalent to getting every second element of S, a list of As.
   ɓ     Starts a dyad with reversed arguments.
           The arguments here are S and As.
    ṁ    This molds S in the shape of As, giving us a list of Bs.
     Ḥ   We double the Bs.
      _  And subtract As from 2 * Bs.

ŻJḟÇṂ;  Second link. Takes S as our left argument.

Ż       Append a 0 to S.
 J      Range [1, len(z)]. This gets range [1, len(S) + 1].
  ḟÇ    Filter out the results of the previous link, our Cs.
    Ṃ   Take the minimum of Cs.
     ;  And concatenate it with the rest of the sequence so far.

1Ç¡U  Third link. Where we feed our input, n.

1     A list with the element 1.
 Ç¡   Run the previous link n times.
   U  Reverse everything at the end.

```
> 4 votes

# Answer
# Ruby, 71 bytes

```
->n,*a{a.fill(0,n){|s|([*1..n]-(1..s/2).map{|o|2*a[s-o]-a[s-2*o]})[0]}}

```

Try it online!

Generates all forbidden values, then takes the complement of that array in (1..n) and takes the first value of the result. That means I am assuming that `a[n] <= n` for all n, which is easily proven using induction (if the first n/2 terms are all less than n/2, then there can't be an arithmetic progression leading to n).

The syntactic trick here is also mildly interesting: `*a` is used to initialize an array of additional arguments (which would be ignored if we passed any), and then `a.fill` mutates the argument array and implicitly returns it.
> 3 votes

# Answer
## MATLAB, 156 147 bytes

I've finally gotten to golf this down a bit:

```
N=input('');s=[0;0];for n=1:N,x=s(n,~~s(n,:));try,a(n)=find(~ismember(1:max(x)+1,x),1);catch,a(n)=1;end,s(n+1:2*n-1,end+1)=2*a(n)-a(n-1:-1:1);end,a

```

Ungolfed:

```
N=input('');                                   % read N from stdin

s=[0;0];
for n=1:N,
    x=s(n,~~s(n,:));                           % x=nonzeros(s(n,:));
    try,
        a(n)=find(~ismember(1:max(x)+1,x),1);  % smallest OK number
    catch,
        a(n)=1;                                % case of blank page for n
    end,

    s(n+1:2*n-1,end+1)=2*a(n)-a(n-1:-1:1);     % determined new forbidden values
end,
a                                              % print ans=...

```

Input is read from STDIN, and printing is done automatically with `ans=` and stuff appended. I hope this qualifies as "reasonable" output.

This is also a sieve-based solution: the variable `s(i,:)` keeps track of those sequence values which are *forbidden* for `a(i)`. The `try-catch` block is needed to treat the case of an empty (meaning full zero) `s` matrix: in this case the lowest value of `1` is already allowed.

However, the memory need (or runtime?) gets pretty messy above `N=2000`. So here's a non-competing, more efficient solution:

```
%pre-alloc
s = zeros([N,fix(N*0.07+20)]); %strict upper bound, needs adjusting later
i = zeros(1,N);

a = 1;
for n = 2:N,
    x = s(n,1:i(n));
    if isempty(x),
        a(n) = 1;
    else
        a(n) = find(~ismember(1:max(x)+1,x),1);
    end,

    j = n+1:min(2*n-1,N);
    i(j) = i(j)+1;
    s(N,max(i(j))) = 0;   %adjust matrix size if necessary
    b = a(n-1:-1:1);
    s(sub2ind([N,size(s,2)+1],j,i(j))) = 2*a(n)-b(1:length(j));
end

```

In this implementation the `s` matrix again contains forbidden values, but in a well-ordered way, without any zero blocks (which are present in the competing version). The index vector `i` keeps track of the number of forbidden vectors in `s`. At first sight cells would be great to keep track of the information stored in `s`, but those would be slow, and we couldn't index a bunch of them at the same time.

One nasty feature of MATLAB is that while you can say `M(1,end+1)=3;` and automatically expand a matrix, you can't do the same with linear indexing. It sort of makes sense (how should MATLAB know the resulting array size, in the framework of which it should interpret the linear indices?), but it still surprised me. This is the reason for the superfluous line `s(N,max(i(j))) = 0;`: this will expand the `s` matrix for us whenever necessary. The starting size guess `N*0.07+20` comes from a linear fit to the first few elements, by the way.

In order to test runtime, I also checked a slightly modified version of the code, where I initialized the `s` matrix to have size `N/2`. For the first `1e5` elements this seems to be a very generous guess, so I removed the expansion step of `s` mentioned in the previous paragraph. These together imply that the code will be faster, but also less robust at very high `N` (since I don't know how the series looks like there).

So here are a few runtimes, comparing

* v1: the competing golfed version,
* v2: the low-starting-size, fool-proof version and
* v3: the generous-starting-size, might-fail-for-large-N version.

I measured these on R2012b, taking the best of 5 runs inside a named function definition with `tic/toc`.

1. `N=100`:
    * v1: `0.011342 s`
    * v2: `0.015218 s`
    * v3: `0.015076 s`
2. `N=500`:
    * v1: `0.101647 s`
    * v2: `0.085277 s`
    * v3: `0.081606 s`
3. `N=1000`:
    * v1: `0.641910 s`
    * v2: `0.187911 s`
    * v3: `0.183565 s`
4. `N=2000`:
    * v1: `5.010327 s`
    * v2: `0.452892 s`
    * v3: `0.430547 s`
5. `N=5000`:
    * v1: N/A (didn't wait)
    * v2: `2.021213 s`
    * v3: `1.572958 s`
6. `N=10000`:
    * v1: N/A
    * v2: `6.248483 s`
    * v3: `5.812838 s`

It would seem that the `v3` version is significantly, but not overwhelmingly faster. I don't know whether an element of uncertainty (for very large `N`) is worth the minor increase in runtime.
> 2 votes

# Answer
# Uiua, 28 bytes

```
⇌⍥(⊂⊗0⍘⊚∸↥0-⬚∞-,▽◿2⇡⧻...)∶[]

```

Try it online!

I don't think I like the "quadruplicate" up front...

Takes n and outputs the first n values of the sequence.

```
⇌⍥(⊂⊗0⍘⊚∸↥0-⬚∞-,▽◿2⇡⧻...)∶[]    input: n
⇌⍥(...):[]    repeat n times to the empty list and reverse the result...
⊂⊗0⍘⊚∸↥0-⬚∞-,▽◿2⇡⧻...    input: current list L reversed, output: next item prepended
                 ▽◿2⇡⧻.      extract every 2nd element using mask 0 1 0 1...
           -⬚∞-,        .     2L minus the above, where the above is padded with ∞
         ↥0                    convert negatives to 0 to appease ⍘⊚
        ∸                     prepend 0 to get 1 at the first iteration
     ⍘⊚                      inverse where; counts of 0, 1, ...
  ⊗0                         index of 0 (the smallest nonnegative integer
                              not in the list before ⍘⊚)
⊂                        .   prepend it to L

```
> 2 votes

# Answer
## ES6, 114 bytes

```
n=>[...r=Array(n)].map((x,i,s)=>{for(y=1;x&&x[y];y++);r[i]=y;for(j=i;++j<n;s[j][y+y-r[i+i-j]]=1)s[j]=s[j]||[]}&&r

```

Returns an array of the first n elements of the sequence, so the indices are 1 off the ungolfed version below. I used the sieve approach. This version slows down after about n=2000; a previous version avoided reading off the beginning of the array which meant it didn't slow down until about n=2500. An older version used the sieve array as a list of forbidden values rather than a boolean array of which values were forbidden; this could get to about n=5000 without breaking sweat. My original version tried to use bitmasks but that turned out to be unhelpful (and was also far too long at 198 bytes).

The not quite so slow version ungolfed:

```
function smoke(n) {
    result = [];
    sieve = [];
    for (i = 1; i <= n; i++) {
        value = 1;
        if (sieve[i]) {
            while (sieve[i][value]) {
                value++;
            }
        }
        result[i] = value;
        for (j = 1; j < i && i + j <= n; j++) {
            if (!sieve[i + j]) sieve[i + j] = [];
            sieve[i + j][value + value - result[i - j]] = true;
        }
    }
    return result;
}

```
> 1 votes

# Answer
# Nibbles, ~~12.5~~ 10.5 bytes (21 nibbles)

```
.~~1/-,~!*2$`%~>>@-

```

Attempt This Online!

Outputs the infinite sequence.
'Nnumbers-the-new-value-must-avoid' approach taken from xnor's Python answer.

```
.~~1/-,~!*2$`%~>>@-     # full program
.~~1/-,~!*2$`%~>>@-$    # with implicit variable shown:
.~~                     #  append until null,
   1                    #  starting with the 1-element list [1]:
                        #   get the numbers the new value must avoid:
        !               #    zip together:
         *2$            #     twice the current list
            `%~>>@      #     and its even-indexed elements
                  -     #     by subtraction,
     -                  #   now remove the numbers to avoid from
      ,~                #    the infinite list of natural numbers
    /              $    #   and get the first element.

```
> 1 votes

# Answer
# 05AB1E, 13 bytes

```
ƒ¯Âxsιθ-∞sKнˆ

```

Inspired by the Python, Nibbles, and Jelly answers, so make sure to upvote those as well!

Try it online.

**Explanation:**

```
ƒ             # Loop the (implicit) input+1 amount of times:
 ¯            #  Push the global array (empty by default)
  Â           #  Bifurcate it; short for Duplicate & Reverse copy
   x          #  Double each value in the reversed list (without popping)
    s         #  Swap so the non-doubled reversed list is at the top again
     ι        #  Uninterleave it into two parts
      θ       #  Pop and leave the last part, for all (0-based) odd-indiced values
       -      #  Remove the values in the lists from one another at the same positions,
              #  removing any trailing items, since the lists are of unequal lengths
        ∞     #  Push an infinite positive list: [1,2,3,...]
         s    #  Swap so the generated list is at the top again
          K   #  Remove all those values from the infinite list
           н  #  Pop and keep the first/smallest value remaining
            ˆ #  Pop and add it to the global array for the next iteration
              # (after the loop, the global array that's still on the stack after the
              # bifurcation is output implicitly as result, hence why we loop +1 amount
              # of times)

```
> 0 votes

# Answer
# JavaScript (Node.js), 65 bytes

```
f=(n,x=1,g=d=>--d?2*f(d)-x!=f(2*d-n)?g(d):g(n,++x):x)=>n>0?g(n):f

```

Try it online!

Slow
> 0 votes

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


title: prOGraMMIng PuZZleS & cOde ____

text:
# Question
Title: prOGraMMIng PuZZleS & cOde ____
## Input

A non-empty encoded string consisting of printable ASCII characters (in the range 32-126), where some missing letters have been replaced with `_`.

## Output

A decoded string of the same length with all letters in lowercase, including the missing ones.

## How?

*Edit: As mentioned by @Deusovi in the comments, this is a variant of Bacon's cipher.*

* Gather all letters in the original string and group them by 5. Additional letters that do not fit in a full group of 5 are ignored.
* Convert each group into binary: lowercase = **0**, uppercase = **1**. This leads to a list of integers.
* Use each value **N** in this list to replace each `_` in the original string with the **N**-th letter of the alphabet (0-indexed), in order of appearance.

**Example:** `prOGraMMIng PuZZleS & cOde ____`

```
prOGr --> 00110 -->  6 -->  7th letter = 'g'
aMMIn --> 01110 --> 14 --> 15th letter = 'o'
gPuZZ --> 01011 --> 11 --> 12th letter = 'l'
leScO --> 00101 -->  5 -->  6th letter = 'f'

```

By replacing the missing letters and converting everything back to lowercase, the original string is unveiled:

```
programming puzzles & code golf

```

This is the expected output.

## Clarifications and rules

* The missing letters are guaranteed to appear at the end of the string. More formally: there will never be any letter after the first `_` in the input string. However, there may be other printable ASCII characters such as spaces and punctuation marks.
* The input is guaranteed not to contain any *useless* capital letter: all capital letters are bits set to **1** which are required to decode the missing letters. Everything else is in lowercase.
* The input string is guaranteed to be valid. Especially:
    + It will always contain enough full groups of 5 letters to decode the underscores.
    + The binary-encoded integers are guaranteed to be in the range **\[0-25\]**.
* There may be no `_` at all in the input string, in which case you just have to return the input.
* This is , so the shortest answer in bytes wins!

## Test cases

```
Input : hello!
Output: hello!

Input : helLO, worl_!
Output: hello, world!

Input : i aM yoUr faTh__.
Output: i am your father.

Input : prOGraMMIng PuZZleS & cOde ____
Output: programming puzzles & code golf

Input : Can YOu gUesS tHE ENd oF This ____?
Output: can you guess the end of this text?

Input : THe qUICk brown FOx JUMps oVEr the la__ ___.
Output: the quick brown fox jumps over the lazy dog.

Input : RoadS? wHERe we're goinG WE doN't need _____.
Output: roads? where we're going we don't need roads.

Input : thE greatESt Trick thE DeVIl EVer PUllEd wAs CONvInciNg tHe WorLD h_ ____'_ _____.
Output: the greatest trick the devil ever pulled was convincing the world he didn't exist.

```

Some extra test-cases:

```
Input : BInar_
Output: binary

Input : 12 MonKey_
Output: 12 monkeys

Input : hyPerbolIZ__
Output: hyperbolized

Input : {[One Last Test ca__]}
Output: {[one last test case]}

```

# Answer
> 22 votes
# 05AB1E, 18 bytes

### Code:

```
áS.u5ôJC>.bv'_y.;l

```

Uses the **05AB1E** encoding. Try it online!

### Explanation:

```
á                       # Remove non-letters from the input string.
 S                      # Split the result into individual characters.
  .u                    # Check if is uppercase for each character.
    5ôJ                 # Split into binary numbers of length 5.
       C                # Convert from binary to decimal.
        >               # Add one.
         .b             # Map 1 → A, 2 → B, 3 → C, ..., 25 → Y, 26 → Z.
           v            # For each letter:
            '_y.;       #   Replace the first occurrence of '_' with the current letter.
                 l      #   Convert the string to lowercase.

```

# Answer
> 9 votes
# Perl 5 `-pF -MList::Util=sum`, 75 bytes

```
@a=grep!/\W|\d/,@F;s!_!(a..z)[sum map{a gt shift@a&&16/2**$_}0..4]!eg;$_=lc

```

Try it online!

## Explanation:

* `-pF` reads a line of input into the variable `$_` and, split into characters, into the array `@F`.
* `@a=grep!/\W|\d/,@F` sets the array `@a` equal to those members of `@F` that don't satisfy the regex `\W|\d`. `\W` is anything but letters, numbers, and `_`; `\d` is numbers. So `\W|\d` is anything but letters and `_`, and `@a` has all the letters and `_` characters. We will wind up never examining the `_` characters in `@a`. (Note that this only works because the input is guaranteed ASCII.)
* `map{a gt shift@a&&16/2**$_}0..4` does the following for 0 through 4: It shifts the next element off of `@a`, shortening it, and evaluates whether `a` is asciibetically greater than that element (i.e. whether that element is uppercase). If so, `&&` isn't short-circuited, so we get 16 divided by 2 to rhe power of the input value (0 through 4). Otherwise `&&` is short-circuited and we get 0. `map` returns the list of five numbers to `sum`, which adds them.
* That's the element we want from the list `a..z`, and that's what we get from `(a..z)[…]`.
* `s!_!…!eg` converts each `_` in `$_`, in turn, to the appropriate letter.
* `$_=lc` converts `$_` to the lowercase version of itself, and `-p` prints it.

# Answer
> 8 votes
# Python 2, 113 bytes

```
s=input()
i=k=0
for c in s:
 if c.isalpha():k+=k+(c<'a');i+=1;s=s.replace('_',chr(k%32+97),i%5<1)
print s.lower()

```

Try it online!

# Answer
> 7 votes
# , ~~62~~ 61 bytes

```
tolower u:@]`(I.@t=.'_'=[)`[}+/@t$97+_5#.\3|0 2 4-.~'@Z`z'&I.

```

Try it online!

# Answer
> 6 votes
# Retina, ~~91~~ 90 bytes

```
T`l`a
T`L`A
[^Aa]

L`.{5}
A
aA
+`Aa
aAA
+T`_lA`l_`[^A]A
^
$+¶
+`_(.*)¶a+(.)
$2$1
0G`
T`L`l

```

Try it online! Explanation:

```
T`l`a
T`L`A
[^Aa]

```

Translate lowercase letters to `a` and uppercase letters to `A`, deleting everything else.

```
L`.{5}

```

Split the `Aa`s into groups of 5.

```
A
aA
+`Aa
aAA

```

Convert from binary into unary, treating `A` as 1 and `a` as 0. Since there were 5 `Aa`s originally, there are 5 `a`s left, plus a number of `A`s depending on the desired position in the alphabet.

```
+T`_lA`l_`[^A]A

```

Increment the last `a` according to the number of following `A`s.

```
^
$+¶

```

Prepend the original input.

```
+`_(.*)¶a+(.)
$2$1

```

Replace any `_`s with the next decoded letter.

```
0G`

```

Remove any spare decoded letters.

```
T`L`l

```

Lowercase everything.

# Retina 0.8.2, 117 bytes

```
.+
$&¶$&
T`L`l`^.*
T`l`a`.*$
T`L`A
T`aAp`aA_`.*$
(.*¶)?.{5}
$&;
A
aA
+`Aa
aAA
+T`_lA`l_`[^A]A
+`_(.*¶)a+(.);
$2$1
1G`

```

Try it online! Explanation:

```
.+
$&¶$&

```

Duplicate the input.

```
T`L`l`^.*

```

Lowercase the first copy.

```
T`l`a`.*$

```

Translate lowercase letters to `a` in the second copy.

```
T`L`A

```

Translate uppercase letters to `A`. These must be in the second copy because the first copy was already lowercased.

```
T`aAp`aA_`.*$

```

Delete everything else in the second copy.

```
(.*¶)?.{5}
$&;

```

Split the second copy (now just `Aa`s) into groups of 5.

```
A
aA
+`Aa
aAA
+T`_lA`l_`[^A]A
+`_(.*¶)a+(.);
$2$1
1G`

```

Decode the letters and insert them as before.

# Answer
> 5 votes
# Scala, 189 bytes

```
def f(s:Array[Char])={var j=0;s.zipWithIndex.collect{case(95,i)=>s(i)=(Integer.parseInt(s.filter(_.isLetter)slice(j,j+5)map(k=>if(k<91)1 else 0)mkString,2)+97)toChar;j+=5};s.map(_.toLower)}

```

Try it online!

Explanation:

```
def f(s: Array[Char]) = {                // takes a String in input
  var j = 0                              // j stores at which block of 5 letters we're currently at
  s.zipWithIndex.collect {               // Array('h', 'e', ...) => Array(('h', 0) ('e', 1), ...) and we apply a collect transformation (filter/map)
    case (95, i) =>                      // we only handle cases where the char is '_' (95)
      s(i) = (                           // we modify the char at index i with the following
        Integer.parseInt(                // Integer.parseInt("00110", 2) = 6
          s                              //
            .filter(_.isLetter)          // filter out non letter chars (spaces, punct, figures, ...) from the input string (thanks @Arnauld for the fix)A
            .slice(j, j+5)               // "substring" the array to the block of 5 letters in question
            .map(                        // map on the current block of 5 letters
              k =>                       // the index of the next char in the block f 5 (e.g. 13)
                if (k < 91) 1 else 0     // if the current char is upper case (<91) then we replace it by a bit true, otherwise by a bit false
            )mkString,                   // Array(0, 1, 1, ...) => "011..."
          2                              // cast string to binary
        )                                //
        + 97                             // +97 to create a lower case char
      )toChar                            // cast from int to char
      j += 5                             // update the starting index of the next block of 5 letters
    }                                    //
  s.map(_.toLower)                       // return the updated seq of chars all in lower case
}                                        //

```

# Answer
> 5 votes
# Jelly,  ~~28 27~~  26 bytes

-1 thanks to Erik the Outgolfer & dylnan

Not a very Jelly-friendly challenge!

```
ḟŒs$Ƈ<”[s5Ḅ+97Ọż@ṣ”_$FṁLŒl

```

A monadic link accepting and returning lists of characters.

**Try it online!**

### How?

```
ḟŒs$Ƈ<”[s5Ḅ+97Ọż@ṣ”_$FṁLŒl - Link: list of characters    e.g. "MfUNE_?"  (shorthand for ['M','f','U','N','E','_','?'])
    Ƈ                      - filter keep each if:
   $                       -   last two links as a monad:
 Œs                        -     swap-case
ḟ                          -     filter discard
                           - ...i.e. keep A-Z,a-z since they change when the case is swapped
                           -                                  "MfUNE"
      ”[                   - literal character                '['
     <                     - less than? (i.e. is upper-case?) [1,0,1,1,1]
        s5                 - split into fives                 [[1,0,1,1,1]]
          Ḅ                - from base two (vectorises)       [[23]]
           +97             - add (vectorises) ninety-seven    [[120]]
              Ọ            - from ordinals (vectorises)       [['x']]
                    $      - last two links as a monad:
                  ”_       -   literal character              '_'
                 ṣ         -   split at                       [['M','f','U','N','E'],['?']]
               ż@          - swapped @rgument zip             [[['M','f','U','N','E'],'x'],['?']]
                     F     - flatten                          "MfUNEx?"
                       L   - length (of input)                7
                      ṁ    - mould like                       "MfUNEx?"
                           - ...removes any excess characters
                        Œl - lower-case                       "mfunex?"

```

# Answer
> 5 votes
# JavaScript (Node.js), 94 bytes

```
x=>x.toLowerCase(w=/[a-z]/gi).replace(/_/g,g=Z=>Z>62?(Z-52).toString(36):g(w.exec(x)<g|2*-~Z))

```

Try it online!

# JavaScript (Node.js), ~~125~~ 124 bytes

```
x=>x.replace(s=/./g,c=>parseInt(c,36)>9?c.toLowerCase(s+=+(c<{})):c=='_'?('0b'+s.slice(4,9)-~9).toString(36,s=s.slice(5)):c)

```

Try it online!

# Answer
> 5 votes
# APL (Dyalog Unicode), 46 bytesSBCS

Anonymous lambda, Assumes `⎕IO` (Index Origin) to be `0`.

```
{_←'_'=⊢⋄819⌶A[2⊥⍉(+/_⍵)5⍴A∊⍨⍵∩A,819⌶A←⎕A]@_⍵}

```

Try it online!

`{``}` two-statement function;  is the argument,  separates statements

argument (no-op function)
`'_'=` where equal to an underscore (i.e. a Boolean mapping function)
`_←` assign that function to `_`

`A[``]@_⍵` put the following characters of `A` **at** positions of underscores in the argument
`⎕A` the uppercase **A**lphabet
`A←` assign that to `A`
`819⌶` lowercase it (*819 ≈ BIg*, with no left argument means not big, i.e. lowercase)
`A,` prepend the uppercase alphabet; this gives us all letters
`⍵∩` intersection of the argument and that; just the letters of the argument
`A∊⍨` which of those are members of the uppercase alphabet; uppercase bits
`(``)5⍴`**r**eshape that to the following number of rows, and five columns:
`_⍵` the mask of underscores in the argument
`+/` sum that; number of underscores
transpose (to treat each row as a number rather than as a bit position)
`2⊥` evaluate as base-2
`819⌶` lowercase everything

# Answer
> 4 votes
# Jelly, 26 bytes

```
xn¥Œs<”[s5Ḅ‘ịØaṛi”_ḟ0Ɗ¦ƒŒl

```

Try it online!

Different approach from Jonathan Allan's. EDIT: So, I, uh, apparently thought of the same byte reduction as Jonathan Allan, so it doesn't hurt to mention his name again.

# Answer
> 3 votes
# CJam, 43 bytes

```
q'_/_0={el_eu=!},_eu.=5/2fb65f+:c1$,(<.+:el

```

Try it online!

# Answer
> 3 votes
# Clean, ~~180~~ ... 150 bytes

```
import StdEnv
?s=['a'+sum[i\\i<-:""&c<-s|c<'a']: ?(drop 5s)]
@['_':b][x:y]=[x: @b y]
@[a:b]z=[toLower a: @b z]
@e _=e
$s= @s(?(filter isAlpha s))

```

Try it online!

Defines the function `$ :: [Char] -> [Char]` with `@ :: [Char] [Char] -> [Char]` as a helper to replace underscores, and `? :: [Char] -> [Char]` as a helper to generate the replacement characters.

# Answer
> 3 votes
# C (gcc), 111 109 101 100 bytes

*Edit:* Added lowercasing per @FrownyFrog's comment; thanks to Lynn, Christoph and user5329483 for their suggestions!

```
f(s,t,i)char*s,*t;{for(t=s;t=strchr(t,95);*t=i+1)for(i=3;i<64;s++)isalpha(*s)?i=2*i|*s<97,*s|=32:0;}

```

Try it online!

# Answer
> 3 votes
# Stax, 22 bytes

```
â╟▓ïMeee¶▐f◄┴≈┘n╛äyΩ○N

```

Run and debug it

The general approach is a regular expression replacement of `"_"` using a callback function that slices letters of the inputs to compute each replacement character.

```
v       convert to lower case
'_      "_" string literal
{       begin block for regex replacement
  yVl|& all the letters only from the original input
  5/    split into chunks of 5
  i@    keep the ith one, where i is the 0-based number of times this block has run
  {97<m map 5-letter chunk to bits to indicate which are lowercase
  :b    decode as 5-bit integer
  97+]  add 97 and wrap in array to convert to lower case character
}       end block for regex replacement
R       do regex replacement

```

Run this one

# Answer
> 3 votes
# JavaScript (Node.js), 100 bytes

```
s=>s.toLowerCase(c=/[a-z]/gi).replace(/_/g,_=>(g=n=>n?(c.exec(s)<{})*n+g(n>>1):10)(16).toString(36))

```

Try it online!

Thanks to @Arnauld, saves 2 bytes.

# Answer
> 3 votes
# , ~~153~~ ~~135~~ 113 bytes

```
function(s,S=utf8ToInt(s)){S[S==95]=2^(4:0)%*%matrix(S[S%in%c(65:90,97:122)]<95,5)+97
cat(tolower(intToUtf8(S)))}

```

Try it online!

Issues some warnings with the use of `matrix` but that shouldn't affect the result. Also issues warnings as `[<-` assignment will remove extraneous assigned objects by default.

*40(!) bytes down thanks to JayCe's improvements*

# Answer
> 3 votes
# Haskell, 139 bytes

```
([]%)
a%(x:y)|x=='_'=['a'..]!!foldl1((+).(2*))(take 5a):drop 5a%y|x>'@',x<'['=[x..]!!32:(a++[1])%y|x>'`',x<'{'=x:(a++[0])%y|1<2=x:a%y
a%e=e

```

Try it online!

# Answer
> 3 votes
# TypeScript's Type System, ~~637~~ ~~526~~ ~~515~~ ~~505~~ ~~496~~ ~~490~~ 489 bytes

```
//@ts-ignore
type a<S="abcdefghijklmnopqrstuvwxyz",A=[]>=S extends`${infer F}${infer R}`?a<R,[...A,F]>:A;type u<S,D>=D extends`${infer A}${infer R}`?`${u<S,R>}${u<S,R>}${S[A]extends a[any]?"":1}`:D;type c<S,T=[]>=S extends[{},{},{},{},{},...infer R]?c<R,[...T,a[a<u<S,"43210">>["length"]]]>:T;type p<S,O=[]>=S extends[infer A,...infer R]?p<R,F<A,0>extends a[any]?[...O,A]:O>:O;type F<S,V=c<p<a<S>>>>=[S,V]extends[`${infer A}_${infer B}`,[{},...infer R]]?F<`${A}${V[0]}${B}`,R>:Lowercase<S>

```

Try it at the TS Playground!

I managed to golf off a load of bytes:

1. I started by using @emanresu A's much shorter binary-to-unary type, but noticed that in this case it would be shorter if it operated on a tuple rather than string of bits, so I modified it accordingly.
2. I then thought to have the binary-to-unary type operate not on 1s and 0s, but on the characters themselves, and check if it's uppercase or lowercase within that same type, saving a lot of bytes.
3. I no longer needed the `Split` type for anything other than the alphabet, so I inlined the alphabet into it's definition.
4. I realized that `F` could be inlined into the `FillBlanks` type, by `Lowercase`ing the final result and giving the fill string a default. I also utilized this tip of mine to reduce two `extends` clauses into one, saving around 10 bytes.
5. I changed the `Chunk` type to operate on a list of characters, so the pattern match could be reduced to just "5 items and the rest", with the 5 items selected individually, and did the splitting in `F`.
6. I did a bit more rearranging to reduce the Chunk type a lot more.
7. I golfed away 2 `infer` clauses and removed a pair of unneeded parentheses.
8. I changed `u` back to using a string and then splitting it to get its length in `c`.

I’d say at this point this is one of my most well-golfed TS submissions.

---

This was a fun one!

The following explanation more closely resembles my old 637 bytes version, but the general structure is still roughly the same.

```
// Split<Str> converts string Str to a tuple of characters.
type Split<
  Str extends string,
  Arr extends string[] = []
> = Str extends `${infer A}${infer R}` ? Split<R, [...Arr, A]> : Arr;

// Lowercase alphabet tuple.
type Alphabet = Split<"abcdefghijklmnopqrstuvwxyz">;

// To get the case of a letter:
// if it is in the lowercase alphabet, return 0, else 1.
type Case<C extends string> = C extends Alphabet[number] ? 0 : 1;

// Replace all occurrences of Find with Rep in string Str.
type Replace<
  Str extends string,
  Find extends string,
  Rep extends string
> = Str extends `${infer Start}${Find}${infer Rest}`
  // Recursively substitute until no more occurrences are found.
  ? Replace<`${Start}${Rep}${Rest}`, Find, Rep>
  : Str;

// See https://esolangs.org/wiki/Binary_to_unary_conversion
type BinToUn1<In extends string> = Replace<In, "1", "0*">
type BinToUn2<In extends string> = Replace<In, "*0", "0**">
type BinToUn3<In extends string> = Replace<In, "0", "">
type BinaryToUnary<Binary extends string> = BinToUn3<
  BinToUn2<BinToUn1<Binary>>
>;

// This type does the bulk of the work.
type Chunk<
  S extends string,
  T extends string = ""
  // Map each chunk of five letters to:
> = S extends `${infer A}${infer B}${infer C}${infer D}${infer E}${infer R}`
  ? Chunk<
      R,
      // The character of the alphabet at index
      `${T}${Alphabet[
        // convert from binary
        Split<BinaryToUnary<
          // the case of each character in the chunk.
          `${Case<A>}${Case<B>}${Case<C>}${Case<D>}${Case<E>}`>
        >["length"]]}`
    >
  : T;

// Filter out non-alphabetic characters.
type Alphabetics<
  S extends string,
  O extends string = ""
> = S extends `${infer A}${infer R}`
  ? Alphabetics<R, Lowercase<A> extends Alphabet[number] ? `${O}${A}` : O>
  : O;

// Fill each underscore with the corresponding character
// of the fill string.
type FillBlanks<
  Str extends string,
  Fill extends string
> = Str extends `${infer Start}_${infer Rest}`
  ? Fill extends `${infer X}${infer R}`
    ? FillBlanks<`${Start}${X}${Rest}`, R>
    : Str
  : Str;

// Final type that composes all of the above to a single type:
type F<S extends string> = Lowercase<FillBlanks<S, Chunk<Alphabetics<S>>>>;

```

Try it at the TS Playground!

All of the recursive types used here are tail-recursive, increasing the recursion limit from 50 to 999. The only exception to this is the binary-to-unary type, but it won't get near the recursion depth for any 5-bit number.

# Answer
> 2 votes
# Go, ~~219~~ ~~217~~ ~~192~~ ~~210~~ ~~209~~ 156 bytes

Saved 25 bytes thanks to @Lynn! Saved 53 bytes thanks to @ovs!

Had to lose 18 bytes because of a bug with strings with no underscores :(

```
func p(s string){b:=0;n:=0;for _,c:=range s{if IsLetter(c){b+=b;if IsUpper(c){b+=1};n++;s=g.Replace(s,"_",string('a'+b%32),(5-n%5)/5)}};Print(g.ToLower(s))}

```

Try it online!

# Answer
> 2 votes
# Red, 247 bytes

```
func[s][a: charset[#"a"-#"z"#"A"-#"Z"]v: copy""parse s[any[copy c a(append v to-string c)|
skip]]k: 0 t: copy""repeat n(length? v)/ 5[c: 0 p: 16
loop 5[if v/(k: k + 1) <#"a"[c: c + p]p: p / 2]append t#"a"+ c]foreach c
t[replace s"_"c]lowercase s]

```

Try it online!

## More readable:

```
f: func[s][
    a: charset[#"a"-#"z"#"A"-#"Z"]
    v: copy ""
    parse s[any[copy c a(append v to-string c)| skip]]
    k: 0
    t: copy ""
    repeat n (length? v) / 5[
        c: 0
        p: 16
        loop 5[
            if v/(k: k + 1) < #"a" [c: c + p]
            p: p / 2
        ]
        append t #"a" + c
    ]
    foreach c t[replace s "_" c]
    lowercase s
]

```

# Answer
> 2 votes
# Haskell, 165 bytes

```
g""
import Data.Char
f t(x:s)('_':r)=x:f t s r
f[0,a]s r=g(s++[chr a])r
f[n,a]s(c:r)=toLower c:f[div n$1+sum[1|isAlpha c],a+sum[n|isUpper c]]s r
f _ s e=e
g=f[16,97]

```

Try it online! Example usage: `g"" "BInar_"` yields `"binary"`.

# Answer
> 2 votes
# PowerShell, 121 bytes

```
switch -r($args|% t*y){_{$_=$a[$n++]+97}[a-z]{$x+=$x+($_-le96);if(!(++$i%5)){$a+=,$x;$x=0};$_=$_-bor32}.{$r+=[char]$_}}$r

```

Try it online!

Less golfed:

```
switch -Regex ($args|% toCharArray){
    _ {                     # is underscore
        $_=$a[$n++]+97      # get a char from the array of letter
    }

    [a-z] {                 # is letter
        $x+=$x+($_-le96)    # $x=2*$x+($_-le96)
        if(!(++$i%5)){      # if(++$i%5 -eq 0)
            $a+=,$x         # add an element to the array of letters
            $x=0            # init
        }
        $_=$_-bor32         # to lower
    }

    . {                     # is any char ('_' and letters included)
        $r+=[char]$_        # add the char to result
    }
}
$r

```

# Answer
> 1 votes
# Ruby, ~~107~~ ~~106~~ 103 bytes

```
->s{s.chars.map{|c|c !~/\W|\d/?c<?a?1:0:p}.join.scan(/.{5}/){|b|s[?_]&&=(b.to_i(2)+97).chr};s.downcase}

```

Try it online!

# Answer
> 1 votes
# Java 10, ~~186~~ ~~184~~ 162 bytes

```
s->{var b="";for(Byte c:s.getBytes())s=(b+=c>64&c<91?1:c>96&c<123?0:"").length()>4?s.replaceFirst("_",(char)(97+c.valueOf(b,2))+(b="")):s;return s.toLowerCase();}

```

-2 bytes thanks to *@ceilingcat*.

Try it online.

**Explanation:**

```
s->{                        // Method with String as both parameter and return-type
  var b="";                 //  Binary-String, starting empty
  for(Byte c:s.getBytes())  //  Loop over the characters of the input-String:
    s=(b+=c>64&c<91?        //   If the current character is a lowercase letter:
           1                //    Append "1" to the binary-String
          :c>96&c<123?      //   Else-if it's an uppercase letter:
           0                //    Append "0" to the binary-String
          :                 //   Else (it's not a letter):
           ""               //    Append nothing to the binary-String
      ).length()>4?         //   And if the length of the new binary-String is now 5:
       s.replaceFirst("_",  //    Replace the first "_" in the input-String with
          (char)(97+c.valueOf(b,2))
                            //    the binary-String as character
         +(b="")):s;        //    And reset the binary-String
  return s.toLowerCase();}  //  Return the modified lowercased input-String

```

# Answer
> 1 votes
# Japt, 25 bytes

```
r'_@r\L mè\A sTT±5 ÍdIÄÃv

```

Try it

---

## Explanation

```
r'_                           :Replace underscores
   @                          :Pass each match through a function
    r                         :  From original input remove
     \L                       :    /[^a-zA-Z]/g
        m                     :  Map
         è                    :    Count
          \A                  :      /[A-Z]/g
             s                :  Slice
              T               :    From index T (initially 0)
               T±5            :    To index T+=5
                   Í          :  Convert from base-2 string to base-10 integer
                     IÄ       :  Add 64+1
                    d         :  Get character at that codepoint
                       Ã      :End function
                        v     :Lowercase

```

# Answer
> 1 votes
# Perl 5 `-p`, 78 bytes

```
for$h(s/\W|\d//gr=~y/a-z/0/r=~y/A-Z/1/r=~/.{5}/g){s%_%chr 65+oct"0b$h"%e}$_=lc

```

Try it online!

# Answer
> 1 votes
# Pyth, 36 bytes

```
Km@Gim!}kGd2c@+r1GGQ5VQp?qN\_.(KZr0N

```

Try it here

### Explanation

```
Km@Gim!}kGd2c@+r1GGQ5VQp?qN\_.(KZr0N
             @+r1GGQ                   Get the letters from the input...
            c       5                  ... in chunks of 5.
 m        d                            For each chunk...
     m!}kG                             ... check if each letter is uppercase...
    i      2                           ... converted to binary...
  @G                                   ... and get the corresponding letter.
                     VQp               For each character in the input...
K                       ?qN\_.(KZ      ... if the character is '_', replace it...
                                 r0N   ... otherwise, lowercase it.

```

# Answer
> 1 votes
# Python 3.5, 296 bytes

```
u=input();f=u.find('_');m=''.join([c for c in u if c.isalpha()]);z=[chr(int(''.join(['0'if o.islower() else'1' for o in l]),2)+65)for l in[m[h:h+5]for h in range(0,len(m),5)]if len(l)==5];[z.insert(v,d)for v,d in enumerate(u[f:])if d!="_"];u=list(u);u[f:]=z[:len(u[f:])];print(''.join(u).lower())

```

Try it online

## First code golf :)

## (I know its not small in bytes, I was just having fun making a 1 line code)

## Here is the explanation:

---

*User input*

> u=input()

---

*Finds the index of the first _ in the string and stores it*

> f=u.find('\_')

---

*strips string of all non-alpha characters*

> m=''.join(\[c for c in u if c.isalpha()\])

---

*Splits the alpha string into an array with each element consisting of 5 characters*

Ex. \['THeqU', 'ICkbr', 'ownFO', 'xJUMp', 'soVEr', 'thela'\]

*Then converts lowercase characters to 0 and uppercase characters to 1*

Ex. \['11001', '11000', '00011', '01110', '00110', '00000'\]

*and converts the binary string to an integer, adds 65 and converts that to a character*

Ex. \['z', 'y', 'd', 'o', 'g', 'a'\]

> z=\[chr(int(''.join(\['0' if o.islower() else '1' for o in l\]),2)+65) for l in \[m\[h:h+5\] for h in range(0,len(m),5)\] if len(l)==5\]

---

*finds all characteres after the first _ and pushes them into the array z at their respective locations (defined above)*

Ex. \['z', 'y', ' ', 'd', 'o', 'g', '.', 'a'\]

> \[z.insert(v,d) for v,d in enumerate(u\[f:\]) if d!="\_"\]

---

*split our string into a list of characters*

> u=list(u)

---

*slice our string from the first _ to the end of the list and replace it with the array z. I also had to slice the array z to the length of the split string from the first _ to the end because I got an extra character in the lazy dog example (the "a" at the end of the examples above)*

> u\[f:\]=z\[:len(list(u\[f:\]))\]

---

\*print out the answer *

> print(''.join(u).lower())

---

# Answer
> 1 votes
# jq, ~~165~~ 159 bytes

*Unnecessary space before `as`, and found a place where`(a|[thing])[]` could be replaced with `(a|thing)`*

```
reduce(split("[^a-z]";"i")|add|explode|while(length>4;.[5:])[:5]|map(try(.>91//1)+0//0)|reduce .[]as $x(3;2*.+$x)+1)as $r(ascii_downcase;sub("_";[$r]|implode))

```

~~Try it online!~~  Try it online!

Phew, this was a fun one! `reduce` is the real star of the show here.

```
reduce (
    # filter to alphanumeric characters and explode string into codepoints
    split("[^a-z]";"i") | add | explode |
    # chunk letters from string into full groups of 5
    while(length>4; .[5:])[:5] |
    # for each chunk emit 1 if uppercase, 0 if lowercase
    map(try(.>91//1)+0//0) |
    # reduce each chunk to a codepoint
    # start with 3, double and add the next element in the array.
    # [0,0,1,1,0] -> 6 [0,1,1,0] -> ... 102, we need to add one to map correctly
    reduce .[] as $x(3;2*.+$x)+1
# for each code point $r:
) as $r (
    # initialize with lowercased input
    ascii_downcase;
    # substitute "_" with the current letter ([codepoint]|implode)
    sub("_";[$r]|implode)
)

```

# Answer
> 1 votes
# Vyxal, 135 bitsv2, 16.875 bytes

```
\_ÞIλ?Ǎ5ẇƛaB›øA}¢ɽ

```

Try it Online!

The `s` flag is for user convenience. Outputs as a list of characters otherwise.

## Explained

```
\_ÞIλ?Ǎ5ẇƛaB›øA}¢ɽ
\_ÞIλ          }¢   # Replace the indices that correspond to "_"s by each letter in:
     ?Ǎ5ẇ           #   Push the input with non-letters removed, wrapped in chunks of length 5
         ƛ     }    #   To each chunk:
          aB›       #     int(is_upper(chunk), 2) + 1
             øA     #     Nth letter
                 ɽ  # Convert that to lowercase

```

Created with the help of Luminespire.

# Answer
> 1 votes
# GolfScript, ~~94~~ ~~84~~ ~~82~~ 72 bytes

```
.{.[65-\97-]{26,?)}/+},5/{{91<}%2base}%:s;0:l;{32|.127={l):l(s=97+}@if}%

```

Try it online!

This is probably not optimal but I can't find anything shorter.

Explanation:

* `{.[65-\97-]{26,?)}/+},`

Filter by:

+ For each of `[inp - 65, inp - 97]`:
        - Index of this in \[0, 1, ..., 25\] (-1 if not found)
        - Add one to get 0 for not found, nonzero otherwise
    + Take the sum of the result, giving 0 iff if both results were 0.
* `5/` Divide into chunks of length 5.
* `{{91<}%2base}%:s;`

Map each chunk of 5 to:

+ Map each of the 5 to:
        - Is it less than 91? (is it uppercase?)
    + Convert this result from binary to decimal. Assign this to the variable `s`.
* `0:l;` Assign the variable `l` to 0.
* `{ ... }%` Map each character of the input to:

+ `32|` Convert to lowercase by bitwise or-ing with 32. This will give 127 for an underscore.
    + `.127={ ... }@if` Return that unless it is 127 (for us, underscore), in which case...

    - `l):l` Increment `l`
        - `(s=` Index into `s`
        - `97+` Add 97 to make it a lowercase letter.

---
Tags: code-golf, string, binary
---


title: Count the number of triangles

text:
# Question
Title: Count the number of triangles
Given a list of positive integers, find the number of triangles we can form such that their side lengths are represented by three distinct entries of the input list.

(Inspiration comes from CR.)

### Details

* A triangle can be formed if *all* permutations of the three side lengths \\$a,b,c\\$ satisfy the *strict* triangle inequality $$a + b \> c.$$ (This means \\$a+b \> c\\$, \\$a+c\>b\\$ and \\$b+c\>a\\$ must all hold.)
* The three side lengths \\$a,b,c\\$ must appear at distinct positions in the list, but do not necessarily have to be pairwise distinct.
* The order of the three numbers in the input list does not matter. If we consider a list `a` and the three numbers `a[i], a[j], a[k]` (where `i,j,k` are pairwise different), then `(a[i],a[j],a[k]), (a[i],a[k],a[j]), (a[j], a[i], a[k])` etc. all are considered as the *same* triangle.
* The input list can assumed to contain at least 3 entries.
* You can assume that the input list is sorted in ascending order.

### Examples

A small test program can be found here on Try it online!

```
Input, Output:
[1,2,3]  0
[1,1,1]  1
[1,1,1,1] 4
[1,2,3,4] 1
[3,4,5,7] 3
[1,42,69,666,1000000] 0
[12,23,34,45,56,67,78,89] 34
[1,2,3,4,5,6,7,8,9,10] 50

```

For the input of `[1,2,3,...,n-1,n]` this is A002623.

For the input of `[1,1,...,1]` (length `n`) this is A000292.

For the input of the first `n` Fibonacci numbers (A000045) this is A000004.

# Answer
> 10 votes
# , ~~62~~ ~~52~~ ~~40~~ 34 bytes

```
sum(c(1,1,-1)%*%combn(scan(),3)>0)

```

Try it online!

Port of Luis Mendo's Octave solution

Since `a<=b<=c`, the triangle condition is equivalent to `a+b-c>0`. The `a+b-c` is succinctly captured by the matrix product `[1,1,-1] * X`, where `X` is the 3-combinations of the input array.

There were a lot of suggestions for improvements made by 3 different people in the comments:

# , 40 bytes

```
y=combn(scan(),3);sum(y[3,]<y[1,]+y[2,])

```

Try it online!

# Answer
> 10 votes
# Stax, ~~8~~ 7 bytes

Thanks to recursive for -1!

```
é═rê÷┐↨

```

Run and debug it at staxlang.xyz!

### Unpacked (8 bytes) and explanation:

```
r3SFE+<+
r           Reverse
 3S         All length-3 combinations
   F        For each combination:
    E         Explode: [5,4,3] -> 3 4 5, with 3 atop the stack
     +        Add the two shorter sides
      <       Long side is shorter? 0 or 1
       +      Add result to total

```

That's a neat trick. If you have a sequence of instructions that will always result in 0 or 1 and you need to count the items from an array that yield the truthy result at the end of your program, `F..+` is a byte shorter than `{..f%`.

Assumes the initial list is sorted ascending. Without this assumption, stick an `o` at the beginning for 8 bytes.

# Answer
> 6 votes
# Haskell, 49 bytes

```
([]%)
[c,b,a]%l|a+b>c=1
p%(h:l)=(h:p)%l+p%l
_%_=0

```

Try it online!

Recursively generates all subsequences of `l` (reversed), and checks which length-3 ones form triangles.

**50 bytes**

```
f l=sum[1|[a,b,c]<-filter(>0)<$>mapM(:[0])l,a+b>c]

```

Try it online!

The same idea, generating the subsequences with `mapM`, by mapping each value in `l` either to itself (include) or `0` (exclude).

**50 bytes**

```
([]%)
p%(b:t)=sum[1|c<-t,a<-p,a+b>c]+(b:p)%t
_%_=0

```

Try it online!

Tries every partition point to take the middle element `b`.

**51 bytes**

```
f(a:t)=f t+sum[1|b:r<-scanr(:)[]t,c<-r,a+b>c]
f _=0

```

Try it online!

The function `q=scanr(:)[]` generates the list of suffixes. A lot of trouble comes from needing to consider including equal elements the right number of times.

**52 bytes**

```
q=scanr(:)[]
f l=sum[1|a:r<-q l,b:s<-q r,c<-s,a+b>c]

```

Try it online!

The helper function `q=scanr(:)[]` generates the list of suffixes.

**57 bytes**

```
import Data.List
f l=sum[1|[a,b,c]<-subsequences l,a+b>c]

```

Try it online!

# Answer
> 5 votes
# Brachylog, 11 bytes

```
{⊇Ṫ.k+>~t}ᶜ

```

Try it online!

I may have forgotten to take advantage of the sorted input in my old solution:

# Brachylog, ~~18~~ ~~17~~ 15 bytes

```
{⊇Ṫ¬{p.k+≤~t}}ᶜ

```

Try it online!

```
{            }ᶜ    The output is the number of ways in which
 ⊇                 a sublist of the input can be selected
  Ṫ                with three elements
   ¬{       }      such that it is not possible to show that
     p             for some permutation of the sublist
       k+          the sum of the first two elements
         ≤         is less than or equal to
      .   ~t}      the third element.

```

# Answer
> 5 votes
# Perl 6, 35 bytes

```
+*.combinations(3).flat.grep(*+*>*)

```

Try it online!

# Explanation

It's a Whatever code, i. e. a concise notation for lambda functions (that works only in very simple cases). Each `*` is a placeholder for one argument. So we take the list of lengths (that appears at the first `*`), make all combinations of 3 elements (they always come out in the same order as in the original list, so that means the combinations are sorted too), flatten the list, and then take the list 3-by-3, and filter (`grep`) only those triplets that satisfy `*+*>*`, i. e. that the sum of the first two arguments is greater than the third. That gives all the triplets, and we finally count them with forcing numeric context with a `+`.

(Of course we need to test it only for the case of "sum of two smaller \> the largest". If this holds, the other hold trivially, if this does not, the triplet does not denote correct triangle lengths and we don't need to look further.)

# Answer
> 4 votes
# Python 3, 73 bytes

```
lambda l:sum(a+b>c for a,b,c in combinations(l,3))
from itertools import*

```

Try it online!

This is the first naive, brute-force approach that comes to my mind. I'll update the post if I find a shorter solution using a different approach. Note that since the input is sorted, the tuple \\$(a,b,c)\\$ is also in the ascending order so it suffices to only check whether \\$a+b\>c\\$ holds.

# Answer
> 4 votes
# Retina, 55 bytes

```
\d+
*
L$`_+
$<'
%L$w`(,_+)\b.*\1(_*)\b(?<=^_+\2,.*)
_
_

```

Try it online! Link includes test cases, but with the values in the 5th case reduced to allow it to finish today. Assumes sorted input. Explanation: Regexes don't really like matching more than one thing. A normal regex would be able to find all of the values that could be a shortest leg of a triangle. Retina's `v` option doesn't help here, except to avoid a lookahead. However Retina's `w` option is slightly more helpful, as it would be able to find both the shortest and longest leg at the same time. That's not enough for this challenge though, as there might be multiple middle legs.

```
\d+
*

```

Convert the input to unary.

```
L$`_+

```

For each input number...

```
$<'

```

... create a line that's the original array truncated to start at that number. `$'` normally means the string after the match, but the `<` modifies it to mean the string after the previous separator, avoiding wasting 2 bytes on `$&`. Each line therefore represents all potential solutions using that number as the shortest leg.

```
%L$w`(,_+)\b.*\1(_*)\b(?<=^_+\2,.*)
_

```

For each of those lines, find all possible middle and longest legs, but ensuring that the difference is less than the first leg. Output a `_` for each matching combination of legs.

```
_

```

Count the total number of triangles found.

# Answer
> 4 votes
# 05AB1E, ~~12~~ ~~10~~ 9 bytes

My first time using 05AB1E! Thanks to Grimmy for -1!

```
3.Æʒ`α›}g

```

Try it online! or test suite

A direct port of my Stax answer. Get all combinations of three entries and count those that could possibly form triangles. It's that counting part that really got me. I spend a load of bytes there. Bound to be some rookie mistake there.

```
3.Æʒ`α›}g
3.Æ          List of length-3 combinations
   ʒ   }g    Count truthy results under operation:
    `          Push the two shorter sides, then the long one
     α         Absolute difference (negated subtraction in this case)
      ›        Remaining short side is longer?

```

# Answer
> 3 votes
# Python 2, 72 bytes

```
f=lambda l,p=[]:l>[]and(p==p[:2]<[sum(p)]>l)+f(l[1:],p)+f(l[1:],p+l[:1])

```

Try it online!

**73 bytes**

```
lambda l:sum(a+b>c for j,b in enumerate(l)for a in l[:j]for c in l[j+1:])

```

Try it online!

# Answer
> 3 votes
# Octave / MATLAB, 33 bytes

```
@(x)sum(nchoosek(x,3)*[1;1;-1]>0)

```

Try it online!

# Answer
> 2 votes
# Excel VBA, ~~171~~ ~~164~~ 152 bytes

*-26 bytes thanks to TaylorScott*

```
Sub z
t=[A:A]
u=UBound(t)
For i=1To u-2
For j=i+1To u-1
For k=j+1To u
a=t(i,1):b=t(j,1):c=t(k,1)
r=r-(a+b>c)*(b+c>a)*(c+a>b)
Next k,j,i
Debug.?r
End Sub

```

Input is in the range `A:A` of the active sheet. Output is to the immediate window.

Since this looks at every combination of every cell in a column that's 220 cells tall (which is nearly 260 combinations), this code is... not fast. You could make it *much* faster but at the expense of bytes.

# Answer
> 2 votes
# JavaScript (ES6), 63 bytes

```
f=([v,...a],p=[])=>v?(!p[2]&p[0]+p[1]>v)+f(a,p)+f(a,[...p,v]):0

```

Try it online!

# Answer
> 2 votes
# Zsh, 66 bytes

```
for a;z=$y&&for b (${@:2+y++})for c (${@:3+z++})((t+=c<a+b))
<<<$t

```

Try it online!

Relatively straightforward, taking advantage of the sorted input, and incrementing in the `for` header (the increment happens once per *parent* loop).

```
for a;{
  z=$y
  for b (${@:2+y++});{   # subarray starting at element after $a
    for c (${@:3+z++})   # subarray starting at element after $b
      ((t+=c<a+b))
  }
}

```

# Answer
> 2 votes
# Pyth, 14 bytes

```
*1sm>sPded.cQ3

```

Try it online!

```
          .cQ3  # All combinations of length 3 from Q (input), sorted in ascending order
   m            # map over that lambda d:
     sPd        #   sum(d[:-1])
    >   ed      #     > d[-1]
  s             # sum all of those (uses the fact that True = 1)
*1              # multiply by 1 so it doesn't output True if there's only one triangle

```

Alternative (also 14 bytes):

```
lfTm>sPded.cQ3

```

# Answer
> 2 votes
# C (clang), 83 bytes

```
x,y,q;f(*a,z){for(x=y=q=0;z;q+=z>1&a[x-=x?1:2-y--]+a[y]>a[z])y=y>1?y:--z;return q;}

```

Try it online!

Saved 1 thanks to @ceilingcat

# Answer
> 2 votes
# Java 8, ~~131~~ ~~130~~ 126 bytes

```
a->{int r=0,i=a.length,j,k,I,J,K;for(;i-->0;)for(I=a[j=i];j-->0;)for(J=a[k=j];k-->0;r+=I+J>K&I+K>J&J+K>I?1:0)K=a[k];return r;}

```

Straightforward approach. The triangle check is the same as my answer for the *Is this a triangle?* challenge.
-4 bytes thanks to *@ceilingcat*.

Try it online.

**Explanation:**

```
a->{                  // Method with integer-array parameter and integer return-type
  int r=0,            //  Result-integer, starting at 0
      i=a.length,j,k, //  Index-integers
      I,J,K;          //  Temp-integers
  for(;i-->0;)        //  Loop `i` in the range (length,0]:
    for(I=a[j=i];     //   Set `I` to the `i`th value
        j-->0;)       //   Inner loop `j` in the range (i,0]:
      for(J=a[k=j];   //    Set `J` to the `j`'th value
          k-->0       //    Inner loop `k` in the range (j,0]:
          ;           //      After every iteration:
           r+=        //       Increase the result by:
              I+J>K&I+K>J&J+K>I?
                      //        If `I`, `J`, and `K` form a triangle:
               1      //         Increase the result by 1
              :       //        Else:
               0)     //         Keep the result the same by increasing with 0
        K=a[k];       //     Set `K` to the `k`'th value
  return r;}          //  After the nested loops, return the result

```

# Answer
> 1 votes
# Wolfram Language (Mathematica), ~~37~~ 35 bytes

```
Tr@Boole[2#3<+##&@@@#~Subsets~{3}]&

```

Try it online!

# Answer
> 1 votes
# Jelly, 9 bytes

```
œc3+>ƭ/€S

```

Try it online!

A monadic link taking a sorted list of integers as its argument and returning the number of triangles.

## Explanation

```
œc3       | Combinations of length 3
     ƭ/€  | Reduce each using each of the following in turn:
   +      | - Add
    >     | - Greater than
        S | Sum (counts the 1s)

```

Alternative 9s:

```
œc3Ṫ€<§ƊS
œc3Ṫ<SƊ€S

```

# Answer
> 1 votes
# Charcoal, 17 bytes

```
ＩΣ⭆θ⭆…θκ⭆…θμ›⁺νλι

```

Try it online! Link is to verbose version of code. Assumes sorted input. Explanation:

```
   θ                Input array
  ⭆                 Map over elements and join
      θ             Input array
     …              Truncated to length
       κ            Outer index
    ⭆               Map over elements and join
          θ         Input array
         …          Truncated to length
           μ        Inner index
        ⭆           Map over elements and join
              ν     Innermost value
             ⁺      Plus
               λ    Inner value
            ›       Is greater than
                ι   Outer value
 Σ                  Take the digital sum
Ｉ                   Cast to string for implicit print

```

# Answer
> 1 votes
# Japt `-x`, 9 bytes

```
à3 ËÌÑ<Dx

```

Try it

```
à3 ®o <Zx

```

Try it

# Answer
> 1 votes
# Ruby, 41 bytes

```
->l{l.combination(3).count{|a,b,c|c<a+b}}

```

Try it online!

# Answer
> 1 votes
# Perl 5 (`-p`), ~~55~~ 52 bytes

using regex backtracking, -3 bytes thanks to @Cows quack using `^` instead of `(?!)` to fail and backtrack.

```
$d='(\d++)';$_=/$d.* $d.* $d(?{$n++if$1+$2>$3})^/+$n

```

or

```
$_=/(\d++).* (\d++).* (\d++)(?{$n++if$1+$2>$3})^/+$n

```

TIO

# Answer
> 1 votes
# Bash, 123 bytes

```
for a;do for((i=2;i<=$#;i++)){ b=${!i};for((j=$[i+1];j<=$#;j++)){ c=${!j};T=$[T+(a<b+c&b<a+c&c<a+b)];};};shift;done;echo $T

```

Try it online!

A fun one.

# Answer
> 1 votes
# , 40 bytes

```
1#.](+/*/@(->])])@#~2(#~3=1&#.)@#:@i.@^#

```

Try it online!

# Answer
> 1 votes
# Nekomata \+ `-n`, 6 bytes

```
SƆ$đ+<

```

Attempt This Online!

```
SƆ$đ+<
S       Find a subset of the input
 Ɔ      Split the subset into the last element and the rest
  $đ    Check if the rest has exactly two elements
    +   Add these two elements
     <  Check if the last element is less than the sum

```

`-n` counts the number of solutions.

# Answer
> 0 votes
# SNOBOL4 (CSNOBOL4), 181 bytes

```
	S =TABLE()
R	X =X + 1
	S<X> =INPUT	:S(R)
I	I =J =K =I + 1	LT(I,X)	:F(O)
J	J =K =J + 1	LT(J,X)	:F(I)
K	K =K + 1	LT(K,X - 1)	:F(J)
	T =T + 1 GT(S<I> + S<J>,S<K>)	:(K)
O	OUTPUT =T
END

```

Try it online!

Brute force \\$O(n^3)\\$ algorithm. Takes input as a newline separated list and outputs the number of triangles, or an empty line for `0`. This is probably allowable since SNOBOL treats the empty string as `0` for numerical calculations.

# Answer
> 0 votes
# Scala, 280 bytes

280 bytes, it can be golfed much more.

---

Golfed version. Try it online!

```
def c(n:Int,l:List[Int]):List[List[Int]]=if(n==0)List(List())else if(n>l.size)List()else if(n==1)l.map(List(_))else{(for(i<-l.indices)yield{val h=l(i);val t=l.drop(i+1);c(n-1,t).map(h::_)}).toList.flatten}
def V(l:List[Int]):Int=c(3,l).count{case List(a,b,c)=>a+b>c&&a+c>b&&b+c>a}

```

Ungolfed version. Try it online!

```
import scala.collection.mutable.ArrayBuffer
import scala.util.control.Breaks._

object Main {
  def combination(n: Int, lst: List[Int]): List[List[Int]] = {
    if (n == 0) List(List())
    else if (n > lst.size) List()
    else if (n == 1) lst.map(List(_))
    else {
      (for (i <- lst.indices) yield {
        val head = lst(i)
        val tail = lst.drop(i + 1)
        combination(n - 1, tail).map(head :: _)
      }).toList.flatten
    }
  }

  def countValidTriangles(lst: List[Int]): Int = {
    val combinations = combination(3, lst)
    combinations.count {
      case List(a, b, c) => a + b > c && a + c > b && b + c > a
    }
  }

  def main(args: Array[String]): Unit = {
    val testCases = List(
      (List(1, 2, 3), 0),
      (List(1, 1, 1), 1),
      (List(1, 2, 3, 4), 1),
      (List(3, 4, 5, 7), 3),
      (List(1, 42, 69, 666, 1000000), 0),
      (List(12, 23, 34, 45, 56, 67, 78, 89), 34),
      (List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), 50)
    )

    for ((lst, expected) <- testCases) {
      val output = countValidTriangles(lst)
      assert(output == expected, (lst, output, expected))
    }
  }
}

```

# Answer
> 0 votes
# JavaScript (Node.js), 49 bytes

```
f=([v,...x],a,b)=>v?f(x,a,b)+(b?a+b>v:f(x,v,a)):0

```

Try it online!

# Answer
> 0 votes
# Uiua, 27 bytes (SBCS)

```
/+≡(|1<+/∘⇌)≐▽▽=3≡/+.⋯⇡ⁿ⧻,2

```

Try it online!

**Explanation**

```
            ≐▽▽=3≡/+.⋯⇡ⁿ⧻,2   # Get all length 3 combinations
                           2   # Put 2 on the stack
                          ,    # Copy the array onto the stack
                         ⧻     # Get the length of the array
                        ⁿ      # Raise 2 to the power of the length
                       ⇡       # Create an array of all natural numbers less than the result
                     ⋯         # Convert to binary
                    .          # Copy the result
                 ≡/+           # For each binary number, add up the bits
               =3              # Check which add up to three
              ▽                # Keep rows of the binary array where the number of 1s is 3
            ≐▽                 # For each of the remaining binary numbers,
                               # keep items in the original array
/+≡(|1<+/∘⇌)                   # Calculate number of triangles
  ≡(|1     )                   # For each row in the resulting array:
          ⇌                    # Reverse the array
        /∘                     # Put the items onto the stack
       +                       # Add the first two numbers
      <                        # Check if the third number is less than the result
/+                             # Add up all the triangles

```

As part of this, I made the combinations part generic. This might be useful for future golfing. If someone can find a shorter way of doing this part, it may help many people.

```
≐▽▽=⊙(≡/+.⋯⇡ⁿ⧻,2)

```

Try it online!

---
Tags: code-golf, sequence, array, integer, geometry
---


title: is_gaussian_prime(z)?

text:
# Question
Title: is_gaussian_prime(z)?
## Task

Write a function that accepts two integers \\$a,b\\$ that represent the Gaussian integer \\$z = a+bi\\$ (complex number). The program must return true or false depending on whether \\$a+bi\\$ is a Gaussian prime or not.

## Definition

\\$a+bi\\$ is a Gaussian prime if and only if it meets one of the following conditions:

* \\$a\\$ and \\$b\\$ are both nonzero and \\$a^2 + b^2\\$ is prime
* \\$a\\$ is zero, \\$|b|\\$ is prime and \\$|b| = 3 \text{ (mod }4)\\$
* \\$b\\$ is zero, \\$|a|\\$ is prime and \\$|a| = 3 \text{ (mod }4)\\$

## Details

You should only write a function. If your language does not have functions, you can assume that the integers are stored in two variables and print the result or write it to a file.

You cannot use built-in functions of your language like `isprime` or `prime_list` or `nthprime` or `factor`. The lowest number of bytes wins. The program must work for \\$a,b\\$ where \\$a^2+b^2\\$ is a 32bit (signed) integer and should finish in not significantly more than 30 seconds.

## Prime list

The dots represent prime numbers on the Gaussian plane (`x` = real, `y` = imaginary axis):

Some larger primes:

```
(9940, 43833)
(4190, 42741)
(9557, 41412)
(1437, 44090)

```

# Answer
# Haskell - 77/108107 Chars

usage: in both the solutions, typing a%b will return whether a+bi is a gaussian prime.

the lowest i managed, but no creativity or performance (77 chars)

```
p n=all(\x->rem n x>0)[2..n-1]
a%0=rem a 4==3&&p(abs a)
0%a=a%0
a%b=p$a^2+b^2

```

this solution just powers through all numbers below n to check if it's prime.

ungolfed version:

```
isprime = all (\x -> rem n x != 0) [2..n-1] -- none of the numbers between 2 and n-1 divide n.
isGaussianPrime a 0 = rem a 4==3 && isprime (abs a)
isGaussianPrime 0 a = isGaussianPrime a 0   -- the definition is symmetric
isGaussianPrime a b = isprime (a^2 + b^2)

```

the next solution has an extra feature - memoization. once you checked if some integer n is prime, you won't need to recalculate the "primeness" of all numbers smaller than or equal to n, as it will be stored in the computer.

(107 chars. the comments are for clarity)

```
s(p:x)=p:s[n|n<-x,rem n p>0] --the sieve function
l=s[2..]                     --infinite list of primes
p n=n==filter(>=n)l!!0       --check whether n is in the list of primes
a%0=rem a 4==3&&p(abs a)
0%a=a%0
a%b=p$a*a+b*b

```

ungolfed version:

```
primes = sieve [2..] where
    sieve (p:xs) = p:filter (\n -> rem n p /= 0) xs
isprime n = n == head (filter (>=n) primes) -- checks if the first prime >= n is equal to n. if it is, n is prime.
isGaussianPrime a 0 = rem a 4==3 && isprime (abs a)
isGaussianPrime 0 a = isGaussianPrime a 0   -- the definition is symmetric
isGaussianPrime a b = isprime (a^2 + b^2)

```

this uses the sieve of Eratosthenes to compute an infinite list of all primes (called l for list in the code). (infinite lists are a well known trick of haskell).

how is it possible to have an infinite list? at the start of the program, the list is unevaluated, and instead of storing the lists elements, the computer stores the way to compute them. but as the program accesses the list it partially evaluates itself up to the request. so, if the program were to request the fourth item in the list, the computer would compute all primes up to the forth that aren't already evaluated, store them, and the rest would remain unevaluated, stored as the way to compute them once needed.

note that all of this is given freely by the lazy nature of the Haskell language, none of that is apparent from the code itself.

both versions of the program are overloaded, so they can handle arbitrarily-sized data.
> 4 votes

# Answer
## C, ~~149~~ 118 characters

Edited version (118 characters):

```
int G(int a,int b){a=abs(a);b=abs(b);int n=a*b?a*a+b*b:a+b,
d=2;for(;n/d/d&&n%d;d++);return n/d/d|n<2?0:(a+b&3)>2|a*b;}

```

This is a single function:

* *G*(*a*,*b*) returns nonzero (true) if *a*+*bi* is a Gaussian prime, or zero (false) otherwise.

It folds the integer primality test into an expression `n/d/d|n<2` hidden in the return value calculation. This golfed code also makes use of `a*b` as a substitute for `a&&b` (in other words `a!=0 && b!=0`) and other tricks involving operator precedence and integer division. For example `n/d/d` is a shorter way of saying `n/d/d>=1`, which is an overflow-safe way of saying `n>=d*d` or `d*d<=n` or in essence `d<=sqrt(n)`.

---

Original version (149 characters):

```
int Q(int n){int d=2;for(;n/d/d&&n%d;d++);return n/d/d||n<2;}
int G(int a,int b){a=abs(a);b=abs(b);return!((a|b%4<3|Q(b))*(b|a%4<3|Q(a))*Q(a*a+b*b));}

```

Functions:

* *Q*(*n*) returns 0 (false) if *n* is prime, or 1 (true) if *n* is nonprime. It is a helper function for *G*(*a*,*b*).
* *G*(*a*,*b*) returns 1 (true) if *a*+*bi* is a Gaussian prime, or 0 (false) otherwise.

Sample output (scaled up 200%) for |*a*|,|*b*| ≤ 128:
> 10 votes

# Answer
# APL (Dyalog Unicode), ~~36~~ ~~47~~ ~~48~~ ~~49~~ ~~47~~ ~~43~~ 28 bytes

Takes an array of two integers `a b` and returns the Boolean value of the statement `a+bi is a Gaussian integer`.

**Edit:** +11 bytes because I misunderstood the definition of a Gaussian prime. +1 byte from correcting the answer again. +1 byte from a third bug fix. -2 bytes due to using a train instead of a dfn. -4 bytes thanks to ngn due to using a guard `condition: if_true ⋄ if_false` instead of `if_true⊣⍣condition⊢if_false`. -15 bytes thanks to ngn due to finding a completely different way to write the condition-if-else as a full train.

```
{2=≢∪⍵∨⍳⍵}|+.×0∘∊⊃|{⍺⍵}3=4||

```

Try it online!

### Explanation

```
{2=≢∪⍵∨⍳⍵}|+.×0∘∊⊃|{⍺⍵}3=4||

                           |  ⍝ abs(a), abs(b) or abs(list)
                       3=4|   ⍝ Check if a and b are congruent to 3 (mod 4)
                  |{⍺⍵}       ⍝ Combine with (abs(a), abs(b))
              0∘∊⊃            ⍝ Pick out the original abs(list) if both are non-zero
                              ⍝ Else pick out (if 3 mod 4)
          |+.×                ⍝ Dot product with abs(list) returns any of
                              ⍝ - All zeroes if neither check passed
                              ⍝ - The zero and the number that IS 3 mod 4
                              ⍝ - a^2 + b^2
{2=≢∪⍵∨⍳⍵}                    ⍝ Check if any of the above are prime, and return

```
> 4 votes

# Answer
# Haskell -- 121 chars (newlines included)

Here's a relatively simple Haskell solution that doesn't use any external modules and is golfed down as much as I could get it.

```
a%1=[]
a%n|n`mod`a<1=a:2%(n`div`a)|1>0=(a+1)%n
0#b=2%d==[d]&&d`mod`4==3where d=abs(b)
a#0=0#a
a#b=2%c==[c]where c=a^2+b^2

```

Invoke as `ghci ./gprimes.hs` and then you can use it in the interactive shell. Note: negative numbers are finicky and must be placed in parentheses. I.e.

```
*Main>1#1
True
*Main>(-3)#0
True
*Main>2#2
False

```
> 3 votes

# Answer
# Python - 121 120 chars

```
def p(x,s=2):
 while s*s<=abs(x):yield x%s;s+=1
f=lambda a,b:(all(p(a*a+b*b))if b else f(b,a))if a else(b%4>2)&all(p(b))

```

`p` checks whether `abs(x)` is prime by iterating over all numbers from 2 to `abs(x)**.5` (which is `sqrt(abs(x))`). It does so by yielding `x % s` for each `s`. `all` then checks whether all the yielded values are non-zero and stops generating values once it encounters a divisor of `x`. In `f`, `f(b,a)` replaces the case for `b==0`, inspired by **@killmous**' Haskell answer.

---

**-1** char and bugfix from **@PeterTaylor**
> 3 votes

# Answer
# Python 2.7, ~~341~~ ~~301~~ 253 bytes, optimized for speed

```
lambda x,y:(x==0and g(y))or(y==0and g(x))or(x*y and p(x*x+y*y))
def p(n,r=[2]):a=lambda n:r+range(r[-1],int(n**.5)+1);r+=[i for i in a(n)if all(i%j for j in a(i))]if n>r[-1]**2else[];return all(n%i for i in r if i*i<n)
g=lambda x:abs(x)%4>2and p(abs(x))

```

Try it online!

```
#pRimes. need at least one for r[-1]
r=[2]
#list of primes and other to-check-for-primarity numbers
#(between max(r) and sqrt(n))
a=lambda n:r+list(range(r[-1],int(n**.5)+1))
#is_prime, using a(n)
f=lambda n:all(n%i for i in a(n))
#is_prime, using r
def p(n):
    global r
    #if r is not enough, update r
    if n>r[-1]**2:
        r+=[i for i in a(n) if f(i)]
    return all(n%i for i in r if i*i<n)
#sub-function for testing (0,y) and (x,0)
g=lambda x:abs(x)%4==3 and p(abs(x))
#the testing function
h=lambda x,y:(x==0 and g(y)) or (y==0 and g(x)) or (x and y and p(x*x+y*y))

```

Thanks: 40+48 -- entire golfing to Jo King
> 3 votes

# Answer
# Perl - ~~110~~ ~~107~~ 105 chars

I hope I followed the linked definition correctly...

```
sub f{($a,$b)=map abs,@_;$n=$a**(1+!!$b)+$b**(1+!!$a);(grep{$n%$_<1}2..$n)<2&&($a||$b%4>2)&&($b||$a%4>2)}

```

Ungolfed:

```
sub f {
  ($a,$b) = map abs, @_;
  $n = $a**(1+!!$b) + $b**(1+!!$a);
  (grep {$n%$_<1} 2..$n)<2 && ($a || $b%4==3) && ($b || $a%4==3)
}

```

Explanation, because someone asked: I read the arguments (`@_`) and put their absolute values into `$a`,`$b`, because the function does not need their sign. Each of the criteria requires testing a number's primality, but this number depends on whether `$a` or `$b` are zero, which I tried to express in the shortest way and put in `$n`. Finally I check whether `$n` is prime by counting how many numbers between 2 and itself divide it without a remainder (that's the `grep...<2` part), and then check in addition that if one of the numbers is zero then the other one equals 3 modulo 4. The function's return value is by default the value of its last line, and these conditions return some truthy value if all conditions were met.
> 2 votes

# Answer
# golflua ~~147~~ 141

The above count neglects the newlines that I've added to see the different functions. Despite the insistence to not do so, I brute-force solve primes within the cases.

```
\p(x)s=2@s*s<=M.a(x)?(x%s==0)~0$s=s+1$~1$
\g(a,b)?a*b!=0~p(a^2+b^2)??a==0~p(b)+M.a(b)%4>2??b==0~p(a)+M.a(a)%4>2!?~0$$
w(g(tn(I.r()),tn(I.r())))

```

Returns 1 if true and 0 if not.

An ungolfed Lua version,

```
-- prime number checker
function p(x)
   s=2
   while s*s<=math.abs(x) do
      if(x%s==0) then return 0 end
      s=s+1
   end
   return 1
end

-- check gaussian primes
function g(a,b)
   if a*b~=0 then
      return p(a^2+b^2)
   elseif a==0 then
      return p(b) + math.abs(b)%4>2
   elseif b==0 then
      return p(a) + math.abs(a)%4>2
   else
      return 0
   end
end

a=tonumber(io.read())
b=tonumber(io.read())
print(g(a,b))

```
> 2 votes

# Answer
# APL(NARS), 99 chars, 198 bytes

```
r←p w;i;k
r←0⋄→0×⍳w<2⋄i←2⋄k←√w⋄→3
→0×⍳0=i∣w⋄i+←1
→2×⍳i≤k
r←1

f←{v←√k←+/2*⍨⍺⍵⋄0=⍺×⍵:(p v)∧3=4∣v⋄p k}

```

test:

```
  0 f 13
0
  0 f 9
0
  2 f 3
1
  3 f 4
0
  0 f 7
1
  0 f 9
0
  4600 f 5603
1

```
> 1 votes

# Answer
# Runic Enchantments, 41 bytes

```
>ii:0)?\S:0)?\:*S:*+'PA@
3%4A|'S/;$=?4/?3

```

Try it online!

Ended up being a lot easier than I thought and wasn't much room for golfification. The original program I blocked out was:

```
>ii:0)?\S:0)?\:*S:*+'PA@
3%4A|'S/!   S/;$=

```

I played around with trying to compare both inputs at the same time (which saved all of one 1 byte), but when that drops into the "one of them is zero" section, there wasn't a good way to figure out *which* item was non-zero in order to perform the last check, much less a way to do it without spending at least 1 byte (no overall savings).
> 1 votes

# Answer
# Mathematica, 149 Characters

```
If[a==0,#[[3]]&&Mod[Abs@b,4]==3,If[b==0,#[[2]]&&Mod[Abs@a,4]==3,#[[1]]]]&[(q=#;Total[Boole@IntegerQ[q/#]&/@Range@q]<3&&q!=0)&/@{a^2+b^2,Abs@a,Abs@b}]

```

The code doesn't use any standard prime number features of mathematica, instead it counts the number of integers in the list {n/1,n/2,...,n/n}; if the number is 1 or 2, then n is prime. An elaborated form of the function:

```
MyIsPrime[p_] := (q = Abs@p;
  Total[Boole@IntegerQ[q/#] & /@ Range@q] < 3 && q != 0)

```

Bonus plot of all the Gaussian Primes from -20 to 20:
> 1 votes

# Answer
# Ruby `-rprime`, ~~65~~ ~~60~~ 80 bytes

Didn't notice the "can't use isPrime" rule...

```
->a,b{r=->n{(2...n).all?{|i|n%i>0}};c=(a+b).abs;r[a*a+b*b]||a*b==0&&r[c]&&c%4>2}

```

Try it online!
> 1 votes

# Answer
# Uiua, 24 bytes

```
=1/+=0◿⇡./+×⍥(=3◿4)∊0..⌵

```

Try it online!

Straightforward implementation of the condition described on the Mathworld page.

```
=1/+=0◿⇡./+×⍥(=3◿4)∊0..⌵   input: a 2-element vector [a b] representing a+bi
                         ⌵   absolute value of each
             ⍥(    )∊0..    on a copy of it, if it contains 0,
                =3◿4        change it to v%4==3
          /+×                elementwise multiply and sum
                             (gives a^2+b^2 if ab!=0, a or b if it is 3 mod 4 and
                             the other is 0, 0 otherwise)
=1/+=0◿⇡.                    primality test

```
> 1 votes

# Answer
# JavaScript (Node.js), 78 bytes

```
a=>b=>P(a*a+b*b)|Math.abs(z=a?a*!b:b)%4+P(z)>3
P=(n,k=2)=>k*k>n||n%k&&P(n,k+1)

```

Try it online!

# JavaScript (Node.js), 93 bytes, slow

```
p=>q=>8==(g=(a,b,c,d)=>(a+n&&g(a-1,b,c,d))+(1/d?a*c-b*d==p&a*d+b*c==q:g(n,a,b,c)))(n=p*p+q*q)

```

Try it online!

Modified from vanilla definition of Gaussian prime: there's exactly 8 pairs of complex \<x,y\>, s.t. x\*y=input
> 1 votes

# Answer
# Vyxal, 136 bitsv2, 17 bytes

```
⋏A[|ȧ:4%3=]Þ•:‹¡›$%¬

```

Try it Online!

Bitstring:

```
1100111001011011010111100100111010100100001111100100100011010011110001011011001001101101100000000000111110011101010011001000101011000001

```

Literal interpretation of mathworld
> 1 votes

# Answer
# Python - ~~117 122~~ 121

```
def f(a,b):
 v=(a**2+b**2,a+b)[a*b==0]
 for i in range(2,abs(v)):
  if v%i<1:a=b=0
 return abs((a,b)[a==0])%4==3or a*b!=0

```
> 0 votes

---
Tags: code-golf, math, primes, complex-numbers
---


title: Reconstruct a missing RGB channel

text:
# Question
Title: Reconstruct a missing RGB channel
Look at these photographs of natural scenes, with one of the RGB channels taken out of them:

Source (with red): https://en.wikipedia.org/wiki/File:Altja\_j%C3%B5gi\_Lahemaal.jpg

Source (with green): https://commons.wikimedia.org/wiki/File:2007\_mather-lake\_hg.jpg

Source (with blue): https://commons.wikimedia.org/wiki/File:Fox\_01.jpg

Even without one of the channels, you can probably make out what colours certain things are supposed to be, or at least have a good idea if a reconstruction of the missing channel is accurate.

For example, here is the first picture with a red channel added back onto it which is just random noise:

This image clearly isn't an accurate reconstruction of the red channel. This is because nature photos generally don't use the entire RGB spectrum, but only a subset of "natural-looking colours". Also, the shades of red will follow certain gradients that correlate with the others.

---

Your task is to build a program that will take a photograph that's had one channel removed and attempt to approximate the original image as closely as possible by reconstructing what it believes is the missing channel.

Your program will be scored on how closely the missing channel matches with the channel of the original image, by counting the percentage of pixels whose values of that channel are within ±15 (inclusive) of the actual value in the original image (where the values range from 0 to 255 as in a standard 8-bit colour channel).

The test cases that your program will be scored on can be found here (9.04 MB zip file, 6 images). Currently it only contains the three example images above and their originals, but I'll add a few more later to make the full suite once I've done them.

Each image is scaled down and cropped to 1024 x 768, so they will have the same weight in your score. The program that can predict the most pixels within the given tolerance wins.

# Answer
# Python 3 + scikit-image

Simply sets the color of the missing channel to the average of the other two.

```
import sys
from skimage import io, color

im = io.imread(sys.argv[1])
h, w, c = im.shape

removed_channel_options = {0, 1, 2}
for y in range(h):
    for x in range(w):
        if len(removed_channel_options) == 1: break
        removed_channel_options -= {i for i, c in enumerate(im[y][x]) if c > 0}
removed_channel = removed_channel_options.pop()

for y in range(h):
    for x in range(w):
        p = [float(c) / 255 for c in im[y][x][:3]]
        p = [sum(p)/2 if i == removed_channel else p[i]
             for i in range(3)]
        im[y][x] = [int(c*255) for c in p] + [255]*(c == 4)

io.imsave(sys.argv[2], im)

```

And the restored images:
> 18 votes

# Answer
# Lua, Love2D

Just sets the missing channel to the smaller of the two remaining channels.

```
local inp = love.image.newImageData(arg[2])

local channels = {1, 2, 3}
local removed = nil
local removed_options = {true,true,true}

inp:mapPixel(function(x,y,r,g,b)
    local o = {r,g,b}
    for k,v in pairs(o) do
        if v > 0 then
            removed_options[k] = false
        end
    end
    return r,g,b
end)

for k,v in pairs(removed_options) do
    if v then
        removed = k
        break
    end
end
inp:mapPixel(function(x,y,r,g,b)
    local o = {r,g,b}
    o[removed] = math.min(o[removed%3+1], o[(removed+1)%3 + 1])
    return unpack(o)
end)

inp:encode('png', IMAGE:gsub("%.png", "2.png"))

```

Takes a filename as an argument on the command line.

## Bonus

I tried setting the missing channel to 255-(a+b), clamping the value. As to "fill in the gap". The results are useless but glorious.

And with 255-(a+b)/2
> 8 votes

# Answer
A little late to the party but I created a ControlNet - Channels RGB machine learning model which was trained on 400K RGB images where each of them have one channel missing in order to restore a missing channel from an image. It uses Stable Diffusion 1.5 generative image AI to infer an image. You can either use the inference as is, or only use the missing channel from the inference (which doesn't look to good unfortunately). I also created an accompanying space which lets you replace the channel from an inference image. Original post is here: https://github.com/lllyasviel/ControlNet/discussions/567 . There are some disadvantages however:

1. it changes the image content a bit,
2. Stable Diffusion 1 works best on images with 512 x n\*64.
3. you have to create a prompt for the image, and
4. you have to cherry-pick one of the generations.

**Results**

first is inference only, second is recomposing the missing channel from inference, the image on the right is ground truth with a missing channel

**Forest**

**Glacier**

**Fox**
> 5 votes

---
Tags: code-challenge, image-processing, test-battery
---


title: Randomize the scalars of an array

text:
# Question
Title: Randomize the scalars of an array
You must fill an array with every number from `0-n` inclusive. No numbers should repeat. However they must be in a random order.

# Rules

All standard rules and standard loopholes are banned

The array must be generated pseudo-randomly. Every possible permutation should have a equal probability.

# Input

`n` in any way allowed in the I/O post on meta.

# Output

The array of numbers scrambled from `0-n` inclusive.

# Answer
# Perl 6, 14 bytes

```
{pick *,0..$_}

```

Try it

## Expanded:

```
{           # bare block lambda with implicit parameter ｢$_｣

  pick      # choose randomly without repeats
    *,      # Whatever (all)
    0 .. $_ # Range from 0, to the input (inclusive)
}

```
> 9 votes

# Answer
# 05AB1E, 3 bytes

```
Ý.r

```

Try it online!

```
Ý   # Make a list from 0 to input
 .r # Shuffle it randomly

```
> 8 votes

# Answer
# Pyth, 3 bytes

```
.Sh

```

Demonstration

`.S` is shuffle. It implicitly casts an input integer `n` to the range `[0, 1, ..., n-1]`. `h` is `+1`, and the input is taken implicitly.
> 8 votes

# Answer
# , 16 bytes

```
sample(0:scan())

```

reads from `stdin`. `sample` randomly samples from the input vector, returning a (pseudo)random sequence.

Try it online!
> 7 votes

# Answer
# Jelly, 3 bytes

```
0rẊ

```

Try it online!

**Explanaion:**

```
0rẊ
0r  Inclusive range 0 to input.
  Ẋ Shuffle.
    Implicit print.

```

## Alternate solution, 3 bytes

```
‘ḶẊ

```

**Explanation:**

```
‘ḶẊ
‘   Input +1
 Ḷ  Range 0 to argument.
  Ẋ Shuffle.

```

Try it online!
> 6 votes

# Answer
# Python 2, 51 bytes

```
lambda n:sample(range(n+1),n+1)
from random import*

```

Try it online!

There is `random.shuffle()` but it modifies the argument in place instead of returning it...
> 5 votes

# Answer
# PHP, 42 Bytes

```
$r=range(0,$argn);shuffle($r);print_r($r);

```

Try it online!
> 5 votes

# Answer
# Bash, ~~18~~ 11 bytes

```
shuf -i0-$1

```

Try it online!
> 5 votes

# Answer
# Japt, 4 bytes

```
ò öx

```

Try it online

---

```
    :Implicit input of integer U
ò   :Generate array of 0 to U.
öx  :Generate random permutation of array.
    :Implicit output of result.

```
> 3 votes

# Answer
# MATL, 4 bytes

```
QZ@q

```

Try it online!

### Explanation

```
Q     % Implicitly input n. Add 1
Z@    % Random permutation of [1 2 ... n+1]
q     % Subtract 1, element-wise. Implicitly display

```
> 3 votes

# Answer
# CJam, ~~7~~ 6 bytes

*1 byte removed thanks to Erik the Outgolfer.*

```
{),mr}

```

This is an anonymous block (function) that takes an integer from the stack and replaces it with the result. **Try it online!**

### Explanation

```
{     e# Begin block
)     e# Increment: n+1
,     e# Range: [0 1 ... n]
mr    e# Shuffle
}     e# End block

```
> 3 votes

# Answer
# Mathematica, 24 bytes

```
RandomSample@Range[0,#]&

```
> 3 votes

# Answer
# Brachylog, 2 bytes

```
⟦ṣ

```

Try it online!

### Explanation

```
⟦     Range from 0 to Input
 ṣ    Shuffle

```
> 3 votes

# Answer
# C#, 76 bytes

```
using System.Linq;i=>new int[i+1].Select(x=>i--).OrderBy(x=>Guid.NewGuid());

```

This returns an IOrderedEnumerable, I hope that's okay, or else I need a few more bytes for a .ToArray()
> 3 votes

# Answer
# Java 8, ~~114~~ ~~111~~ 97 bytes

```
import java.util.*;n->{List l=new Stack();for(;n>=0;l.add(n--));Collections.shuffle(l);return l;}

```

-3 bytes and bug-fixed thanks to *@OlivierGrégoire*.
-4 bytes thanks to *@Jakob*.
-10 bytes by removing `.toArray()`.

**Explanation:**

Try it here.

```
import java.util.*;        // Required import for List, Stack and Collections
n->{                       // Method with integer parameter and Object-array return-type
  List l=new Stack();      //  Initialize a List
  for(;n>=0;l.add(n--));   //  Loop to fill the list with 0 through `n`
  Collections.shuffle(l);  //  Randomly shuffle the List
  return l;                //  Convert the List to an Object-array and return it
}                          // End of method

```
> 3 votes

# Answer
# Ohm, 2 bytes

```
#╟

```

Try it online!
> 2 votes

# Answer
# Pyth, 4 Bytes

```
.S}0

```

Try it here!
> 2 votes

# Answer
# C, 75 bytes

```
a[99],z,y;f(n){if(n){a[n]=--n;f(n);z=a[n];a[n]=a[y=rand()%(n+1)];a[y]=z;}}

```

Recursive function that initializes from the array's end on the way in, and swaps with a random element before it on the way out.
> 2 votes

# Answer
# Ruby, 20 bytes

`->n{[*0..n].shuffle}`
> 2 votes

# Answer
# Charcoal, 33 bytes

```
Ａ…·⁰ＮβＦβ«ＡβδＡ‽δθＰＩθ↓Ａ⟦⟧βＦδ¿⁻θκ⊞βκ

```

Try it online! Link is to verbose version of code.

Apparently it takes 17 bytes to remove an element from a list in Charcoal.

Edit: These days it only takes three bytes, assuming you want to remove all occurrences of the item from the list. This plus other Charcoal changes cut the answer down to 21 bytes: Try it online!
> 2 votes

# Answer
# APL (Dyalog), 5 bytes

```
?⍨1+⊢

```

Try it online!

Assumes `⎕IO←0`, which is default on many machines.

### Explanation

the right argument

`1+` add 1 to it

`?⍨` generate numbers 0 .. `1+⊢`-1 and randomly deal them in an array so that no two numbers repeat
> 2 votes

# Answer
# q/kdb+, 11 bytes

**Solution:**

```
{(0-x)?1+x}

```

**Example:**

```
q){(0-x)?1+x}10
5 9 7 1 2 4 8 0 3 10
q){(0-x)?1+x}10
6 10 2 8 4 5 9 0 7 3
q){(0-x)?1+x}10
9 6 4 1 10 8 2 7 0 5

```

**Explanation:**

Use the `?` operator with a negative input to give the full list of `0->n` without duplicates:

```
{(0-x)?1+x} / solution
{         } / lambda expression
         x  / implicit input
       1+   / add one
      ?     / rand
 (0-x)      / negate x, 'dont put item back in the bag'

```
> 2 votes

# Answer
# TI-83 BASIC, 5 bytes (boring)

```
randIntNoRep(0,Ans

```

Yep, a builtin. `randIntNoRep(` is a two-byte token, and `Ans` is one byte.

### More fun, 34 bytes:

```
Ans→N
seq(X,X,0,N→L₁
rand(N+1→L₂
SortA(L₂,L₁
L₁

```

Straight from tibasicdev. Probably golfable, but I haven't found anything yet.

What this does: Sorts a random array, moving elements of the second arg (`L₁` here) in the same way as their corresponding elements.
> 2 votes

# Answer
# JavaScript (ES6), 51 bytes

```
n=>[...Array(n+1).keys()].sort(_=>.5-Math.random())

```
> 1 votes

# Answer
# Aceto, ~~15~~ ~~14~~ 16 bytes

```
@lXp
Y!`n
zi&
0r

```

Push zero on the stack, read an integer, construct a range and shuffle it:

```
Y
zi
0r

```

Set a catch mark, test length for 0, and (in that case) exit:

```
@lX
 !`

```

Else print the value, a newline, and jump back to the length test:

```
   p
   n
  &

```

*(I had to change the code because I realized I misread the question and had constructed a range from 1-n, not 0-n.)*
> 1 votes

# Answer
# Go, 92 bytes

Mostly losing to the need to seed the PRNG.

```
import(."fmt";."math/rand";."time")
func f(n int){Seed(Now().UnixNano());Println(Perm(n+1))}

```

Try it online!
> 1 votes

# Answer
# 8th, ~~42~~ ~~36~~ 34 bytes

**Code**

```
>r [] ' a:push 0 r> loop a:shuffle

```

SED (Stack Effect Diagram) is `n -- a`

**Usage and example**

```
ok> 5 >r [] ' a:push 0 r> loop a:shuffle .
[2,5,0,3,1,4]

```
> 1 votes

# Answer
# Javascript (ES6), 68 bytes

```
n=>[...Array(n+1)].map((n,i)=>[Math.random(),i]).sort().map(n=>n[1])

```

Creates an array of form

```
[[Math.random(), 0],
 [Math.random(), 1],
 [Math.random(), 2],...]

```

Then sorts it and returns the last elements in the new order
> 1 votes

# Answer
# Tcl, 90 bytes

```
proc R n {lsort -c {try expr\ rand()>.5 on 9} [if [incr n -1]+2 {concat [R $n] [incr n]}]}

```

Try it online!

~~Tcl, 96 bytes
```
proc R n {proc f a\ b {expr rand()>.5}
set i -1
while \$i<$n {lappend L [incr i]}
lsort -c f $L}

```
Try it online!<br>~~
> 1 votes

# Answer
# J, 11 Bytes

```
(?@!A.i.)>:

```

### Explanation:

```
         >:   | Increment
(?@!A.i.)     | Fork, (f g h) n is evaluated as (f n) g (h n)
      i.      | Integers in range [0,n) inclusive
 ?@!          | Random integer in the range [0, n!)
    A.        | Permute right argument according to left

```

Examples:

```
    0 A. i.>:5
0 1 2 3 4 5
    1 A. i.>:5
0 1 2 3 5 4
    (?@!A.i.)>: 5
2 3 5 1 0 4
    (?@!A.i.)>: 5
0 3 5 1 2 4

```
> 1 votes

# Answer
# JavaScript ES6, 60 bytes, uniform distribute

```
f=n=>n?(z=f(n-1),z[n]=z[y=Math.random()*-~n|0],z[y]=n,z):[0]

s={};
for(i=0; i<1000; i++) k=f(2), s[k]=-~s[k];
for(i in s) console.log(i, s[i]);
```
> 1 votes

# Answer
# AWK, ~~82~~ 80 bytes

```
{for(n=$1+2;++j<n;$j=j-1);for(srand();--n;){t=$(i=int(n*rand()+1));$i=$n;$n=t}}1

```

Try it online!

`AWK` doesn't have a built-in shuffle, so this is the best I could come up with.
The `srand()` call is needed to prevent each execution from returning the same randomized sequence.

Thanks go to @ceilingcat for moving the call to *srand()* and the arithmetic tweaks to save 2 bytes.
> 1 votes

# Answer
# Thunno 2, 3 bytes

```
Ėµr

```

Try it online!

#### Explanation

```
Ėµr  # Implicit input
Ė    # Push [0..input]
 µr  # Random shuffle
     # Implicit output

```
> 1 votes

# Answer
# Factor, 25 bytes

```
[ dup [0,b] swap sample ]

```

Try it online!

```
        ! 10
dup     ! 10 10
[0,b]   ! 10 { 0 1 2 3 4 5 6 7 8 9 10 }
swap    ! { 0 1 2 3 4 5 6 7 8 9 10 } 10
sample  ! { 3 6 9 10 4 8 2 5 7 0 }

```
> 1 votes

# Answer
# Arturo, 17 bytes

```
$=>[shuffle@0..&]

```

Try it!

```
$=>[          ; a function where input is assigned to &
    0..&      ; a range from 0 to input inclusive
    @         ; reify the range (make it a concrete array)
    shuffle   ; shuffle it
]             ; end function

```
> 1 votes

# Answer
# RProgN 2, 3 bytes

```
0Rñ

```

## Explained

```
0Rñ
0R  # Range of numbers 0-n (Implicit input)
  ñ # Shuffle, Implicit output.

```

Try it online!
> 1 votes

# Answer
# Perl 5, 21 bytes

```
@a{0..<>}=$,=$/;say%a

```

Try it online!
> 0 votes

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