title: The multiples are missing

text:
# Question
Title: The multiples are missing
Given a number \\$n\\$, you are to compute the sequence of positive numbers where for each number \\$a\\$, the \\$n\\$-times multiple \\$n\cdot a\\$ is missing.

### Example

We always start with the sequence of all positive numbers: $$1,2,3,4,5,6,7,8,9,10,11,12,13,14,15, \dots$$

For \\$n=2\\$, going left-to-right, we first encounter \\$1\\$ and remove its double, \\$2\\$: $$\require{cancel}\underline{1},\\!\cancel{2}\\!,3,4,5,6,7,8,9,10,11,12,13,14,15, \dots$$

Next is in line is thus number \\$3\\$, so we remove \\$6\\$: $$1,\\!\cancel{2}\\!,\underline{3},4,5,\\!\cancel{6}\\!,7,8,9,10,11,12,13,14,15, \dots$$ Continuing, we remove the \\$8\\$ because of the \\$4\\$, then the \\$10\\$ because of the \\$5\\$, but *not* the \\$12\\$ (because the \\$6\\$ has already been removed), then the \\$14\\$ and so on: $$1,\\!\cancel{2}\\!,3,4,5,\\!\cancel{6}\\!,\underline{7},\\!\cancel{8}\\!,9,\\!\cancel{10}\\!,11,12,13,\\!\cancel{14}\\!,15, \dots$$

Likewise, for \\$n=3\\$, we get the following sequence by removing the triple of each number we encounter: $$1,2,\\!\cancel{3}\\!,4,5,\\!\cancel{6}\\!,7,8,9,10,11,\\!\cancel{12}\\!,13,14,\\!\cancel{15}\\!, \dots$$

### Task

Given a number \\$n\>1\\$ as input, compute the respective sequence as described above. The default rules for challenges apply, meaning you can either choose to

* take no further input and output the sequence indefinitely, or
* take an index \\$i\\$ as additional input and output (zero or one indexed)
    + the element at this index, or
    + all elements of the sequence up to this index.

This is , so the shortest answer in bytes in each language wins.

### Testcases

```
n=2:  [1,3,4,5,7,9,11,12,13,15,16,17,19,20,21,23,25,27,28,29,31,33,35,36,37,39,41,43,44,45,47,48,49,51,52,53,55,57,59,60,61,63,64,65,67,68,69,71,73,75,76,77,79,80,81,83,84,85,87,89,91,92,93,95,97,99,100,101,103,105,107,108,109,111,112,113,115,116,117,119,121,123,124,125,127,129,131,132,133,135,137,139,140,141,143,144,145,147,148,149]
n=3:  [1,2,4,5,7,8,9,10,11,13,14,16,17,18,19,20,22,23,25,26,28,29,31,32,34,35,36,37,38,40,41,43,44,45,46,47,49,50,52,53,55,56,58,59,61,62,63,64,65,67,68,70,71,72,73,74,76,77,79,80,81,82,83,85,86,88,89,90,91,92,94,95,97,98,99,100,101,103,104,106,107,109,110,112,113,115,116,117,118,119,121,122,124,125,126,127,128,130,131,133]
n=4:  [1,2,3,5,6,7,9,10,11,13,14,15,16,17,18,19,21,22,23,25,26,27,29,30,31,32,33,34,35,37,38,39,41,42,43,45,46,47,48,49,50,51,53,54,55,57,58,59,61,62,63,65,66,67,69,70,71,73,74,75,77,78,79,80,81,82,83,85,86,87,89,90,91,93,94,95,96,97,98,99,101,102,103,105,106,107,109,110,111,112,113,114,115,117,118,119,121,122,123,125]
n=5:  [1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19,21,22,23,24,25,26,27,28,29,31,32,33,34,36,37,38,39,41,42,43,44,46,47,48,49,50,51,52,53,54,56,57,58,59,61,62,63,64,66,67,68,69,71,72,73,74,75,76,77,78,79,81,82,83,84,86,87,88,89,91,92,93,94,96,97,98,99,100,101,102,103,104,106,107,108,109,111,112,113,114,116,117,118,119]
n=6:  [1,2,3,4,5,7,8,9,10,11,13,14,15,16,17,19,20,21,22,23,25,26,27,28,29,31,32,33,34,35,36,37,38,39,40,41,43,44,45,46,47,49,50,51,52,53,55,56,57,58,59,61,62,63,64,65,67,68,69,70,71,72,73,74,75,76,77,79,80,81,82,83,85,86,87,88,89,91,92,93,94,95,97,98,99,100,101,103,104,105,106,107,108,109,110,111,112,113,115,116]
n=17: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,103,104,105,106]

```

---

For n=2, the sequence is A003159, for n=3 A007417, and A171948 for n=4 when dropping the zero.

# Answer
> 6 votes
# Jelly, ~~7~~ 6 bytes

```
1ọḂ¬ɗ#

```

Try it online!

A full program that takes two arguments: `n` is the first and the second is the number of terms to return, starting from the first.

Thanks to @JonathanAllan for saving a byte!

## Explanation

```
1ọḂ¬ɗ#
1   ɗ# | Starting with 1, find the number of valid sequence members indicated by the second argument by testing each positive integer in turn with the following:
 ọ     | - Find out how many times the integer can be divided by the first argument
  Ḃ    | - Mod 2
   ¬   | - Not

```

# Answer
> 6 votes
# Haskell, ~~49~~ 48 bytes

```
n%a=not$mod a n<1&&n%div a n
f n=filter(n%)[1..]

```

Try it online!

`n%a` checks if there's an even amount of base-`n` zeros at the end of `a`. Laikoni saved a byte.

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

Outputs the sequence indefinitely.

```
n=>{for(k=o=[];;)o[++k]||print(o[k*n]=k)}

```

Try it online!

### Commented

```
n => {           // n = input
  for(           // infinite loop:
    k =          //   k = counter, initially zero'ish
    o = [];;     //   o[] = array to store excluded integers
  )              //
    o[++k]       //   increment k and test o[k]
    ||           //   do nothing if o[k] is truthy, otherwise:
      print(     //
        o[k * n] //     set o[k * n] to something truthy
        = k      //     and print k
      )          //
}                //

```

# Answer
> 5 votes
# Haskell, ~~35~~ 34 bytes

```
f[1..]
f(x:r)n=x:f[y|y<-r,y/=n*x]n

```

Attempt This Online!

Call with, e.g., `f[1..] 17` for \\$n=17\\$. Contructs the sequence as infinite list by a recursive approach. We start with the infite list `[1..] = [1,2,3,4,5,...]`. In every recursive call, we take the first element `x` from the list, add it to our output list and remove the number `n*x` from the remaining list `r` with a list comprehension before the next recursive call.

*Thanks to xnor for -1 byte*

# Answer
> 3 votes
# Vyxal, 5 bytes

```
⁰Ǒ₂)ȯ

```

Try it Online!

Ports jelly. Tbh I don't know why this works.

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

```
∞ʒIвγθ0¢È

```

-1 byte thanks to *@CommandMaster*.

Outputs the infinite sequence.

Try it online or verify the first 100 values of all test cases.

**Explanation:**"

The numbers that get removed are the ones with an odd amount of trailing `0`s in their base-\\$n\\$ representation. For \\$n=2\\$ this is A036554 and for \\$n=3\\$ this is A145204.

```
∞         # Push an infinite positive list: [1,2,3,...]
 ʒ        # Filter it by:
  Iв      #  Convert the current number to base-input as list
    γ     #  Group equal adjacent values together
     θ    #  Pop and keep the last group
      0¢  #  Pop and count the amount of 0s in this last group
        È #  Check if this count is even (so the odd ones are removed after the filter)

```

# Answer
> 3 votes
# \>\<\> (Fish), ~~29~~ 24 bytes

```

```

Hover over any symbol to see what it does

Try it If the above doesn't display correctly:

```
i}l2g?!v>
l::oanl/\p2*-2

```

# \>\<\> (Fish), 22 bytes

Works on every integer except 7 so not technically valid

```

```

Hover over any symbol to see what it does

Try it

# Answer
> 3 votes
# Ruby, 39 bytes

```
->n,*r{1.step{|x|r&[x]==[]&&r<<p(x)*n}}

```

Try it online!

# Answer
> 3 votes
# , 46 bytes

```
\(n)while(F<-F+1)if(all(T-F/n))T=c(T,print(F))

```

Attempt This Online!

Prints the infinite sequence of missing-multiples-of-encountered-`n`.

# Answer
> 3 votes
# Nibbles, 8.5 bytes

```
|,~%,/`=`@@*@$$@~

```

Attempt This Online!

```
|,~%,/`=`@@*@$$@~
|                 filter
 ,~                each k from 1 to ∞
           *@$      k * n
        `@@         convert to base n
      `=      $     group into chunks of equal digits
     /         @    last group
    ,               length
   %            ~   modulo 2

```

Somehow still better than 05AB1E…

# Answer
> 2 votes
# Haskell, 52 bytes

```
f m i n|i`elem`m=f m(i+1)n|1>0=i:f(n*i:m)(i+1)n
f[]1

```

Attempt This Online!

### Explanation

A somewhat "ugly" solution using the definition of the sequence rather than observations about multiplicity of factors.

```
f m i n

```

Helper function `f` takes: `m`, a list of multiples to be excluded; `i`, the current number under consideration; and `n`, the multiplier.

```
|i`elem`m=

```

If `i` is in the list `m`:

```
f m(i+1)n

```

