title: Number triangle flip

text:
# Question
Title: Number triangle flip
Say you list the positive integers in a triangle, then flip it left-to-right. Given a number, output the number it's sent to. This is a self-inverse mapping.

```
         1                      1
       2   3                  3   2
     4   5   6    <--->     6   5   4
   7   8   9  10         10   9   8   7
11  12  13  14  15     15  14  13  12  11

```

This is the n'th element of A038722, one-indexed:

```
1, 3, 2, 6, 5, 4, 10, 9, 8, 7, 15, 14, 13, 12, 11, ...

```

This sequence reverses contiguous chunks of the positive integers with increasing lengths:

```
 1, 3, 2, 6, 5, 4, 10, 9, 8, 7, 15, 14, 13, 12, 11, ...
<-><----><-------><-----------><------------------>

```

Test cases:

```
1 -> 1
2 -> 3
3 -> 2
4 -> 6
14 -> 12
990 -> 947
991 -> 1035
1000 -> 1026
1035 -> 991
1036 -> 1081
12345 -> 12305

```

---

**Leaderboard:**

```
var QUESTION_ID=117879,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/117879/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
## JavaScript (ES7), 26 bytes

```
n=>((2*n)**.5+.5|0)**2-n+1

```

An implementation of the following formula from OEIS:

### Demo

```
let f =

n=>((2*n)**.5+.5|0)**2-n+1

for(n = 1; n <= 50; n++) {
  console.log(n, '->', f(n))
}
```
> 18 votes

# Answer
# Jelly, ~~8~~ 7 bytes

```
RṁR€UFi

```

*Thanks to @ErikTheOutgolfer for saving 1 byte!*

Try it online!

### How it works

```
RṁR€UFi  Main link. Argument: n

R        Range; yield [1, ..., n].
  R€     Range each; yield [[1], [1, 2], [1, 2, 3], ..., [1, ..., n]].
 ṁ       Mold the left argument like the right one, yielding
         [[1], [2, 3], [4, 5, 6], ...]. The elements of the left argument are
         repeated cyclically to fill all n(n+1)/2 positions in the right argument.
    U    Upend; reverse each flat array, yielding [[1], [3, 2], [6, 5, 4], ...].
     F   Flatten, yielding [1, 3, 2, 6, 5, 4, ...].
      i  Index; find the first index of n in the result.

```
> 7 votes

# Answer
## Alice, 27 bytes

*Thanks to Sp3000 for the `.C` idea.*

```
/o
\i@/.2:e2,tE*Y~Z.H2*~.C+

```

Try it online!

### Explanation

I think there may be a shorter way to compute this using triangular numbers, but I thought this is an interesting abuse of a built-in, so here's a different solution.

The basic idea is to make use of Alice's "pack" and "unpack" built-ins. "Pack", or `Z`, takes two integers maps them bijectively to a single integer. "Unpack", or `Y`, inverts this bijection and turns one integer into two. Normally, this can be used to store a list or tree of integers in a single (large) integer and recover the individual values later. However, in this case we can use the functions in the opposite order, to let the nature of the bijection work for us.

Unpacking one integer into two integers basically consists of three steps:

1. Map **ℤ → ℕ** (including zero) with a simple "folding". That is, map negative integers to odd naturals, and non-negative integers to even naturals.
2. Map **ℕ → ℕ2**, using the Cantor pairing function. That is, the naturals are written along the diagonals of an infinite grid and we return the indices:

```
   ...
3  9 ...
2  5 8 ...
1  2 4 7 ...
0  0 1 3 6 ...

   0 1 2 3

```

E.g. `8` would be mapped to the pair `(1, 2)`.
3. Map **2 → ℤ2**, using the inverse of step 1 on each integer individually. That is, odd naturals get mapped to negative integers, and even naturals get mapped to non-negative integers.

To pack two integers into one, we simply invert each of those steps.

Now, we can see that the structure of the Cantor pairing function conveniently encodes the triangle we need (although the values are off-by-one). To reverse those diagonals, all we need to do is swap the **x** and **y** coordinates into the grid.

Unfortunately, since all three of the above steps are combined into a single built-in `Y` (or `Z`), we need to undo the **ℤ → ℕ** or **ℕ → ℤ** mappings ourselves. However, while doing so we can save a couple of bytes by directly using **+ → ℤ** or **ℤ → ℕ+** mappings, to take care of the off-by-one error in the table. So here is the entire algorithm:

1. Map **+ → ℤ** using **(n/2) * (-1)n-1**. This mapping is chosen such that it cancels the implicit **ℤ → ℕ** mapping during unpacking, except that it shifts the value down by 1.
2. Unpack the result into two integers.
3. Swap them.
4. Pack the swapped values into a single integer again.
5. Map **ℤ → ℕ+** using **|2n| + (n≥0)**. Again, this mapping is chosen such that it cancels the implicit **ℕ → ℤ** mapping during packing, except that it shifts the value up by 1.

With that out of the way, we can look at the program:

```
/o
\i@/...

```

This is simply a framework for linear arithmetic programs with integer input and output.

```
.    Duplicate the input.
2:   Halve it.
e    Push -1.
2,   Pull up the other copy of the input.
t    Decrement.
E    Raise -1 to this power.
*    Multiply. We've now computed (n/2) * (-1)^(n-1).
Y    Unpack.
~    Swap.
Z    Pack.
.H   Duplicate the result and take its absolute value.
2*   Double.
~    Swap with other copy.
.C   Compute k-choose-k. That's 1 for k ≥ 0 and 0 for k < 0.
+    Add. We've now computed |2n| + (n≥0).

```
> 6 votes

# Answer
# Jelly, 8 bytes

```
Ḥ½+.Ḟ²‘_

```

Try it online!

Port of my MATL answer.
> 5 votes

# Answer
# Haskell, 31 bytes

```
r=round
f n=r(sqrt$2*n)^2-r n+1

```

Try it online!

This answer just uses the formula. It is the least interesting answer here, but it also happens to be the golfiest.

# Haskell, ~~38~~ ~~36~~ 34 bytes

```
x!y|x<=y=1-x|v<-y+1=v+(x-y)!v
(!0)

