title: Compute minimax of an array

text:
# Question
Title: Compute minimax of an array
Consider an array `x` such as `[1 5 3 4]` and a number `n`, for example `2`. Write all length-`n` sliding subarrays: `[1 5]`, `[5 3]`, `[3 4]`. Let the *minimax* of the array be defined as the minimum of the maxima of the sliding blocks. So in this case it would be the minimum of `5, 5, 4`, which is `4`.

## Challenge

Given an array `x` and a positive integer `n`, output the minimax as defined above.

The array `x` will only contain positive integers. `n` will always be at least `1` and at most the length of `x`.

Computation may be done by any procedure, not necessarily as defined above.

Code golf, fewest bytes wins.

## Test cases

`x`, `n`, result

```
[1 5 3 4], 2                    4
[1 2 3 4 5], 3                  3
[1 1 1 1 5], 4                  1
[5 42 3 23], 3                 42

```

# Answer
> 21 votes
# Dyalog APL, 4 bytes

```
⌊/⌈/

```

This is a monadic function train that expects array and integer as right and left arguments, resp.

Try it with TryAPL.

### How it works

A train of two functions is an *atop*, meaning that the right one is called first (with both arguments), then the left one is called on top of it (with the result as sole argument).

A monadic `f/` simply reduces its argument by `f`. However, if called dyadically, `f/` is n-wise reduce, and takes the slice size as its left argument.

```
⌊/⌈/    Monadic function. Right argument: A (array). Left argument: n (list)

  ⌈/    N-wise reduce A by maximum, using slices of length n.
⌊/      Reduce the maxima by minimum.

```

# Answer
> 8 votes
## CJam (11 bytes)

```
{ew::e>:e<}

```

Online demo

# Answer
> 6 votes
# Ruby 39 bytes

```
->(x,n){x.each_slice(n).map(&:max).min}

```

Where x is the array and n is the number to chunk the array by.

# Answer
> 4 votes
# Oracle SQL 11.2, 261 bytes

```
SELECT MIN(m)FROM(SELECT MAX(a)OVER(ORDER BY i ROWS BETWEEN CURRENT ROW AND :2-1 FOLLOWING)m,SUM(1)OVER(ORDER BY i ROWS BETWEEN CURRENT ROW AND:2-1 FOLLOWING)c FROM(SELECT TRIM(COLUMN_VALUE)a,rownum i FROM XMLTABLE(('"'||REPLACE(:1,' ','","')||'"'))))WHERE:2=c;

```

Un-golfed

```
SELECT MIN(m)
FROM   (
         SELECT MAX(a)OVER(ORDER BY i ROWS BETWEEN CURRENT ROW AND :2-1 FOLLOWING)m,
                SUM(1)OVER(ORDER BY i ROWS BETWEEN CURRENT ROW AND :2-1 FOLLOWING)c
         FROM   (
                  SELECT TRIM(COLUMN_VALUE)a,rownum i
                  FROM XMLTABLE(('"'||REPLACE(:1,' ','","')||'"'))
                )
       )
WHERE :2=c;

```

# Answer
> 3 votes
# MATL, 6 bytes

```
YCX>X<

```

**Try it online!**

```
YC    % Implicitly input array and number. Build a matrix with columns formed
      % by sliding blocks of the array with size given by the number
X>    % Maximum of each column
X<    % Minimum of all maxima. Implicitly display

```

# Answer
> 3 votes
## Pyth, 10 bytes

```
hSmeSd.:QE

```

Explanation:

```
           - autoassign Q = eval(input())
      .:QE -   sublists(Q, eval(input())) - all sublists of Q of length num
  meSd     -  [sorted(d)[-1] for d in ^]
hS         - sorted(^)[0]

```

Takes input in the form `list newline int`

Try it here!

Or run a Test Suite!

### Or also 10 bytes

```
hSeCSR.:EE

```

Explanation:

```
      .:EE -    sublists(Q, eval(input())) - all sublists of Q of length num
    SR     -   map(sorted, ^)
  eC       -  transpose(^)[-1]
hS         - sorted(^)[0]

```

Test Suite here

# Answer
> 3 votes
# Jelly, 6 bytes

```
ṡ»/€«/

```

Try it online!

### How it works

```
ṡ»/€«/  Main link. Left input: A (list). Right input: n (integer)

ṡ       Split A into overlapping slices of length n.
 »/€    Reduce each slice by maximum.
    «/  Reduce the maxima by minimum.

```

# Answer
> 3 votes
# JavaScript (ES6), ~~84~~ ~~83~~ 72 bytes

```
(x,y)=>Math.min(...x.slice(y-1).map((a,i)=>Math.max(...x.slice(i,i+y))))

```

Thanks to user81655 for helping shave off 11 bytes

# Answer
> 3 votes
# Julia 0.6, 51 bytes

```
f(x,n)=min([max(x[i-n+1:i]...)for i=n:endof(x)]...)

```

Try it online!

Nothing too groundbreaking. This is a function that accepts an array and an integer and returns an integer. It just uses the basic algorithm. It would be a whole lot shorter if `min` and `max` didn't require splatting arrays into arguments.

We get each overlapping subarray, take the max, and take the min of the result.

# Answer
> 3 votes
# Perl 6, 32 bytes

```
{@^a.rotor($^b=>1-$b)».max.min}

```

### Usage:

```
my &minimax = {@^a.rotor($^b=>1-$b)».max.min}

say minimax [1,5,3,4], 2;    # 4
say minimax [1,2,3,4,5], 3;  # 3
say minimax [1,1,1,1,5], 4;  # 1
say minimax [5,42,3,23], 3;  # 42

```

# Answer
> 3 votes
# R, ~~41~~ 35 bytes

Requires zoo to be installed.

```
function(x,n)min(zoo::rollmax(x,n))

```

*edit* \- 6 bytes by realizing `zoo::rollmax` exists!

# Answer
> 3 votes
# Vyxal, 4 bytes

```
lvGg

```

Try it Online!

Why reduce by things when you can just vectorise.

## Explained

```
lvGg
l    # overlaps of input list of size input integer.
 vG  # maximum of each window
   g # minimum of that

```

# Answer
> 3 votes
# Husk, 4 bytes

```
▼m▲X

```

Try it online!

### Explanation

```
▼m▲X
   X  each consecutive slice of length
 m▲   maximum of each
▼     minimum

```

# Answer
> 3 votes
# Jelly, 4 bytes

```
ṡṀ€Ṃ

```

Try it online!

Since Dennis' answer, the aximum and inimum monadic atoms have been added

# Answer
> 2 votes
# Python 3, 55 bytes.

```
lambda x,n:min(max(x[b:b+n])for b in range(len(x)-n+1))

```

Test cases:

```
assert f([1, 5, 3, 4], 2) == 4
assert f([1, 2, 3, 4, 5], 3) == 3
assert f([1, 1, 1, 1, 5], 4) == 1
assert f([5, 42, 3, 23], 3 ) == 42

```

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

```
f=lambda l,n:l[n-1:]and min(max(l[:n]),f(l[1:],n))

```

Recursively computes the minimum of two things: the max of the first `n` entries, and the recursive function on the list with first element removed. For a base case of the list having fewer than `n` elements, gives the empty list, which serves as infinity because Python 2 puts lists as greater than numbers.

# Answer
> 2 votes
# Mathematica, 23 bytes

```
Min@BlockMap[Max,##,1]&

```

**Test case**

```
%[{1,2,3,4,5},3]
(* 3 *)

```

# Answer
> 2 votes
# Java 8, ~~128~~ ~~126~~ ~~124~~ 105 bytes

```
a->n->{int r=0,m,j,t,i=-1;for(;i++<a.length-n;r=r<1|m<r?m:r)for(m=j=0;j<n;m=t>m?t:m)t=a[i+j++];return r;}

```

Try it online.

**Explanation:**

```
a->n->{                    // Method with Integer-array & Integer as parameters
                           // and Integer return-type
  int r=0,                 //  Result-integer, starting at 0
      m,                   //  Max-integer, uninitialized
      j,t,                 //  Temp integers
  i=-1;for(;i++<a.length-n //  Loop `i` in the range (-1,length-n]:
           ;               //    After every iteration:
            r=             //     Change the result to:
              r<1          //      If the result is 0 (first iteration),
              |m<r?        //      or the max is smaller than the result:
                m          //       Change the result to this max
              :            //      Else:
               r)          //       Keep it unchanged
    for(m=                 //   Reset the max to 0
        j=0;j<n            //   Inner loop `j` in the range [0,n):
        ;                  //     After every iteration:
         m=t>m?t:m)        //      Set `m` to the max of `m` and `t`
      t=a[i+j++];          //    Set `t` to the `i+j`'th item of the array
  return r;}               //  After the nested loops, return the result

```

# Answer
> 2 votes
# J, 9 bytes

```
[:<./>./\

```

Similar to the APL answer. `>./\` applies `>./` (maximum) to the (left arg)-subsets of the right arg. Then, `<./` finds the minimum of that, since it's capped with `[:`.

## Test cases

```
   f =: [:<./>./\
   2 f 1 5 3 4
4
   3 f 1 2 3 4 5
3
   3 f 1 1 1 1 5
1
   3 f 5 42 3 23
42

```

# Answer
> 2 votes
# Factor, 34 bytes

```
[ clump [ supremum ] map infimum ]

```

Try it online!

## Explanation

```
                  ! { 1 5 3 4 } 2
clump             ! { { 1 5 } { 5 3 } { 3 4 } }
[ supremum ] map  ! { 5 5 4 }
infimum           ! 4

```

# Answer
> 2 votes
# 05AB1E, 6 bytes

```
ŒIù€àß

```

Try it online or verify all test cases.

**Explanation:**

```
Œ       # Get all sublists of the (implicit) input-list
 Iù     # Only keep those of a size equal to the second input
   €à   # Get the maximum of each inner list
     ß  # Pop and push the minimum of that
        # (after which the result is output implicitly)

```

# Answer
> 2 votes
# Rust, 46 bytes

```
|s,n|s.windows(n).map(|a|a.iter().max()).min()

```

Try it online!

Takes in a `&[u32]` and returns an `Option<Option<&u32>>`. The result will be `Some(Some(&minimax))` so long as valid input is supplied.

# Answer
> 2 votes
# Burlesque, 7 bytes

```
CO)>]<]

```

Try it online!

```
CO  # Sliding window length N
)>] # Map max of block
<]  # Min of result

```

# Answer
> 2 votes
# Julia 1.0, 48 bytes

```
x\n=minimum(n:length(x).|>i->max(x[i-n+1:i]...))

```

Try it online!

based on Alex A.'s answer

# Answer
> 1 votes
# JavaScript (ES6), 70 bytes

```
x=>n=>-M(...x.slice(n-1).map((_,i)=>-M(...x.slice(i,i+n)))),M=Math.max