Recursively call `f`, incrementing `i` and leaving `m` the same. (Don't add `i` to the returned list.)

```
|1>0=

```

Otherwise:

```
i:f(n*i:m)(i+1)n

```

Prepend `i` to a recursive call in which `n*i` is prepended to `m` (and `i` is incremented, as before).

```
f[]1

```

Our submission function starts with `m` empty and `i` equal to 1, and takes `n` as an argument.

# Answer
> 2 votes
# Fortran (GFortran), 115 bytes

```
program x
real::r(999)=1
n=2
i=100
do j=1,999
if(r(j)/=0)then
print*,j
r(j*n)=0
i=i-1
if(i<1)stop
end if
end do
end

```

Try it online!

`n` is the input number, `i` is the number of result values to be created.

How it works: create an array `r` of floating point numbers (because the word `real` is shorter than the word `integer`) of an adequate size (2 * `i` is enough) and set all numbers to 1. Iterate the array with the loop variable `j`. Because of its name, `j` is implicitly an integer in Fortran, while an `a` as in the challenge description would be a floating point number, which would not be allowed as a loop variable. If the value at the index `j` of `r` is not 0, the value is printed, the value at `j*n` is set to 0, and the count of pending numbers is decreased by one. If the count of pending numbers is 0, the program ends.

# Answer
> 1 votes
# Charcoal, 26 bytes

```
ＮθＮηＷ‹Ｌυη⊞υ⁺⊕↨υ⁰№×υθ⊕↨υ⁰Ｉυ

```

Try it online! Link is to verbose version of code. Outputs the first `i` values. Explanation:

```
ＮθＮη

```

Input `n` and `i`.

```
Ｗ‹Ｌυη

```

Repeat until `i` values have been found.

```
⊞υ⁺⊕↨υ⁰№×υθ⊕↨υ⁰

```

Push the next integer, but add 2 if the next integer appears in `n` vectorised multiplied by the list.

```
Ｉυ

```

Output the found values.

Would be 18 bytes to output the members of the sequence between `1` and `i` inclusive:

```
ＮθＦＮＦ¬№×υθ⊕ι⊞υ⊕ιＩυ

```

Try it online!

Alternative 18-byte version that outputs the members of the sequence between `1` and `i` inclusive in constant memory:

```
ＮθＩΦ⊕Ｎ¬﹪⌕⮌Ｘ⁰↨ιθ⁰¦²

```

Try it online! Link is to verbose version of code. Would be 17 bytes to output the members of the sequence less than `i` (remove the ).

# Answer
> 1 votes
# Perl 5.10 -n, 31 bytes

```
1while$d{++$k}||say$d{$k*$_}=$k

```

Try it online!

Translate of @Arnaulds Javascript method above.

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


# Question
Title: Is there a shorter way to get user input in python?
This is not a challenge. I'm wondering if it's at all possible to get user input into two separate variables in python (2 or 3) with less than 19 bytes. These are all the shortest I can get:

```
a,b=input(),input()
a=input();b=input() (newline replaced with semicolon for readability)
i=input;a,b=i(),i()

```

Is there any shorter way to do this?

# Answer
> 12 votes
If prompting the user doesn't matter, this is slightly shorter than `eval` for 3 or more:

```
a,b,c=map(input,[1]*3)
a,b,c=map(input,'111')

```

It's also shorter even if prompting is not ok:

```
a,b,c=map(input,['']*3)

```

Sadly, xnor's idea doesn't save anything for 2 inputs as it is still longer (19 bytes). However if you have some string (or appropriate iterable) with the appropriate length already (because magic?) then it could be shorter.

xnor found an example of a magic string for 3 inputs in Python 2 only:

```
a,b,c=map(input,`.5`)

```

This also requires that the prompts not be important, though.

This trick actually helps to save bytes for large numbers of inputs by using `1eX` notation (getting x+3 inputs):

```
 a,b,c,d,e,f=map(input,`1e3`)

```

---

Explanation:

Python's `map` function performs the function it is passed on each element of the iterable that is also passed to it, and returns the list (or map object) containing the results of these calls. For the first example, the map could be decomposed to:

```
[input(1), input(1), input(1)]

```

# Answer
> 8 votes
For 3 or more inputs, this is shorter:

```
a,b,c=eval("input(),"*3)

```

# Answer
> 4 votes
*Note that unless the question specifies the input type or requires a complete program, you can take input as function arguments, cutting out the need for* `input()`. *Where this is not an option, the following may help in certain cases.*

---

If you want single characters in the variables `a` and `b`, you can use

```
a,b=input()

```

Entering a 2 character string will then result in the first character being assigned to `a` and the second character being assigned to `b`. (Less than 2 or more than 2 characters in the string will give an error.)

If you require more than a single character per variable then this approach will not work. This could still be used to enter 2 single digit numbers as a string. If numbers beyond 9 are required then the full range of potential input characters could be interpreted as numbers.

Note that this also works for more than 2 variables:

```
a,b,c,d,e,f,g,h=input()

```

This works because in Python a string is a sequence of characters, and can be used anywhere a sequence is expected.

# Answer
> 2 votes
This may be much shorter for Python3 and inputs as integer

```
a,b,c=map(int,open(0))

```

For example expected input is: 23 45 56

The above golf code will assign respective integer values a=23, b=45, c=56

---
Tags: code-golf, tips, python
---


# Question
Title: What is the smallest possible binary output you can generate
Here is a challenge:

What is the shortest possible compiled program? Writing one line programs are fun, but they often lean on language libraries that get pulled into the final bits. How lean can you get the 'scaffolding' that supports and hooks into the compiled instructions? This seems like an interesting question because then the smallest possible program for problem 'X' is going to be: (Smallest scaffolding bytecode size) + (smallest instructions to solve probem 'x")

The code must run on a common modern OS, such as \*nix or windows (no embedded hex that runs on 1970s era mobos and chips). Doesn't matter if you are just exiting immediately, what language / platform produces the smallest bytecode? If you can get bytecode that is below a few dozen bytes, show your output.

I'll kick this off by setting a (very) low bar:

```
int main()
{
    return 0;
}

```

This compiled in VS Pro 2022 as a release build c++ app with no changes to the default build flags produces an 11k exe that runs in windows. I think I might be able to get this smaller by playing with the build flags and possibly by building it as a 32 bit c app. I'm digging into some ASM docs to see if you can still hand write exes that run on a modern OS

Lets say that IL output is fair game, but non-compiled script languages need not apply...

**A FEW ADDITIONAL NOTES**

I used the definition of a 'modern' OS as one of the criteria. People are getting this right, but I am talking about either a 32 bit or 64 bit build. I think that 32 bit is generally going to be smaller in size, but feel free to try out 64 bit builds if you are so inclined.

Be sure that you aren't making debug builds in your compiler, as this will probably include additional debugging symbols. No need for debugging these apps, they are going to run perfectly on the first try, right?

# Answer
All from the blog post linked in the question comments; this is not my work, all credit goes to Brian Raiter: https://www.muppetlabs.com/~breadbox/software/tiny/return42.html

## NASM (32-bit Linux x86 ELF), 45 bytes

```
BITS 32

        org 0x00010000

        db  0x7F, "ELF"
        dd  1
        dd  0
        dd  $$
        dw  2
        dw  3
        dd  _start
        dd  _start
        dd  4
_start: mov bl, 42          ; set ebx to exit code 42
        xor eax, eax        ; set eax to 1 (exit syscall)
        inc eax
        int 0x80            ; and exit
        db  0
        dw  0x34
        dw  0x20
        db  1

filesize    equ $ - $$

```

(https://www.muppetlabs.com/~breadbox/software/tiny/tiny-i386.asm.txt)

## NASM (64-bit Linux x86 ELF), 80 bytes

```
BITS 64

        org 0x500000000

        db  0x7F            ; e_ident
_start: db  "ELF"           ; 3 REX prefixes (no effect)
        and eax, 0x00000101
        lea edi, [rax + 42] ; rdi = exit code
        mov al, 60          ; rax = syscall number
        syscall             ; exit(rdi)
        dw  2               ; e_type
        dw  62              ; e_machine
        dd  1               ; e_version
phdr:   dd  1               ; e_entry   ; p_type
        dd  5               ; p_flags
        dq  phdr - $$       ; e_phoff   ; p_offset
        dq  phdr            ; e_shoff   ; p_vaddr
        dd  0               ; e_flags   ; p_paddr
        dw  0x40            ; e_ehsize
        dw  0x38            ; e_phentsize
        dw  1               ; e_phnum   ; p_filesz
        dw  0x40            ; e_shentsize
        dw  0               ; e_shnum
        dw  0               ; e_shstrndx
        dq  0x00400001      ; p_memsz
        dq  0               ; p_align

```

(https://www.muppetlabs.com/~breadbox/software/tiny/tiny-x64.asm.txt)

## NASM (Linux x86 a.out), 35 bytes

```
BITS 32

        org     0x1000
                            ; a.out header
        dd      0x006400CC  ;   a_info
        dd  filesize        ;   a_text
        dd      0           ;   a_data
_start:     mov bl, 42      ; set exit code ;   a_bss
        jmp short part2
        dd  0               ;   a_syms
        dd  _start          ;   a_entry
        dd  0               ;   a_trsize
        dd  0               ;   a_drsize

part2:  inc eax             ; set syscall number
        int 0x80            ; exit(ebx)

filesize    equ $ - $$

```

(https://www.muppetlabs.com/~breadbox/software/tiny/tiny-aout.asm.txt)
> 3 votes

# Answer
# x86 assembly DOS .COM file 1 byte

```
ret # assembles to 0xC3

```

COM files are executable and have no header or other mandatory content. An empty COM file produces an error, so the shortest executable COM file consists of just the RET instruction.

One way of testing this is by using DEBUG from the DOS prompt, tested using MSDOS 6.22 via pcjs. The following are typed as sequential lines (including a blank line after `ret`). However, this should also run under 32-bit Windows 7 or 10 which are ‘modern’ OSes.

```
DEBUG
n c:\test.com
a
ret

rcx
1
w
q
C:\test.com

```

Mathias Bynen’s small GitHub repo is also a useful resource for this.
> 6 votes

# Answer
# FASM (32-bit ELF executable), 87 bytes

*Larger than the final ELF-file in the blog post linked in the comments of the question, but less than a third of the size of the smallest output they were able to generate without directly creating the ELF-file, and a few bytes shorter than the shortest program without overlapping sections in the ELF-file*

```
format ELF executable 3 ; 32 bit elf
segment readable executable
entry $
  inc   eax   ; eax and ebx default to 0
  int   0x80  ; syscall 1 (exit) with exit code 0

```

produces the following (statically linked, 32-bit) ELF-executable:

```
457f 464c 0101 0301 0000 0000 0000 0000
0002 0003 0001 0000 8054 0804 0034 0000
0000 0000 0000 0000 0034 0020 0001 0028
0000 0000 0001 0000 0000 0000 8000 0804
8000 0804 0057 0000 0057 0000 0005 0000
1000 0000 cd40 0080

```

As far as I can tell the actual code takes only 3 bytes, so the main way for reducing the file size would be to somehow convince the assembler to make the different parts of the ELF-file overlap (like in the blog post)
> 4 votes

# Answer
# Python 3.4.10 (.pyc file), 63 bytes

```
00000000: ee0c 0d0a 50a6 2265 0000 0000 6300 0000  ....P."e....c...
00000010: 0000 0000 0000 0000 0001 0000 0043 0000  .............C..
00000020: 00f3 0200 0000 4753 a900 a900 a900 a900  ......GS........
00000030: a900 da00 da00 0100 0000 f300 0000 00    ...............

```

Generation script:

```
import marshal
import types

# taken from a pyc file generated from a blank file
header = b'\xee\x0c\r\nP\xa6"e\x00\x00\x00\x00'

open("c.pyc","wb").write(
    header +
    # b'\x47S' == LOAD_BUILD_CLASS + RETURN_VALUE
    # shorter than LOAD_CONST None and allows for empty co_consts tuple
    marshal.dumps(types.CodeType(0,0,0,1,67,b'\x47S',(),(),(),'','',1,b''))
    # replace TYPE_REF to empty string w/ TYPE_SHORT_ASCII_INTERNED b/c it's shorter
    .replace(b'r\x02\x00\x00\x00',b'\xda\x00')
    # replace TYPE_REF to empty tuple w/ empty TYPE_SMALL_TUPLE
    .replace(b'r\x01\x00\x00\x00',b'\xa9\x00'))

```

I believe that Python 3.4-3.5 .pyc files should be the shortest for Python 3, as they have `TYPE_SHORT_ASCII` and `TYPE_SMALL_TUPLE` (both 3.4+) and don't have `co_posonlyargcount` (3.8+), PEP 552 (3.7+), nor fixed 2-byte opcodes (3.6+).

# Python 2.7.18 (.pyc file), 79 bytes

```
00000000: 03f3 0d0a 4496 2265 6300 0000 0000 0000  ....D."ec.......
00000010: 0001 0000 0043 0000 0073 0400 0000 6400  .....C...s....d.
00000020: 0053 2801 0000 004e 2800 0000 0028 0000  .S(....N(....(..
00000030: 0000 2800 0000 0028 0000 0000 7400 0000  ..(....(....t...
00000040: 0052 0000 0000 0100 0000 5200 0000 00    .R........R....

```

Generation script:

```
import marshal
import types
header = '\x03\xf3\r\nD\x96"e'
# b"d\x00\x00S" == LOAD_CONST 0 + RETURN_VALUE
code = types.CodeType(0, 0, 1, 67, b"d\x00\x00S", (None,), (), (), "", "", 1, "")
# TYPE_STRING and TYPE_STRINGREF are the same length in Python 2.7
open("a.pyc", "w").write(header + marshal.dumps(code))

```

Unsure if this is the shortest Python 2 version; I don't have access to any earlier Python 2 versions to test.

---

Thanks to https://github.com/python/cpython/blob/3.4/Python/marshal.c and https://github.com/fedora-python/marshalparser/
> 4 votes

# Answer
# C (GCC, Linux, x86 32-bit), 260 bytes

*Feel free to edit this answer if you find ways to improve the score*

source code:

```
int _start(void){    // using libc significantly increases the score -> need to use _start instead of main
  asm("inc  %eax;"
      "int  $0x80"); // exit program seems to be the only way to exit a program without using the standard library
}

```

compiler options: `gcc -nostdlib -Oz small.c -Qn -m32 -static -s -N -Wl,--build-id=none -fno-asynchronous-unwind-tables`

hexdump:

```
00000000: 7f45 4c46 0101 0100 0000 0000 0000 0000  .ELF............
00000010: 0200 0300 0100 0000 7480 0408 3400 0000  ........t...4...
00000020: 8c00 0000 0000 0000 3400 2000 0200 2800  ........4. ...(.
00000030: 0300 0200 0100 0000 7400 0000 7480 0408  ........t...t...
00000040: 7480 0408 0400 0000 0400 0000 0700 0000  t...............
00000050: 0100 0000 51e5 7464 0000 0000 0000 0000  ....Q.td........
00000060: 0000 0000 0000 0000 0000 0000 0600 0000  ................
00000070: 1000 0000 40cd 80c3 002e 7368 7374 7274  ....@.....shstrt
00000080: 6162 002e 7465 7874 0000 0000 0000 0000  ab..text........
00000090: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000000a0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000000b0: 0000 0000 0b00 0000 0100 0000 0700 0000  ................
000000c0: 7480 0408 7400 0000 0400 0000 0000 0000  t...t...........
000000d0: 0000 0000 0100 0000 0000 0000 0100 0000  ................
000000e0: 0300 0000 0000 0000 0000 0000 7800 0000  ............x...
000000f0: 1100 0000 0000 0000 0000 0000 0100 0000  ................
00000100: 0000 0000                                ....

```
> 2 votes

---
Tags: code-challenge, optimization, assembly
---


title: Generate Conway's Atomic Elements

text:
# Question
Title: Generate Conway's Atomic Elements
### Background

The look-and-say sequence begins with \\$1\\$, each following term is generated by looking at the previous and reading each group of the same digit (eg. \\$111\\$ is three ones, so \\$111 \rightarrow 31\\$). The first few terms are $$ 1, 11, 21, 1211, 111221, 312211, \dots $$ Conway's cosmological theorem says that from any starting point, the sequence eventually becomes a sequence of "atomic elements", which are finite subsequences that never again interact with their neighbors. There are 92 such elements.

See also: Wikipedia, OEIS

### The Challenge

In this challenge you will take no input and you must output all 92 of Conway's atomic elements. The output may be in any order, and of any reasonable form for a list of numbers.

This is , so the shortest answer wins.

Sample Output:

```
22
13112221133211322112211213322112
312211322212221121123222112
111312211312113221133211322112211213322112
1321132122211322212221121123222112
3113112211322112211213322112
111312212221121123222112
132112211213322112
31121123222112
111213322112
123222112
3113322112
1113222112
1322112
311311222112
1113122112
132112
3112
1112
12
3113112221133112
11131221131112
13211312
31132
111311222112
13122112
32112
11133112
131112
312
13221133122211332
31131122211311122113222
11131221131211322113322112
13211321222113222112
3113112211322112
11131221222112
1321122112
3112112
1112133
12322211331222113112211
1113122113322113111221131221
13211322211312113211
311322113212221
132211331222113112211
311311222113111221131221
111312211312113211
132113212221
3113112211
11131221
13211
3112221
1322113312211
311311222113111221
11131221131211
13211321
311311
11131
1321133112
31131112
111312
132
311332
1113222
13221133112
3113112221131112
111312211312
1321132
311311222
11131221133112
1321131112
311312
11132
13112221133211322112211213322113
312211322212221121123222113
111312211312113221133211322112211213322113
1321132122211322212221121123222113
3113112211322112211213322113
111312212221121123222113
132112211213322113
31121123222113
111213322113
123222113
3113322113
1113222113
1322113
311311222113
1113122113
132113
3113
1113
13
3

```

# Answer
> 6 votes
# Charcoal, 174 bytes

```
Ｆ⪪⪪”}∧Ｉ*₂φ,.i\`β↷Ht≧'θvυＱ=^ι←ºρ²≡O✂⟦Ｆ!n^φ⁰γ↨ΣP@g,Ｃ[¦⟦“↥⁼>∕νＤＩwO4(fO↓;⧴�i⁷·P↨]]ＷＷＵＢ⎚Rcρw∕✳Iⅉ}⟲⊘&:'▶≕…7»↗→➙…⁶⪪✳‖↨FＭ＆⦄Ｊs/″⁷mβ⊗⊞4W⟲Ｌ.”0²«≔⊟ιθＦＩ⊟ι«⟦θ⟧≔⟦⟧ηＦθ⊞⊞Ｏη⊕∧⁼↨η⁰Ｉλ∧⊟η⊟ηＩλ≔⪫ηωθ

```

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

```
Ｆ⪪⪪”...”0²«

```

Split and loop over a compressed string of elements that aren't the result of a look-and-say of another element and the number of elements in that element's group of look-and-say derivatives.

```
≔⊟ιθ

```

Get the element.

```
ＦＩ⊟ι«

```

Loop over it and each derivative.

```
⟦θ⟧

```

Output the element.

```
≔⟦⟧η

```

Collect the look-and-say results in an array.

```
Ｆθ

```

Loop over the digits of this element.

```
⊞⊞Ｏη⊕∧⁼↨η⁰Ｉλ∧⊟η⊟ηＩλ

```

If this digit equals the last digit so far then the previous digit is removed and incremented otherwise `0` is incremented and that and the current digit is then pushed (back).

```
≔⪫ηωθ

```

Join the array to create the next element. (Note that the "last" element is never output.)

# Answer
> 6 votes
# Jelly, 47 bytes

```
ŒrF
J‘œṖ€⁸Ç9¡€F⁼ɗƇÇ9¡Ḣ)Ẏḟ®
3WWḷ;ɼÑWÇÐLƊ€ẎƲÐLḊɼU

```

Try it online!

A full program that runs with no input and outputs the 92 Conway elements. Broadly, this works by starting with `[3]`, iteratively generating the next look say sequence member and then attempting to iteratively split this into irreducible elements. Each irreducible element thus found is then passed onto the next iteration after filtering out any previously seen ones. Testing for irreducibility is done by splitting a sequence into every possible pairwise split and finding the first where nine generations of look say algorithm produces the same result as running 9 generations on the unsplit sequence. (Nine was found empirically.) Full explanation to follow.

Note the order is determined by the first time a sequence is seen with this approach, so is not the same as the order in Conway’s paper.

## Explanation

```
ŒrF                     # Helper link 1: takes a sequence of integers and returns the look say encoding (reversed)
Œr                      # Run-length encode
  F                     # Flatten

J‘œṖ€⁸Ç9¡€F⁼ɗƇÇ9¡Ḣ)Ẏḟ®  # Helper link 2: Takes a list of sequences and returns a list of sequences where each of the original ones have been split, if possible, into two
                  )     # For each sequence in list:
J                       # - Range from 1 to length of sequence
 ‘                      # - Increment by 1
  œṖ€⁸                  # - Split each of the original sequence just before the index of each of these integers
            ɗƇ          # - Keep only those where:
      Ç9¡€F             #   - The result of running helper link 1 on each half of the split and then flattening
           ⁼            #   - Is equal to:
              Ç9¡       #     - The result of running helper link 1 on the unsplit sequence
                 Ḣ      # - Take the first valid split (which will be the original sequence and an empty list if there is no split possible)
                   Ẏ    # Join outer lists together
                    ḟ®  # Filter out any sequences already held in the register

3WWḷ;ɼÑWÇÐLƊ€ẎƲÐLḊɼU    # Main link: takes no arguments and returns a list of all 92 elements
3WW                     # Start with 3 wrapped in a list and wrapped again (i.e. [[3]])
              ƲÐL       # Repeat the following until no change between iterations:
    ;ɼÑ                 # - Concatenate the current list of elements to the register
   ḷ                    # - But then revert to the current list of elements
           Ɗ€           # - For each element in the list:
      Ñ                 #   - Use helper link 1 to generate the next look say sequence from this
       W                #   - Wrap this in a list
        ÇÐL             #   - Then use helper link 2 to iteratively split the sequence into irreducible elements
             Ẏ          # - Join outer lists
                 Ḋɼ     # Remove the first member of the list in the register (will be a 0 that started off there originally)
                   U    # Finally, reverse each element (since helper link 1 generates them reversed)

```

Created with the help of Luminespire.

## Alternative without use of the register, 49 bytes

```
ŒrF
J‘œṖ€⁸Ç9¡€F⁼ɗƇÇ9¡Ḣ
3WW,⁸ÑWÇ€ẎḟɗƬṪʋ€Ẏ,ɗ;¥/ÐLṪU

```

Try it online!

# Answer
> 2 votes
# 05AB1E, ~~104~~ 103 bytes

```
3 90FDÅγs.ιJ•KтË:äþÒ¶Æ₁Ž“cì¥%ât5)§65g-Aér)тθñ.µBηâε;Ü∍ï¨ZÀи}â*5ü”7₃Lƒ-ñh5!•43вNè•"[¯₁Šä•₂в.¥Nåi£ë.£]22)

```

Outputs Conway's atomic elements in reversed order as list.

Try it online.

**Explanation:**

If we look at the *Element name* and *Decays into* of the Wikipedia table, we can see that a lot of the *Decays into* are just a single element. The others are either at the start or end, with the exceptions of `Ho.Pa.H.Ca.Co` to `Ca` (Atomic Number 21) and `Hf.Pa.H.Ca.Li` to `H` (Atomic Number 2), although those still work fine if we take a portion of another element at the start/end instead.

I basically generate all Conway's atomic elements in reversed order, starting at `3`, taking either the leading or trailing portion of the correct output-length. I'll take the leading portion if the (0-based) index is one of `[19,23,24,28,30,34,52,53,59,67]`, and the trailing portion (or full look-and-say number) otherwise. And because this would end with `12`, I drop that value (by looping one iteration less) and add a hard-coded `22` instead.

```
3             # Start with a 3
90F           # Loop `N` in the range [0,90):
   D          #  Duplicate the current value
   Åγs.ιJ     #  Convert it to its look-and-say number:
   Åγ         #   Run-length encode the number into two separated lists of values and lengths
     s        #   Swap so the list of values is at the top of the stack
      .ι      #   Interleave the lists of lengths and values together
        J     #   Join this list together to a single string
   •KтË:äþÒ¶Æ₁Ž“cì¥%ât5)§65g-Aér)тθñ.µBηâε;Ü∍ï¨ZÀи}â*5ü”7₃Lƒ-ñh5!•
              #  Push compressed integer 50110820926426684400408736251820828634922551372994851769669719792848756768639391390052494466780374103702329447321431509239639153836796651173069320
    43в       #  Convert it to base-43 as list: [2,4,4,6,10,12,7,10,10,9,12,14,18,24,28,34,42,27,32,5,6,10,14,9,7,12,16,11,7,6,3,6,8,10,5,6,8,14,18,13,7,5,8,10,12,18,24,21,15,20,28,23,7,7,10,14,16,20,26,23,17,3,6,8,5,8,12,5,8,14,16,2,4,4,6,10,12,7,10,10,9,12,14,18,24,28,34,42,27,32]
       Nè     #  Index the current loop-index `N` into this list
              #  (let's call this value, which are the lengths of the outputs, `L`)
   •"[¯₁Šä•  "#  Push compressed integer 104005171539992
    ₂в        #  Convert it to base-26 as list: [19,4,1,4,2,4,18,1,6,8]
      .¥      #  Undelta it with leading 0: [0,19,23,24,28,30,34,52,53,59,67]
        Nåi   #  If the current loop-index `N` is in this list:
           £  #   Keep the first `L` amount of digits from the current string
          ë   #  Else:
           .£ #   Keep the last `L` amount of digits from the current string
  ]           # Close both the if-statement and loop
   22         # Push the final edge-case value 22
     )        # Wrap everything on the stack into a list
              # (which is output implicitly as result)

```

See this 05AB1E tip of mine (sections *How to compress large integers?* and *How to compress integer lists?*) to understand how the compressed integers(-lists) work.

: For the full numbers it doesn't matter if we take the leading or trailing portion. So the additional `0` in the undelta-list `[0,19,23,24,28,30,34,52,53,59,67]` loopup list, won't make any difference in the output for this first (length 2) value `13`.

# Answer
> 1 votes
# Ruby, ~~256~~ 201 bytes

```
z=?3;"7773398pr20540910737b10720340557d19713567l19f39r10710760n17h1h33353054b26773398pr272100".scan(/.../){|x|a,b,c=x.chars.map{|r|r.to_i 36};a.times{z=p(z).gsub(/(.)\1*/){|a|"#{a.size}#$1"}};z=z[b,c]}

```

Try it online!

Use the sequence from the linked page starting with '3'.

# Answer
> 1 votes
# Retina 0.8.2, 396 bytes

```

221¶3122113222122211211232221122¶1232221128¶13221123¶126¶311324¶321123¶3123¶132211331222113321¶311311222113111221132221¶31121126¶11121331¶123222113312221131122111¶3113221132122213¶1322113312221131122111¶132116¶31122211¶13221133122111¶111315¶1324¶11132222¶132211331121¶13211323¶3113112221¶111324¶3122113222122211211232221132¶1232221138¶13221133¶37
%`.$
$*#
{%`#$

#+
$&¶$%`
(?=(\d).*#)(\1)+
$#2$1

```

Try it online! Explanation: Port of my Charcoal answer.

```

221¶3122113222122211211232221122¶1232221128¶13221123¶126¶311324¶321123¶3123¶132211331222113321¶311311222113111221132221¶31121126¶11121331¶123222113312221131122111¶3113221132122213¶1322113312221131122111¶132116¶31122211¶13221133122111¶111315¶1324¶11132222¶132211331121¶13211323¶3113112221¶111324¶3122113222122211211232221132¶1232221138¶13221133¶37

```

Insert the base elements each with the count of derived elements appended to them.

```
%`.$
$*#

```

Convert the element counts to unary.

```
{`

```

Repeat until all elements have been derived.

```
%`#$

```

Decrement the remaining count by 1 for each element.

```
#+
$&¶$%`

```

Duplicate each unfinished element, but without the count.

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

```

Perform the look-and-say to derive the next element.

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

Uses the construction described on this page (linked from OEIS and pointed out by Level River St).

```
B=Buffer;for(i in[...q=B(s="(3(d   3   38(499  !4M( =3(d2")])for(v=q[i]*96+B(".:oyKhZXY;LhXMH:xX]x(ZJKU:oyp")[i]-3104,k=0;k<=v%8;console.log(k++?s:s=s.substr(v>>8,v/8&31)))s=s.replace(/(.)\1*/g,s=>s.length+s[0])

```

Try it online!

# Answer
> 1 votes
# Ruby, 222 bytes

A full program printing output in reverse order to the question. Longer than I had hoped for with this approach, but will be golfed when I have time.

```
w="\2[IGBeECQwggWOUEGMecgKgie[IG"
s=?3
j=0
q=0xa02411270730708b3140480
92.times{|k|p s
c=0
(s+t=b=?X).chars{|i|i!=b ? t+=c.to_s+b*c=1:c+=1;b=i}
s=t[3,99]
(0<1&q/=2)&&(v=w[j-=1].ord;s=s[(v/32-3)*v%=32,v])}

```

Try it online!

Starting with `3` we work through the look and say sequence as shown on http://www.se16.info/js/lands2.htm . At the branch points it is only necessary to carry on with exactly one branch. These are binary encoded in magic number `q`.

The sequence on the linked page actually uses a branch at the beginning or the end of the current string (even in the case `21Sc -> 20Ca` although it is not explained that way.) The only exception is `1H` where the required substring `22` is found at position `-6` (six from the right) in the output of the previous step (amongst other positions.)

The magic string encodes (from right to left) in each character the number of characters in the branch, as well as the number `3` or `2` for the index (in the format `index code * 32 + length`). When 3 is subtracted from the code, we get `(3-3)*l=0` for substrings that appear at the beginning, and `(2-3)*l=-l` for substrings that appear at the end. Ruby interprets `-l` as `l` characters from the righthand end of the string and extracts the correct characters.

For `2H` an escape sequence gives ASCII 2 which gives `l=2` and `(0-3)*2=-6` giving the correct characters for `2H`.

---
Tags: code-golf, kolmogorov-complexity
---


title: Sort an Integer List

text:
# Question
Title: Sort an Integer List
# The Challenge

It's quite simple really, sort a list of numbers.

# Details

You must sort a list of numbers in ascending order, without using any built-in sorting functions/libraries/etc (i.e. `list.sort()` in Python).

Input/output can be done in any method you choose, as long as it is human readable.

Standard loopholes are disallowed as always.

Shortest code in bytes wins.

You must explain/list what sort method you used (Bubble, Insertion, Selection, etc.)

Input will not contain duplicates.

# Sample Input/Output

Input: `99,-2,53,4,67,55,23,43,88,-22,36,45`

Output: `-22,-2,4,23,36,43,45,53,55,67,88,99`

Note: A near direct opposite of Sort a List of Numbers

# Answer
# 05AB1E, 2 bytes

Code:

```
œß

```

Same algorithm as the Jelly answer. Computes all permutations of the input and pops out the smallest one.

Try it online!

---

A more efficient method is:

```
E[ß,Ž

```

Performs **selection sort**. Uses **CP-1252** encoding.

Try it online!
> 24 votes

# Answer
# Jelly, 3 bytes

```
Œ!Ṃ

```

This generates all permutations of the input list, then selects the lexographically smallest permutation. *Very* efficient.

Credits to @Adnan who had the same idea independently.

Try it online!

---

# Jelly, 4 bytes

```
ṂrṀf

```

This builds the range from the minimum of the list to the maximum of the list, then discards the range elements not present in the original list. This is technically a **bucket sort**, with very small buckets. I'm not aware of a name for this specific variant.

Try it online!

### How it works

```
ṂrṀf  Main link. Argument: A (list/comma-separated string)

Ṃ     Compute the minimum of A.
  Ṁ   Compute the maximum of A.
 r    Yield the inclusive range from the minimum to the maximum.
   f  Filter the range by presence in A.

```
> 21 votes

# Answer
# Python, 46 45 bytes

```
lambda l:[l.pop(l.index(min(l)))for _ in 1*l]

```

Simple selection sort.
> 14 votes

# Answer
# x86-16 machine code (BubbleSort int8\_t), ~~20~~ 19 bytes

# x86-64/32 machine code (JumpDownSort) ~~21~~ 19 bytes

Changelog:

* Thanks to @ped7g for the `lodsb`/`cmp [si],al` idea, and putting that together with a pointer increment / reset that I'd been looking at. Not needing `al`/`ah` lets us use nearly the same code for larger integers.
* New (but related) algorithm, many implementation changes: Bubbly SelectionSort allows a smaller x86-64 implementation for bytes or dwords; break-even on x86-16 (bytes or words). Also avoids the bug on size=1 that my BubbleSort has. See below.
* It turns out that my Bubbly Selection Sort with swaps every time you find a new min is already a known algorithm, JumpDown Sort. It's mentioned in Bubble Sort: An Archaeological Algorithmic Analysis (i.e. how did Bubble Sort become popular despite sucking in general for speed).

---

**Sorts 8-bit signed integers in-place**. (Unsigned is the same code size, just change the `jge` to a `jae`). Duplicates are not a problem. We swap using a 16-bit rotate by 8 (with a memory destination).

**Bubble Sort sucks for performance**, but I've read that it's one of the smallest to implement in machine code. This seems especially true when there are special tricks for swapping adjacent elements. This is pretty much its only advantage, but sometimes (in real life embedded systems) that's enough advantage to use it for very short lists.

**I omitted the early termination on no swaps**. I used Wikipedia's "optimized" BubbleSort loop which avoids looking at the last `n − 1` items when running for the `n`-th time, so the outer loop counter is the upper bound for the inner loop.

NASM listing (`nasm -l /dev/stdout`), or plain source

```
 2 address  16-bit       bubblesort16_v2:
 3          machine      ;; inputs: pointer in ds:si,  size in in cx
 4          code         ;; requires: DF=0  (cld)
 5          bytes        ;; clobbers: al, cx=0
 6
 7 00000000 49               dec     cx          ; cx = max valid index.  (Inner loop stops 1 before cx, because it loads i and i+1).
 8                       .outer:                 ; do{
 9 00000001 51               push    cx          ;   cx = inner loop counter = i=max_unsorted_idx
10                       .inner:                 ;   do{
11 00000002 AC               lodsb               ;     al = *p++
12 00000003 3804             cmp     [si],al     ;     compare with *p (new one)
13 00000005 7D04             jge     .noswap
14 00000007 C144FF08         rol     word [si-1], 8    ; swap
15                       .noswap:
16 0000000B E2F5             loop    .inner      ;   } while(i < size);
17 0000000D 59               pop     cx          ;  cx = outer loop counter
18 0000000E 29CE             sub     si,cx       ;  reset pointer to start of array
19 00000010 E2EF             loop    .outer      ; } while(--size);
20 00000012 C3               ret

22 00000013  size = 0x13 = 19 bytes.

```

push/pop of `cx` around the inner loop means it runs with `cx` = outer\_cx down to 0.

Note that `rol r/m16, imm8` is not an 8086 instruction, it was added later (186 or 286), but this isn't trying to be 8086 code, just 16-bit x86. If SSE4.1 `phminposuw` would help, I'd use it.

A 32-bit version of this (still operating on 8-bit integers but with 32-bit pointers / counters) is 20 bytes (operand-size prefix on `rol word [esi-1], 8`)

Bug: size=1 is treated as size=65536, because nothing stops us from entering the outer do/while with cx=0. (You'd normally use `jcxz` for that.) But fortunately the 19-byte JumpDown Sort is 19 bytes and doesn't have that problem.

---

**Original x86-16 20 byte version** (without Ped7g's idea). Omitted to save space, see the edit history for it with a description.

---

**Performance**

Partially-overlapping store/reload (in memory-destination rotate) causes a store-forwarding stall on modern x86 CPUs (except in-order Atom). When a high value is bubbling upwards, this extra latency is part of a loop-carried dependency chain. Store/reload sucks in the first place (like 5 cycle store-forwarding latency on Haswell), but a forwarding stall brings it up to more like 13 cycles. Out-of-order execution will have trouble hiding this.

See also: Stack Overflow: bubble sort for sorting string for a version of this with a similar implementation, but with an early-out when no swaps are needed. It uses `xchg al, ah` / `mov [si], ax` for swapping, which is 1 byte longer and causes a partial-register stall on some CPUs. (But it may still be better than memory-dst rotate, which needs to load the value again). My comment there has some suggestions...

---

# x86-64 / x86-32 JumpDown Sort, 19 bytes (sorts int32\_t)

Callable from C using the x86-64 System V calling convention as
`int bubblyselectionsort_int32(int dummy, int *array, int dummy, unsigned long size);` (return value = max(array\[\])).

This is https://en.wikipedia.org/wiki/Selection\_sort, but **instead of remembering the position of the min element, swap the current candidate into the array**. Once you've found the min(unsorted\_region), store it to the end of the sorted region, like normal Selection Sort. This grows the sorted region by one. (In the code, `rsi` points to one past the end of the sorted region; `lodsd` advances it and `mov [rsi-4], eax` stores the min back into it.)

The name Jump Down Sort is used in Bubble Sort: An Archaeological Algorithmic Analysis. I guess my sort is really a Jump Up sort, because high elements jump upwards, leaving the bottom sorted, not the end.

This exchange design leads to the unsorted part of the array ending up in mostly reverse-sorted order, leading to lots of swaps later on. (Because you start with a large candidate, and keep seeing lower and lower candidates, so you keep swapping.) I called it "bubbly" even though it moves elements the other direction. The way it moves elements is also a little bit like a backwards insertion-sort. To watch it in action, use GDB's `display (int[12])buf`, set a breakpoint on the inner `loop` instruction, and use `c` (continue). Press return to repeat. (The "display" command gets GDB to print the whole array state every time we hit the breakpoint).

`xchg` with mem has an implicit `lock` prefix which makes this extra slow. Probably about an order of magnitude slower than an efficient load/store swap; `xchg m,r` is one per 23c throughput on Skylake, but load / store / mov with a tmp reg for an efficient swap(reg, mem) can shift one element per clock. It might be a worse ratio on an AMD CPU where the `loop` instruction is fast and wouldn't bottleneck the inner loop as much, but branch misses will still be a big bottleneck because swaps are common (and become more common as the unsorted region gets smaller).

```
 2 Address               ;; hybrib Bubble Selection sort
 3        machine         bubblyselectionsort_int32:   ;; working, 19 bytes.  Same size for int32 or int8
 4        code               ;; input: pointer in rsi, count in rcx
 5        bytes              ;; returns: eax = max
 6
 7                           ;dec  ecx           ; we avoid this by doing edi=esi *before* lodsb, so we do redundant compares
 8                                               ; This lets us (re)enter the inner loop even for 1 element remaining.
 9                       .outer:
10                           ; rsi pointing at the element that will receive min([rsi]..[rsi+rcx])
11 00000000 56               push   rsi
12 00000001 5F               pop    rdi
13                           ;mov    edi, esi     ; rdi = min-search pointer
14 00000002 AD               lodsd
16 00000003 51               push   rcx          ; rcx = inner counter
17                       .inner:                   ; do {
18                           ; rdi points at next element to check
19                           ; eax = candidate min
20 00000004 AF               scasd                 ; cmp eax, [rdi++]
21 00000005 7E03             jle  .notmin
22 00000007 8747FC           xchg   [rdi-4], eax   ; exchange with new min.
23                         .notmin:
24 0000000A E2F8             loop  .inner          ; } while(--inner);
26                           ; swap min-position with sorted position
27                           ; eax = min.  If it's not [rsi-4], then [rsi-4] was exchanged into the array somewhere
28 0000000C 8946FC           mov    [rsi-4], eax
29 0000000F 59               pop   rcx           ; rcx = outer loop counter = unsorted elements left
30 00000010 E2EE             loop  .outer        ; } while(--unsorted);
32 00000012 C3               ret

34 00000013 13           .size: db $ - bubblyselectionsort_int32
           0x13 = 19 bytes long

```

Same code size for `int8_t`: use `lodsb` / `scasb`, `AL`, and change the `[rsi/rdi-4]` to `-1`. The same machine-code works in 32-bit mode for 8/32-bit elements. 16-bit mode for 8/16-bit elements needs to be re-built with the offsets changed (and 16-bit addressing modes use a different encoding). But still 19 bytes for all.

It avoids the initial `dec ecx` by comparing with the element it just loaded before moving on. On the last iteration of the outer loop, it loads the last element, checks if it's less than itself, then is done. This allows it to work with size=1, where my BubbleSort fails (treats it as size = 65536).

I tested this version (in GDB) using the this caller: Try it online!. You can run this it on TIO, but of course no debugger or printing. Still, the `_start` that calls it exits with exit-status = largest element = 99, so you can see it works.
> 13 votes

# Answer
# Brachylog, ~~12~~ 7 bytes

```
p.'(s>)

```

This uses permutation sort, which is obviously terrible, but hey it's shorter than Pyth!

### Explanation

```
p.       Unifies the output with a permutation of the input
  '(  )  True if what's inside the parentheses cannot be proven, else backtrack and
         try with another permutation of the input.
    s    Take an ordered subset from the output
     >   True if the first element is bigger than the second (hence not sorted)
         We don't need to check that the subset is 2 elements long because > will be false
         for inputs that are not 2 elements long anyway

```
> 10 votes

# Answer
# Oracle SQL 11.2, 205 bytes

```
WITH s AS(SELECT COLUMN_VALUE||''e FROM XMLTABLE(('"'||REPLACE(:1,',','","')||'"'))),v(p,f)AS(SELECT e,e FROM s UNION ALL SELECT p||','||e,e FROM v,s WHERE e+0>f)SELECT p FROM v WHERE LENGTH(p)=LENGTH(:1);

```

Un-golfed

```
WITH
s AS  -- Split the string using ',' as separator
(     -- ||'' cast the xml type to varchar
  SELECT COLUMN_VALUE||''e FROM XMLTABLE(('"'||REPLACE(:1,',','","')||'"'))
),
v(p,f) AS  -- Recursive view : p = sorted string, f last number added
(
  SELECT e,e FROM s -- use each number as seed
  UNION ALL         -- only add a number if it is > the last added
  SELECT p||','||e,e FROM v,s WHERE e+0>f  -- +0 is needed to compare int and not strings
)
-- The valid string has the same length as the input
SELECT p FROM v WHERE LENGTH(p)=LENGTH(:1)

```

As for what sort method it is, I have no idea, `ORDER BY` made sure I forgot them.
> 10 votes

# Answer
## Haskell, 38 bytes

```
h%t|(a,b)<-span(<h)t=a++h:b
foldr(%)[]

```

The binary function `%` insert a new element `h` into a sorted list `t` by partitioning `t` into a prefix `a` of elements `<h` and a suffix `b` of elements `>h`, and sticks in `h` between them.

The operation `foldr(%)[]` then builds up a sorted list from empty by repeatedly inserting elements from the input list.

This is one byte shorter than the direct recursive implementation

```
f(h:t)|(a,b)<-span(<h)$f t=a++h:b
f x=x

```

Another strategy for 41 bytes:

```
f[]=[]
f l|x<-minimum l=x:f(filter(/=x)l)

```
> 9 votes

# Answer
## JavaScript (ES6), 51 bytes

```
a=>a.map(_=>m=Math.min(...a.filter(e=>e>m)),m=-1/0)

```

Each loop finds the smallest number that hasn't been found so far.
> 8 votes

# Answer
## Haskell, ~~42~~ ~~41~~ 38 bytes

```
f u=filter(`elem`u)[(minBound::Int)..]

```

Loops through all integers (signed 64bit, on my machine) and keeps those that are in `u`. Of course it doesn't finish in reasonable time.

The previous version looped through `[minimum u..maximum u]` which has the same worst case running time.

Edit: @xnor saved a byte. Thanks!
> 8 votes

# Answer
## Python 2, 34 bytes

```
def f(s):m=min(s);print m;f(s-{m})

```

Takes input as a set, printing its elements in increasing order, terminating with error.

A clean termination can be done in 41 bytes:

```
def f(s):
 if s:m=min(s);print m;f(s-{m})

```

or

```
l=input()
while l:m=min(l);print m;l-={m}

```

The input can be take as a list for 39 bytes, or 38 bytes in Python 3.5:

```
def f(l):m=min(l);print m;f(set(l)-{m})
def f(l):m=min(l);print(m);f({*l}-{m})

```
> 8 votes

# Answer
# C, 72 bytes

```
i,j;a(int*l,int n){for(i=0;i=i?:--n;j>l[n]?l[i]=l[n],l[n]=j:0)j=l[--i];}

```

Bubblesort. The first argument is a pointer to the array, the second argument is the length of the array. Works with gcc.
> 7 votes

# Answer
# Python 3, ~~91~~ ~~62~~ 47 bytes

```
def f(z):
 while z:m=min(z);z.remove(m);yield m

```

Thanks to wnnmaw and Seeq for golfing help.

The argument `z` should be a list. This is a variant of selection sort.

I'm not sure how `min` stacks up against `built-in sorting functions`, since I'm not sure how Python implements `min`. Hopefully, this solution is still okay. Any golfing suggestions in the comments or in PPCG chat are welcome.
> 5 votes

# Answer
# MATL, ~~11~~ 10 bytes

```
Y@t!d0>AY)

```

Extremely inefficient examination of all permutations of the input.

**Try it Online!**

**Explanation**

```
        % Implicitly grab input array
Y@      % Compute all permutations (each permutation as a row)
t       % Duplicate this matrix
!d      % Transpose and take the differences between the values
0>A     % Find the rows where all differences are > 0
Y)      % Return only the row where this is true
        % Implicitly display the result

```
> 5 votes

# Answer
# Python, 120 Bytes

```
def f(a):import time,threading;[threading.Thread(None,lambda b=b,c=min(a):print(time.sleep(b-c)or b)).start()for b in a]

```

This probably won't be the shortest answer but I feel like this algorithm belongs here. call with a list of integers, they'll be printed in a sorted manner to stdout. I wouldn't try it with too large numbers though.
> 5 votes

# Answer
# Ruby, 40 bytes

Selection sort. Anonymous function; takes the list as argument.

```
->a{r=[];r<<a.delete(a.min)while[]!=a;r}

```
> 5 votes

# Answer
# Awk, 66 bytes

```
{b=$0;a[b]}m<b{m=b}n>b{n=b}END{for(i=n;i<=m;i++)if(i in a)print i}

```

Arrays in awk are like dictionaries, not like C arrays. The indexes can be non-contiguous, and they grow (and are created) as needed. So, we create an array `a` for the input, with each line being a key. And we save the min and max values. Then we loop from min to max, and print all keys which exist in `a`. `b` is just to avoid repeated usage of `$0`.
> 5 votes

# Answer
# Pyth - ~~15~~ ~~13~~ ~~11~~ 10 bytes

*Two bytes saved thanks to @Jakube.*

Bogosort.

```
f!s>VTtT.p

```

Try it online here.

I don't need the `h` cuz we are guaranteed no duplicates.
> 4 votes

# Answer
# MATL, 11 bytes

```
`t4#X<2#)tn

```

**Try it online!**

This sorts by the following procedure, which is *O*(*n*2):

1. Take the minimum of the array.
2. Remove that value from the array, and store it for subsequent display.
3. Apply the same procedure with the rest of the array, until it becomes empty.
4. Display all numbers in the order in which they were obtained.

MATL is stack-based. The array with remaining values is kept at the top of the stack. The removed values are below, in order. At the end of the program all those values are displayed. The array at the top would also be displayed, but since it's empty it's not shown.

```
`        % Do...while loop
  t      %   Duplicate. Implicitly take input in the first iteration
  4#X<   %   Compute index of mininum of the array
  2#)    %   Push the minimum, and then the array with remaining entries
  tn     %   Duplicate and push number of elements, to be used as loop condition
         % Implicitly end do...while loop
         % Implicitly display stack contents

```
> 4 votes

# Answer
## Java 8, ~~112~~ 92 bytes

Here is another selection sort. The input is a `List t` of integers and the sorted output is printed to standard out.

```
t->{for(;0<t.size();System.out.println(t.remove(t.indexOf(java.util.Collections.min(t)))));}

```

**Update**

* **-20** \[16-08-21\] Used a lambda
> 4 votes

# Answer
# MIPS, 68 bytes

I wrote a simple unoptimized bubble sort implementation a while ago. Byte count begins at `loop` and ends at `li $v0, 10`, assuming that the list address and list length are already in memory.

```
 Address    Code        Basic                     Source

0x00400000  0x3c011001  lui $1,4097           5    main:   la      $s0, list       # List address
0x00400004  0x34300000  ori $16,$1,0
0x00400008  0x2411000a  addiu $17,$0,10       6            li      $s1, 10         # List length
0x0040000c  0x24080000  addiu $8,$0,0         8    loop:   li      $t0, 0          # swapped
0x00400010  0x24090001  addiu $9,$0,1         9            li      $t1, 1          # for loop "i"
0x00400014  0x1131000b  beq $9,$17,11         11   for:    beq     $t1, $s1, fend  # break if i==length
0x00400018  0x00095080  sll $10,$9,2          13           sll     $t2, $t1, 2     # Temp index, multiply by 4
0x0040001c  0x01505020  add $10,$10,$16       14           add     $t2, $t2, $s0   # Combined address
0x00400020  0x8d4b0000  lw $11,0($10)         15           lw      $t3, 0($t2)     # list[i]
0x00400024  0x8d4cfffc  lw $12,-4($10)        16           lw      $t4, -4($t2)    # list[i-1]
0x00400028  0x21290001  addi $9,$9,1          18           addi    $t1, $t1, 1     # i++
0x0040002c  0x016c082a  slt $1,$11,$12        20           ble     $t4, $t3, for   # if list[i-1] > list[i]
0x00400030  0x1020fff8  beq $1,$0,-8
0x00400034  0xad4bfffc  sw $11,-4($10)        21           sw      $t3, -4($t2)    # swap and store
0x00400038  0xad4c0000  sw $12,0($10)         22           sw      $t4, 0($t2)
0x0040003c  0x24080001  addiu $8,$0,1         23           li      $t0, 1          # swapped=true
0x00400040  0x08100005  j 0x00400014          24           j       for
0x00400044  0x20010001  addi $1,$0,1          26   fend:   subi    $s1, $s1, 1     # length--
0x00400048  0x02218822  sub $17,$17,$1
0x0040004c  0x1500ffef  bne $8,$0,-17         27           bnez    $t0, loop       # Repeat if swapped==true
0x00400050  0x2402000a  addiu $2,$0,10        29           li      $v0, 10
0x00400054  0x0000000c  syscall               30           syscall

```

Now I wait to be blown out of the water with x86...
> 4 votes

# Answer
# Julia, ~~28~~ 27 bytes

```
x->colon(extrema(x)...)∩x

```

Try it online!
> 4 votes

# Answer
## Seriously, 6 bytes

```
,;l@╨m

```

Try it online!

This does the same thing as many other answers: generate all permutations, select minimum. I kinda forgot that this would work while I was working on the below solution.

Explanation:

```
,;l@╨m
,;l@    push len(input), input
    ╨m  minimum permutation

```

---

## Seriously, 25 bytes (non-competing)

This would be competitive if it wasn't for a bug in the shuffle command that I just fixed.

```
,1WX╚;;pX@dXZ`i@-0<`MπYWX

```

Try it online! This implements the best sorting algorithm ever: Bogosort!

Explanation:

```
,1WX╚;;pX@dXZ`i@-0<`MπYWX
,                          get input
 1W                    WX  do-while:
   X                         discard
    ╚                        shuffle
     ;;                      dupe twice
       pX@dX                 remove first element of first dupe and last element of second dupe
            Z                zip
             `i@-0<`MπY      test if all differences are positive (if any are not, the list is not sorted), negate (1 if not sorted else 0)

```
> 3 votes

# Answer
# MATL, ~~17~~ 16 bytes

Saved one byte creating null array thanks to @LuisMendo

```
vTbtX<-QI$(f8M+q

```

Bucket sort. Don't try it with a range greater than 231-1.

Try it online!

**Explanation**

```
v                  % push an empty array
 T                 % push 1
  b                % bubble the input array up to the top of the stack
   t               % duplicate it
    X<             % find the minimum
      -            % subtract min from input array
       Q           % and increment to adjust for 1-based indexing
        I$(        % resulting array used as indices of empty array
                   % (the [] way up at the top) that are assigned 1 (from T)
           f       % find the nonzero indices
            8M     % magically retrieve the 4th previous function input :/
                     (aka, the min input array value)
              +    % add it to the indices
               q   % and decrement

```

---

TIL:

* You can initialize an empty array in MATL using `[]` and grow it, just like in MATLAB
* How to use `(` for assignment indexing
* How to use the `M` automatic clipboard

---

New day, new TIL:

* `vertcat` magically creates an empty array when there's nothing on the stack to concatenate
> 3 votes

# Answer
# R, 68 Bytes

Takes input `i` and outputs `o` which is the sorted list.

```
o<-i
for(j in 1:length(i)){
x<-(i-min(i))==0
o[j]<-i[x]
i<-i[!x]
}
o

```

Explanation:

```
o<-i                      # Defines output as o
 for(j in 1:length(i)){   # Initializes loop for length of input
  x<-(i-min(i))==0        # Generates logical vector by finding the value 0
                          # of input less the minimum of input.
   o[j]<-i[x]             # Puts the smallest value at position j
    i<-i[!x]              # Removes the smallest value from input
      }                   # Ends loop
       o                  # Returns sorted list

```

Avoiding the permutations means it can sort large lists relatively quickly. The "trick" is that subtracting the smallest value from the input leaves a single 0 that determine both the smallest value and the position of the smallest value.
> 3 votes

# Answer
## Clojure, ~~73~~ 35 bytes

Bogosort :)

```
#(if(apply < %)%(recur(shuffle %)))

```

Earlier version:

```
#(reduce(fn[r i](let[[a b](split-with(partial > i)r)](concat a[i]b)))[]%)

```

Reduces to a sorted list `r` by splitting it into "smaller than i" and "larger than i" parts. I guess this is the insertion sort.
> 3 votes

# Answer
# Python 3, 53 bytes

```
lambda l:[i for i in range(min(l),max(l)+1)if i in l]

```

Try it online!
> 3 votes

# Answer
# , 47 bytes

implements bogosort.

```
function(l){while(is.unsorted(l))l=sample(l);l}

```

Try it online!
> 3 votes

# Answer
# Retina, 95

Modified bubble sort. I suspect there are much better ways to do this, even without the retina sort builtin.

```
-\d+
$*n
\d+
$*11
+`(1+) (n+)
$2 $1
+`\b(n+) (\1n+)|(1+)(1+) \3\b
$2$3 $1$3$4
1(1*)
$.1
n+
-$.&

```
* Stage 1 - convert -ve integers to unary with `n` as the digit; drop the `-` signs.
* Stage 2 - convert +ve and zero integers to unary with `1` as the digit; add `1` to each one, so that zero is represented by `1`.
* Stage 3 - Move all -ves to the front.
* Stage 4 - Sort: move all -ves with the largest magnitude (i.e. smallest numerical) ahead of higher -ves. Move smaller +ves ahead of larger +ves.
* Stage 5 - Remove 1 from, and convert +ve unaries back to decimal.
* Stage 6 - convert -ve unaries back to decimal, including sign.

Try it online.
> 2 votes

# Answer
# Ruby, 22 bytes

A *quick* permutation sort. Runs in O(n!) space and time.

```
->a{a.permutation.min}

```
> 2 votes

# Answer
## Ruby, ~~26~~ 24 bytes

Selection sort, similar to Value Ink's answer, but using a different approach for greater golfiness.

According to the specification: "Input/output can be done in any method you choose, as long as it is human readable". I think this fits the description, output is an array of arrays with a single element.

```
->l{l.map{l-l-=[l.min]}}

```

example:

```
->l{l.map{l-l-=[l.min]}}[[2,4,3,1]]
=> [[1], [2], [3], [4]]

```
> 2 votes

# Answer
# Java 7, ~~106~~ 104 bytes

```
void a(int[]a){for(int b=a.length-1,d=0,c=0,e;d<b*b;c=++d%b)if(a[c]>a[c+1]){e=a[c];a[c++]=a[c];a[c]=e;}}

```

Here's a good ole bubble sort. The function parameter is modified in place so I don't have to return anything. Still trying to squeeze some bytes out of this so I can beat the java lambda that someone posted.

-1 byte thanks to Geobits for pointing out that normal swapping beats xor'ing
-1 byte thanks to Leaky Nun for pointing out that I can move all the int declarations into the for-loop

Try it online!
> 2 votes

# Answer
## Ruby, 22 bytes

```
->a{[*a.min..a.max]&a}

```

Builds an array out of the range between the minimum and maximum elements of the input array. Returns the intersection between the two arrays.
> 2 votes

# Answer
# Jolf, 13 bytes

Uses **bogosort**. Try it out here! Replace  with `\x7f`. Input is a comma-separated list of numbers like `5,3,2,4,1`.

```
W⌂Z,k)ok Tk}k

```

Explanation:

```
W⌂Z,k)ok Tk}k
W    )         while
 ⌂Z,            !isSorted
    k            input {
      ok          k =
        _Tk        shuffle(k)
           }   }
            k  out k

```
> 1 votes

# Answer
# Python 2, 159

Implements bozosort (randomly swap two elements until the array is sorted).

It's not very efficient...

```
from random import randint as r
def b(l):
 s,a=len(l)-1,0
 while not a:
        c,d=r(0,s),r(0,s);l[d],l[c]=l[c],l[d];e,a=l[0],1
        for f in l:a,e=a*(f>=e),f
 return l

```
> 1 votes

# Answer
# Javascript 55 bytes

```
a=>[...a].map(b=>a.splice(a.indexOf(Math.min(...a)),1)

```
> 1 votes

# Answer
# Tcl, 49: sleep sort

The examples so far aren't very consistent in how they take input, so this sorts command-line arguments. On particularly slow systems, where the foreach takes more than a millisecond, it might need three extra bytes (`after ${x}0`).

```
foreach x $argv {after $x puts $x}
vwait forever

```
> 1 votes

# Answer
# SmileBASIC, 79 bytes

```
DEF S A
FOR Z=0TO I
FOR I=1TO LEN(A)-1SWAP A[I-(A[I-1]>A[I])],A[I]NEXT
NEXT
END

```

It's bubble sort but instead of checking to see if it's finished, it just assumes that every input is the worst case and does n^2 (actually n\*(n+2)) iterations.
> 1 votes

# Answer
# Perl 5, 65 bytes

Insertion sort subroutine:

```
sub r{map{$t=0;$_[$_]<$_[$t]&&($t=$_)for 0..$#_;splice@_,$t,1}@_}

```

Try it online!
> 1 votes

# Answer
# Dodos, 75 bytes

```
	/
/
	/ s w
w
	h
	/ t
s
	s R
R
	t
	h
h
	t I q
q
	dot t
	dot
I
	I dip
t
	dab

```

Try it online!

Only support non negative integers. Terrible runtime, especially for large numbers.

---

**Explanation**

First, define `t` to be the tail of a list. (all elements except the first)

Given a list `[x,y]` where `x<y`, function `I` computes the **i**ncremental difference (with a `0` prepended), which is used in `h` (head of a list, by getting the sum of all elements, subtract by the sum of all elements except the first)

Function `R` reverses a list of 2 elements. (concatenate the **t**ail and the **h**ead) Generally, it rotates the first element to the last.

`s` sorts a list of 2 elements. Generally, given a list, it find the least non negative `n` such that rotate the list left by `n` make the list less than itself `R`ed.

`/` sorts a list of arbitrarily many elements, by `/` the list' tail, and then `/ s` the result.
> 1 votes

# Answer
# Haskell, 97 bytes

```
s=f.map pure
a@(x:y)!b@(z:w)|x>z=z:a!w|0<1=x:y!b
a!b=a++b
d(x:y:z)=x!y:d z
d p=p
f[x]=x
f x=f$d x

```

Try it online!

A stable, incremental merge sort.
> 1 votes

# Answer
# Pyth, 8 bytes

```
_ueg#G.p

```

Try it online!

* `ueg#G.p`:
    + `u` Repeatedly apply the following function to the input until the result stops changing.
    + `.p`: Generate all permutations of the current list
    + `g#G`:
        - `#`: Filter the list of permutations
        - `g`: On being greater than or equal to
        - `G`: The current list
    + `e`: Take the last permutation in the filtered list. This will only be the same as the current list if the filter only leaves behind one list, because the permutation function `.p` always puts its input first.

At this point, we have the maximum permutation of the input, which is in reverse sorted order. `_` reverses that to give the sorted list.

---

Note that Pyth does not have an opposite of `g` \- there is no less than or equal to builtin.

---

I wanted to see what the intermediate lists are when sorting with this method. Putting a newline at the end of the code prints all of the intermediate lists:

Try it online!

For the input `[0,7,4,1,6,5,2,3]`, here's what the intermediate lists look like:

```
[0, 7, 4, 1, 6, 5, 2, 3]
[3, 2, 5, 6, 1, 4, 7, 0]
[7, 0, 4, 1, 6, 5, 2, 3]
[7, 3, 2, 5, 6, 1, 4, 0]
[7, 4, 0, 1, 6, 5, 2, 3]
[7, 5, 3, 2, 6, 1, 0, 4]
[7, 6, 4, 0, 1, 2, 3, 5]
[7, 6, 5, 3, 2, 1, 0, 4]
[7, 6, 5, 4, 0, 1, 2, 3]
[7, 6, 5, 4, 3, 2, 1, 0]
[0, 1, 2, 3, 4, 5, 6, 7]

```

Basically, what's happening is that at each step, the (reverse) sorted prefix stays, and then the last number larger than the front unsorted number is moved to the front of the unsorted region, and the rest of the unsorted region is reversed. It's like a low-quality selection sort with reversals thrown in for fun.

I think this runs in approximately `O(n^2 n!)` time - `n!` permutations, `n` comparisons each, and `O(n)` rounds (at most `2n`, from what I can tell.
> 1 votes

# Answer
# minigolf, 48 bytes

Implements insertion sort.

```
0,;i,:#1,;ns,s,n2,;:,n_T*+0s,,_1_,o_,n__n1+,;o__

```

Try it online!

## Explanation

```
0,;         Begin from an empty `sorted` list
i,          For each item in input list:
  :#1,;       Duplicate, and wrap `sorted`'s length
              in a singleton list
              (that is to be used later in a 'fry' structure)

  ns          Push current foreach item, and swap it below the length
  ,           'Fry' the input list's length inside
              (accessed with n; singleton lists only loop once)

              Note: at this point the remaining items on the stack are the `sorted` list and the current item of the outer foreach loop.
    s           Swap outer foreach loop item below the `sorted` list
    ,           Foreach item in the sorted list:
      n           Push current foreach item in `sorted` list
      2,;         Pair (but reversed); to implement a conditional swap
                  if the pair happens to be in decreasing order at any point in our loop
      :           Duplicate it, to perform a conditional check
      ,n_         Dump the pair onto the stack
      T*+         Subtract them

      0s          Swap 0 underneath
      ,,_1_       Repeat n times: drop & push 1
                  So if the left item in the pair > right item in the pair,
                  We would definitely execute the next conditional 1 time.

      ,o_         Execute (0 pr 1 times) based on our previous value: reverse the pair
      ,n_         Dump the pair onto the stack
    _           End foreach loop over sorted list
                (We're now in our 'fry' structure.)
    n           Push the length of our previous `sorted` list
    1+          Add 1 to that
    ,;o         Wrap last n items into a list,
                and reverse it back into the right order
                (Now we have a new `sorted` list for the next iteration of the foreach loop.)
  _           End fry sequence
_           End foreach loop in input list

```
> 1 votes

# Answer
# Javascript, 49 Bytes

```
a=>a.map(c=>setTimeout(alert,c-Math.min(...a),c))

```

Basic sleep sort implementation. Takes input as an array and outputs as alerts.
> 1 votes

# Answer
# Thunno 2 `M`, 2 bytes

```
lṗ

```

Try it online!

Port of Adnan's 05AB1E answer.

#### Explanation

```
lṗ  # Implicit input
l   # Length of input
 ṗ  # Permutations with that length
    # Implicit output of minimum

```
> 1 votes

# Answer
# Vyxal, 14 bitsv1, 1.75 bytes

```
⇧İ

```

Try it Online!

Grade up technically doesn't sort the list, but rather gives the position of the first minimum, followed by the position of the second most minimum, followed by the position of the third most minimum and so on.

## Explained

```
⇧İ
⇧  # Grade up the list
 I # and index into the input

```
> 1 votes

# Answer
# Desmos, ~~99~~ 80 bytes

*-19 thanks to Aiden Chow!*

Unfortuantely Desmos does not have great capabilities for my favorite sorting algorithm, so here is an implementation of **counting sort**!

```
m=A.min
r=[m...A.max]
f(A)=[r[∑_{n=m}^rA[A=n].length=i][1]fori=[1...A.length]]

```

Try it on Desmos!

**How it works:**

\\$m\\$ is just a shorthand for \\$A.\operatorname{min}\\$ to shave off a few bytes from the code. Note that we are referring to \\$A\\$ even when it is not defined in this context, but this still works due to some wacko variable scoping.

\\$r\\$ is also a shorthand for the range \\$\[m\dots A.\operatorname{max}\]\\$. This expression appears twice so we can also shave off yet a few more bytes with this.

Next comes the actual sorting procedure:

```
f(A)=[r[∑_{n=m}^rA[A=n].length=i][1]fori=[1...A.length]]
     [                              fori=[1...A.length]]  repeat for i∈[1,A.length]
      r[                        ]                         filter r
        ∑_{n=m}^r                                         sum from min to r
                 A[A=n].length                            # of occurrences of n
                              =i                          sum=i
                                 [1]                      take the first result

```

*Still doesn't make sense?* Let's review the algorithm:

* counting sort: count the occurrences of each value and reassemble them in order
    + \# of occurrences is always 0 or 1 since every element is distinct
* instead of reassembling, we **construct the sorted array on the spot**
    + how? *figure out where each element should be*
    + since we know the number of times each element occurs, we can add up the past occurrences to get the sorted index of the current element
    + now we just look for the element with the specified index (and repeat this for every index)

For example:

```
A = [ 3 2 9 5 ]

             i ->  1 2 3 4 5 6 7 8
             r = [ 2 3 4 5 6 7 8 9 ]
 A[A=i].length = [ 1 1 0 1 0 0 0 1 ]  number of occurrences
∑A[A=i].length = [ 1 2 2 3 3 3 3 4 ]  cumulative sum/new index

```

Now for each index \\$i\\$ in the final sorted array we look for the first item in \\$r\\$ for which \\$\sum A\[A=i\].\operatorname{length}=i\\$. This gives all the elements in the original list, but in sorted order.
> 1 votes

# Answer
# TI-Basic, ~~42~~ 41 bytes

```
Ans→A
cumSum(seq(sum(Ans=I),I,min(Ans),max(Ans
min(ʟA)+seq(sum(Ans<I),I,1,dim(ʟA

```

Counting sort. Takes input in `Ans`. Fails if the range is greater than the list size limit.

---

### ~~45~~ 44 bytes

```
Ans→A
While 0>min(ΔList(augment(Ans,{max(Ans
randIntNoRep(1,dim(Ans
seq(ʟA(Ans(I)),I,1,dim(Ans
End
Ans

```

Bogosort. Takes input in `Ans`. Only works on calculators where `randIntNoRep(` is supported. For lists with more than one element, you can replace `augment(Ans,{max(Ans` with `Ans` for -5 bytes.

---

### 63 bytes

```
Prompt A
For(I,1,dim(ʟA
For(J,I,dim(ʟA
ʟA(I→T
If Ans>ʟA(J:Then
ʟA(J→ʟA(I
T→ʟA(J
End
End
End
ʟA

```

Similar method to this answer, though I'm not sure if it's exactly bubble sort as the elements it compares aren't always adjacent.

---

### ~~72~~ 71 bytes

```
Ans→A
For(I,1,dim(Ans)-1
min(Ans→ʟB(I
sum(not(cumSum(ʟA=Ans
seq(ʟA(I+(I>Ans)),I,1,dim(ʟA)-1→A
End
Ans(1→ʟB(I:ʟB

```

Selection sort. Takes input in `Ans`. For lists with more than one element, you can replace `Ans(1→ʟB(I:ʟB` with `augment(ʟB,Ans` for -6 bytes.
> 1 votes

# Answer
# Julia, 58 29 bytes

`r(A,B=[])=A>[] ? (push!(B,popat!(A,argmin(A)));r(A,B)) : B`

```
!A=A.|>_->popat!(A,argmin(A))

```

Attempt This Online!

* an `out-place` selection sort
* shortened slightly considerably by @MarcMush
> 1 votes

# Answer
# ReRegex, 78 bytes

```
(_+),-(_+)/-$2,$1/-(_+),-\1(_+)\b/-$1$2,-$1/(?<!-)(_+)(_+),\1\b/$1,$1$2/#input

```

Try it online!

Essentially a Parallel Bubble-sort. Takes input as Signed Unary. Much of the program is just edge-cases for signed integers, without them this is just:

### Unsigned, 28 bytes

```
(_+)(_+),\1\b/$1,$1$2/#input

```

Try it online!
> 1 votes

# Answer
# C#, 125 bytes

```
using System.Linq;x=>{for(int i=0;i<x.Count;i++){int temp=x.GetRange(i,x.Count-i).Min();x[x.IndexOf(temp)]=x[i];x[i]=temp;}};

```

It uses the selection sort. I don't need to return the sorted list, because in C# lists are reference types, so the variable only holds a reference to the actual object, and if I change the object from here, it'll be visible at other places, as described in this stackoverflow question.
> 0 votes

# Answer
# Tcl, 160 bytes

```
set i 0
time {incr j;set x 0;while \$x<$i {if [lindex $L $i]<[lindex $L $x] {set L [lreplace [linsert $L $x [lindex $L $i]] $j $j]};incr x};incr i} [llength $L]

```

Try it online!

Without even thinking on a "standard" method, I implement it by using Insertion Sort.
> 0 votes

# Answer
# Attache, 36 bytes

```
{If[#_,Min[_]'$[Remove[_,Min!_]],_]}

```

Try it online!

Selection sort. Recursively sorts the list by concatenating the minimum with the sorted removed list.
> 0 votes

# Answer
# Haskell, 3332 bytes

```
import Data.Set
s=elems.fromList

```

Try it online!
> 0 votes

# Answer
# Javascript

`for(i=0;i<size;i++){for(j=i+1;j<size;j++){if(num[i]>num[j]){swap=num[j];num[j]=num[i];num[i]=swap;}}}for(i=0;i<size;i++)console.log(num[i])`

Here's an implementation of bubble sort.
> 0 votes

# Answer
# JavaScript, 42 bytes

```
a=>Object.keys(a.reduce((o,k)=>o[k]=o,{}))

```

**Note:** doesn't work for negative numbers. The iteration order of an object's keys are defined as such in the current spec, requiring that all numerical indexes are iterated in sorted numerical order first.
> 0 votes

# Answer
# Japt `-m`, 9 bytes

```
M=Wk§M rm

```

Try it
> 0 votes

# Answer
# C# (Visual C# Interactive Compiler), 77 bytes

```
a=>{for(int@i=0,t;++i<a.Count;)if((t=a[i-1])>a[i]){a[i-1]=a[i];a[i]=t;i=0;}};

```

Try it online!
> 0 votes

# Answer
# Itr, 9 bytes

`äRm«â-ÍÌ+`

online-interpreter

## Explanation

```
äRm«â-ÍÌ+  ; implicit input
ä          ; duplicate the input
 Rm«       ; get the smallest element
    â      ; push a copy of the element below the list
     -     ; subtract the smallest element from the list
      Í    ; create list with 1's at the positions given by the list
       Ì   ; get the positions of the ones (in ascending order)
        +  ; add back the minimum element

```
> 0 votes

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


title: Calculate NDos-size of given integer

text:
# Question
Title: Calculate NDos-size of given integer
# Objective

Given a nonnegative integer, calculate its **NDos-size** as defined below, and output it.

# NDos' numeral system

The concept of NDos-size comes from the numeral system I made. It represents every nonnegative integer by a nested list, as follows:

* With the binary expansion of given nonnegative integer, each entry of the corresponding NDos-numeral stands for each set bit (`1`). The order of the entries is LSB-first.
* The content of each entry is, recursively, the NDos-numeral of the number of the trailing `0`s of the `1` that the entry stands for, counted till the end or another `1`.

For illustrative purposes, here are representations of few integers in NDos' numeral system:

```
Integer = Binary = Intermediate representation = NDos-numeral

0 = []
1 = 1 = [0] = [[]]
2 = 10 = [1] = [[[]]]
3 = 11 = [0, 0] = [[], []]
4 = 100 = [2] = [[[[]]]]
5 = 101 = [0, 1] = [[], [[]]]
6 = 110 = [1, 0] = [[[]], []]
7 = 111 = [0, 0, 0] = [[], [], []]
8 = 1000 = [3] = [[[], []]]
9 = 1001 = [0, 2] = [[], [[[]]]]

```

The **NDos-size** of the given integer is the number of pairs of square brackets of the corresponding NDos-numeral. That gives the NDos-size of few integers as:

```
0 -> 1
1 -> 2
2 -> 3
3 -> 3
4 -> 4
5 -> 4
6 -> 4
7 -> 4
8 -> 4
9 -> 5

```

Note that this sequence is not monotone. `18 -> 6` and `24 -> 5` are one counterexample.

# I/O format

Flexible. Standard loopholes apply.

Be careful not to abuse this loophole. For example, you cannot just input an NDos-numeral as a string and count its left brackets.

# Answer
> 2 votes
# Jelly, ~~10~~ 9 bytes

```
Bṣ1Ẉß€Ḋ¡S

```

Try it online!

A monadic link that takes and returns an integer. Written independently of @CommandMaster’s 05AB1E answer but uses effectively the same method.

Thanks to @JonathanAllan for saving a byte!

# Answer
> 5 votes
# 05AB1E, 9 bytes

```
λNb1¡€g₅O

```

Try it online! (or more nicely formatted)

## Explanation

Recursively generates the sequence of NDos-sizes for all numbers.

Note that if in the encoding we split by `1`s and count the size of each part, we'll get the same intermediate representation except an additional `0`. But that additional `0` is good, because it accounts for the `+1` we need for the outer pair of brackets.

```
λ        # recursive environment, with base case a(0)=1
 N        # push the current index
 b        # convert it to binary
 1¡       # split on ones
 €g       # push the size of each part
 ₅        # recursively calculate a(i) for each part size
 O        # and sum

```

# Answer
> 3 votes
# Python, 49 bytes

```
f=lambda n:n<1or f(d:=len(bin(n&-n))-3)+f(n>>d+1)

```

Attempt This Online!

# Answer
> 2 votes
# Python, ~~65~~ 57 bytes

-8 thanks to @bsoelch

```
f=lambda x:sum(map(f,map(len,f"{x:b}".split('1')[1:])))+1

```

Attempt This Online!

Recursively calculates the NDos-size.

# Answer
> 2 votes
# Retina 0.8.2, 37 bytes

```
.+
1$&$*0
{`0?1
#
0
1
}+`(1+)\1
$+0
#

```

Try it online! Link includes test cases. Explanation:

```
.+
1$&$*0

```

Start with the binary representation of `2ⁿ`.

```
0?1
#

```

Keep a running total of the number of `1` bits. The `0?` is part of the unary to binary conversion below. (See the Retina tutorial.)

```
0
1
+`(1+)\1
$+0

```

Convert the `0`s from unary to binary.

```
{`
}`

```

Repeat until there are no more bits to process.

```
#

```

Output the total number of `1` bits generated.

# Answer
> 2 votes
# JavaScript (Node.js), 37 bytes

```
f=(x,i)=>x?f(x>>1,~x%2*~i)+x%2*f(i):1

```

Try it online!

-1 byte as suggested by l4m2

# Answer
> 2 votes
# Python, 46 bytes

```
f=lambda n,a=0:n<1or n%2*f(a)+f(n//2,~n%2*-~a)

```

Attempt This Online!

Essentially a port of @tsh's JS. But also fairly similar to @ovs's Python.

# Answer
> 1 votes
# Python3, 107 bytes:

```
lambda x:f(bin(x)[2:])
f=lambda x,c=0:x in['','0']or(f(bin(c)[2:])+f(x[:-1])if'1'==x[-1]else f(x[:-1],c+1))

```

Try it online!

# Answer
> 1 votes
# Charcoal, 27 bytes

```
≔×0ＮθＷ№θ0≔⪫Ｅ⪪θ1∧κ⍘Ｌκ²1θＩ⊕Ｌθ

```

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

```
≔×0Ｎθ

```

Start with `n` `0`s.

```
Ｗ№θ0

```

Repeat until no more `0`s are left.

```
≔⪫Ｅ⪪θ1∧κ⍘Ｌκ²1θ

```

Convert each run of `0`s to binary.

```
Ｉ⊕Ｌθ

```

Output the final number of `1`s plus one for the containing list.

24 bytes using the newer version of Charcoal on ATO:

```
⊞υ×0ＮＷ⌈υ≔ΣＥυ⪪∧κ⍘Ｌκ²1υＩＬυ

```

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

```
⊞υ×0Ｎ

```

Start with `n` `0`s.

```
Ｗ⌈υ

```

Repeat until no more `0`s are left.

```
≔ΣＥυ⪪∧κ⍘Ｌκ²1υ

```

Convert each string of `0`s to binary and split it on `1`s.

```
ＩＬυ

```

Output the final length.

# Answer
> 1 votes
# Pip, 14 bytes

```
a?fMS#_MTBa^1o

```

Attempt This Online!

### Explanation

A full program that calculates the NDos size recursively. Identical approach to Command Master's 05AB1E answer, but discovered independently.

```
a?fMS#_MTBa^1o
a?             ; Is the argument nonzero?
               ; If so (recursive case):
        TBa    ;  Convert it to binary
           ^1  ;  Split on 1s
     #_M       ;  Take the length of each element
  fMS          ;  Map a recursive call to each and sum the results
               ; Otherwise, the argument is 0 (base case):
             o ;  Return 1

```

Splitting the binary representation on 1s treats it as if there's an extra, empty run of 0s at the beginning. This works out perfectly, since it translates to an extra +1 to the final value, which matches the +1 needed to account for the outer pair of brackets.

# Answer
> 1 votes
# Japt, ~~12~~ 10 bytes

```
Ò¢ôÍÅx@ßXÊ

```

Try it

-2 bytes thanks to two really clever tricks pointed out by Shaggy.

This uses roughly the same method as Command Master’s Python answer.

```
Ò¢ôÍÅx@ßXÊ
Ò            Add 1 to:
 ¢           The input, converted to binary,
  ôÍ         split on elements which are true when inverted.
    Å        Slice this list from index 1 to the end.
     x@      Sum after mapping each X to
       ß       the result of recursing with
        XÊ     the length of X as the input.

```

Created with the help of Luminespire.

# Answer
> 1 votes
# Ruby, 41 bytes

```
f=->n,k=0{n<1?1:n%2*f[k]+f[n/2,~n%-2*~k]}

```

Try it online!

### Bonus stage:

The solution is nothing particularly original, (as it often happens), but I went a little deeper down the rabbit hole and found an interesting pattern and put that in the test cases.

I can't prove anything with so little data, but if I perform a run-length encoding of the sequence, then discard the values and keep only the length, the longest run is always  ~~7~~ 9, and the sequence starts from the beginning after **4423** "chunks". Going a little further, the sequence seems to be always the same, and always repeating every 4423 chunks, or  ~~32080~~ **16384** numbers.

I don't think that this pattern will repeat forever, I guess that some arbitrary large n multiplied by 16384 will break the sequence.

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