```

Try it online!

`(!0)` is the point free function we are concerned with.

## Explanation

Let me start out by saying I'm very happy with this answer.

The basic idea here is that if we remove the largest triangular number smaller than our input we can reverse it and add the triangular number back. So we define an operator `!`, `!` takes our regular input, `x`, but it also takes an extra number `y`. `y` keeps track of the size of the growing triangular number. If `x>y` we want to recurse, we decrease `x` by `y` and increase `y` by one. So we calculate `(x-y)!(y+1)` and add `y+1` to it. If `x<=y` we have reached our base case, to reverse `x`'s placement in the row of the triangle we return `1-x`.

# Haskell, 54 bytes

```
f x|u<-div(x^2-x)2=[u+x,u+x-1..u+1]
(!!)$0:(>>=)[1..]f

```

Try it online!

`(!!)$0:(>>=)[1..]f` is a point-free function

## Explanation

The first thing we are concerned with is `f`, `f` is a function that takes `x` and returns the `x`th row of th triangle in reverse. It does this by first calculating the `x-1`nd triangular number and assigning it to `u`. `u<-div(x^2-x)2`. We then return the list `[u+x,u+x-1..u+1]`. `u+x` is the `x`th triangular number and the first number on the row, `u+x-1` is one less than that and the second number on the row `u+1` is one more than the last triangular number and thus the last number on the row.

Once we have `f` we form a list `(>>=)[1..]f`, which is a flattening of the triangle. We add zero to the front with `0:` so that our answers will not be offset by one, and supply it to our indexing function `(!!)`.

# Haskell, 56 bytes

```
f 0=[0]
f x|u<-f(x-1)!!0=[u+x,u+x-1..u+1]
(!!)$[0..]>>=f

```

Try it online!

This one is 2 bytes longer but a bit more elegant in my opinion.
> 5 votes

# Answer
# MATL, ~~15~~ 11 bytes

```
EX^.5+kUG-Q

```

Try it online!

This uses the formula

```
a(n) = floor(sqrt(2*n)+1/2)^2 - n + 1.

```
> 4 votes

# Answer
# Octave, ~~71~~ 68 bytes

*3 bytes saved thanks to Conor O'Brien.*

```
x=triu(ones(n=input('')));x(~~x)=1:nnz(x);disp(nonzeros(flip(x))(n))

```

This doesn't work for large inputs due to memory limitations.

Try it online!

### Explanation

Consider input `n = 4`. The code first builds the matrix

```
 1     1     1     1
 0     1     1     1
 0     0     1     1
 0     0     0     1

```

Then it replaces nonzero entries in column-major order (down, then across) by `1`, `2`, `3` ... :

```
 1     2     4     7
 0     3     5     8
 0     0     6     9
 0     0     0    10

```

Then it flips the matrix vertically:

```
 0     0     0    10
 0     0     6     9
 0     3     5     8
 1     2     4     7

```

Finally, it takes the `n`-th nonzero value in column-major order, which in this case is `6`.
> 4 votes

# Answer
# C (gcc), 48 bytes

```
k,j,l;f(n){for(k=j=0;k<n;)l=k,k+=++j;n=1+k-n+l;}

```

Try it online!

Probably suboptimal, but I'm pretty happy with this one. Uses the fact that

NTF**N** = T**N** \+ A057944(**N**) - **N** \+ 1

(If I wrote the formula down correctly, that is.)
> 3 votes

# Answer
# 05AB1E, 30 bytes

```
U1V[YLO>X›iYLOX-UY<LO>X+,q}Y>V

```

Try it online!
> 2 votes

# Answer
## Batch, 70 bytes

```
@set/ai=%2+1,j=%3+i
@if %j% lss %1 %0 %1 %i% %j%
@cmd/cset/ai*i+1-%1

```

Uses a loop to find the index of the triangular number at least as large as `n`.
> 2 votes

# Answer
# Husk, 6 bytes

```
!ṁ↔´CN