```

Using currying, this function saves 2 bytes from the previous answer.

## Demo

```
f=x=>n=>-M(...x.slice(n-1).map((_,i)=>-M(...x.slice(i,i+n)))),M=Math.max
a=[[[1,5,3,4],2,4],[[1,2,3,4,5],3,3],[[1,1,1,1,5],4,1],[[5,42,3,23],3,42]]
document.write(`<pre>${a.map(r=>`${f(r[0])(r[1])==r[2]?'PASS':'FAIL'} ${r[1]}=>${r[2]}`).join`\n`}`)
```

# Answer
> 1 votes
## Racket 84 bytes

```
(λ(l i)(apply min(for/list((j(-(length l)(- i 1))))(apply max(take(drop l j) i)))))

```

Ungolfed:

```
(define f
  (λ (l i)
    (apply min (for/list ((j (- (length l)
                                (- i 1))))
                 (apply max (take (drop l j) i))
                 ))))

```

Testing:

```
(f '[1 5 3 4]  2)
(f '[1 2 3 4 5] 3)
(f '[5 42 3 23] 3)

```

Output:

```
4
3
42

```

# Answer
> 1 votes
## Clojure, 51 bytes

```
#(apply min(for[p(partition %2 1 %)](apply max p)))

```

# Answer
> 1 votes
# SmileBASIC, 68 bytes

```
M=MAX(X)DIM T[N]FOR I=.TO LEN(X)-N-1COPY T,X,I,N
M=MIN(M,MAX(T))NEXT

```

Nothing special here. Inputs are `X[]` and `N`

# Answer
> 1 votes
# T-SQL, 131 bytes

```
SELECT top 1max(iif(a<c,c,a))FROM x y
CROSS APPLY(SELECT a c FROM x WHERE y.b<b and b<y.b+@)z
GROUP BY b
HAVING-@=~sum(1)ORDER BY 1

```

**Try it online**

# Answer
> 1 votes
# , 64 bytes

```
function(x,n)min(apply(matrix(x,l<-sum(x|1)+1,n)[n:l-n,],1,max))

```

Try it online!

Answer without using `zoo`.

# Answer
> 1 votes
# K (ngn/k), 6 bytes

```
&/|/':

```

Try it online!

Similar to @Dennis' APL answer, adapted to ngn/k.

* `|/':` set up a stencil `i f':x`, taking the stencil/window length as the left arg (`i`) and the list input as the right arg (`x`). to each window, apply `|/`, i.e. the maximum
* `&/` take the minimum of the maximums

# Answer
> 1 votes
# Arturo, 48 bytes

```
$[a,n][min map 0..-size a n'x->max a\[x..x+n-1]]

```

Try it

---
Tags: code-golf, number, array
---


title: A randomly colored walk

text:
# Question
Title: A randomly colored walk
Given two inputs, a distance \\$d\\$ and a number \\$n\\$ output a list of \\$n\\$ random colors which each have distance \\$d\\$ from the previous.

## Background

A random walk is a path which is defined by choosing a random direction and (usually) fixed distance to go at each step. We will be taking a random walk through the RGB color space using Euclidean distance as our metric.

## The challenge

For this challenge you will take two inputs, \\$n\\$ and \\$d\\$. Let \\$n\\$ be the number of colors to output, this will always be an integer \\$1 \leq n\\$, and \\$d\\$ be the distance between consecutive elements, which will always be \\$0 \leq d \leq 128\\$. You may additionally assume that \\$d\\$ is an integer.

For each consecutive pair of elements \\$(r\_1, g\_1, b\_1), (r\_2, g\_2, b\_2)\\$ of the \\$n\\$ element sequence output, it must be the case that all values are between 0 and 255 inclusive (or \\$\[0,256)\\$ for floats), and the distance between elements must be within 1 of d, that is \\$|\sqrt{(r\_1-r\_2)^2+(g\_1-g\_2)^2+(b\_1-b\_2)^2} - d| \< 1\\$. This should allow one to restrict their output to integers if they so choose. The walk need not be uniform, but it does need to be random. Specifically, there should be a non-zero chance of each step going in any direction which stays in bounds (within a distance 1 error tolerance). The starting point of the walk should be random as well.

Standard i/o rules apply, input and output can be in any reasonable format. Graphical output is allowed (and encouraged, though I doubt it will be golfy to do so) so long as the order of the sequence is clear.

This is , so the shortest answer in bytes wins.

## Test cases

For these test cases input is in the order \\$n,d\\$ and output is (r, g, b) as integers. These are some possible results.

```
5, 5 -> (81, 60, 243), (81, 57, 239), (76, 60, 240), (80, 62, 241), (84, 60, 243)
4, 10 -> (163, 89, 77), (162, 83, 85), (166, 75, 79), (166, 82, 87)
4, 50 -> (212, 36, 232), (247, 1, 239), (220, 44, 243), (217, 81, 209)

```

# Answer
> 8 votes
# Wolfram Language (Mathematica), 96 bytes

```
(d=#2;r={0,255};NestList[⌊RandomPoint[Sphere[#,d],1,{r,r,r}][[1]]⌋&,RandomInteger[r,3],#1])&

```

Try it online!

Graphical output is possible with Mathematica desktop. If the above function named `g`:

And just for fun:

# Answer
> 5 votes
# JavaScript (V8), 105 bytes

Expects `(n)(d)`. Prints tuples of 3 floats.

```
n=>d=>{for(b=[m=Math,0,0];~~(m.hypot(...b.map((v,i)=>v-=a[i]=m.random()*256,a=[]))-d)||print(b=a)|--n;);}

```

Try it online!

### Graphical output

This snippet generates a graphical rendering of `f(4)(50)`.

```
f=
n=>d=>{for(b=[m=Math,0,0];~~(m.hypot(...b.map((v,i)=>v-=a[i]=m.random()*256,a=[]))-d)||print(b=a)|--n;);}

i = 0; print = ([r, g, b]) => document.getElementsByTagName("div")[i++].style.backgroundColor = `rgb(${r},${g},${b})`; f(4)(50)
```

```
div { float: left; width: 32px; height: 32px; margin-right: 8px; }
```

```
<div></div><div></div><div></div><div></div>
```

### Commented

```
n =>                     // outer function taking n
d => {                   // inner function taking d
  for(                   // main loop:
    b = [                //   initialize b[]:
      m = Math,          //     m = alias for Math
      0,                 //     by inserting this NaN'ish value into
      0                  //     the initial b[], we force the first
    ];                   //     random RGB tuple to be accepted
    ~~(                  //   force to integer:
      m.hypot(...        //     compute the Euclidean distance:
        b.map((v, i) =>  //       for each value v at index i in b[]:
          v -=           //         subtract a[i] from v
            a[i] =       //         where a[i] is set to
              m.random() //         a random float in [0, 256[
              * 256,     //
          a = []         //         start with a[] = []
        )                //       end of map()
      ) - d              //     subtract d from the Euclidean distance
    ) ||                 //   if the result is within ]-1,1[:
      print(b = a)       //     print a[], update b[] to a[]
      | --n;             //     and decrement n (stop if it's 0)
  );                     // end of loop
}                        //

```

# Answer
> 3 votes
# Python, ~~123~~ ~~107~~ ~~111~~ 108 bytes

*-16 bytes from @xnor by using math.dist
+4 bytes from @Arnauld from correctly meeting the spec
-3 bytes from @The Thonnu*

```
import os,math
def f(n,d,r=os.urandom):
 X=r(3)
 while n:
  if-1<math.dist(x:=r(3),X)-d<1:print(*x);X=x;n-=1

```

Attempt This Online!

# Answer
> 3 votes
# Charcoal, 44 bytes

```
ＮθＮηＷ⊙Φ⊟Ｅθ⊞ＯυＥ³‽²⁵⁶λ‹¹↔⁻η₂ΣＥκＸ⁻μ§§υλν²≔⟦⟧υＩυ

```

Attempt This Online! Link is to verbose version of code. Explanation: Simply generates `n` sets of random colours until it finds a set that meets the distance criterion, which it then outputs.

Although that algorithm finishes with 100% probability, it's inordinately slow and unusable for `n>3`, so here's a 52-byte alternative program that randomly generates each colour in turn until it finds one that meets the distance criterion:

```
ＮθＮηＷ‹Ｌυθ«⊞υＥ³‽²⁵⁶¿∧⊖Ｌυ‹¹↔⁻η₂ΣＥ§υ±²Ｘ⁻κ§§υ±¹λ²≔⊟υι»Ｉυ

```

Attempt This Online! Link is to verbose version of code.

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


title: At least h with at least h

text:
# Question
Title: At least h with at least h
# Input

A list of nonnegative integers.

# Output

The largest nonnegative integer `h` such that at least `h` of the numbers in the list are greater than or equal to `h`.

# Test Cases

```
[0,0,0,0] -> 0
[12,312,33,12] -> 4
[1,2,3,4,5,6,7] -> 4
[22,33,1,2,4] -> 3
[1000,2,2,2] -> 2
[23,42,12,92,39,46,23,56,31,12,43,23,54,23,56,73,35,73,42,12,10,15,35,23,12,42] -> 20

```

# Rules

You can write either a full program or a function, and anonymous functions are allowed too. This is code-golf, so the fewest byte count wins. Standard loopholes are disallowed.

# Background

The h-index is a notion used in academia which aims to capture the impact and productivity of a researcher. According to Wikipedia, a researcher has index *h*, if he or she has published *h* scientific articles, each of which has been cited in other articles at least *h* times. Thus, this challenge is about computing the h-index from a list of citation counts.

---

# Update

Wow, great answers all round! I have accepted the shortest one, but if someone else comes up with an even shorter one, I'll update my choice accordingly.

# Winners by language

Here's a table of winners by language that I'll also try to keep up to date. I have included all posts with nonnegative score. Please correct me if I have made a mistake here.

* **APL**: 7 bytes by @MorisZucca
* **Bash + coreutils**: 29 bytes by @DigitalTrauma
* **C#**: 103 bytes by @LegionMammal978
* **C++**: 219 bytes by @user9587
* **CJam**: 15 bytes by @nutki
* **GolfScript**: 13 bytes by @IlmariKaronen
* **Haskell**: 40 bytes by @proudhaskeller
* **J**: 12 bytes by @ɐɔıʇǝɥʇuʎs
* **Java**: 107 bytes by @Ypnypn
* **JavaScript**: 48 bytes by @edc65
* **Mathematica**: 38 bytes by @kukac67
* **Perl**: 32 bytes by @nutki
* **Pyth**: 10 bytes by @isaacg
* **Python**: 49 bytes by @feersum
* **R**: 29 bytes by @MickyT
* **Ruby**: 41 bytes by @daniero
* **Scala**: 62 bytes by @ChadRetz
* **SQL**: 83 bytes by @MickyT
* **TI-BASIC**: 22 bytes by @Timtech

# Answer
> 8 votes
**APL 7**

```
+/⊢≥⍋∘⍒

```

Can be tried online on tryapl.org

```
f←+/⊢≥⍋∘⍒
f¨(4⍴0)(12 312 33 12)(⍳7)(22 33 1 2 4)(1000 2 2 2)(23 42 12 92 39 46 23 56 31 12 43 23 54 23 56 73 35 73 42 12 10 15 35 23 12 42)
0 4 4 3 2 20

```

# Answer
> 12 votes
# Python 2, 49

Input should be typed in the same format as the examples.

```
i=0
for z in sorted(input())[::-1]:i+=z>i
print i

```

# Answer
> 11 votes
# Python, 52

```
f=lambda s,n=0:n<sum(n<x for x in s)and f(s,n+1)or n

```

A recursive solution. Run this in Stackless Python if you're worried about overflows.

Starting from `n=0`, checks whether at least `n+1` of the numbers are at least `n+1`. If so, increments `n` and starts again. If not, outputs `n`.

The conditional is done using Python's short-circuiting for Booleans. The expression `sum(n<x for x in s)` counts the number of values in `s` that are greater than `n` by adding the indicator Booleans, which are treated as `0` or `1`.

For comparison, the iterative equivalent is 2 chars longer. It requires Python 2.

```
s=input()
n=0
while n<sum(n<x for x in s):n+=1
print n

```

Unfortunately, the input need to be saved for a variable before being iterated over or else Python will try to read the input repeatedly.

# Answer
> 11 votes
# Pyth, ~~13~~ 10 bytes

```
tf<l-QUTT1

```

Input in a form such as `[22,33,1,2,4]` on STDIN.

Try it here.

How it works:

`-QUT` is all of the numbers in the input (`Q`) at least as large as the number being checked, `T`.

`<l-QUTT` is true if the the length of that list is less than `T`.

`f<l-QUTT1` finds the first integer which returns true for the inner check, starting at `1` and going up.

`tf<l-QUTT1` decrements that by one, giving the largest value for which the condition is false, which is the h-index.

Starting at 1 ensures that `0` is returned when the test is always true, such as in the first test case.

# Answer
> 9 votes
# CJam, 15 bytes

Direct translation of my Perl solution.

```
l~{~}${W):W>},,

```

# Answer
> 6 votes
# J (~~13~~ 12)

```
[:+/i.@#<\:~

```

Pretty similar to randomra's solution. Demonstration:

```
   f=:[:+/i.@:#<\:~
   f 0,0,0,0
0
   f 12,312,33,12
4
   f 1,2,3,4,5,6,7
4
   f 22,33,1,2,4
3
   f 1000,2,2,2
2
   f 23,42,12,92,39,46,23,56,31,12,43,23,54,23,56,73,35,73,42,12,10,15,35,23,12,42
20

```

# Answer
> 5 votes
# Mathematica, 44 42 40 38 bytes

Anonymous function:

```
LengthWhile[i=0;SortBy[#,-#&],#>i++&]&

```

Run it by tacking the input on to the end like so:

```
In: LengthWhile[i=0;SortBy[#,-#&],#>i++&]&@{1,2,3,4,5,6,7}
Out: 4

```

# Answer
> 4 votes
## SQL, ~~81~~ ~~94~~ 83

Given a table (I) of values (V), the following query will return h. Tested in PostgreSQL and will also work in SQL Server. **Edit** Make it return 0 rather than NULL. Made better with a COUNT, thanks @nutki

```
SELECT COUNT(R)FROM(SELECT ROW_NUMBER()OVER(ORDER BY V DESC)R,V FROM I)A WHERE R<=V

```

SQLFiddle example

Essentially it numbers the rows on a descending sort of the values. Then it returns the maximum row number where the row number is greater than equal to the value.

# Answer
> 4 votes
## R, ~~39~~ ~~35~~ 29

```
s=sort(i);sum(s>=length(s):1)

```

Given a vector of integers in i and using the logic of a reverse sort then returning the ~~length~~ of the vector where element number is less than s. Thanks to @plannapus for the nice tip.

```
> i=c(23,42,12,92,39,46,23,56,31,12,43,23,54,23,56,73,35,73,42,12,10,15,35,23,12,42)
> s=sort(i);length(s[s>=length(s):1])
[1] 20
> i=c(0,0,0,0)
> s=sort(i);length(s[s>=length(s):1])
[1] 0

```

# Answer
> 4 votes
# Japt, 4 bytes

```
ñÍè>

```

Try it here

```
ñÍè>     :Implicit input of array
ñ        :Sort by
 Í       :  Subtracting from 2
  è      :Count the elements that are
   >     :  Greater than their 0-based indices

```

# Answer
> 3 votes
# CJam, 23 bytes

```
l~:I,),W%{_If>:!:+>}$0=

```

This takes the list as an array on STDIN, like

```
[23 42 12 92 39 46 23 56 31 12 43 23 54 23 56 73 35 73 42 12 10 15 35 23 12 42]

```

Test it here.

You can use this to run all test cases:

```
[0 0 0 0]
[12 312 33 12]
[1 2 3 4 5 6 7]
[22 33 1 2 4]
[1000 2 2 2]
[23 42 12 92 39 46 23 56 31 12 43 23 54 23 56 73 35 73 42 12 10 15 35 23 12 42]]
{:I,),W%{_If>:!:+>}$0=N}/

```

## Explanation

```
l~:I,),W%{_If>:!:+>}$0=
l~:I                    "Read input, evaluate, store in I.";
    ,                   "Get length of input N.";
     ),W%               "Create range from 0 to N, reverse.";
         {         }$   "Sort stably.";
          _I            "Duplicate candidate h, push input list.";
            f>          "Map each number to 1 if it's less or 0 otherwise.";
              :!        "Invert all results.";
                :+      "Sum them up.";
                  >     "Check if the sum is less than the candidate h.";
                     0= "Pick the first element.";

```

The logic is a bit backwards, but it saved a couple of bytes. Basically, the block passed to sort returns `0` for valid candidates and `1` otherwise. So the valid candidates come first in the sorted array. And because the sort is stable, and we begin with a list from N down to 1, this will return the largest valid h.

# Answer
> 3 votes
# Perl 5: 32 (30 + 2 for `-pa`)

```
#!perl -pa
$_=grep$_>$i++,sort{$b<=>$a}@F

```

Takes space separated input on STDIN:

```
perl hidx.pl <<<'1 2 3 4 5 6 7'

```

# Answer
> 3 votes
# Python (63)

Basically a direct port of my J solution. Obviously, a lot longer, as one might imagine.

```
lambda x:sum(a>b for a,b in zip(sorted(x)[::-1],range(len(x))))

```

# Answer
> 3 votes
# Haskell, 40

```
f s=[x-1|x<-[1..],x>sum[1|r<-s,r>=x]]!!0

```

this searches for the first number to not fit the scheme and returns it's predecessor.

# Answer
> 3 votes
# Ruby ~~44~~ 41

Recursive, more or less same strategy as xnor's Python solution:

```
f=->a,n=0{a.count{|x|x>n}<n+1?n:f[a,n+1]}

```

# Ruby 52

Non-recursive:

```
f=->a{a.size.downto(0).find{|x|a.count{|y|y>=x}>=x}}

```

"Stabby" lambda/anonymous functions, require Ruby 1.9 or newer. Call with e.g. `f[[22,33,1,2,4]]`

# Answer
> 3 votes
# Bash + coreutils, 29

```
sort -nr|nl -s\>|bc|grep -c 0

```

Input taken from stdin as a newline-separated list.

* `sort` the integers in descending order
* `nl` prefixes each line with its 1-based line number, separating the line number and rest of the line with a greater-than `>`
* Arithmetically evaluate each line with `bc`. Integers less than their line number result in 0. Otherwise 1.
* `grep` counts the number of `0`s, i.e. the number of integers greater than or equal to `h`

### Example

```
$ for i in {23,42,12,92,39,46,23,56,31,12,43,23,54,23,56,73,35,73,42,12,10,15,35,23,12,42}; do echo $i; done | ./atleasth.sh
20
$ for i in {1,2,3,4,5,6,7}; do echo $i; done | ./atleasth.sh
4
$

```

# Answer
> 2 votes
# JavaScript (ES6) 48

Recursive solution.

```
F=(l,h=-1)=>l.filter(v=>v>h).length>h?F(l,h+1):h

```

**Test** in FireFox/FireBug console

```
;[
  [0,0,0,0],
  [12,312,33,12],
  [1,2,3,4,5,6,7],
  [22,33,1,2,4],
  [1000,2,2,2],
  [23,42,12,92,39,46,23,56,31,12,43,23,54,23,56,73,35,73,42,12,10,15,35,23,12,42]
 ].forEach(l=>console.log(l,F(l)))

```

*Output*

```
[0, 0, 0, 0] 0
[12, 312, 33, 12] 4
[1, 2, 3, 4, 5, 6, 7] 4
[22, 33, 1, 2, 4] 3
[1000, 2, 2, 2] 2
[23, 42, 12, 92, 39, 46, 23, 56, 31, 12, 43, 23, 54, 23, 56, 73, 35, 73, 42, 12, 10, 15, 35, 23, 12, 42] 20

```

# Answer
> 2 votes
# Java 8, 116 bytes.

Full class:

```
import java.util.*;
import java.util.stream.*;

class H{

    public static void main(String[]a){
        System.out.println(new H().f(Stream.of(a[0].split(",")).mapToInt(Integer::parseInt).toArray()));
    }

    int i;

    int f(int[]n){
        Arrays.sort(n);
        i=n.length;
        Arrays.stream(n).forEach(a->i-=a<i?1:0);
        return i;
    }
}

```

Function:

```
import java.util.*;int i;int f(int[]n){Arrays.sort(n);i=n.length;Arrays.stream(n).forEach(a->i-=a<i?1:0);return i;}}

```

# Answer
> 2 votes
# APL, 12 characters

`(+/⊢≥⍒)⊂∘⍒⌷⊢`

# Answer
> 2 votes
**C++ ~~815~~ 219 from (wc -c main.cpp)**

Alright here's some of the worst code I've ever written! :)

```
#include <iostream>
#include <list>
using namespace std;int main(int c,char** v){list<int>n(--c);int h=c;for(int&m:n)m=atoi(*(v+(h--)));n.sort();for(auto r=n.rbegin();r!=n.rend()&&*r++>++h;);cout<<(h==c?h:--h)<<endl;}

```

# Answer
> 2 votes
# Jelly, 6 bytes

```
NỤỤ<’S

```

Explanation:

```
N           Negate (so that repeated elements won't mess up the second grade down)
 Ụ          Grade down
  Ụ         Twice.
   <’       Predicate, check for each element if the new one (after grading) is lower than original array (minus 1 on each element)
     S      Sum

```

# Answer
> 2 votes
## Haskell, ~~72~~ 59 bytes

My C++ solution looked pretty verbose, and the recursive nature made me think of Haskell, so here's my attempt:

```
a!i|i<foldr(\x s->s+fromEnum(i<x))0 a=a!(i+1)|1<2=i
H a=a!0

```

Explanation:

```
foldr (\x s -> s + fromEnum(i < x)) 0 a

```

I'm sure there's a shorter way to do this, because I'm pretty new to haskell, but basically it counts how many elements of `a` are less than `x`.

If this is greater than `i`, we can check `i+1`, otherwise, return `i`.

And the `H` function is so that we don't need to pass in `0` to `h`. It adds ~~10~~ 8 bytes, so I'm pretty sure there's a better way.

**-13 bytes** thanks to ovs

# Answer
> 1 votes
## J, ~~15~~ 11 chars

(Current shortest J solution.)

```
   [:+/#\<:\:~

   ([:+/#\<:\:~) 1 2 3 4 5 6 7
4

```

Compares `<:` sorted list `\:~` elements with 1..n+1 `#\` and counts true comparisons `+/`.

Testing similarity against other J solution on 100 random test cases:

```
   */ (([:+/#\<:\:~) = ([:+/i.@#<\:~))"1 ?100 100$100
1

```

# Answer
> 1 votes
# CJam, 22 bytes

```
q~:Q,),{Q{1$>},,>!},W=

```

Takes the list as input:

```
[23 42 12 92 39 46 23 56 31 12 43 23  54 23 56 73 35 73 42 12 10 15 35 23 12 42]

```

Output:

```
20

```

Try it here

# Answer
> 1 votes
# C#, 103

Anonymous function.

```
a=>{try{return a.OrderBy(b=>-b).Select((b,c)=>new{b,c}).First(b=>b.b<b.c+1).c;}catch{return a.Length;}}

```

Indented:

```
a =>
{
    try
    {
        return a.OrderBy(b => -b).Select((b, c) => new { b, c }).First(b => b.b < b.c + 1);
    }
    catch
    {
        return a.Length;
    }
}

```

# Answer
> 1 votes
# JAGL Alpha 1.2 - 14

***Doesn't count*** because the 'C' reverse array functionality was added after the question, but am answering for fun anyway.

Assumes that the array is the first item on the stack, and puts the answer at the top of the stack.

```
0SJC{Sd@>+1}/S

```

To print, just add `P` at the end, adding a byte.

Explanation:

```
0               Push the number 0 (the counter)
 SJC            Swap to array, sort and reverse
    {Sd@>+1}/   For each item in the array, add 1 to counter if counter is less than item
             S  Swap counter to top of stack

```

# Answer
> 1 votes
# GolfScript, 13 bytes

```
$-1%0\{1$>+}/

```

Test this code online.1

Takes input as an array on the stack. Uses the same algorithm as feersum's Python solution, iterating over the numbers in the array and incrementing a counter from 0 until it equals or exceeds the current element of the array.

1) The online GolfScript server seems to be experiencing random timeouts again. If the program times out for you, try re-running it.

# Answer
> 1 votes
# TI-BASIC, 22 bytes

ASCII representation:

```
Input L1:1:While Ans≤sum(Ans≥L1:Ans+1:End:Ans

```

Hex dump:

```
DC 5D 00 3E 31 3E D1 72 6D B6 72 6C 5D 00 3E 72 70 31 3E D4 3E 72

```

Gets a list as input. Starting from Ans=0, checks whether at least Ans+1 of the numbers are at least Ans+1. If so, increments Ans and loops again. If not, outputs Ans.

# Answer
> 1 votes
# Reng v.3.2, 43 bytes

```
1#xk#yaïí'1ø ~n-1$\
1+)x(%:1,%1ex+y1-?^#y#x

```

Try it here! This code can be split into three parts: initial, computational, and final.

## Initial

```
1#xk#yaïí'1ø

```

This stores `1` to `x`, the length of the input stack `k` to `y`, and gets all input (`aïí`) which is then sorted (`'`).  goes to the next line, i.e., the next part.

## Computational

```
1+)x(%:1,%1ex+y1-?^#y#x

```

Reng has no built-in for inequality. Thus, an algorithm must be implemented. The shortest algorithm I found for `a < b` is `%:1,%1e`; this looks like this:

```
Command | Stack
  ---   | a, b
   %    | a/b
   :    | a/b, a/b
   1    | a/b, a/b, 1
   ,    | a/b, (a/b)%1
   e    | (a/b) == ((a/b)%1)

```

I'm sure *that* cleared it up! Let me explain further. `x % 1`, i.e modulus with 1, maps `x` to `(-1,1)`. We know that `(a/b) % 1` is `a/b` when `a < b`. Thus, this expression is equal to `a < b`.

However, this doesn't work quite as well because of problems with modulus with zero. So, we increment every member of the stack and the counter initially.

After we get the inequality Boolean on the stack, `x+` adds it to x, but leaves it on the stack for the moment. `y1-` decrements `y`, and `?^` goes up iff `y == 0` and we proceed to the final phase. Otherwise, we put `y-1` into `y` and the new `x` into `x`.

## Final

```
             ~n-1$\

```

This pops the residual `y-1` from the stack, decrements the result, outputs it, and ends the program.

# Answer
> 1 votes
# 05AB1E, 5 bytes

```
{Rā@O

```

Try it online! or as a Test Suite

**Explanation**

```
{R      # sort descending
  ā@    # check each element if it's greater than or equal to its 1-based index
    O   # sum

```

# Answer
> 1 votes
# Scala, ~~41~~ 39 bytes

```
_.sorted.:\(0){(n,h)=>h+(n/(h+1)).sign}

```

Try it online!

In Scala 2.13, `signum` was changed to `sign`, so it's 2 bytes extra in TIO, which still uses Scala 2.10.

## Scala, 41 bytes

```
a=>a.max to(0,-1)find(b=>a.count(b<=)>=b)

```

Try it online!

This isn't mine, it's just a modified version of Chad Retz's answer, but since they're not active anymore, I decided to put it here instead of commenting on it.

# Answer
> 1 votes
# Vyxal `s`, 5 bytes

```
s₌Ṙż≥

```

Try it Online!

A port of the 05AB1E answer. I originally had `ẏ'?<∑≤` \+ `-G`, which I kinda like more.

## Explained

```
s₌Ṙż≥
s     # sort the input list
 ₌Ṙż  # and push reversed(^) and range(1, len(^) + 1)
    ≥ # vectorise >= over ^ and input
      # -s sums that

```

```
ẏ'?<∑≤
ẏ       # The range [0, len(input))
 '      # with only elements where: (call each element N)
  ?<∑   #   the sum of all elements of the input greater than N
     ≤  #   is less than or equal to N
        # (this gets all h with at least h)
        # -G gets the biggest h from the possible h's

```

# Answer
> 1 votes
## C++, 81 bytes

```
int h(std::list<int>a,int i=0){int c=0;for(int x:a)c+=i<x;return i<c?h(a,i+1):i;}

```

Similar solution to most of the other ones.

Assuming that `<list>` is included.

Non-recursive solution (~~85~~ 83 bytes):

```
int h(std::list<int>a){for(int i=0,c;;i++){c=0;for(int x:a)c+=i<x;if(i>=c)return i;}}

```

It might be possible to put the `c` initialization outside the function (because that defaults to 0, and you also don't need the `int`, but it doesn't seem to work on TIO.

# Answer
> 0 votes
# Mathematica, 57 bytes

```
FirstCase[Range[Length@#,0,-1],h_/;Count[#,k_/;k>=h]>=h]&

```

This is an anonymous function taking a list and returning an integer, like

```
FirstCase[Range[Length@#,0,-1],h_/;Count[#,k_/;k>=h]>=h]&@{1,2,3,4,5,6,7}

```

Use this to check all test cases:

```
FirstCase[Range[Length@#,0,-1],h_/;Count[#,k_/;k>=h]>=h]& /@ {
  {0, 0, 0, 0},
  {12, 312, 33, 12},
  {1, 2, 3, 4, 5, 6, 7},
  {22, 33, 1, 2, 4},
  {1000, 2, 2, 2},
  {23, 42, 12, 92, 39, 46, 23, 56, 31, 12, 43, 23, 54, 23, 56, 73, 35,
    73, 42, 12, 10, 15, 35, 23, 12, 42}
}

```

# Answer
> 0 votes
# Scala, 62

```
def h(a:Int*)=Range(a.size,-1,-1).find(b=>a.count(b<=)>=b).get

```

# Answer
> 0 votes
## Java, 107

```
long f(java.util.ArrayList<Long>l){for(int i=0;;){long x=i++;l.removeIf(j->j<x);if(l.size()<x)return x-1;}}

```

Explanation:

```
long f(java.util.ArrayList<Long> l) {
    for(int i = 0;;) {
        long x = i;
        i++;
        l.removeIf(j -> j<x);
        if(l.size() < x)
            return x-1;
    }
}

```

# Answer
> 0 votes
# MATL, ~~8~~ 7 bytes

```
SPGf<~s

```

**Try it online!**

### Explanation

Direct application of the definition:

```
SP    % Take input array implicitly. Sort in non-increasing order
Gf    % Push array of indices of nonzero entries of the input. This gives
      % [1 2 ... n] where n is input size
<~    % True for values of the sorted input that are >= those in [1 2 ... n]
s     % Sum. Implicitly display

```

# Answer
> 0 votes
# x86 machine code, 24 bytes

Hexdump:

```
53 8b c2 8b d8 52 39 44 91 fc 72 01 4b 4a 75 f6
5a 48 4b 7d ee 5b 40 c3

```

A function that takes a pointer to the list and its length; outputs the number.

C-compatible declaration:

```
int __fastcall hindex(int* list, int size);

```

Source code:

```
    // eax = h
    // ebx counts down from h to 0; if it gets to 0, we have found h
    // ecx = list
    // edx = array size
    push ebx;
    mov eax, edx;                   // h = size ... down to 0
h_loop:
    mov ebx, eax;                   // init the countdown
    push edx;
array_loop:
    cmp [ecx + edx * 4 - 4], eax;   // check 1 list element
    jb skip;
    dec ebx;
skip:
    dec edx;                        // go to next element
    jnz array_loop;
    pop edx;
    dec eax;                        // go to next h
    dec ebx;                        // compare the countdown to 0
    jge h_loop;                     // if it was 0 or less, stop
    pop ebx;
    inc eax;                        // undo going to next h
    ret;

```

It uses a peculiar way to compare a register with 0:

```
    dec ebx;

```

Here, if `ebx` was less or equal to 0, it will be negative now, and then we should stop the outer loop (`h_loop`). Otherwise, continue:

```
    jge h_loop;

```

There is a small price (1 byte) to pay for this trick: the loop control variable `h` (`eax`) has already been advanced. So this has to be undone after the loop ends:

```
    inc eax;

```

However, even with this price, this trick gives the code the proper `do-while` structure, which saves 2 bytes when compared to a `for` structure.

# Answer
> 0 votes
# Octave, 41 bytes

```
@(x)sum(cumprod(-sort(-x)>=(1:numel(x))))

```

This is an anonymous function.

Try it at Ideone.

# Answer
> 0 votes
# Arturo, 43 bytes

```
$=>[0-1enumerate arrange&=>[2-&]=>[>&<=1+]]

```

Try it

---
Tags: code-golf, number, array
---


title: Converge to a number

text:
# Question
Title: Converge to a number
Your challenge is to, given a positive integer n, count up to each digit of it, giving the effect of converging on it.

Basically, count up to the first digit of n by its place value (\\$⌊\log\_{10}\left(x\right)⌋\\$). Then do the same for each subsequent digit, but with the values of the previous digits added.

Example implementation (animated):

```
function count(){
  let countTo = document.getElementById('number').value.toString().split``,output = document.getElementById('x');
  let numbers = [], accumulator = 0;
  countTo.map((value, index) => {
    for(let i = 0; i < +value; i++){
      accumulator += 10 ** (countTo.length - index - 1)
      numbers.push(accumulator)
    }
  });
  //document.getElementById('y').innerHTML = 'All values:<br>' + numbers.join`<br>`;
  (function next(){let nextVal = numbers.shift();if(nextVal){output.innerHTML = nextVal;setTimeout(next,300)}})()
}
```

```
p{font-family:monospace}
```

```
<label for=number>Number: </label><input id=number type=number> <button onclick=count()>Count!</button><p id=x></p><p id=y></p>
```

You should just return an array of numbers - for n=47:

```
10
20
30
40
41
42
43
44
45
46
47

```

You may optionally have leading zeroes. IO may be strings, numbers, digit lists, etc.

Testcases:

```
4 => [1, 2, 3, 4]
16 => [10, 11, 12, 13, 14, 15, 16]
35 => [10, 20, 30, 31, 32, 33, 34, 35]
103 => [100, 101, 102, 103]
320 => [100, 200, 300, 310, 320]
354 => [100, 200, 300, 310, 320, 330, 340, 350, 351, 352, 353, 354]
1000 => [1000]
1001 => [1000, 1001]
3495 => [1000, 2000, 3000, 3100, 3200, 3300, 3400, 3410, 3420, 3430, 3440, 3450, 3460, 3470, 3480, 3490, 3491, 3492, 3493, 3494, 3495]
4037 => [1000, 2000, 3000, 4000, 4010, 4020, 4030, 4031, 4032, 4033, 4034, 4035, 4036, 4037]
84958320573493 => [10000000000000, 20000000000000, 30000000000000, 40000000000000, 50000000000000, 60000000000000, 70000000000000, 80000000000000, 81000000000000, 82000000000000, 83000000000000, 84000000000000, 84100000000000, 84200000000000, 84300000000000, 84400000000000, 84500000000000, 84600000000000, 84700000000000, 84800000000000, 84900000000000, 84910000000000, 84920000000000, 84930000000000, 84940000000000, 84950000000000, 84951000000000, 84952000000000, 84953000000000, 84954000000000, 84955000000000, 84956000000000, 84957000000000, 84958000000000, 84958100000000, 84958200000000, 84958300000000, 84958310000000, 84958320000000, 84958320100000, 84958320200000, 84958320300000, 84958320400000, 84958320500000, 84958320510000, 84958320520000, 84958320530000, 84958320540000, 84958320550000, 84958320560000, 84958320570000, 84958320571000, 84958320572000, 84958320573000, 84958320573100, 84958320573200, 84958320573300, 84958320573400, 84958320573410, 84958320573420, 84958320573430, 84958320573440, 84958320573450, 84958320573460, 84958320573470, 84958320573480, 84958320573490, 84958320573491, 84958320573492, 84958320573493]

```

# Answer
# Jelly, 9 bytes

```
DLḶU⁵*xDÄ

```

Try it online!

```
DL           Digits, length
  ḶU⁵*       Compute [10^(n-1), …, 10, 1]
      xD     Use the digits as repeat counts for this array
               e.g.   423 -> [100, 100, 100, 100,  10,  10,   1,   1,   1]
        Ä    Cumulative sum: [100, 200, 300, 400, 410, 420, 421, 422, 423]

```
> 18 votes

# Answer
# JavaScript (ES6),  ~~48~~  46 bytes

```
f=(n,k=1)=>n?n%k?[...f(n-k/10),n]:f(n,k*10):[]

```

Try it online!

### How?

Instead of going from \\$0\\$ to \\$n\\$, we go from \\$n\\$ to \\$0\\$ and store the intermediate steps in reverse order.

At each step, we start with \\$k=1\\$ and recursively multiply \\$k\\$ by \\$10\\$ until \\$n\bmod k\neq 0\\$, which is a way to locate the least significant non-zero digit in \\$n\\$. We decrement this digit by subtracting \\$k/10\\$ from \\$n\\$ and repeat the process until \\$n=0\\$.

---

# JavaScript (ES6), 49 bytes

This version expects a string and uses a lookahead assertion to locate and decrement the least significant non-zero digit.

```
f=n=>+n?[...f(n.replace(/.(?=0*$)/,c=>c-1)),n]:[]

```

Try it online!
> 12 votes

# Answer
# 05AB1E, ~~11~~ 9 bytes

*Thanks to @ovs for 2 bytes off, and to @KevinCruijssen for pointing out that the input can be an integer instead of an array*

```
ā<R°¹ÅΓηO

```

Port of Lynn's answer.

**Try it online!**
> 8 votes

# Answer
# APL (Dyalog Unicode), 13 bytes

*Port of Lynn's solution – upvote that!*

Anonymous prefix lambda, taking a digit list as argument and returning a numeric list. Requires 0-based indexing.

```
{+\⍵/10*⌽⍳≢⍵}

```

Try it online!

`{``}` "dfn"; argument is :

`+\` cumulative sum of…

`⍵/` the argument numbers replicating the respective numbers in…

`10*` ten raised to the powers of…

the reversed…

indices in an array of size…

tally of elements in…

argument

---

### Old solution: ~~24~~ 17 bytes

−4 thanks to ovs

Full program. Prompts for digit list.

```
↑¨{⍺,,¨∘⍵⊃⌽⍺}/⍳¨⎕

```

Try it online!

prompt for digit list

`⍳¨` generate 1…n for each digit

`{``}/` reduce (from the right) using this lambda:

`⊃⌽⍺` the last element of the left argument (lit. the first of the reverse)

`,¨∘⍵` prepend that to each of the left argument elements

`⍺,` prepend the left argument to that

`↑¨` combine each list of lists into a matrix, zero-padding on the right
> 7 votes

# Answer
# Raku, 37 bytes

```
{[\R+] flat (10 X**^$_)Zxx.flip.comb}

```

Try it online!

An anonymous code block that takes a number and returns an array.

### Explanation:

```
{                                   }  # Anonymous code block
            (10 X**^$_)                  # Generate powers of 10
                       Zxx               # Zip repeat each by
                          .flip.comb     # The reversed digits of the number
       flat                              # Flatten this list
 [ R+]                                   # Reduce by reverse addition
  \                                      # Keeping intermediate values

```
> 7 votes

# Answer
# Jelly, 9 bytes

```
æḟ⁵ạƊƬINÄ

```

Try it online!

9 bytes sure seems to be special here.

```
     Ƭ       Collect results while unique from repeating:
   ạ         absolute difference from
æḟ⁵          greatest less than or equal power of 10.
        Ä    Take the cumulative sum of
      IN     each amount by which it decreased.

```

# Jelly, 9 bytes

```
ọ⁵⁵*ạoµƬU

```

Try it online!

Conceived of independently from, but very similar to, Arnauld's solution.

```
      µƬ     Collect results while unique from repeating:
ọ⁵           How many times does 10 evenly divide it?
  ⁵*         Raise 10 to that power,
    ạ        take the absolute difference,
     o       and keep the previous value (ending the loop) if it's 0.
        U    Reverse.

```
> 6 votes

# Answer
# Python 2, ~~58~~ 57 bytes

```
f=lambda n,k=1:n%k and f(n-k/10)+[n]or n*[1]and f(n,k*10)
```

Attempt This Online!

Port of Arnauld's answer.

-1 thanks to @ovs

# Python 2, ~~76~~ 64 bytes

```
x=input()
c=0
i=len(x)
for d in x:i-=1;exec"c+=10**i;print c;"*d
```

Attempt This Online!

Port of Lynn's answer.

-12 thanks to @ovs

---

## Python 2, 74 bytes

```
x=input()
o=[0]*len(x)
i=0
for d in x:
 while o[i]<d:o[i]+=1;print o
 i+=1
```

Attempt This Online!
> 5 votes

# Answer
# , ~~64~~ ~~52~~ 43 bytes

Or **\>=4.1, 36 bytes** by replacing the word `function` with a `\`.

*Edit: -12 bytes thanks to @Giuseppe.*

```
function(d)cumsum(rep(10^(sum(d|1):1-1),d))

```

Try it online!

Yet another port of @Lynn's answer.

Takes input as a vector of digits.

---

### , 49 bytes

Or **\>=4.1, 42 bytes** by replacing the word `function` with a `\`.

```
function(n)while(n>F)show(F<-F+10^(nchar(n-F)-1))

```

Try it online!

Direct approach inspired by @DLosc's answer.
> 5 votes

# Answer
# Vyxal, 9 bytes

```
ẏ↵ṘZvƒẋf¦

```

Try it Online!

Jelly porting fun
> 4 votes

# Answer
# Pip, ~~26~~ ~~24~~ 22 bytes

```
b:DQa#b?(fa).0ALa.\,bl

```

Requires a flag for nicely formatted list output; `-p`, `-l`, and `-s` are all good options. Replit! Or, Try it online!

### Explanation

A recursive full program that returns a list:

```
b:DQa#b?(fa).0ALa.\,bl
    a                   The argument number
  DQ                    Dequeue the last digit
b:                      and assign it to local variable b
                        (In the base case, a was empty and b is now nil)
     #b?                If b is a digit (thus has a nonzero length):
        (fa)             Call the main function recursively on a
            .0           Concatenate 0 to the end of each number in the result
              AL         Append this list:
                a.        Concatenate a with each of
                  \,b     Inclusive range from 1 to b
                        Otherwise (b is nil):
                     l   Return empty list

```
> 4 votes

# Answer
# Scala, ~~105~~ ~~101~~ 92 bytes

```
i=>i.indices.flatMap(e=>Seq.fill(i(e)-48)(("1"+"0"*(i.size-1-e)).toLong)).scan(0L)(_+_).tail

```

Try it online!
> 4 votes

# Answer
# QBasic, 51 bytes

```
INPUT n
WHILE n>g
g=g+10^(LEN(STR$(n-g))-2)
?g
WEND

```

Try it at Archive.org!

### Explanation

We can calculate which digit we want to increment by getting the length of the difference between the input number `n` and the current number `g`:

```
 1234
-1210
=====
   24 -> length 2, increment by 10^1

```

Since QBasic's `STR$` function adds a space to the front of nonnegative numbers, the power of 10 that we need is `LEN` minus 2. Thus, we add `10^(LEN(STR$(n-g))-2)` to `g`, print `g` (`?` is a shortcut for `PRINT`), and loop until `g` and `n` are equal.
> 4 votes

# Answer
# C (gcc), 74 bytes

```
a;g(x){a=0;f(x,1);}f(x,y){y<x&&f(x,y*10);for(;a+y<=x;)printf("%d ",a+=y);}

```

Try it online!
> 4 votes

# Answer
# Perl 5 `-F`, ~~55~~ 47 bytes

```
@a=(0)x@F;map{for$b(0..shift@F){$_=$b;say@a}}@a

```

Try it online!
> 4 votes

# Answer
# brainfuck, 73 bytes

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

```

Try it online!

Treats this as a string processing task. At each step, we find the first digit that still needs to be incremented, increment it, and print the number.

```
Input loop
,[

  Place 48 in cell while subtracting 47 from input cell
  >-[-----<-<+>>]<++++<--->>>

Repeat until input exhausted
,]
If input number was 1024 we now have 48 2 48 1 48 3 48 5 0 (0)

Set up fake 0 digit at the end (to save bytes later)
+

Set up output LF
<++++++++++

Return to first input cell
[<]>>

This loop always starts at the first nonzero input cell remaining
Loop until done:
[

  Decrement digit
  -

  If cell is zero we just blanked an already "zero" digit so do nothing
  [

    Increment corresponding output digit
    <+

    Output entire number with LF
    [<<]>>[.>>]

    Return to input cell prior to first nonzero input cell
    <[<<]

  ]

  Move to first nonzero input cell
  >>

]

```
> 4 votes

# Answer
# JavaScript, 55 bytes

```
x=>eval("for(y=[x];x;)y=[x-=1+`${x}`.match`0+$`,...y]")

```

Try it online!
> 3 votes

# Answer
# Retina 0.8.2, 25 bytes

```
^
$%'¶
1T`d`0d`.0*¶
}A`^0

```

Try it online! Link includes test cases (sorry the output is smashed together). Explanation:

```
^
$%'¶

```

Duplicate the first line.

```
1T`d`0d`.0*¶

```

Decrement the last nonzero digit on that line.

```
A`^0

```

Delete the first line if it's zero.

```
}`

```

Repeat until the first line had been reduced to zero.
> 3 votes

# Answer
# PowerShell Core, 56 bytes

```
($args|%{0.."$_"-ne0|%{"$c$_"}
$c+=$_;$i++})|% *ht $i 48

```

Try it online!

Takes a number as a string using splatting in input and returns a list of numbers

*-8 bytes thanks to mazzy* !
> 3 votes

# Answer
# MathGolf, 14 bytes

```
hrxúma\m*─Å+o;

```

Input as a digit-list.

Try it online.

**Explanation:**

```
h              # Push the length of the (implicit) input
 r             # Pop and push a list in the range [0,length)
  x            # Reverse it to (length,0]
   ú           # Convert each value in this list to 10**value
    ma         # Wrap each inner number into a list
      \        # Swap so the input-list is at the top
       m*      # Repeat each wrapped [10**v] that amount of times
         ─     # Flatten the list of lists
          Å    # Loop over this list, using 2 characters as inner code-block:
           +   #  Add the top two values on the stack together
            o  #  Print this number (without popping)
             ; # After the loop, discard the number (since MathGolf implicitly
               # outputs the entire stack after a program ends)

```
> 3 votes

# Answer
# Python 3, 125 bytes

```
def f(x):
    s=c=int("1"+~-len(str(x))*"0")
    while s<=x//10*10:
        yield s;s+=c
    for i in range(1,x%10+1):yield i

```

Try it online!
> 3 votes

# Answer
# Wolfram Language (Mathematica), ~~49~~ ~~44~~ ~~43~~ 41 bytes

```
If[#<1,{0},Max[p=10#0[.1#]]~Range~#⋃p]&

```

Try it online!

Includes one leading zero.

`Range` stops before the first number greater than the maximum. For example, `Range[3.14]` yields `{1,2,3}`.
> 3 votes

# Answer
# Charcoal, ~~22~~ 19 bytes

```
⭆θ⭆Ｉι⁺⭆◨⁺…θκ⊕λＬθΣν¶

```

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

```
 θ                  Input string
⭆                   Map over digits and join
    ι               Current digit
   Ｉ                Cast to integer
  ⭆                 Map over implicit range and join
          θ         Input string
         …          Truncated to length
           κ        Outer index
        ⁺           Concatenated with
             λ      Inner value
            ⊕       Incremented
       ◨            Right pad with spaces to
              Ｌ     Length of
               θ    Input string
      ⭆             Map over characters and join
                 ν  Current character
                Σ   Change space to zero
     ⁺              Concatenated with
                  ¶ Literal newline

```
> 2 votes

# Answer
# Pari/GP, 47 bytes

```
f(n)=if(n,concat(f(n-10^valuation(n,10)),n),[])

```

Try it online!

Port of @Arnauld's JavaScript answer.
> 2 votes

# Answer
# Haskell, 60 bytes

```
c 0=[]
c x|(d,m)<-x`divMod`10=map(*10)(c d)++map(x-m+)[1..m]

```

Try it online!

---

Simple recursive solution, for example `c 345` is equal to

```
map (*10) (f 34) ++ map (340+) [1..5]

```

34 is 345 \`div\` 10

5 is 345 \`mod\` 10

340 is 345 minus the remainder
> 2 votes

# Answer
# Thunno `D`, \\$ 20 \log\_{256}(96) \approx \\$ 16.46 bytes

```
LR10@rsZZeAuZOA*ESz(

```

Attempt This Online!

Input as a digit list.

## Thunno, \\$ 22 \log\_{256}(96) \approx \\$ 18.11 bytes

```
dDLR10@rsZZeAuZOA*ESz(

```

Attempt This Online!

Input as an integer.

Port of Lynn's Jelly answer.

#### Explanation

```
dD          # Get digits and duplicate
            # (Not needed in the first answer)
  LR        # Pop one and push the length range
    10@     # Pop and push 10 ** each
       rs   # Reverse and swap
         ZZ # Zip with the digits of the input
eAu         # Map over this list:
   ZO       #  Wrap the power of ten in a list
     A*     #  And repeat it the digit times
       E    # End map
        S   # Flatten the list
         z( # And push the cumulative sums

```
> 2 votes

# Answer
# Regex (.NET), 30 bytes

```
((?(1)\1{10}|x{9}))*x(?<=(x*))

```

Takes its input in unary, as a string of `x` characters whose length represents the number. Returns its output as the list of matches' `\2` captures.

Try it online!

```
    # head + tail = N = input number; first match starts with head=0 and tail=N
# Subtract the largest possible power of 10 from tail
(               # \1 = the following, on each iteration (and on each
                #      iteration, add it to head and subtract it from tail):
    (?(1)       # Conditional on whether \1 is set; on the first iteration,
                # it is unset, and on all subsequent iterations it is set:
        \1{10}  # if \1 is set: \1 * 10
    |
        x{9}    # if \1 is unset: 9
    )
)*              # Iterate the above as many times as possible without preventing
                # the following from matching:
x               # Assert tail ≥ 1; head += 1; tail -= 1
(?<=(x*))       # Inside a lookbehind, \2 = head

```

# Regex (Java / .NET), 33 bytes

```
(\1{10}|(?!\2)x{9}())*x(?<=(^x*))

```

Returns its output as the list of matches' `\3` captures.

Try it online! \- **Java**
Try it online! \- .NET

This adds Java support to the 30 byte version by removing the use of the conditional, and hinting how far backwards to go inside the lookbehind.

# Regex (.NET), 36 bytes

```
(((?<=^\3?)x{9}|\2{10})*x(?<=(x*)))*

```

Returns its output as the list of captures on the Balancing Group `\3` stack.

Try it online!

```
    # head + tail = N = input number; first match starts with head=0 and tail=N
(
    # Subtract the largest possible power of 10 from tail
    (              # \1 = the following, on each iteration (and on each
                   #      iteration, add it to head and subtract it from tail):
        (?<=^\3?)  # Make sure this alternative is only used on the first
                   # iteration of this loop, by asserting that head == 0 on the
                   # first iteration of the outermost loop, or head == \3
                   # on subsequent iterations of the outermost loop.
        x{9}       # 9
    |
        \2{10}     # \2 * 10
    )*             # Iterate the above as many times as possible without
                   # preventing the following from matching:
    x              # Assert tail ≥ 1; head += 1; tail -= 1
    (?<=(x*))      # Inside a lookbehind, \3 = head (which is pushed onto the
                   # Group 3 capture stack)
)*                 # Iterate the above as many times as possible, minimum 0

```

# Regex (Python`regex` / .NET), ~~41~~ 40 bytes

```
((?=((?(3)\3{10}|x{9})))(\2))*x(?<=(x*))

```

Returns its output as the list of matches' `\4` captures.

Attempt This Online! \- **Python (with `regex`)**
Try it online! \- .NET

This adds Python`regex` support to the 30 byte version, by replacing the use of the nested backreference `\1` with copying a value back and forth between two forward-declared backreferences `\2` and `\3`.

# Regex (ECMAScript 2018 / Python`regex` / .NET), 41 bytes

```
(?=.*?(((x+)\3{8}(?=\3$))*x$))\1(?<=(x*))

```

Returns its output as the list of matches' `\4` captures.

Try it online! \- **ECMAScript 2018**
Attempt This Online! \- Python (with `regex`)
Try it online! \- .NET

```
    # head + tail = N = input number; first match starts with head=0 and tail=N
(?=                           # Atomic lookahead - whatever matches first is
                              # locked in.
    .*?                       # Subtract as little as possible from tail in
                              # order to satisfy the following:
    # Assert that tail is a power of 10, and capture it in \1.
    (                         # \1 = tail
        (
            (x+)\3{8}(?=\3$)  # Assert that 10 divides tail; tail /= 10
        )*                    # Iterate the above as many times as necessary
                              # (minimum 0) to satisfy the following:
        x$                    # Assert tail == 1
    )
)
\1                            # head += \1; tail -= \1
                              # (this applies also to the next match)
(?<=(x*))                     # Inside a lookbehind, \4 = head

```

# Regex (ECMAScript 2018 / Java / Python`regex` / .NET), 42 bytes

```
(?=.*?(((x+)\3{8}(?=\3$))*x$))\1(?<=(^x*))

```

Try it online! \- ECMAScript 2018
Try it online! \- Java
Attempt This Online! \- Python (with `regex`)
Try it online! \- .NET

This adds Java support to the 41 byte version by hinting how far backwards to go inside the lookbehind.
> 2 votes

# Answer
# Nekomata, 11 bytes

```
¢DsCr↔~c¢b-

```

Attempt This Online!

Take `47` as an example.

```
¢DsCr↔~c¢b-
¢D              Convert the input to decimal digits.
                    47 becomes [4, 7]
  s             Non-deterministically choose a suffix of the list.
                    Possible suffixes are [4, 7], [7], [].
   C            Split the list into the head and the tail.
                    Possible heads are 4 and 7, and the corresponding tails are [7] and [].
    r           Range from 0 to the head minus 1.
                    4 becomes [0, 1, 2, 3], and 7 becomes [0, 1, 2, 3, 4, 5, 6].
     ↔          Reverse the range.
                    Possible results are [3, 2, 1, 0] and [6, 5, 4, 3, 2, 1, 0].
      ~         Non-deterministically choose an element from the range.
                    Possible elements are 3, 2, 1, 0, 6, 5, 4, 3, 2, 1, 0.
       c        Join the element with the tail.
                    Possible results are [3, 7], [2, 7], [1, 7], [0, 7], [6], [5], [4], [3], [2], [1], [0].
        ¢b      Convert the list to a base-10 number.
                    Possible results are 37, 27, 17, 7, 6, 5, 4, 3, 2, 1, 0.
          -     Subtract it from the input.
                    Possible results are 10, 20, 30, 40, 41, 42, 43, 44, 45, 46, 47.
                    The interpreter will print all of them.

```
> 2 votes

# Answer
# Perl 5 -F -p, 63 bytes

```
//+push@a,map$a[-1]+$_*10**(@F-$'),1..$F[$_-1]for 1..@F;$_="@a"

```

Try it online!
> 1 votes

# Answer
Unlike my other regex answer, this outputs in reverse order, in order to support regex engines that are incapable of outputting it in ascending order.

The algorithm used here was conceived of independently from, but is very similar to, Arnauld's JavaScript answer (and therefore pxeger's Python answer) and Unrelated String's 2nd Jelly answer. Unlike those answers, it is impossible to reverse the order of the list before outputting it.

# Regex (Perl / PCRE / .NET), ~~39~~ 35 bytes

```
(?=((((?(3)\3{10}|x{9}))*x)\2*$))\2

```

Takes its input in unary, as a string of `x` characters whose length represents the number. Returns its output as the list of matches' `\1` captures.

Try it online! \- Perl
Try it online! \- PCRE
Try it online! \- .NET

```
    # on the first match, tail = N = input number
(?=
    (                       # \1 = tail (the return value)
        (                   # \2 = the largest power of 10 that divides tail
            (               # \3 = the following, on each iteration (and on each
                            #      iteration, subtract it from tail):
                (?(3)       # Conditional on whether \3 is set; on the first
                            # iteration, it is unset, and on all subsequent
                            # iterations it is set:
                    \3{10}  # if \3 is set: \3 * 10
                |
                    x{9}    # if \3 is unset: 9
                )
            )*              # Iterate the above as many times as possible
                            # without preventing the following from matching:
            x               # Assert tail ≥ 1; tail -= 1
        )
        \2*$                # Assert that \2 divides tail
    )
)
\2                          # tail -= \2, in preparation for the next match

```

It's impossible for regex flavors without variable-length lookbehind to output this sequence in ascending order. Emulating this with recursion and fixed-width lookbehind in Perl/PCRE doesn't work, because captures made inside a subroutine call are erased upon returning from the call. It's impossible even to guess what the capture will be before it's made using non-atomic lookahead in PCRE2, because there isn't enough room to capture that after the sequence has passed \\$n/2\\$.

# Regex (Perl / Java / PCRE / .NET), ~~39~~ 37 bytes

```
(?=(((\3{10}|(?!\4)x{9}())*x)\2*$))\2

```

Try it online! \- Perl
Try it online! \- **Java**
Try it online! \- PCRE
Try it online! \- .NET

This adds Java support to the 35 byte version by removing the use of the conditional.

# Regex (Perl / Python`regex` / Ruby / PCRE / .NET), 45 bytes

```
(?=((((?=((?(5)\5{10}|x{9})))(\4))*x)\2*$))\2

```

Try it online! \- Perl
Attempt This Online! \- **Python (with `regex`)**
Try it online! \- **Ruby**
Try it online! \- PCRE
Try it online! \- .NET

This adds Python`regex` and Ruby support to the 35 byte version, by replacing the use of the nested backreference `\3` with copying a value back and forth between two forward-declared backreferences `\4` and `\5`.

# Regex (Perl / ~~Java~~ / Python`regex` / Ruby / PCRE / .NET), 47 bytes

```
(?=((((?=(\6{10}|(?!\5)x{9}()))(\4))*x)\2*$))\2

```

Try it online! \- Perl
Try it online! \- Python (with `regex`)
Try it online! \- Ruby
Try it online! \- PCRE
Try it online! \- .NET

This attempts to add Java support to the 45 byte version by removing the use of the conditional (just like the 37 byte version does to the 35 byte version), but while it works on the other engines, it **exposes a bug** in Java's regex engine: Try it online! / Attempt This Online!

# Regex (ECMAScript / Boost / Python or better), ~~54~~ 52 bytes

```
(?=((|x+)\2*(?=(\2$|.*$\2))((x+)\5{8}(?=\5$))*x$))\3

```

Try it online! \- **ECMAScript**
Try it online! \- **ECMAScript 2018**
Try it online! \- Perl
Try it online! \- Java
Try it online! \- **Boost** \- only works with small numbers
Try it online! \- **Python**
Attempt This Online! \- Python (with `regex`)
Try it online! \- Ruby
Try it online! \- PCRE
Try it online! \- .NET

```
(?=
    (                         # \1 = tail (the return value)
        (|x+)                 # \2 = 0 or the largest number that satisfies the
                              #      following, whichever matches first
        \2*                   # tail -= \2 * {any nonnegative integer}, to
                              # satisfy the following:
        (?=                   # Lookahead (atomic - first match is locked in)
            (                 # \3 = tail
                \2$           # Assert tail == \2
            |             # or...
                .*$\2         # Assert \2 == 0
            )
        )
        # Assert that tail is a power of 10
        (
            (x+)\5{8}(?=\5$)  # Assert that 10 divides tail; tail /= 10
        )*                    # Iterate the above as many times as necessary
                              # (minimum 0) to satisfy the following:
        x$                    # Assert tail == 1
    )
)
\3                            # tail -= \3, in preparation for the next match

```

Boost works fine with the previous **54 byte** version: Try it online!
> 1 votes

# Answer
# JavaScript (Node.js), 107 bytes (non-competitive)

I tried to do this challenge in JS with a "functional programming approach", without any recursive call and without regex, and it has become surprinsingly long!
I'm still quite new to JS, so does any of you see if this could this be shortened in some way while keeping this approach?

```
p=>[...p+=""].flatMap((a,i)=>(r=[...Array(a*=1)].map((b,j)=>(t*10+j+1)*10**(p.length-i-1)),t=t*10+a,r),t=0)

```

Try it online!

(I can ungolf it if this needs explanations)
> 0 votes

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


title: "Sort" by element duplication

text:
# Question
Title: "Sort" by element duplication
Inspired by one of many bugs I ran into while implementing selection sort in trilangle.

Given a non-empty list of non-negative integers, "sort" the list using the following procedure:

1. Find and output the smallest value in the list.
2. If the list only has one element, stop.
3. Recurse on a sublist:
    * If the last element in the list is the smallest, recurse on everything but the last value.
    * Otherwise, recurse on everything but the first value.

Your code doesn't have to follow this procedure exactly, as long as the result is the same.

Sample implementation in JS:

```
function* sort(arr) {
    if (arr.length === 1) {
        return yield arr[0];
    }
    const min = Math.min(...arr);
    yield min;
    if (min === arr.at(-1)) {
        arr.pop();
        yield* sort(arr);
    } else {
        const [, ...rest] = arr;
        yield* sort(rest);
    }
}

```

Some notes on the algorithm:

* The output will always contain the same number of elements as the input.
* The input *may* contain duplicates.
* Every element in the output is an element of the input, but they don't necessarily appear the same number of times.
* The elements of the output will be in nondecreasing order.

## I/O

I/O defaults apply. Since I don't see this mentioned there, I will explicitly add the following rule:

You are allowed to implement this destructively. If taking the input by reference, the input does not have to have the same value once the procedure is completed. Note that I use this in the sample implementation above: I call `.pop()` without copying the array first.

## Examples

```
[4, 3, 1, 2] => [1, 1, 1, 2]
[1, 2, 3, 4] => [1, 2, 3, 4]
[3, 2, 1, 0] => [0, 1, 2, 3]
[1, 2, 3, 1] => [1, 1, 2, 3]
[101, 103, 101, 105] => [101, 101, 101, 105]

```

## Scoring

This is , so shortest program (per language) wins.

# Answer
> 10 votes
# Vyxal, ~~15~~ ~~13~~ ~~10~~ 9 bytes

```
(:g…Ȯt=ǔḢ

```

Try it Online!

~~It's not every day I get to use recursion in a lambda~~ Nevermind, I don't anymore.

*-3 thanks to AndrovT*

*-1 by outputting items on newlines*

## Explained

```
(:g…Ȯt=ǔḢ
(          # input length times:
 :g…       #   get the minimum of the top of the stack without popping and print that without popping
    Ȯt     #   push the tail of the item over the top of the stack
      =    #   does that equal the min?
       ǔ   #  rotate the list right that many times (once if tail is min [placing tail at front] or no times at all).
        Ḣ  #  Remove the head of the list

```

# Answer
> 9 votes
# Nekomata, 10 bytes

```
ᶦ{:Ɔ≥$tI}ṁ

```

Attempt This Online!

```
ᶦ{:Ɔ≥$tI}ṁ
ᶦ{      }     Iterate the block until it fails
       I      Choose the first non-failed result between the following two:
  :Ɔ≥$          If the last item is the smallest, remove it from the list; otherwise fail
      t         Remove the first item of the list
         ṁ    Take the minimum of each step of the iteration

```

---

## Nekomata v0.1.0.0, 13 bytes

```
ⁱ{:↔C≥↔$t?∃}⊥

```

```
ⁱ{:↔C≥↔$t?∃}⊥
ⁱ{         }     Iterate the block until it fails
         ?∃       Choose the first non-failed result between the following two:
  :↔C≥↔$            If the last item is the smallest, remove it from the list; otherwise fail
        t           Remove the first item of the list
            ⊥   Take the minimum of each step of the iteration

```

# Answer
> 9 votes
# Jelly, 10 bytes

```
ṖḊṂṄ=Ṫʋ`?ƒ

```

Try it online!

Full program, printing each element on its own line with a trailing newline.

I tried a couple printing-based solutions earlier (including some with  that also attempted to leverage it for ), but they all tied the pure solution. However, Jonathan Allan's golf to that gave me room to fit a print in with the extra space so long as it was also with dyadic chaining, which then required some creative wrestling with the loop quick of choice (at one point the program ended in `µµ¿`!) until it eventually inspired me to abuse `ƒ`.

```
         ƒ    Reduce over the list, starting with the list, by:
              Ignoring the right argument,
        ?     if
     Ṫʋ       the last element (popped) from
    =  `      the list of for each element in the list if it equals
  Ṃ           the minimum
   Ṅ          which is printed on its own line,
Ṗ             then remove the last element,
 Ḋ            else remove the first element.
         ƒ    The end result is an empty list with no effect on the output.

```

# Jelly, ~~12~~ 11 bytes

```
ṖḊ=ṂṪƊ?ƬṂ€Ṗ

```

Try it online!

*-1 thanks to Jonathan Allan*

Feels kinda clumsy, but may as well post it ~~while it's the shortest~~ :P

```
       Ƭ       Repeat while unique, collecting all results:
      ?        If
    Ṫ          the last element (popped) from
  =  Ɗ         the list of, for each element of the input, if it's equal to
   Ṃ           the minimum,
Ṗ              then remove the last element,
 Ḋ             else remove the first element.
        Ṃ€     Take the minimum of each result
          Ṗ    and remove the last.

```

# Answer
> 7 votes
# 05AB1E, ~~10~~ 9 bytes

```
vDW=Qθ._¦

```

-1 byte being inspired by the rotate used in *@lyxal*'s Vyxal answer.

Try it online or verify all test cases.

**Original 10 bytes answer:**

```
vDW=Êθ·<.$

```

Outputs the result on separated newlines.

Try it online or verify all test cases.

**Explanation:**

```
v           # Loop over the (implicit) input-list, without using its values:
 D          #  Duplicate the current list
            #  (which will be the implicit input-list in the first iteration)
  W         #  Push its minimum (without popping the list)
   =        #  Output it with trailing newline (without popping)
    Q       #  Check for each value in the list whether it's equal to this minimum
     θ      #  Pop and push the last item
      ._    #  Rotate the list that many times towards the left
        ¦   #  Remove the first item

vDW=        # Same as above
    Ê       #  Check for each value in the list whether it's NOT equal to this minimum
     θ      #  Pop and push the last item
      ·     #  Double it
       <    #  Decrease it by 1
        .$  #  Remove that many leading items from the list
            #  (1 will remove the first item; -1 will remove the last item)

```

# Answer
> 7 votes
# JavaScript (ES6), 65 bytes

```
f=a=>a+a?[m=Math.min(...b=[...a]),...f(b.pop()^m?a.slice(1):b)]:a

```

Try it online!

### Commented

```
f = a =>            // recursive function taking the input array a[]
a + a ?             // if a[] is not empty:
  [                 //   append ...
    m = Math.min(   //   ... m, which is the minimum value in a[]
      ...b = [...a] //   define b[] as a copy of a[]
    ),              //
    ...f(           //   append the result of a recursive call:
      b.pop()       //     remove the last element from b[]
      ^ m ?         //     if it's not equal to the minimum:
        a.slice(1)  //       pass a[] without the first element
      :             //     else:
        b           //       pass b[] (i.e. a[] without the last element)
    )               //   end of recursive call
  ]                 //
:                   // else:
  a                 //   stop

```

---

# JavaScript (ES13), 64 bytes

Suggested by @tsh.

```
f=a=>a+a?[m=Math.min(...a),...f(a,a.splice((a.at(-1)>m)-1,1))]:a

```

Attempt This Online!

# Answer
> 4 votes
# PARI/GP, 57 bytes

```
f(a)=if(#a,concat(m=vecmin(a),f(a[^if(m-a[#a],1,#a)])),a)

```

Attempt This Online!

# Answer
> 3 votes
# Charcoal, 25 bytes

```
Ｗθ«⟦Ｉ⌊θ⟧≔⎇⁼↨θ⁰⌊θ…θ⊖ＬθΦθλθ

```

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

```
Ｗθ«

```

Repeat until the list is empty.

```
⟦Ｉ⌊θ⟧

```

Output its minimum.

```
≔⎇⁼↨θ⁰⌊θ…θ⊖ＬθΦθλθ

```

Remove the last or first element as appropriate.

# Answer
> 3 votes
# Excel (ms365), 153 bytes

\-  \-  \-  \-

With data in `A1:A4`, formula in `B1`:

```
=TOCOL(BYCOL(REDUCE(A1:A4,A1:A3,LAMBDA(x,y,LET(z,TOCOL(TAKE(x,,-1),2),HSTACK(x,IF(TAKE(z,-1)=MIN(z),DROP(z,-1),DROP(z,1)))))),LAMBDA(a,MIN(TOCOL(a,2)))))

```

# Answer
> 3 votes
# , ~~68~~ ~~63~~ 57 bytes

```
f=function(l)if(L<-sum(l|1))c(m<-min(l),f(l[-L^!l[L]>m]))

```

Try it online!

-5 bytes thanks to pajonk. 50 bytes if using newer versions of R.

# Answer
> 2 votes
# Python, 53 bytes

```
f=lambda l:l and[m:=min(l)]+f(l[l[-1]>m:][:len(l)-1])

```

Attempt This Online!

Find the minimum. Remove the first element, or not, as appropriate; then take the first n−1 elements where n is the original number of elements, which removes the last element if the first wasn't removed. Call recursively.

# Answer
> 2 votes
# Swift 5.6, 96 bytes

```
func f(x:[Int])->[Int]{x.min().map{[$0]+f(x:$0==x.last ?x.dropLast():[_](x.dropFirst()))} ?? []}

```

Try it on SwiftFiddle

It's not often you see `Optional.map(_:)` used in real-world code, since it's easily confused with other operations of the same name (i.e. `Array.map(_:)`).

Ungolfed:

```
func f(_ arr: [Int]) -> [Int] {
    return arr.min()
        .map { min in
            [min] + f(
                arr.last == min
                    ? arr.dropLast()
                    : Array(arr.dropFirst()) // dropFirst is lazy by default
            )
        } ?? []
}

```

Or, written without `.map`:

```
func f(_ arr: [Int]) -> [Int] {
    if let min = arr.min() {
        return [min] + f(
            arr.last == min
                ? arr.dropLast()
                : Array(arr.dropFirst())
        )
    } else {
        return []
    }
}

```

# Answer
> 2 votes
# Arturo, 63 bytes

```
f:$[a][([]=a)?->a[m:min a@[m]++f(m=last a)?->chop a->drop a 1]]

```

Try it

# Answer
> 2 votes
# Pip, 19 bytes

```
WgIg@v=PMNgDQgELPOg

```

Takes input as multiple command-line arguments. Attempt This Online!

### Explanation

I was expecting to use recursion for this, but a plain old while loop ended up shorter.

```
WgIg@v=PMNgDQgELPOg
                    ; g is list of command-line args; v is -1 (implicit)
Wg                  ; Loop while g is not empty:
  I                 ;  If
        MNg         ;   Minimum of g
       P            ;   (Print that value)
      =             ;   Is equal to
   g@v              ;   Last element of g
                    ;  Then
           DQg      ;   Remove last element of g
              EL    ;  Else
                POg ;   Remove first element of g

```

# Answer
> 2 votes
# Haskell + hgl, 25 bytes

```
uue$mn-<(nt?.tl~<gj*=*mn)

```

## Explanation

This answer is based around the `uue` builtin, which has the type:

```
uue :: (List a -> (b, List a)) -> List a -> List b

```

This is a bit complex but it basically describes the recursion scheme we want, it accepts a function which removes a value from a list, and repeatedly applies the function until the list is empty collecting the results in a list.

With this all we have to do is build a function which takes a list and "removes" the proper value. Getting the value itself is really easy, it's the minimum, so we can just use `mn`. We just have to build the list itself. `nt` removes the last element from a list and `tl` removes the first. We combine them with the ternary `(?.)` to make `nt?.tl` which accepts a boolean and a list and removes the last if true and the first otherwise. Then we make `gj*=*mn` which takes a list and compares if the minimum `mn` and the last `gj` are equal. We combine these with `(~<)` to thread their arguments together, to build

```
nt?.tl~<gj*=*mn

```

Which removes an element based on the logic described in the question.

To finish this off we use the fanout `(-<)` to combine the parts int a single function emitting a tuple, and feed that to `uue`.

## Reflection

This is pretty good, the logic in the question itself is pretty messy, and it feels like this captures it pretty efficiently. But I'm seeing a few things that could be improved.

* I could pre-compose `uue` and variants with a fanout. This can't be done with every unfolding function, but it would save a bunch of bytes here, and has reusability.
```
uef mn$nt?.tl~<gj*=*mn

```
* `ixu` could do with a version pre-composed with `ø`. i.e. an "interate until empty" function. This would save 1 byte:
```
mn<<ixe(nt?.tl~<gj*=*mn)

```
While I'm at that I might as well add other variants, like `ixz` for "iterate until zero".

# Answer
> 1 votes
# Go, ~~166~~ 160 bytes

```
func f(I[]int)[]int{m,L,k:=I[0],len(I),I
if L<2{return I}
for _,e:=range I{if e<m{m=e}}
if m==I[L-1]{k=f(I[:L-1])}else{k=f(I[1:])}
return append([]int{m},k...)}

```

Attempt This Online!

A quick-and-dirty port of the sample implementation.

Changelog:

* `L==1 -> L<2`, `return I[0:1] -> return I`: -5 bytes

# Answer
> 1 votes
# Julia 1.0, 41 bytes

```
!l=!l[(2:end).-(l[end]==@show min(l...))]

```

Try it online!

I interpreted *"1. Find and output the smallest value in the list."* as *"print the value with garbage around it"*, hopefully that's acceptable. Also ends with an error. Otherwise, cleaner version below

## Julia 1.0, 55 bytes

```
!l=l>[] ? [(m=min(l...););!l[(2:end).-(l[end]==m)]] : l

```

Try it online!

Clean version (returns the "sorted" list)

# Answer
> 1 votes
# Excel, 136 bytes

Define `g` in *Name Manager* as:

```
=LAMBDA(a,
    LET(
        b,TAKE(a,-1),
        c,MIN(a),
        d,DROP(a,-1^(c=b)),
        e,MIN(d),
        IF(COUNT(d),VSTACK(e,g(d)))
    )
)

```

Then, within the worksheet:

```
=LET(f,A1:A4,VSTACK(MIN(f),DROP(g(f),-1)))

```

Assumes data in `A1:A4`.

# Answer
> 1 votes
# Pyth, 13 bytes

```
#=?qeQ
hSQPQt

```

Try it online!

### Explanation

```
#=?qeQhSQPQtQ    # implicitly add Q
                 # implicitly assign Q = eval(input())
#                # repeat until error
 =               # assign to Q
  ?qeQhSQ        # if the last element of Q equals the minimum element of Q (min element is printed here by newline)
         PQ      #   all but the last element of Q
           tQ    # else all but the first element of Q

```

# Answer
> -1 votes
as long as the numbers are within a small range, like `[0, 10^8)`, one could do ::::

```
 echo '1,1,3,101,2,2,2,101,103,4,3,3,4,105,1,3,0,2,1,1' |

```

> ```
>   mawk  '
>   function ______(__,___,_,____) {
>       for(_ in __) break
>       if (length(__) <= (_+=_^=NF=FS=OFS="")) {
>          if (+__[___=_--]<+__[_]) {
>                __[_]=__[___] substr("",
>                __[___]=__[_])
>       } return } _=+(____=" ")
>       for(___ in __) { !+(_=__[___]) ? ($!_=(_)____$!_) : $_=$_(____)_ }
>       return split($(_<_),__,NF=FS=OFS=____)
>   } BEGIN { CONVFMT = "%.250g"
>     ORS = "," } { printf("\n [ %s%.0s ]\n\n [ ",
>                   $_, split($_,__,",")______(__))
>     for(___ = length(__); ++_<___;) print __[_]
>     printf("%s ]\n\n", __[___]) }'
>
> ```

```
 [ 1,1,3,101,2,2,2,101,103,4,3,3,4,105,1,3,0,2,1,1 ]

 [ 0,1,1,1,1,1,2,2,2,2,3,3,3,3,4,4,101,101,103,105 ]

```

instead of doing any sort of comparisons, it's what I would call `"NF-sort"` \- it's essentially like a hybrid between counting sort and pigeonhole (aka bucket) sort,

e.g. right before the last step in the function,

> `$101 == "101 101"` \- 2 copies of the string `"101"`

although the code isn't short at all, it's a purely linear algorithm (aka `O(n)`) since no comparisons, nested loops, or recursions are needed other than for the special case of `"0"`, which are prepended at `$1` instead.

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