```

Try it online!

### Explanation

```
!ṁ↔´CN  -- implicit input N, for example: 4
   ´ N  -- duplicate the natural numbers:
           [1,2,3,…] [1,2,3,…]
    C   -- cut the second argument into sizes of the first:
           [[1],[2,3],[4,5,6],[7,8,9,10],…]
 ṁ↔     -- map reverse and flatten:
           [1,3,2,6,5,4,10,9,8,7,15,…
!       -- index into that list:
           6

```
> 2 votes

# Answer
# tinylisp, 78 bytes

```
(d _(q((R N T)(i(l T N)(_(a R 1)N(a T R))(a 2(a T(s T(a N R
(d f(q((N)(_ 2 N 1

```

Defines a function `f` that performs the mapping. Try it online!

### Ungolfed

We find the smallest triangular number that is greater than or equal to the input number, as well as which row of the triangle our number is in. From these, we can calculate the flipped version of the number.

* If the current triangular number is less than N, recurse to the next row of the triangle. (We treat the top row as row 2 to make the math simpler.)
* Otherwise, the flipped version of N is (T-N)+(T-R)+2.

The main function `flip` simply calls the helper function `_flip` starting from the top row.

```
(load library)

(def _flip
 (lambda (Num Row Triangular)
  (if (less? Triangular Num)
   (_flip Num (inc Row) (+ Triangular Row))
   (+ 2
    (- Triangular Num)
    (- Triangular Row))))))

(def flip
 (lambda (Num) (_flip Num 2 1)))

```
> 2 votes

# Answer
# Julia 1.0, ~~29~~ 23 bytes

```
!n=round((2n)^.5)^2-n+1

```

Try it online!

Port of Arnauld's JS answer.

-6 thx to @steffan
> 2 votes

# Answer
# 05AB1E, 9 bytes

```
·LD£í˜¹<è

```

Try it online!

**Explanation**

```
·L          # push range [1 ... 2n]
  D         # duplicate
   £        # split the first list into pieces with size dependent on the second list
    í       # reverse each sublist
     ˜      # flatten
      ¹<è   # get the element at index <input>-1

```

Array flattening unfortunately doesn't handle larger lists very well.
At the cost of 1 byte we could do ·t2z+ïn¹-\> using the mathematical formula `floor(sqrt(2*n)+1/2)^2 - n + 1` found on OEIS.
> 1 votes

# Answer
# Pyt, ~~13~~ 12 bytes

```
←Đ2*√½+⌊²-~⁺

```

Port of Arnauld's approach
> 1 votes

# Answer
# Python 3, ~~37~~ ~~35~~ 32 bytes

```
lambda n:round((2*n)**.5)**2-n+1

```

Try it online!

Port of Arnauld's JS answer.

-3 thx to @Steffan
> 1 votes

# Answer
# Vyxal, 8 bytes

```
dɾ:ẇRfJi

```

Try it Online!
> 1 votes

# Answer
# PHP, 35 Bytes

```
<?=((2*$argn)**.5+.5^0)**2-$argn+1;

```

Same formula that is used in Arnaulds Approach
> 0 votes

# Answer
# C#, ~~46~~ 44 bytes

```
n=>Math.Pow((int)(Math.Sqrt(2*n)+.5),2)-n+1;

```

I port @Arnauld's solution. Thank you!

* Pow of 0.5 is Sqrt. 2 bytes saved!
> 0 votes

# Answer
# APL (Dyalog), 27 bytes

I've got two solutions at the same bytecount.

A train:

```
⊢⊃⊃∘(,/{⌽(+/⍳⍵-1)+⍳⍵}¨∘⍳)

```

Try it online!

And a dfn:

```
{⍵⊃⊃((⍳⍵),.{1+⍵-⍳⍺}+\⍳⍵)}

```

Try it online!

Both of these solutions first create the flipped triangle and then extract element at the index stated by the argument (`1`-based).
> 0 votes

# Answer
# J, 25 bytes

```
3 :'>:y-~*:>.-:<:%:>:8*y'

```

As an explanation, consider `f(n) = n(n+1)/2`. `f(r)`, given the row `r`, returns the leftmost number of the the `r`th row of the mirrored triangle. Now, consider `g(n) = ceiling[f⁻¹(n)]`. `g(i)`, given the index `i`, returns the row on which index i is found. Then, `f(g(n))` returns the leftmost number of the row on which index n is found. So, `h(n) = f(g(n)) - (n - f(g(n)-1)) + 1` is the answer to the above problem.

Simplifying, we get `h(n) = [g(n)]² - n + 1 = ceiling[(-1 + sqrt(1 + 8n))/2]² - n + 1`.

From the looks of @Arnauld's formula, it appears that:

`ceiling[(-1 + sqrt(1 + 8n))/2] = floor[1/2 + sqrt(2n)]`.
> 0 votes

# Answer
# , 19 bytes

```
1-]-0.5*:@<.@+%:@+:

```

Try it online! Uses the formula from Arnauld's answer.

```
1-]-0.5*:@<.@+%:@+:
                 +:    2n
              %:@      sqrt(^)
    0.5      +         0.5 + ^
          <.@          floor(^)
       *:@             square(^)
  ]-                   input - ^
1-                     1 - ^
                       (computes - input + 1 in a golfier way)

```

# , 43 bytes

```
1+;@((#{.[:;(1<@,#&0)"0)<@|.;.1>:)@i.@+:i.]

```

Try it online!

Shortest non-formula solution I could think of. The array form of `;.` is really unwieldly for code golf, and it doesn't help that ragged lists aren't that golfy either.

```
1+;@((#{.[:;(1<@,#&0)"0)<@|.;.1>:)@i.@+:i.]
                                  @i.@+:      range [0, 2n)
    (                       ;.1>:)            segment [1, 2n] according to
     (                 )                      the indices of triangular numbers:
            (       )"0                         over each integer in [0, 2n):
                 #&0                            create that many 0s
             1  ,                               prepend a 1 (a cut location)
              <@                                and box it
         [:;                                    then raze that boxed list
      #{.                                       and take 2n entries from that array
                        <@|.                  box and reverse each segment
  ;@                                          raze this list
                                        i.]   get the 0-based index of the input in it
1+                                            and add 1

```

For generating the indices of triangular number, the invariance under inverse transform `(=(-:@*>:)@<.@%:@+:)` is 1 byte longer, but much faster.
> 0 votes

# Answer
# Japt, 11 bytes

0-indexed

```
gUòò@T±1ÃcÔ

```

Try it

```
gUòò@T±1ÃcÔ     :Implicit input of integer U
g               :Index into
 Uò             :  Range [0,U]
   ò            :  Range [0,each]
    @           :  Map each subrange
     T±1        :    Increment T (initially 0) by 1
        Ã       :  End map
         c      :  Flat map
          Ô     :    Reverse

```
> 0 votes

---
Tags: code-golf, math, sequence
---


title: Scan a ragged list

text:
# Question
Title: Scan a ragged list
hgl has a "scan" function called `sc`. What it does in general is a little bit abstract, so we will just talk about one specific way you can use it.

If we want to take a list of integers and get the partial sums of every prefix we can scan with `+` for sums and `0` as a starting value:

```
ghci> sc (+) 0 [1,2,3,4,5,6]
[1,3,6,10,15,21]

```

This moves left to right adding each value of the list to the accumulator and replacing it with the sum.

We can also scan things other than lists. We can scan all sorts of trees and list-like things. hgl more or less builds the scan function based on the type we give it.

One weirder example is ragged lists. These are lists that contain a mixture of values and other ragged lists. For example:

```
[1,2,3,[2,3,4],[],2,1,[4,8,[6],5],2]

```

The compiler has dreamed up a rather weird way to scan these. When the list contains values it behaves normally:

```
ghci> sc (+) 0 [1,2,3,[2,3,4],[],2,1,[4,8,[6],5],2]
[1,2,3,[2,3,4],[],2,1,[4,8,[6],5],2]
 ^1
[1,3,3,[2,3,4],[],2,1,[4,8,[6],5],2]
   ^3
[1,3,6,[2,3,4],[],2,1,[4,8,[6],5],2]
     ^6

```

but when it hits a list it splits the read head in two. One goes down that list and scans it, the other skips it and scans the rest of the outer list.

```
[1,3,6,[8,3,4],[],2,1,[4,8,[6],5],2]
       ^6
[1,3,6,[8,3,4],[],2,1,[4,8,[6],5],2]
        ^8     ^6
[1,3,6,[8,11,4],[],8,1,[4,8,[6],5],2]
          ^11      ^8
[1,3,6,[8,11,15],[],8,9,[4,8,[6],5],2]
             ^15      ^9
[1,3,6,[8,11,15],[],8,9,[4,8,[6],5],2]
                        ^9
[1,3,6,[8,11,15],[],8,9,[13,8,[6],5],11]
                         ^13         ^11
[1,3,6,[8,11,15],[],8,9,[13,21,[6],5],11]
                            ^21
[1,3,6,[8,11,15],[],8,9,[13,21,[6],5],11]
                               ^21
[1,3,6,[8,11,15],[],8,9,[13,21,[27],26],11]
                                ^27 ^26
[1,3,6,[8,11,15],[],8,9,[13,21,[27],26],11]

```

This treats a ragged list as a sort of tree, where the main list forms a spine and each nested list is an offshoot from that spine.

## Task

Take a ragged list of positive integers as input and perform the scan shown above (`sc (+) 0`) returning the scanned list.

You may take and output a ragged list in any reasonable format.

This is so answers will be scored in bytes with minimizing the source size being the goal.

## Test cases

```
[] -> []
[8] -> [8]
[1,2,3] -> [1,3,6]
[1,1,1,1,1] -> [1,2,3,4,5]
[[1],[1],[1]] -> [[1],[1],[1]]
[1,[1],[1],[1]] -> [1,[2],[2],[2]]
[1,2,3,[2,3,4],[],2,1,[4,8,[6],5],2] -> [1,3,6,[8,11,15],[],8,9,[13,21,[27],26],11]
[[1,2,3,4],[1,2,3],[1,2,3]] -> [[1,3,6,10],[1,3,6],[1,3,6]]

```

# Answer
# Python, ~~57~~ ~~54~~ 53 bytes

```
f=lambda x,a=0:[i*0==0and(a:=a+i)or f(i,a)for i in x]
```

Attempt This Online!

Thanks to @ovs for -3 bytes.

# Whython, 42 bytes

```
f=lambda x,a=0:[(a:=a+i)?f(i,a)for i in x]
```

Attempt This Online!

Uses the `?` operator to catch `TypeError: unsupported operand type(s) for +: 'int' and 'list'` and recurse in that case.
> 10 votes

# Answer
# BQN, 34 bytesSBCS

```
{×≠?(⊑){=?∾˜⋈;+0∾}1↓;}

```

Run online!

```
{×≠?(⊑){=?∾˜⋈;+0∾}1↓;} # Function taking a nested list as
 ×≠?                          ;  # If the list is empty, return it
                            1↓    # Tail of
                                  # Recursive call on the tail
                                   # If that fails, return the tail (for the base case)
      ⊑                           # The first element of the list
        {      ...      }         # Call the inner function with parameters
                                   #  - : result of recursive call
                                   #  - : first element
                                   #  - : a reference to the outer function
          =?<list>;<int>          #   Conditional, the rank of  is 0 for ints and 1 for lists
                                 #   If  is a list, call  on that
             ∾˜⋈                  #   And insert the result in the front of
                      0∾          #   If  is an integer, prepend 0 to the list
                    +             #   And add  to each integer in the resulting nested list

```

I tried to handle the base case with  (Catch) instead of an explicit conditional, but couldn't get it to work properly. See the revision history for my failed attempts.
> 6 votes

# Answer
# Wolfram Language (Mathematica), 39 bytes

```
a_~f~b___:=Join[{f@@a},0&@@a+f@b]
_f={}

```

Try it online!

Input `[list...]`. Inputting `[list]` works, but returns inside an extra layer of `{}`.

```
a_~f~b___:=                         when input is nonempty:
                 f@@a                 recurse on first element
                                      (do nothing if it's an integer)
           Join[{    },      f@b]     followed by recursion on remainder
                           a+           with first element added
                       0&@@             (or 0 if it's a list)
_f={}                               otherwise return empty list

```

---

### Wolfram Language (Mathematica), 40 bytes

```
f=#/.{a_,b___}:>Join[{f@a},0&@@a+f@{b}]&

```

Try it online!

Input `[list]`.
> 6 votes

# Answer
# , ~~111~~ ~~107~~ ~~103~~ 98 bytes

*Edit: -5 bytes each thanks to pajonk and Giuseppe*

```
`~`=function(x,t=0)`if`(length(x),`if`(is.list(y<-el(x)),c(list(y~t),x[-1]~t),c(y+t,x[-1]~y+t)),x)

```

Try it online!
> 5 votes

# Answer
# Pip `-xp`, 27 bytes

```
b|:0FdacPB:xNd?b+:d(fdb)c|l

```

Recursive main program, takes the list as a command-line argument. Attempt This Online!

### Explanation

```
b|:0FdacPB:xNd?b+:d(fdb)c|l
                             a (1st arg) is the input list; b (2nd arg) is the starting
                             number for the scan
                             When the function is called as the main program, b is not
                             specified, so it is nil
b|:0                         If b is falsey (nil or 0), set it to 0 instead
                             c and d are also local variables which are nil b/c 3rd and
                             4th arguments are not given
    Fda                      For each element d in the input list:
           xNd                 Does d contain x (empty string)?
              ?                If so, it's an integer:
               b+:d              Add it to b in-place
                               If not, it's a list of integers:
                   (f  )         Make a recursive call
                     d           using d as the new list
                      b          and the current value of b as the new starting point
       cPB:                    Take that result and push it onto the end of c
                               (Pushing an element to a nil variable makes it a list)
                        c    After the loop, return c...
                         |   except if c is falsey, it's still nil...
                          l  so return empty list instead

```
> 3 votes

# Answer
# Ruby, 39 bytes

```
f=->d,t=0{d.map{|x|x*0==0?t+=x:f[x,t]}}

```

Try it online!

Ruby has the same operator `*` for Integer and Array which takes the same right operand type(number).
If we multiply a number by 0 we get 0, if an Array we get an empty Array.
> 3 votes

# Answer
# Japt, ~~25~~ 12 bytes

emanresu's solution made me realise that, although I had the right method, my approach to it was *all* wrong - I honestly don't know *what* I was thinking!- so please upvote them if you're upvoting this.

```
Ë¶Ô?ßDÔV:V±D

```

Try it

```
Ë¶Ô?ßDÔV:V±D     :Implicit input of array U, with second input variable V defaulting to 0
Ë                :Map each D in U
 ¶               :  Is D strictly equal to
  Ô              :  Its reverse, if it's an array, or maximum, if it's an integer (see more detailed explanation below)
   ?             :  If true
    ß            :    Recursive call with arguments
     DÔ          :    U = D reversed (because reversing an array in JS mutates the original), and
       V         :    Current value of V
        :        :  Else
         V±D     :    Increment V by D

```

---

To (try to) explain how the `Ô` (which is a shortcut for the `w` method, without any arguments) allows us to differentiate between arrays & numbers by testing for strict equality:

While it's true that in JavaScript 2 arrays containing the exact same elements are not strictly equal as they are 2 distinct objects, an array assigned to a variable is, of course, equal to itself. Add to that that the `reverse` method for arrays (`w` in Japt) mutates the original array and that explains how an array assigned to a variable (`D` in this case) can be strictly equal to its reverse.

As to why a number does not equal its maximum, that's down to a peculiarity of Japt. Firstly, when applied to a number, Japt's `w` method returns the maximum of that number and the arguments passed to the method, as a `Number`. However, if *no* arguments are passed to the `w` method then the number it's applied to is returned as excpected but, for some reason, Japt converts the returned value to an `Object` and a `Number` cannot be strictly equal to an `Object`

---

## Original, 25 bytes

Preserving this version as Conor O'Brien awarded it an unexpected boubty.

```
W=Uv)?[W¶Ô?ßWÔ:V±W]cßUV:U

```

Try it
> 3 votes

# Answer
# tinylisp, ~~116~~ ~~108~~ 96 bytes

```
(d S(q((L A)(i L(i(a(h L)1)(c(a(h L)A)(S(t L)(a(h L)A)))(c(S(h L)A)(S(t L)A)))L
(d f(q((L)(S L 0

```

Try it online!

-8 bytes by removing `(load library` thanks to chunes in chat. -12 bytes thanks to some type abuse.
> 3 votes

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

```
f=(v,a=0)=>v.map(z=>z.at?f(z,a):a+=z)

```

Attempt This Online!

Port of several of the other answers.
> 3 votes

# Answer
# 05AB1E, ~~30~~ 29 bytes

```
0U"εdiXćy+š¬ëXD¬šUy®.V}sU"©.V

```

Try it online or verify all test cases.

**Explanation:**

Unfortunately 05AB1E lacks recursive methods. We can however mimic this behavior by using `"recursive_function_here®.V"©.V`. One big disadvantage about this however, is that the variables will always be in the scope of the full program, rather than this recursive function. So instead, we use and modify a list as variable.

```
0U         # Start with X=[0] (or actually X=0, but it behaves as [0])
  "..."    # Push a string with the recursive function explained below
       ©   # Store this string in variable `®` (without popping)
        .V # Evaluate it as 05AB1E code
           # (after which the result is output implicitly)

ε          # Map each item `y` to:
 di        #  If `y` is a (non-negative) integer:
   X       #   Push list X
    ć      #   Extract its head; pop and push remainder-list and first item
           #   separated to the stack
     y+    #   Add the current integer `y` to this head
       š   #   Prepend it back to the remainder-list
        ¬  #   Push this prepended head again (without popping the list)
  ë        #  Else (`y` is an inner list instead):
   X       #   Push `X`
    D      #   Push `X` again by duplicating
     ¬š    #   In this second `X`, prepend its own head
       U   #   Pop and replace `X` with this modified list
   y       #   Push the current list `y`
    ®.V    #   Do a recursive call with it
  }        #  After the if-else statement:
   s       #   Swap so the (potentially modified) `X` is at the top of the stack
    U      #   Pop and replace `X` with this modified list

```
> 2 votes

# Answer
# Python3, 74 bytes:

```
f=lambda x,h=0:x and[int==type(x[0])and(h:=h+x[0])or f(x[0],h)]+f(x[1:],h)

```

Try it online!
> 1 votes

# Answer
# BQN, 44 bytesSBCS

```
0⊸{0=≠?;×≡⊑?(⋈⊑)∾1↓;a∾(a←+⊑)1↓}

```

Run online!
> 1 votes

# Answer
# Charcoal, 51 bytes

```
⊞υ⊞Ｏθ⁰Ｆυ«≔⊟ιηＦＬι«≔§ικζ¿⁼ζ⁺ζ⟦⟧⊞υ⊞Ｏζη«≧⁺ζη§≔ικη»»»⭆¹θ

```

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

```
⊞υ⊞Ｏθ⁰

```

Temporarily push the initial accumulator to the list and push that list to the list of lists.

```
Ｆυ«

```

Loop over all of the lists.

```
≔⊟ιη

```

Remove the accumulator from the list.

```
ＦＬι«

```

Loop over the elements of the list.

```
≔§ικζ

```

Get the current element.

```
¿⁼ζ⁺ζ⟦⟧

```

Check whether it's a list. Adding an empty list to a list produces the original list, but adding it to an integer vectorises therefore producing the empty list rather than an integer.

```
⊞υ⊞Ｏζη

```

If it's a sublist then temporarily push the accumulator to the sublist and push the sublist to the list of lists.

```
«≧⁺ζη§≔ικη

```

Otherwise add the value to the accumulator and replace the value with the total.

```
»»»⭆¹θ

```

Pretty-print the result as the default output format doesn't handle ragged lists very well.
> 1 votes

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

```
f=([h,...t],v=0)=>h?[h+0>h?f(h,v):v+=h,...f(t,v)]:[]

```

Try it online!
> 1 votes

---
Tags: code-golf, array, tree-traversal, ragged-list
---


title: Sort a string, sort of

text:
# Question
Title: Sort a string, sort of
If you sort a string you'll typically get something like:

```
         ':Iaaceeefggghiiiiklllllmnnooooprrssstttttuuyyyy

```

Yes, that was the first sentence sorted.

As you can see, there are a lot of repeated characters, `aa`, `eee`, `ttttt`, 9 spaces and so on.

If we add `128` to the ASCII-value of the first duplicate, `256` to the second, `384` to the third and so on, sort it again and output the new string (modulus 128 to get the same characters back) we get the string:

```
 ':Iacefghiklmnoprstuy aegilnorstuy egilosty iloty lt

```

(Note the single leading space and the 4 trailing spaces).

The string is "sequentially sorted" `<space>':I....uy`, `<space>aeg....uy`, `<space>egi....ty`, `<space>iloty`, `<space>lt`, `<space>`, `<space>`,`<space>`, `<space>`.

It might be easier to visualize this if we use a string with digits in it. The string `111222334` will when "sorted" be: `123412312`.

## Challenge:

To no surprise, the challenge is to write a code that sorts a string according to the description above.

You can assume that the input string will contain only printable ASCII-characters in the range 32-126 (space to tilde).

---

**Test cases:**

```
**Test cases:**
 *:Tacest*es*s*

If you sort a string you'll typically get something like:
 ':Iacefghiklmnoprstuy aegilnorstuy egilosty iloty lt

Hello, World!
 !,HWdelorlol

#MATLAB, 114 bytes
 #,14ABLMTbesty 1A

f=@(s)[mod(sort(cell2mat(cellfun(@(c)c+128*(0:nnz(c)-1),mat2cell(sort(s),1,histc(s,unique(s))),'un',0))),128),''];
'()*+,-0128:;=@[]acdefhilmnoqrstuz'(),0128@acefilmnorstu'(),12celmnostu'(),12celnstu(),clnst(),cls(),cs(),()()()()

```

---

This is , so the shortest code in *each language* counted in bytes will winref.

# Answer
> 16 votes
# Pyth, 5 bytes

```
s.T.g

```

Test suite

Very straightforward: Group and sort, transpose, concatenate.

```
s.T.g
s.T.gkQ    Implicit variables
   .gkQ    Group the input input lists of elements whose values match when the
           identity function is applied, sorted by the output value.
 .T        Transpose, skipping empty values. This puts all first characters into
           a list, then all second, etc.
s          Concatenate.

```

# Answer
> 15 votes
# Jelly, 3 bytes

```
ĠZị

```

Try it online!

### How it works

Oh boy, this challenge was all but made for Jelly.

The *group* atom (`Ġ`) takes an array1 as input and groups indices that correspond to identical elements of the array. The array of index groups is sorted with the corresponding elements as keys, which is precisely the order we require for this challenge.

Next, the *zip* atom (`Z`) transposes rows and columns of the generated (ragged) matrix of indices. This simply consists of reading the columns of the matrix, skipping elements that are not present in that column. As a result, we get the first index of the character with the lowest code point, followed by the first index of the character with the second lowest code point, … followed by the second index of the character with the lowest code point, etc.

Finally, the *unindex* atom () retrieves the elements of the input array at all of its indices in the generated order. The result is a 2D character array, which Jelly flattens before printing it.

---

1 Jelly doesn't have a *string* type, just arrays of characters.

# Answer
> 10 votes
# Python 3, ~~109~~ ~~105~~ ~~104~~ ~~103~~ ~~99~~ ~~93~~ ~~90~~ ~~88~~ ~~81~~ ~~79~~ 69 bytes

*2 bytes saved thanks to FlipTack*

*7 bytes saved because flornquake caught my dumb error*

*2 bytes saved thanks to xnor*

*10 bytes saved thanks to Dennis*

```
a=[*input()]
while a:
    for c in sorted({*a}):print(end=c);a.remove(c)

```

## Explanation

We start by converting our string to a list using a splat and storing that list in a variable `a`. Then while our `a` is not the empty list we go through each unique member of `a` in sorted order, print it and remove a copy of that character from the list.

Each iteration prints thus prints one copy of each character present in `a`.

# Answer
> 7 votes
## Haskell, 44 bytes

```
import Data.List
concat.transpose.group.sort

```

Usage example:

```
Prelude Data.List> concat.transpose.group.sort $ "If you sort a string you'll typically get something like:"
" ':Iacefghiklmnoprstuy aegilnorstuy egilosty iloty lt    "

```

Sort, group equal chars to a list of strings (e.g. `"aabbc"` -\> `["aa","bb","c"]`), transpose and flatten into a single string, again.

# Answer
> 6 votes
# Python 2, 75 bytes

```
lambda s:`zip(*sorted((s[:i].count(c),c)for i,c in enumerate(s)))[1]`[2::5]

```

Try it online!

# Answer
> 5 votes
# APL (Dyalog Unicode), ~~21~~ 20 bytes

```
t[0~⍨∊⍉(⊂⍋∪t)⌷⊢⌸t←⍞]

```

Try it online!

`t[`...`]` index *t* (to be defined shortly) with...

`0~⍨` zeros removed from

the enlisted (flattened)

transposed

`(⊂``)⌷` reordered using…

the indices which would sort

the unique letters of

`t`*t* (to be defined shortly)

`⊢⌸t` keyed\* *t*, which has the value of

prompted text input

TryAPL online!

---

`⊢⌸t` creates a table where the rows (padded with zeros for a rectangular table) list each unique letters' indices in *t*.

# Answer
> 4 votes
# C, ~~109~~ ~~106~~ ~~105~~ ~~104~~ ~~102~~ ~~100~~ ~~97~~ ~~98~~ ~~96~~ 91 Bytes

~~Back up to 98 Bytes, needed to initialize j to make f(n) re-useable~~

~~Down to 96 Bytes using puts in place of strlen B-)~~

It's strange I had to back to strlen but I got rid of the for(;i++;) loop so now it's down to 91 Bytes. Apparently the man page for puts reads;

```
"RETURNS
   If successful, the result is a nonnegative integer; otherwise, the result is `EOF'."

```

... I was lucky it was working in the first place

```
char*c,i,j;f(m){for(j=strlen(m);j;++i)for(c=m;*c;c++)if(*c==i){*c=7,putchar(i),j--;break;}}

```

test code...

```
main(c,v)char**v;
{
    char test[] = "If you sort a string you'll typically get something like: ";
    char test2[] = "Hello, World!";

    f(test);puts("");
    f(test2);puts("");
}

```

Here are a few test cases, now it's time to golf this down

```
C:\eng\golf>a.exe
 ':Iacefghiklmnoprstuy aegilnorstuy egilosty iloty lt
 !,HWdelorlo

```

# Answer
> 4 votes
# Mathematica, ~~68~~ ~~60~~ 59 bytes

```
Split[Characters@#~SortBy~ToCharacterCode]~Flatten~{2}<>""&

```

Accepts a String. Outputs a String.

**If list of characters were allowed (46 bytes):**

```
Split[#~SortBy~ToCharacterCode]~Flatten~{2,1}&

```

**Version using `Sort` (40 bytes):**

```
Split@Sort@Characters@#~Flatten~{2}<>""&

```

This version cannot be my answer because `Sort` cannot be used here; `Sort` sorts by canonical order, not by character code.

# Answer
> 3 votes
## JavaScript (ES6), 79 bytes

```
f=s=>s&&(a=[...new Set(s)]).sort().join``+f(a.reduce((s,e)=>s.replace(e,``),s))
```

```
<input oninput=o.textContent=f(this.value)><pre id=o>
```

Works by extracting the set of unique characters, sorting it, removing them from the original string, and recursively calculating the sort of the rest of the string. 81 byte solution that I found interesting:

```
f=s=>s&&(s=[...s].sort().join``).replace(r=/(.)(\1*)/g,"$1")+f(s.replace(r,"$2"))

```

# Answer
> 3 votes
# Python 2, ~~77~~ 76 bytes

```
d={}
def f(c):d[c]=r=d.get(c,c),;return r
print`sorted(input(),key=f)`[2::5]

```

Takes a quoted string as input from stdin.

Try it online!

# Answer
> 3 votes
## , ~~16~~ 15 bytes

```
/:+/@(={:)\;"0]

```

This is a verb that takes and returns one string. Try it online!

Miles saved a byte, thanks!

## Explanation

Nothing too fancy here: sort primarily by order of occurrence, secondarily by char value.

```
/:+/@(={:)\;"0]  Input is y.
          \      Map over prefixes:
  +/              Sum
    @(   )        of
      =           bit-array of equality
       {:         with last element.
                 This gives an array of integers whose i'th element is k
                 if index i is the k'th occurrence of y[i].
           ;     Pair this array
            "0   element-wise
              ]  with y
/:               and sort y using it as key.

```

# Answer
> 2 votes
# Brainf\*ck, ~~458~~ 226 bytes

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

```

Try it online! - BF

# Numberwang, ~~262~~ 226 bytes

```
8400000087111111442111911170004000400000071114002241202271214020914070419027114170270034427171114400000091111112711170000007000400040000007111400224120227121402091407041902711417027004219190071420091171411111170007000771111117

```

Try it online! - NW

I put both of these here because they are identical code.

# Answer
> 2 votes
# PHP, 83 bytes

```
for($s=count_chars($argv[1]);$s=array_filter($s);$c%=128)echo$s[++$c]--?chr($c):'';

```

Unfortunately you can't have `unset` in a ternary so I need to use the annoyingly long `array_filter`.
Use like:

```
php -r "for($s=count_chars($argv[1]);$s=array_filter($s);$c%=128)echo$s[++$c]--?chr($c):'';" "If you sort a string you'll typically get something like:"

```

# Answer
> 2 votes
# , ~~37~~ 36 bytes

Thanks @DJMcMayhem for the byte!

```
Í./&ò
dd:sor
Íî
òÍ¨.©¨±«©±À!¨.«©/±³²

```

Try it online!

Not sure I like the regex at the end, but I needed to make the `ò` break somehow.

### Explain

```
Í./&ò                    #All chars on their own line
dd:sor                   #Delete empty line, sort chars
Íî                       #Join all lines together s/\n//
òÍ¨.©¨±«©±À!¨.«©/±³² #until breaking s/\v(.)(\1+)\1@!(.+)/\3\2\1

```

# Answer
> 2 votes
## Python 2, 70 bytes

```
f=lambda s,i=0,c='':s[i>>7:]and(s.count(c)>i>>7)*c+f(s,i+1,chr(i%128))

```

Try it online

This is very inefficient. The test link changes the `i>>7` to `i>>5` and sets the recursion limit to 10000. Assumes the inputs only has ASCII values up to 126.

Uses the div-mod trick to iterate through two loops: minimum counts `i/128` in the outer loop and ASCII values `i%128` in the inner loop. Includes a character `c` with the given ASCII value if the number of times it appears in the string is at least its minimum count.

The code uses a trick to simulate the assignment `c=chr(i%128)` so that it can be referenced in the expression `(s.count(c)>i>>7)*c`. Python `lambda`s do not allow assignment because they only take expressions. Converting to a `def` or full program is still a net loss here.

Instead, the function pushes forward the value `chr(i%128)` to the next recursive call as an optional input. This is off by one because `i` has been incremented, but doesn't matter as long as the string doesn't contain special character `'\x7f'` (we could also raise 128 to 256). The initial `c=''` is harmless.

# Answer
> 2 votes
# Vyxal `d`, 3 bytes

```
sĠ∩

```

Try it Online!

```
s   # Sort
 Ġ  # Group run lengths
  ∩ # Transpose
    # (d flag) take deep sum

```

# Answer
> 1 votes
# Perl 6, 68 bytes

```
{my \a=.comb.sort;[~] flat roundrobin |a.squish.map({grep *eq$_,a})}

```

I was a little surprised to find that there's no built-in way to group like elements in a list. That's what the squish-map bit does.

# Answer
> 1 votes
# JavaScript (ES6), ~~77~~ 75 bytes

```
s=>(a=[],x={},[...s].sort().map(c=>a[x[c]=n=-~x[c]]=(a[n]||'')+c),a).join``

```

Stable sorts the lexicographically sorted string by nth occurence

```
F=s=>(a=[],x={},[...s].sort().map(c=>a[x[c]=n=-~x[c]]=(a[n]||'')+c),a).join``

const update = () => {
  console.clear();
  console.log(F(input.value));
};
input.oninput = update;
update();
```

```
#input {
  width: 100%;
  box-sizing: border-box;
}
```

```
<input id="input" type="text" value="         ':Iaaceeefggghiiiiklllllmnnooooprrssstttttuuyyyy" length=99/>
<div id="output"></div>
```

# Answer
> 1 votes
# FSharp, ~~194~~ ~~190~~ ~~170~~ ~~140~~ 133 bytes

```
let f=Seq.map
let(@)=(>>)
f int@Seq.groupBy id@f(snd@Seq.mapi((*)128@(+)))@Seq.concat@Seq.sort@f((%)@(|>)128@byte)@Array.ofSeq@f char

```

Using Seq instead of Array saves a couple of bytes

Defining a shorter name, and using another maps to avoid a `(fun ->)` block

It turns out F# can map a char to an in, so removing the shortened name of System.Text.Encoding.ASCII, and adding in another map saves me 20 bytes!

Returning a char array instead of a string, saves me 30 bytes!

I no longer need to make sure it's a string, saves me 7 bytes

# Answer
> 1 votes
# Perl 6, 54 bytes

```
{[~] flat roundrobin |.comb.classify(~*){*}.sort»[*]}

```

Explanation:

* `{ }`: A lambda that takes one argument -- e.g. `21211`.
* `.comb`: Split the input argument into a list of characters -- e.g. `(2,1,2,1,1)`.
* `.classify(~*)`: Group the characters using string comparison as the grouping condition, returning an unordered Hash -- e.g. `{ 2=>[2,2], 1=>[1,1,1] }`.
* `{*}`: Return a list of all values of the Hash -- e.g. `[2,2], [1,1,1]`.
* `.sort`: Sort it -- e.g. `[1,1,1], [2,2]`.
* `»[*]`: Strip the item containers the arrays were wrapped in due to being in the hash, so that they won't be considered as a single item in the following step -- e.g. `(1,1,1), (2,2)`.
* `roundrobin |`: Zip the sub-lists until all are exhausted -- e.g. `(1,2), (1,2), (1)`.
* `flat`: Flatten the result -- e.g. `1, 2, 1, 2, 1`.
* `[~]`: Concatenate it to get a string again -- e.g. `12121`.

(Credit for the `roundrobin` approach goes to Sean's answer.)

# Answer
> 1 votes
# 05AB1E, 15 bytes

```
{.¡"ä"©¹g×«øJ®K

```

Try it online! or as a Test suite

**Explanation**

```
{                # sort input
 .¡              # group by equal elements
   "ä"©          # push "ä" and store a copy in the register
       ¹g×       # repeat the "ä" input-nr times
          «      # concatenate the result to each string in the grouped input
           ø     # zip
            J    # join to string
             ®K  # remove all instances of "ä" in the string

```

10 of the 15 bytes are for getting around 05AB1E's way of handling zipping strings of different length.

# Answer
> 1 votes
# Husk, 4 bytes

```
ΣTgO

```

Try it online!

## Explanation

```
ΣTgO
   O Order
  g  group
 T   Transpose
Σ    join

```

# Answer
> 1 votes
# JavaScript (Node.js), 71 bytes

```
f=x=>x&&[...x].filter(k=c=>k[c]?![h+=c]:k[c]=1,h='').sort().join``+f(h)

```

Try it online!

# Answer
> 1 votes
# Japt `-P`, 4 bytes

Input as a character array, output as a string.

```
ü Õc

```

Try it

```
ü Õc     :Implicit input of character array
ü        :Group & sort
  Õ      :Transpose
   c     :Flatten
         :Implicitly join & output

```

# Answer
> 0 votes
# JavaScript (ES6), 114 bytes

Separated with newline for clarity, not part of byte count:

```
s=>[...s].map(a=>(m[a]=-~m[a])*128+a.charCodeAt(),m={})
.sort((a,b)=>a-b).map(a=>String.fromCharCode(a%128)).join``

```

## Demo

```
`**Test cases:**
 *:Tacest*es*s*

If you sort a string you'll typically get something like:
 ':Iacefghiklmnoprstuy aegilnorstuy egilosty iloty lt

Hello, World!
 !,HWdelorlol

#MATLAB, 114 bytes
 #,14ABLMTbesty 1A

f=@(s)[mod(sort(cell2mat(cellfun(@(c)c+128*(0:nnz(c)-1),mat2cell(sort(s),1,histc(s,unique(s))),'un',0))),128),''];
'()*+,-0128:;=@[]acdefhilmnoqrstuz'(),0128@acefilmnorstu'(),12celmnostu'(),12celnstu(),clnst(),cls(),cs(),()()()()`.split`\n\n`.map(s=>(p=s.split`\n`,console.log(`${p[0]}\n\n${r=f(p[0])}\n\nmatch: ${r==p[1]}`)),
f=s=>[...s].map(a=>(m[a]=-~m[a])*128+a.charCodeAt(),m={}).sort((a,b)=>a-b).map(a=>String.fromCharCode(a%128)).join``)
```

# Answer
> 0 votes
## Clojure, 79 bytes

```
#(for[V[(group-by(fn[s]s)%)]i(range 1e9)k(sort(keys V))c[(get(V k)i)]:when c]c)

```

An anonymous function, returns a sequence of characters. Supports up-to 10^9 repetitions of any characters, which should be plenty.

# Answer
> 0 votes
## Retina, 24 bytes

```
O`.
O$#`(.)(?=(\1)*)
$#2

```

Try it online!

# Answer
> 0 votes
# Ruby, 59+1 = 60 bytes

Adds one byte for the `-n` flag. Port of @PatrickRoberts' dictionary solution.

```
d={};print *$_.chars.sort_by{|c|d[c]||=0;c.ord+128*d[c]+=1}

```

# Answer
> 0 votes
# BQN, 6 bytesSBCS

```
∾·⊒⊸⊔∧

```

Run online!

sort, group by occurrence count, join.

# Answer
> 0 votes
# Factor \+ `grouping.extras`, 48 bytes

```
[ natural-sort [ ] group-by values round-robin ]

```

Attempt This Online!

* `natural-sort` Sort the input
* `[ ] group-by values` Group like contiguous elements, e.g. `"aabbc"` -\> `{ "aa" "bb" "c" }`
* `round-robin` One from each group in order, until there are no elements left. e.g. `{ "aa" "bb" "c" }` -\> `"abcab"`

---
Tags: code-golf, string, sorting
---