title: Rotate a column

text:
# Question
Title: Rotate a column
Given an integer *k* and either a block of text, or a 2d array that the inner arrays may have unequal lengths (that resembles a block of text), rotate every character or element in the *k*-th column up or down to the next position that exists.

### Example

Rotate the 20th column of the following text (1-based):

```
A line with more th**a**n k characters.
A longer line with **m**ore than k character.
A short line.
Rotate here: ------**v**--
This is long enough**.**

This is not enough.
Wrapping around to **t**he first line.

```

Output:

```
A line with more th**t**n k characters.
A longer line with **a**ore than k character.
A short line.
Rotate here: ------**m**--
This is long enough**v**

This is not enough.
Wrapping around to **.**he first line.

```

Rotating the *k*-th column of the same input where 35 \< *k* \< 42 would yield the input text unchanged.

### Rules

* You may use raw text, an array of lines, a 2d array of characters, or any reasonable format to represent the data. You may also use data types other than characters.
* The number of possible values of the data type of the elements must be at least 20 if your code length depends on it, otherwise at least 2. This could be a subset of the characters or other values supported in the native type.
* Spaces and any kind of null values are just normal values, if you allow them in the input. You may also simply exclude them in the element type.
* **Rule change:** You are allowed to pad the shorter arrays with a generic default value (such as spaces), if you prefer using arrays with equal lengths to store the data.
* *k* could be 0-based or 1-based. It is guaranteed to be inside the longest line in the input (implying the input has at least one non-empty line).
* You may choose whether it rotates up or down.
* Either just rotate one position, or rotate *n* positions where *n* is a positive integer given in the input.
* Shortest code wins.

# Answer
> 9 votes
# APL (Dyalog Extended), 9 bytesSBCS

Full program. Prompts stdin for 2D block of text, then *k* (0-based or 1-based, depending on APL's current setting), then *n*. Positive *n* rotate up, negative *n* rotate down.

The domain consists of either one of the following:

1. all Unicode characters, *except spaces*, leaving 1114111 allowed values, which is more than the required 20.
2. all numbers, *except 0*, leaving approximately 2129 allowed values, which is more than the required 20.

Since APL requires 2D blocks to be rectangular, the input must be padded with spaces/zeros. This can be done automatically by entering  to the left of a list of strings/numerical lists.

```
⎕⌽@≠@⎕⍢⍉⎕

```

Try it online! (the apparent spaces are actually non-breaking spaces)

prompt for text block

`⍢⍉` while transposed:

`@⎕` apply the following on the input'th row:

`@≠` at elements different from their prototype (space for characters, zero for numbers):

`⎕⌽` rotate "input" steps left

# APL (Dyalog Unicode), 22+ bytesSBCS

This version allows the full character set by using zeros as identifiable fill element.

```
0~¨⍨↓⍉⎕⌽@(0≠⊢)@⎕⍉↑0,¨⎕

```

Try it online!

This of course means that zeros are not allowed in numeric arguments. The corresponding program for all numbers would have the three occurrences of `0` replaced by `' '` and thus use space as fill:

```
' '~¨⍨↓⍉⎕⌽@(' '≠⊢)@⎕⍉↑' ',¨⎕

```

If we truly want the full ranges of (even a mixture of) both characters and numbers, we could use null as fill:

```
n~¨⍨↓⍉⎕⌽@(n≠⊢)@⎕⍉↑⎕,¨⍨n←⎕NULL

```

And finally, if we wanted to include nulls and objects in the input domain, we could define a fill class and use instances of this as fills:

```
~∘I¨⍨↓⍉⎕⌽@(~⊢∊I←⎕INSTANCES⊢∘C)@⎕⍉↑⎕,¨⍨⎕NEW⎕FIX':Class C' ':EndClass'

```

# Answer
> 11 votes
# Python 2, ~~111~~ ~~110~~ ~~109~~ ~~99~~ ~~98~~ ~~96~~ 94 bytes

```
lambda a,n:[l[:n]+(l[n:]and[L[n]for L in a[i:]+a if L[n:]][1]+l[n+1:])for i,l in enumerate(a)]

```

Try it online!

Takes input as a list of lines and 0-index column, and returns a list of strings.

Column is rotated up 1.

-11 bytes, thanks to Jo King

# Answer
> 9 votes
# Zsh, ~~94 87 78 74 69~~ 68 bytes

***-7 bytes** by changing to an arithmetic ternary, **-9 bytes** by changing the character in-place (TIL), **-4 bytes** by inputting the index on stdin and the strings as arguments, **-5 bytes** by using a string instead of an array to store the rotating characters, **-1 byte** thanks to @pxeger letting me know `${c[])` allows arithmetic ternary.*

```
read i
for s;c+=$s[i]
c=$c[-1]$c
for s;s[i]=${c[$#s<i?0:++j]}&&<<<$s

```

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

Here are the keys to making this answer work:

* `$array[0]` or `$string[0]` is always empty
* `$array[n]` or `$string[n]` is empty if n is larger than the length of the array/string
* `array[i]=c` or `string[i]=c` will replace the element/character.
* In `$[$#s<i?0:++j]`, `j` is *not* incremented if `$#s<i`.

---

In the original 94 byte answer, there was an interesting issue I came across involving using `<<<` to print. I had to use `echo` to get around it:

```
for s;echo $s[0,i-1]$c[$[$#s<i?0:++j]]${s:$i}

```

The reason for this can be seen here:

```
echo $ZSH_SUBSHELL   # prints 0
<<< $ZSH_SUBSHELL    # prints 1

```

Here-strings are run in subshells because they are given as stdin to another program. If there is no program given, it is implicitly given to `cat`. You can see this with `<<< $_`. `<<< $ZSH_SUBSHELL` is similar to `echo $ZSH_SUBSHELL | cat`. Since we need to increment `j`, we can't be in a subshell.

# Answer
> 7 votes
# Java 8, ~~107~~ ~~106~~ ~~135~~ 107 bytes

```
k->m->{int s=m.length,i=-1;for(char p=0,t;i<s;t=m[i%s][k],m[i%s][k]=p<1?t:p,p=t)for(;m[++i%s].length<=k;);}

```

+29 bytes for a bug-fix..

0-indexed; rotates down like the example.
Input as a character-matrix; modifies the char-matrix instead of returning a new one to save bytes.

Try it online.

**Explanation:**

```
k->m->{                 // Method with integer and char-matrix parameters and no return-type
  int s=m.length,       //  Amount of lines in the matrix `s`
      i=-1;             //  Index-integer `i`, starting at -1
  for(char p=0,         //  Previous-character, starting at 0
           t;           //  Temp-char, uninitialized
      i<s               //  Loop as long as `i` is smaller than `s`:
      ;                 //    After every iteration:
       t=m[i%s][k],     //     Set the temp to the `k`th character of the `i`'th line
       m[i%s][k]=       //     Replace the `k`'th character of the `i`'th line with:
         p<1?           //      If `p` is still 0:
          t             //       Set it to the temp we just set
         :              //      Else:
          p,            //       Set it to the previous-character instead
       p=t)             //     And then replace `p` with the temp for the next iteration
    for(;m[++i          //   Increase `i` by 1 before every iteration with `++i`,
             %s].length //   And continue this loop until the length of the `i`'th line
           <=k;);}      //   is smaller than or equal to the input `k`

```

# Answer
> 6 votes
# , 62 bytes

```
function(L,n){L[A,n]<-rep(L[A<-L[,n]!=' ',n],2)[1+1:sum(A)];L}

```

Try it online!

Takes input as a space-padded matrix of characters. Rotates upwards. All thanks to Kirill L.!

# , 74 bytes

```
function(L,n){substr(L[A],n,n)=rep(substr(L[A<-nchar(L)>=n],n,n),2)[-1]
L}

```

Try it online!

This submission predates the allowance of padded lines.

Aliasing `substr` here won't work because we're calling `substr` and `substr<-` in the first line.

I/O as a list of non-padded lines; rotates upwards.

# Answer
> 5 votes
# C# (Visual C# Interactive Compiler), 82 bytes

```
k=>a=>{var c='0';a.Where(b=>b.Count>k&&((b[k],c)=(c,b[k])).c>0).ToList()[0][k]=c;}

```

Try it online!

Credit to @ASCIIOnly for suggesting `foreach` which led to a 12 byte savings!

-8 bytes thanks to @someone!
-1 byte thanks to @EmbodimentofIgnorance!

# Answer
> 4 votes
# Ruby, 57 bytes

```
->a,k{b=a.map{|i|i[k]}-[p];c=-2;a.map{|i|i[k]&&=b[c+=1]}}

```

Try it online!

Takes input as an array of lines `a`. Rotates the text down at 0-based position `k`. Returns by modifying the input `a`.

# Answer
> 4 votes
# K4, 22 ~~41~~ bytes

## New Rules:

**Solution:**

```
{+@[+x;y;.q.rotate 1]}

```

If the input is already padded to the maximum length, then this becomes much shorter.

## Old Rules:

**Solution:**

```
{.[x;i;:;.q.rotate[1;x . i:(&y<#:'x;y)]]}

```

**Explanation:**

Not sure if I'm missing something... 0 index, rotates up (change the `1` to `-1` for rotate down)

```
{.[x;i;:;.q.rotate[1;x . i:(&y<#:'x;y)]]} / the solution
{                                       } / lambda taking implicit x and y
 .[x; ;:;                              ]  / index apply assignment back into x
         .q.rotate[1;                 ]   / left rotate 1 character
                           (       ; )    / two item list
                                    y     / index to rotate
                               #:'x       / count (#:) each (') input
                             y<           / index less than ?
                            &             / indexes where true
                         i:               / assign to variable w
                     x .                  / index into x
     i                                    / indexes we saved as i earlier

```

# Answer
> 3 votes
# 05AB1E, 21 bytes

```
ʒg‹}U¹εXyk©diX®<èIèIǝ

```

Can definitely be golfed some more..

0-indexed; input and output both as a list of strings.
It rotates down like the example, but `<` can be replaced with `>` to rotate up instead.

Try it online (footer joins the list by newlines, remove it to see the actual list output).

**Explanation:**

```
ʒ  }             # Filter the (implicit) input-list by:
 g               #  Where length of the current string
  ‹              #  is larger than the (implicit) input-integer
    U            # Pop and store this filtered list in variable `X`
¹ε               # Map over the first input-list again:
  Xyk            #  Get the index of the current string in variable `X`
     ©           #  Store it in the register (without popping)
      di         #  If the index is not -1, so the current string is present in variable `X`
        X®<è     #   Get the (index-1)'th string in variable `X`
            Iè   #   Get the character at the index of the input-integer
              Iǝ #   And insert it at the index of the input-integer in the current string

```

# Answer
> 3 votes
# Japt v2.0a0, 18 bytes

0-based with input & output as a multi-line string. Rotates up by 1.

There's gotta be a shorter method!

```
yÈr\S_Y¦V?Z:°TgXrS

```

Try it

```
yÈr\S_Y¦V?Z:°TgXrS     :Implicit input of string U & integer V
y                      :Transpose
 È                     :Pass each line X at 0-based index Y through the following function & transpose back
  r                    :  Replace
   \S                  :  RegEx /\S/g
     _                 :  Pass each match Z through the following function
      Y¦V              :    Test Y for inequality with V
         ?Z:           :    If true, return Z, else
            °T         :    Increment T (initially 0)
              g        :    Index into
               XrS     :    X with spaces removed

```

# Answer
> 3 votes
# Jelly, 16 bytes

```
z⁷⁹ịỴFṙ-ṁƲY⁸ṛ⁹¦"

```

A dyadic Link accepting a list of lines (lists of characters containing no newline characters) on the left and an integer on the right which returns a list of lines.

**Try it online!** (footer splits on newlines, calls the Link, and joins by newlines again)

### How?

```
z⁷⁹ịỴFṙ-ṁƲY⁸ṛ⁹¦" - Link: lines L; index I        e.g. example in question; 20
z⁷               - transpose L with filler '\n'       ['AAART\nTW', '   oh\nhr', ...]
  ⁹ị             - Ith item                           'am\nv.\n\nt'
    Ỵ            - split at newlines                  ['am', 'v.', '', 't']
         Ʋ       - last four links as a monad - i.e. f(X):
     F           -   flatten                          'amv.t'
       -         -   -1
      ṙ          -   rotate left by                   'tamv.'
        ṁ        -   mould like X                     ['ta', 'mv', '', '.']
          Y      - join with newlines                 'ta\nmv\n\n.'
                 -   -- call this C
           ⁸     - chain's left argument, L
               " - zip with - i.e. [f(L1,C1), f(L2,C2), ...]:
              ¦  -   sparse application...
             ⁹   -   ...to indices: chain's right argument, I
            ṛ    -   ...of: right argument, Cn

```

# Answer
> 2 votes
# Charcoal, ~~34~~ ~~28~~ 21 bytes

```
θＪη⁰≔ΦＫＤＬθ↓℅ιζＵＭζ§ζ⊖κ

```

Try it online! Link is to verbose version of code. Takes an array of strings as input. 0-indexed. Edit: Now that `PeekDirection` has been fixed, I can manipulate it directly. Explanation:

```
θ

```

Print the input strings.

```
Ｊη⁰

```

Jump to the top of the column to be rotated.

```
≔ΦＫＤＬθ↓℅ιζ

```

Extract the cells that have been printed in.

```
ＵＭζ§ζ⊖κ

```

Replace each printed cell with the value of the previous cell (cyclically). Conveniently the cell values are read at the time of the `PeekDirection` call so the fact that the `MapCommand` call writes new values into the cells doesn't matter.

# Answer
> 2 votes
# perl 5 (`-p`), 75 bytes

k is 0-indexed, rotate down

```
s/.*//;$r="^.{$&}";s/
//;/$r(.)/;$c=$1;s/$r\K.(?=(?s:.)*?$r(.)|)/$1||$c/gme

```

TIO

# Answer
> 2 votes
# Perl 6, 38 33 bytes

Modifies the array in place (rules don't disallow)

```
{@^a.grep(*>$^b+1)[*;$b].=rotate}

```

Try it online!

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

```
k=>a=>a.filter(b=>b[k]&&([b[k],a]=[a,b[k]]))[0][k]=a

```

Try it online!

-7 bytes thanks to Shaggy!

Didn't see a JavaScript answer yet! Port of my C# answer.

# Answer
> 1 votes
# Pip `-rn`, 32 bytes

```
POgY#(g@_)>aFI,#gFiyAE@ySsg@i@ag

```

0-indexed, rotates down. Try it online!

Filters to find the indices of all rows that are long enough to participate in the rotation. Then loops over those rows, swapping the appropriate character on each row with a temp variable `s`. Visiting the first row again at the end swaps the dummy value back out again.

# Answer
> 1 votes
# Jelly, 19 bytes

```
ZnÄ×$ịḟ¹ṙ-;ɗɗʋ€⁹¦⁶Z

```

Try it online!

1-indexed. Rotates down. A monadic link that takes a right-padded list of Jelly strings (a list of lists of characters) as the first argument and k as the second. Spaces are forbidden in the input except as right padding, but all other characters are permitted.

As implemented on TIO, the footer splits a single string input into a list of strings and right-pads it, but this is for convenience; as I understand it, the result of that step is permitted input for the main link per the rules.

# Answer
> 1 votes
# GFortran, 182 bytes

Requires user to input `k` and `n` on the first line, where `k` is the column to rotate, and `n` is the number of rows of text. Subsequent inputs are the lines of text to be rotated. This was a pain to write! Fortran is so pedantic! Try it Online.

```
character(99),allocatable::A(:);character(1)r,s
read*,k,n;allocate(A(n))
do i=1,n;read'(A)',A(i);r=A(i)(k:k)
if(r.ne.' ')then;A(i)(k:k)=s;s=r;endif;enddo
A(1)(k:k)=s;print'(A)',A;end

```

Original, ungolfed program here, with comments and compilation notes: rotcol.f

Saved 20B by reading from stdin rather than a file. Saved 14B by using implicit integers for `i k n`. Saved 4B by cleanup of spaces and `::`. Saved 17B by simplfying logic, and cutting i/o formatting guff.
~~203 bytes~~
~~199 bytes~~

# Answer
> 1 votes
# APL (Dyalog Unicode), 19 chars

```
{⍉¯1⌽@{' '≠⍵}@⍺⍉↑⍵}

{                  ↑⍵} ⍝ from nested vector of char vectors to char matrix (padding=space)
{                ⍉   } ⍝ transpose
{              @⍺     } ⍝ apply on row ⍺ (left argument)
{  ¯1⌽@{' '≠⍵}       } ⍝ rotation towards the right only elements that are note spaces
{⍉                   } ⍝ transpose back

```

Try it online!

# Answer
> 0 votes
# T-SQL, 195 bytes

```
WITH C as(SELECT rank()over(order by i)r,sum(1)over()c,*FROM @t
WHERE len(x)>=@)SELECT
isnull(stuff(c.x,@,1,substring(e.x,@,1)),t.x)FROM @t t
LEFT JOIN c ON t.i=c.i
LEFT JOIN c e ON e.r%c.c+1=c.r

```

**Try it online** ungolfed version

---
Tags: code-golf, string, array
---


title: Write a Whitespace Interpreter

text:
# Question
Title: Write a Whitespace Interpreter
## Challenge:

Your challenge is to write an interpreter for Whitespace. Given a string consisting of spaces, tabs, newlines, and potentially other characters, as well as possible inputs for the Whitespace program itself, output the result of the given Whitespace program.

## Here is an overview of the Whitespace language and its builtins:

Whitespace is a stack-based language which uses only three characters: spaces (ASCII codepoint 32); tabs (ASCII codepoint 9); and newlines (ASCII codepoint 10); all other characters are ignored.
It only has a couple of basic builtins, which I will go over below. Whitespace has a stack, which can only consist of integers, as well as a heap, which is a map of integers (both the key and value).

From here on out I will be using `S` for spaces, `T` for tabs, and `N` for newlines to make the text more compact.

*Stack Manipulation (always starts with leading `S`):*

* Push a number to the stack: `SS`, followed by either an `S`/`T` for positive/negative respectively, followed by some `S` and/or `T` which is the binary representation of the number (`S=0`; `T=1`), followed by a trailing newline `N`. Some examples:
    + `SSSTN` pushes the number `1`; a positive integer with binary `1`.
    + `SSTTSN` pushes the number `-2`; a negative integer with binary `10`.
    + `SSSTSTSN` pushes the number `10`; a positive integer with binary `1010`.
    + `SSTTTSSTSSN` pushes the number `-100`; a negative integer with binary `1100100`.
    + Pushing number `0` is an edge case, since it can be done in multiple ways. Some examples:
        - `SSSN`: push a positive integer without any binary digits.
        - `SSTN`: push a negative integer without any binary digits.
        - `SSSSN`: push a positive integer with binary `0`.
        - `SSTSSSN`: push a negative integer with binary `000`.
* Duplicate the top of the stack: `SNS`.
* Copy the 0-based \\$n\\$th item from the top of the stack to the top of the stack: `STS` followed by a number similar as mentioned earlier (excluding the leading `SS`). I.e. let's say the stack currently contains the integers `[47,12,0,55]`, then we could use `STSSTSN` to copy the 0-based 2nd item (which is the `12` in this case) to the top. So the stack becomes: `[47,12,0,55,12]`.
    + NOTE: This index may not be negative. On TIO this would result in a negative index error, but that same program would push a `0` in the vii5ard interpreter, and it could even be different in yet another interpreter. For the sake of this challenge, you can therefore assume a given copy will never be negative. So the copy will always start with `STSS`, followed by the binary of the top-to-bottom index, followed by a trailing `N`.
* Swap the top two items on the stack: `SNT`.
* Discard the top item of the stack: `SNN`.
* Discard/slice \\$n\\$ items from the top of the stack, but keep the top item: `STN`, followed by a number similar as mentioned earlier (excluding the leading `SS`). I.e. let's say the stack currently contains the integers `[1,2,3,4,5,6,7]`, then we could use `STNSTTN` to discard 3 items from the stack (except the top one). So the stack becomes: `[1,2,3,7]`.
    + You can again assume no negative slice values will be used, so this will always start with `STNS`, followed by the amount to slice, followed by a trailing `N`.

*Arithmetic (always starts with leading `TS`):*

* Addition; add the top two items on the stack together: `TSSS`.
* Subtraction; subtract the top item of the stack from the (top-1)th item of the stack: `TSST`.
* Multiplication; multiply the top two items on the stack: `TSSN`.
* Integer division; integer divide the (top-1)th item of the stack by the top item of the stack: `TSTS`. (NOTE: Since Whitespace only has integers, this will always be integer division and never result in decimal values.)
* Modulo; take the modulo of the (top-1)th item of the stack with the top item of the stack: `TSTT`.
    + You can assume no negative values will be used for the modulo.

For each of these two argument builtins the same applies: if none or only a single integer is on the stack, this will result in an error. How you implement this error in your interpreter is up to you, as long as the program stops when this occurs. I thought about not allowing it for the sake of this challenge, but decided not to because it's a commonly used strategy to stop a program with an error when printing hardcoded texts, using the approach explained in this Whitespace codegolfing tip.

*Heap Access (always starts with leading `TT`):*

* Pop the top two items of the stack, and store the top item in the (top-1)th address of the heap: `TTS`. I.e. let's say the stack contains the integers `[1,2,3,4,5]` and the heap already contains `[{2:10}]`. When you use this store builtin twice in a row, the stack would contain `[1]` and the heap will contain `[{2:3},{4:5}]` (note how the `{2:10}` has been replaced with the `{2:3}`).
    + NOTE: Just like with the Arithmetic builtins, if no or a single argument is given, it will cause an error. But for the sake of this challenge you can assume this will never be given for this builtin.
* Pop the top item of the stack, and push the item corresponding with that heap address to the top of the stack: `TTT`. I.e. let's say the stack contains the integers `[1,4]` and the heap contains `[{2:3},{4:5}]`. If you now use the retrieve builtin once, the stack would become `[1,5]` (and the heap will remain the same).
    + NOTE: If you use an address that isn't in the heap yet (or the heap is empty), it will push a `0` to the stack instead. But for the sake of this challenge you can also ignore this.

*Flow Control (always starts with leading `N`):*

* Mark a location in the program with a label: `NSS`, followed by some (optional) `S`/`T` which aren't used by other labels/subroutines, followed by an `N`. I.e. if you're only using a single label in your full program, `NSSN` would be what to use when code-golfing. If you need two or three labels, you can add `NSSSN` and/or `NSSTN`.
    + Although it is possible to have multiple of the same labels in the TIO and vii5args interpreters, it will cause issues, so we assume the input will always only create a label/subroutine once.
    + Also, although `NSSN` would be a logical first label to use, it's completely valid to use a label `NSSTSTSTTTSN` instead as only label in the program.
* Call a subroutine with the given label: `NST`, followed by some (optional) `S`/`T` which aren't used by other labels/subroutines, followed by an `N`. I.e. `NSTTSTSTTTSN` would jump to the label `TSTSTTTS` as subroutine.
* Jump unconditionally to a label: `NSN`, followed by some (optional) `S`/`T`, followed by an `N`. I.e. `NSNN` would jump to the (empty) label `N` and continue the program flow from there.
* Pop the top integer, and jump to a label if it is exactly 0: `NTS`, followed by some (optional) `S`/`T`, followed by an `N`. I.e. if the stack is currently `[4,1,0]` and we'd use `NTSSN`, it would jump to the label `SN` and continue the program flow from there (with stack `[4,1]`). If instead the stack is currently `[4,1]` and we'd use the `NTSSN`, it would jump past it to the next builtin below it (with stack `[4]`).
* Pop the top integer, and jump to a label if it is negative: `NTT`, followed by some (optional) `S`/`T`, followed by an `N`. I.e. if the stack is currently `[4,1,-10]` and we'd use `NTTTN`, it would jump to the label `TN` and continue the program flow from there (with stack `[4,1]`). If instead the stack is currently `[4,1]` and we'd use the `NTTTN`, it would jump past it to the next builtin below it (with stack `[4]`).
    + Minor note: There is no *Jump to label if positive* builtin available in Whitespace.
* End a subroutine, and go back to the caller (a.k.a. return): `NTN`.
* End the entire program: `NNN` (everything after that becomes no-ops).

*I/O (always starts with leading `TN`):*

* Pop the top integer, and print as character with that codepoint to STDOUT: `TNSS`. I.e. if the stack is currently `[10,101]` and we'd call the `TNSS` twice, it will output a lowercase `e` followed by a newline to STDOUT.
* Pop the top integer, and print as integer to STDOUT: `TNST`.
* Pop the top integer, and read a character from STDIN, for which its codepoint-integer will be stored in the heap with the popped integer as address: `TNTS`. I.e. if the stack is `[0,0]`, the heap is empty, and STDIN contains the capital letter `I`, and we'd use `TNTS`. The stack will become `[0]` and the heap `[{0:73}]`. (After which we could use the retrieve builtin `TTT` to put this input on the stack.)
* Pop the top integer, and read an integer from STDIN, which will be stored in the heap with the popped integer as address: `TNTT`.

## Challenge rules:

* You can assume the Whitespace input is always valid with the builtins above. So the compilation phase would always succeed.
* You can assume executing the Whitespace input will never result in any errors, **except when the Arithmetic builtins will only get 0 or 1 stack-arguments instead of the required 2**. Although there are loads of other possible errors when executing a Whitespace program, like negative indices, jumps to labels that doesn't exist, read from STDIN when it's empty, etc. For the sake of this challenge you can assume none of those kind of errors will occur, and the input-program is error-free (except for the Arithmetic builtins).
* You can assume the additional inputs given will be valid as well. So an integer when we want to read an integer or a character / string of multiple characters if we want to read those.
* The Whitespace program-input can be taken in any reasonable format. Could be a string, list of characters, list of codepoint-integers, etc. Same applies to the other inputs.
* Any non-whitespace character in the Whitespace-program input is ignored. You can assume the no-op characters will only be printable ASCII. So the Whitespace input will only contain the UTF-8/ASCII characters with the codepoints \[9, 10, 32..126\].
* Whitespace numbers can in theory be as large as you want, but for the sake of this challenge you can assume the integers used will be in the range \[-9223372036854775808, 9223372036854775807\] (signed 64 bit integer).

## General rules:

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

## Test cases:

***You should copy the actual test cases from the Try it online links to verify your interpreter.***

```
Input(s):
 SSTTSTTTTNSSSTSNSSSTNSTSSTNSSTTSTNSSTTSNSNSSSSTNSTSSTNSSTTSSTTTSNSSTTTSSTTNSSSNSSTTSTNSSTTTNSSSTSNSSTTNSSSTTTNSSSTSNSSTTSSTTTSNSSSTSNSSTTNSSSTTTNSSTTSNSSSTSNSSTTSSTTTSNSSTTTSSTTNSSTTTNSSTTSNSSTTSTNSSTTNSSTTSSTTTSNSSTTNSSSTTTNSSTTSTNSSSNSSTTSTNSSTTSNSNSSSSTNSSTTTTTSNNSSNSSSTTSTTTSNTSSSTNSSNSNN
Builtins used:
 Push num; duplicate; copy; add; create label; jump to label; print as char
Output:
 Pollinium milk; plump pumpkin; lollipop?

```

Try it online as actual program using raw spaces, tabs, newlines.
See this Whitespace answer of mine for an explanation.

```
Input(s):
 SSTTSNSNSTSSNTNST
Builtins used:
 Push num; duplicate; multiply; print as int
Output:
 4

```

Try it online as actual program using spaces, tabs, newlines, and comments.

```
Input(s):
 SSTTNTNSTNNNTSNTNTSSS
Builtins used:
 Push num; print as int; stop program; (no-ops)
Output:
 -1

```

Try it online as actual program using raw spaces, tabs, newlines.
See this Whitespace answer of mine for an explanation.

```
Input(s):
 SSSNSNSSNSTNTTTTTNSSNSNSTNSTSSSTSTSNTNSSSNTSSSTNTSSSSTSSTNSTSSTNSNSSSSTSSNTSTTSNSNTSSNSSSTNTSSTSNSNTSTNSSSTNTSSTNTSSSNSNTSTSSTNTSSTNSNNNSSSNSNNTSTSSTSSTSNSTSSTSNTSTTNTSNNNNNSSTNSNNTSSNNSNNNSSSSNTSSSNSNN
 21
Builtins used:
 Push num; duplicate; swap; copy; discard; add; subtract; multiply; divide; modulo; retrieve; create label; jump to label; jump to label if 0; stop program; read as int; print as char; print as int
Output:
 21
 21
 23
 20
 5
 25
 31
 24
 3
 27
 37
 26

```

Try it online as actual program using spaces, tabs, newlines, and comments.
See this Whitespace answer of mine for an explanation.

```
Input(s):
 NSSNSSSNSNSTNTSTTTSNSSSSTSTSNTSSTNTSSNSSSNSNSTNTSTTTTSSTNTSNSSSNTNSTNSSSN
 TThhiiss  iiss  ddoouubblee  ssppeeaakk!!\n
Builtins used:
 Push num; duplicate; subtract; retrieve; create label; jump to label if 0; read as char; read as int
Output:
 0

```

Try it online as actual program using spaces, tabs, newlines, and comments.
See this Whitespace answer of mine for an explanation.

```
Inputs(s):
 SSSNSNSTNTTTTTSSSNSNSTNTTTTTTSSSTNST
 -3
 5
Builtins used:
 Push num; duplicate; add; retrieve; read as int; print as int
Output:
 2

```

Try it online as actual program using spaces, tabs, newlines, and comments.
See this Whitespace answer of mine for an explanation.

```
Input(s):
 SSSTSSSTTTTTSSSSSSSTTSSSTSTTTTTSSTTSNTNST
Builtins used:
 Push num; print as int
Output:
 4815162342

```

Try it online as actual program using spaces, tabs, newlines, and comments.
See this Whitespace answer of mine for an explanation.

```
Input(s):
 SSSTTTNTNTSSSSTSSSSTNSSSTSTSNNSSTTNSSSTNTSSTSNSNTTSNSTSSTNSNTNSNTTNNSSSNSSSTTTNTTTSTNSSSTSTNTNSTSSSTSNNSSTNSNTSNNSNTTNSSSSSTSNTSTSSNSNTSSSNNSNTNNSSSSNNNN
 〹
Builtins used:
 Push num; duplicate; swap; discard; copy; slice; retrieve; create label; jump to label; jump to label if 0; jump to label if negative; exit program; read as char; print as char; print as int
Output:
 12345!!

```

Try it online as actual program using spaces, tabs, newlines, and comments.

```
Inputs(s):
 SSSTTNSNSSNSSNSTTSSSSTTTNTTSNSTNTNSSNNNSSTNNSSNTTTNTNSSTN
Builtins used:
 Push num; duplicate; store; retrieve; call subroutine; return; exit program; print as char; (no-ops)
Output:
   (character with unicode value 7)

```

Try it online as actual program using spaces, tabs, newlines, and comments.

# Answer
> 21 votes
# Vim, 2366 bytes

```
:let@z=''
:%s/\S//eg
:%s/ /S/&
:%s/    /T/&
:%s/\n/N/&
$xo"Zyl:if"<C-v><C-r>z"=="SS"||"<C-v><C-r>z"=="STS"||"<C-v><C-r>z"=="STN"||"<C-v><C-r>z"=="NST"||"<C-v><C-r>z"=="NSN"||"<C-v><C-r>z"=="NTS"||"<C-v><C-r>z"=="NTT"<C-v>
norm fN<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="SNS"||"<C-v><C-r>z"=="SNT"||"<C-v><C-r>z"=="SNN"||"<C-v><C-r>z"=="TSSS"||"<C-v><C-r>z"=="TSST"||"<C-v><C-r>z"=="TSSN"||"<C-v><C-r>z"=="TSTS"||"<C-v><C-r>z"=="TSTT"||"<C-v><C-r>z"=="TTS"||"<C-v><C-r>z"=="TTT"||"<C-v><C-r>z"=="NTN"||"<C-v><C-r>z"=="TNSS"||"<C-v><C-r>z"=="TNST"||"<C-v><C-r>z"=="TNTS"||"<C-v><C-r>z"=="TNTT"||"<C-v><C-r>z"=="NNN"<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="NSS"<C-v>
norm hhxxrmfN<C-v>
let@z=''<C-v>
en<C-v>
l@t<Esc>^"tC"Zyl:if"<C-v><C-r>z"=="SS"<C-v>
norm @a<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="STS"<C-v>
norm @b<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="STN"<C-v>
norm @c<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="SNS"<C-v>
norm @d<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="SNT"<C-v>
norm @e<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="SNN"<C-v>
norm @f<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="TSSS"<C-v>
norm @g<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="TSST"<C-v>
norm @h<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="TSSN"<C-v>
norm @i<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="TSTS"<C-v>
norm @j<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="TSTT"<C-v>
norm @k<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="TTS"<C-v>
norm @l<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="TTT"<C-v>
norm @m<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="NST"<C-v>
norm @o<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="NSN"<C-v>
norm @p<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="NTS"<C-v>
norm @q<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="NTT"<C-v>
norm @r<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="NTN"<C-v>
norm @s<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="TNSS"<C-v>
norm @u<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="TNST"<C-v>
norm @v<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="TNTS"<C-v>
norm @w<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="TNTT"<C-v>
norm @x<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="m"<C-v>
norm fNl<C-v>
let@z=''<C-v>
elsei"<C-v><C-r>z"=="NNN"<C-v>
k<C-v>
el<C-v>
norm l<C-v>
en<C-v>
@n<Esc>^"nClylmc'sO<C-v><Esc>p:s/T/-/e<C-v>
:s/S/+/e<C-v>
"9xms`cytN'sp^x@y^"9PC<C-v><C-r>=<C-v><C-r>"<C-v>
<C-v><Esc>ms`cfNl<Esc>^"aCllytNmc'sO<C-v><Esc>p@y<C-v><C-a>^Dms@"jy$'spms`cfNl<Esc>^"bCllytNmc'so<C-v><Esc>p@y^DJ@"dd`cfNl<Esc>^"cCmc'sy$O<C-v><C-r>"<C-v><Esc>ms`cl<Esc>^"dCmc'sddpkms`cl<Esc>^"eCmc'sddms`cl<Esc>^"fCmc'sy$ddmsC<C-v><C-r>=<C-v><C-r>0+<C-v><C-r>"<C-v>
<C-v><Esc>`cl<Esc>^"gCmc'sy$ddmsC<C-v><C-r>=-<C-v><C-r>0+<C-v><C-r>"<C-v>
<C-v><Esc>`cl<Esc>^"hCmc'sy$ddmsC<C-v><C-r>=<C-v><C-r>"*<C-v><C-r>0<C-v>
<C-v><Esc>`cl<Esc>^"iCmc'sy$ddmsC<C-v><C-r>=<C-v><C-r>"/<C-v><C-r>0<C-v>
<C-v><Esc>`cl<Esc>^"jCmc'sy$ddmsC<C-v><C-r>=<C-v><C-r>"%<C-v><C-r>0<C-v>
<C-v><Esc>`cl<Esc>^"kCmc'sy$ddDJms'h:s/ <C-v><C-r>"(\d*)//eg<C-v>
A <C-v><C-r>"(<C-v><C-r>0)<C-v><Esc>`cl<Esc>^"lCmc'sy$'h/ <C-v><C-r>"(<C-v>
%yT('sC<C-v><C-r>0<C-v><Esc>`cl<Esc>^"mCfN:let@9=col('.')+1<C-v>
vTNy/m<C-v><C-r>"<C-v>
fNlmc'xO<C-v><Esc>"9pmx`c<Esc>^"oCfNvTNy/m<C-v><C-r>"<C-v>
fNl<Esc>^"pCmc'sDJ`c:if<C-v><C-r>"==0<C-v>
norm fNvTNlly/m<C-v><C-v><C-v><C-r>"<C-v><C-v><C-v>
fNl<C-v>
el<C-v>
norm fNl<C-v>
en<C-v>
<Esc>^"qC
mc'sDJ`c:if<C-v><C-r>"<0<C-v>
norm fNvTNlly/m<C-v><C-v><C-v><C-r>"<C-v><C-v><C-v>
fNl<C-v>
el<C-v>
norm fNl<C-v>
en<C-v>
<Esc>^"rCmc'xDJmx`c@"|<Esc>^"sCmc'sDJms`oA<C-v><C-r>=nr2char(<C-v><C-r>-)<C-v>
<C-v><Esc>mo`cl<Esc>^"uCmc'sDJms`o$"-pmo`cl<Esc>^"vCmc'iDJ'sO<C-v><C-r>=char2nr('<C-v><C-r>"')<C-v>
<C-v><Esc>ms`c@l<Esc>^"wCmc'iDJ'sO<C-v><C-r>"<C-v><Esc>ms`c@l<Esc>^"xC0i0<C-v><Esc>y$@=len("<C-v><C-r>"")<C-v>
I(<C-v><Esc>^x:s/S/*2)/eg<C-v>
:s/T/*2+1)/&<C-v>
^C<C-v><C-r>=<C-v><C-r>"<C-v>
<C-v><Esc><Esc>^"yDo<Esc>mxo
Stack:
<Esc>mso
Heap:
<Esc>mho
Input:
<Esc>mio
Output:
<Esc>mo:let@z=''

```

Try it online!

I sure do love me a thicc Vim program.

This program replaces all of the spaces, tabs, and newlines with the letters `STN`. This is only necessary for the newlines, because Vim is primarily a text editor and treats them differently, but it does it to each character for consistency. It then takes each Whitespace command and puts it into its own macro. Here's a list of all of the macros, and what command they map to. After creating all of the macros, it goes through a compilation phase, followed by an execution phase.

The compilation phase goes through the program, and for every `NSS` command, it replaces the `NSS` with an `m`, to be able to easily jump to it later.

The execution phase collects characters into the `"z` register, and once the register matches a command, the macro for that command is executed, and the `"z` register is cleared.

The stack is simply a bunch of lines containing a number, with the top of the stack having the label `s`. When we want to access the top of the stack, we just jump to the label, then we can use the `c` label to jump back to the code.

The heap is a line that stores many values in the form `key(value)`. To set a value, the program deletes the matching key/value pair if it exists, then adds the key/value to the end of the heap. To get the value, it just does `/ key(`, which finds the key, then it uses `%yT(` to copy only the value.

Input can be passed to the program by adding ``ii<input>` to the beginning of the footer. Each value must be on a separate line to work: Try it online! The `gg@tgg@n` at the end of the footer compiles and runs the program. To view only the output of the Whitespace program, add ``idH` to the end of the footer.

# Answer
> 12 votes
# JavaScript (Node.js),  ~~608 597 586~~  551 bytes

Takes input as `(source)(input)`, where *input* is an array containing single characters and/or integers.

```
s=>I=>eval([..."@CDEJKLMNQTUWYZ^_bkmqw"].reduce((s,c)=>(a=s.split(c)).join(a.pop()),"(R=X=>(H={},o=P=[],S=[],z=x=p=i=0,gUs[p]?~(j=` 	\n`.indexOf(s[p++]N?j:gK:3,hUgK<2?Mn*2+j):V=n,GUx=z--&&S.pop(y=x),FUg(x=`mbQQ$mS[z+~(b])TSCce((z-=V=b-1,V)$mkJLmyJkTTLH[x]=y$mHD)qR[M1)]=_?R[P@p),V]:_Y_&!kY_&k<0Yp$E?P.popK:pT$^QQQQQqW+yw-yw*yw/y|0w%yN:^QTTo+=Buffer(D)$o+=k$Z.codePointAtKZ`Ct`$`[n-9],x&&eval(x,n=1N<3&&F(n*3+jN(1N(0)||R(1)||owN:^$WqTT$mz=S@kGKbgK?-M0):M0N_p$M1),E^E?g:pZ$HD=I[i++]Y?R[V]:Wz>1?(LmxU=n=>T$$QqqN))Mh(Lk,k,K()J),mx)$Ep=XD[k]C.spli@.pusM"))

```

Try it online! (all test cases without comments)

Try it online! (an example with a commented source code as input)

### How?

Because the code is packed with RegPack, it is more efficient to repeat the same pieces of code over and over rather than defining too many helper functions.

The sequences of spaces, tabs and linefeeds are converted to an integer in base 3 with a leading \\$1\\$ until they match a known value:

```
 seq. | mnemonic | base 3 | decimal
------+----------+--------+---------
 SS   |    PSH   |    100 |     9
 STS  |    CPY   |   1010 |    30
 STN  |    SLI   |   1012 |    32
 SNS  |    DUP   |   1020 |    33
 SNT  |    SWP   |   1021 |    34
 SNN  |    DIS   |   1022 |    35
------+----------+--------+---------
 TTS  |    PUT   |   1110 |    39
 TTT  |    GET   |   1111 |    40
------+----------+--------+---------
 NSS  |    LBL   |   1200 |    45
 NST  |    JSR   |   1201 |    46
 NSN  |    JMP   |   1202 |    47
 NTS  |    JZE   |   1210 |    48
 NTT  |    JMI   |   1211 |    49
 NTN  |    RTN   |   1212 |    50
 NNN  |    END   |   1222 |    53
------+----------+--------+---------
 TSSS |    ADD   |  11000 |   108
 TSST |    SUB   |  11001 |   109
 TSSN |    MUL   |  11002 |   110
 TSTS |    DIV   |  11010 |   111
 TSTT |    MOD   |  11011 |   112
------+----------+--------+---------
 TNSS |    CHR   |  11200 |   126
 TNST |    INT   |  11201 |   127
 TNTS |    RCH   |  11210 |   129
 TNTT |    RNU   |  11211 |   130

```

The commands are simply stored in a lookup table and executed with `eval()`.

Everything is wrapped within the function \\$R\\$ which is called twice:

* First pass (\\$X=0\\$): the jumps and the stack errors are ignored so that the whole code is parsed linearly and all labels are stored
* Second pass (\\$X=1\\$): the code is executed normally

### Unpacked and formatted

```
s => I => (
  R = X => (
    H = {},
    o = P = [],
    S = [],
    z = x = p = i = 0,
    g = n => s[p] ? ~(j = ` \t\n`.indexOf(s[p++])) ? j : g() : 3,
    h = n => g() < 2 ? h(n * 2 + j) : V = n,
    G = n => x = z-- && S.pop(y = x),
    F = n => g(
      x = [
        /* PSH */ "z=S.push(g()?-h(0):h(0))",,,,,,,,,,,,,,,,,,,,,
        /* CPY */ "z=S.push(S[z+~(g()?-h(0):h(0))])",,
        /* SLI */ "S.splice((z-=V=g()?-h(0):h(0))-1,V)",
        /* DUP */ "z=S.push(G()),z=S.push(x)",
        /* SWP */ "G(),G(),z=S.push(y),z=S.push(x)",
        /* DIS */ "G()",,,,

        /* PUT */ "G(),G(),H[x]=y",
        /* GET */ "z=S.push(H[G()])",,,,,

        /* LBL */ "R[h(1)]=p",
        /* JSR */ "h(1),p=X?R[P.push(p),V]:p",
        /* JMP */ "h(1),p=X?R[V]:p",
        /* JZE */ "h(1),p=X&!G()?R[V]:p",
        /* JMI */ "h(1),p=X&G()<0?R[V]:p",
        /* RTN */ "p=X?P.pop():p",,,
        /* END */ "p=X?g:p",,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

        /* ADD */ "z>1?(G(),G(),z=S.push(x+y)):p=X?g:p",
        /* SUB */ "z>1?(G(),G(),z=S.push(x-y)):p=X?g:p",
        /* MUL */ "z>1?(G(),G(),z=S.push(x*y)):p=X?g:p",
        /* DIV */ "z>1?(G(),G(),z=S.push(x/y|0)):p=X?g:p",
        /* MOD */ "z>1?(G(),G(),z=S.push(x%y)):p=X?g:p",,,,,,,,,,,,,,

        /* CHR */ "o+=Buffer([G()])",
        /* INT */ "o+=G()",,
        /* RCH */ "H[G()]=I[i++].codePointAt()",
        /* RNU */ "H[G()]=I[i++]"
      ][n - 9],
      x && eval(x, n = 1)
    ) < 3 && F(n * 3 + j)
  )(1)
)(0) || R(1) || o

```

# Answer
> 5 votes
# Pip Classic, ~~441~~ ~~399~~ 377 bytes

```
,:mn:@>gs:lt:v**@_*FBTM_a:(Ja@wTR"
"012`(00|01.|20.|21[01]).*?2|1[02]..|...`)M{!a@<2?"lPU(t".a@>2.')a@<3=10?"lPUl@(t".a@>3.')a@<3=12?"l:@lALl@>++(t".a@>3.')2=@a?("7080I!370I3<z70i:POs00sPUi7"^0a@<3%13).a@>3a=20?"lPU@l"a=21?"S@ll@o"a=22?3a=110?"Y36"a=111?"lPUm@3"a@1?("O C30O30Y APO@60YPO6"^0a)98J['*x"//"'%'+'-]@a}Wi<#a{Va@iR9"Y3l?lPU3"R8"y;Vk"R7"i:a@?"R6"nm@3:y"R3C`POl`++i}

```

Try it online!

Takes the Whitespace code as its first command-line argument, and the arguments to the Whitespace program as the following command-line arguments. (A string of characters should be given as a single argument.) The heap has a fixed size of 1000 entries.

### How?

The broad-strokes version:

* Strip non-whitespace characters from code
* Transliterate space, tab, and newline to 0, 1, and 2
* Use regex to break the program into a list of valid statements
* Translate each statement into Pip code
* While the program counter (initially set to 0) is less than the length of the program, execute the statement at that index and increment the program counter

When the program needs to halt, either because the Halt instruction was executed or because there were not enough operands for an arithmetic operation, it does so by throwing an error using the idiom `Vk` (explained in this tip).

### Ungolfed & commented

Here's the ungolfed version that I started from. **Note:** this is written in modern Pip, so it won't work on TIO. I've restructured the golfed version a bit, particularly to compress some of the cases in the translation section, but the basic approach is the same.

```
;;;;;;;;;;;
;; Setup ;;
;;;;;;;;;;;

; Use S/T/N temporarily for ease of development
$codepage : "STN"

; Stack starts out empty
$stack : []
; Heap size is 1000 (initial values don't matter)
$heap : u RL 1000

; Whitespace code is first command-line argument
$code : a
; Program inputs are remaining command-line args
$inputs : g @> 1
; Program counter starts at 0
$pc : 0

; To handle subroutines, we need to store a stack of return-to line numbers
$return_addrs : []

; Function to decode number literals
$to_int : {
  $magnitude : FB TM a
  $sign : (-1) E @a
  $sign * $magnitude
}

;;;;;;;;;;;;;
;; Parsing ;;
;;;;;;;;;;;;;

; Remove characters from code that aren't in codepage
$code FI: _ N $codepage
; Transliterate code from codepage to 0 (space), 1 (tab), and 2 (newline)
$code TR: $codepage 012

; Split code into separate instructions
$command_rgx : `(00|01.|20.|21[01]).*?2|1[02]..|...`
P $code : (J $code) @ $command_rgx

; Translate each instruction into Pip commands
$program : $code M {
  $instr : a
  ; Push a number
  $instr @< 2 Q 00 ? "$stack PU " . ($to_int $instr @> 2)
  ; Copy nth number on stack
  $instr @< 3 Q 010 ? "$stack PU $stack @ " . ($to_int $instr @> 3)
  ; Slide n numbers off from under top of stack
  $instr @< 3 Q 012 ? "$stack : $stack @ 0 AL $stack @> " . 1 + ($to_int $instr @> 3)
  ; Label (no-op)
  $instr @< 3 Q 200 ? $instr @> 3
  ; Gosub label
  $instr @< 3 Q 201 ? "$return_addrs PU $pc; $pc : $program @? " . $instr @> 3
  ; Goto label
  $instr @< 3 Q 202 ? "$pc : $program @? " . $instr @> 3
  ; If top of stack is zero, goto label
  $instr @< 3 Q 210 ? "I PO $stack = 0 $pc : $program @? " . $instr @> 3
  ; If top of stack is negative, goto label
  $instr @< 3 Q 211 ? "I PO $stack < 0 $pc : $program @? " . $instr @> 3
  ; Dup
  $instr Q 020 ? "$stack PU $stack @ 0"
  ; Swap
  $instr Q 021 ? "$stack @ 0 :: $stack @ 1"
  ; Drop
  $instr Q 022 ? "PO $stack"
  ; Add
  $instr Q 1000 ? "Y PO $stack; $stack ? $stack PU (PO $stack) + y; V k"
  ; Subtract
  $instr Q 1001 ? "Y PO $stack; $stack ? $stack PU (PO $stack) - y; V k"
  ; Multiply
  $instr Q 1002 ? "Y PO $stack; $stack ? $stack PU (PO $stack) * y; V k"
  ; Divide
  $instr Q 1010 ? "Y PO $stack; $stack ? $stack PU (PO $stack) // y; V k"
  ; Modulo
  $instr Q 1011 ? "Y PO $stack; $stack ? $stack PU (PO $stack) % y; V k"
  ; Store top of stack on heap at second-on-stack address
  $instr Q 110 ? "Y PO $stack; $addr : PO $stack; $heap @ $addr : y"
  ; Recall number from heap at top-of-stack address
  $instr Q 111 ? "$stack PU $heap @ PO $stack"
  ; Print as char
  $instr Q 1200 ? "O C PO $stack"
  ; Print as number
  $instr Q 1201 ? "O PO $stack"
  ; Read char and store it on heap at top-of-stack address
  $instr Q 1210 ? "Y A PO $inputs @ 0; $addr : PO $stack; $heap @ $addr : y"
  ; Read number and store it on heap at top-of-stack address
  $instr Q 1211 ? "Y PO $inputs; $addr : PO $stack; $heap @ $addr : y"
  ; Return from subroutine
  $instr Q 212 ? "$pc : PO $return_addrs"
  ; Halt
  $instr Q 222 ? "V k"
  ; Unrecognized instruction
  ""
}

P $program
P "------------"

;;;;;;;;;;;;;;;
;; Execution ;;
;;;;;;;;;;;;;;;

; Loop while the program counter hasn't gone past the end of the program
W $pc < # $program {
  ; Eval the current statement
  V $program @ $pc
  ; Increment the program counter
  U $pc
}

```

---
Tags: code-golf, string, interpreter, whitespace-language
---


# Question
Title: Smallest possible Scratch 3.0 project file (SB3)
The objective is to make the smallest SB3 file that can simply be imported into Scratch 3.0 without a "The project file that was selected failed to load" error. Any means can be used, like editing the JSON or better compression. Here's where I am with project.json, the only file inside mine:

```
{"targets":[{"isStage":true,"name":"Stage","variables":{},"lists":{},"broadcasts":{},"blocks":{},"comments":{},"costumes":[{"assetId":"00000000000000000000000000000000","name":"","md5ext":"00000000000000000000000000000000.svg","dataFormat":"svg"}],"sounds":[]}],"meta":{"semver":"3.0.0","vm":"0.0.0"}}

```

# Answer
> 2 votes
# 303 bytes

I think this is the lowest possible score. I managed to remove some more stuff from `project.json` and used the best compression 7-zip could offer me. File is here.

project.json

```
{"targets":[{"isStage":true,"name":"Stage","variables":{},"blocks":{},"costumes":[{"assetId":"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","name":"","md5ext":"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa.svg","dataFormat":"svg"}],"sounds":[]}],"meta":{"semver":"3.0.0","vm":"0.1.0"}}

```

# Answer
> 2 votes
# ~~263~~ 257 bytes

~~The MD5 uses 0s instead of As, `semver` and `vm`'s locations are swapped, `vm`'s `0.0.0`, `project.json`'s creation, modification and access times are 01/01/2000 00:00:00 with the N (none) attribute (Attribute Changer 10 used) and FileOptimizer's used to optimize the SB3's compression.~~

```
~~{"targets":[{"isStage":true,"name":"Stage","variables":{},"blocks":{},"costumes":[{"assetId":"00000000000000000000000000000000","name":"","md5ext":"00000000000000000000000000000000.svg","dataFormat":"svg"}],"sounds":[]}],"meta":{"vm":"0.0.0","semver":"3.0.0"}}~~
```
I've done some more swapping, used the A (archive) attribute and changed all the numbers to 3, even the date and time (03/03/3333 03:33:33). Oddly, the year 2108 problem occurs after optimization.
```
{"targets":[{"costumes":[{"assetId":"33333333333333333333333333333333","md5ext":"33333333333333333333333333333333.svg","dataFormat":"svg","name":""}],"name":"Stage","isStage":true}],"blocks":{},"sounds":[],"variables":{},"meta":{"semver":"3.3.3","vm":"3.3.3"}}
```

---
Tags: code-golf, compression, json
---


title: Infinite ordinals from a well-ordering

text:
# Question
Title: Infinite ordinals from a well-ordering
Your task is to write a short program that represents a large (infinite) ordinal, using a well-ordering of the set of positive integers. Your program will take two different positive integers and indicate which one is greater in your chosen well-ordering. The order type of the well-order is the represented ordinal. The challenge is to min-max your code size and the represented ordinal respectively.

# Explanation

Usually the positive integers are ordered like so:

```
1, 2, 3, 4, 5, ...

```

In this ordering, the expressions: `2 < 5`, `1 < 2`, `3 < 19`, are true, as usual. The expressions `5 < 2`, `10 < 3`, and so on, are false. However, we can order the positive integers also in the following way:

```
2, 4, 6, 8, 10, ..., 1, 3, 5, 7, ...

```

Here all the even numbers are followed by all the odd numbers. Now the expressions `2 < 1`, `6 < 8`, `1 < 5`, `100 < 51` are true, and the expressions `101 < 2` `5 < 3` and `120 < 110` are false.

This is another well-ordering:

```
2, 4, 6, 8, 10, ..., 3, 9, 15, 21, ..., 5, 25, 35, 55, ..., 7, 49, 77, ..., ..., 1

```

First we have all the even numbers, then all the remaining numbers that are divisible by 3, then ones that are divisible by 5 and so on. Finally, at the very end is 1. Notice that we have a nested "...". This is allowed. What is not allowed is a "..." that starts from the left.

```
1, 3, 5, 7, 9, ..., ..., 10, 8, 6, 4, 2

```

This is not a well-order (just a total order). A more rigorous way of stating this rule is that every nonempty subset must have a smallest element. Here the subset of even numbers doesn't have a smallest element.

Another way of looking at this, is to imagine starting from the right and walking to the left. You can jump over an arbitrary (possibly infinite) amount of numbers, but you have to always go left. If the numbers are well-ordered, your walk will always take a finite amount of steps. In this example however, you can just stay on the even side, by never jumping over the three dots, thus never reaching the beginning.

Notice that if you lay the three well-orders on top of each other like so:

```
1, 2, 3, 4, 5,  ...
2, 4, 6, 8, 10, ..., 1, 3, 5,  7,  ...
2, 4, 6, 8, 10, ..., 3, 9, 15, 21, ..., 5, 25, ..., ..., 1

```

They have different "length". The bottom one is the longest, and the top one is the shortest. The "length" is called the "order type", and it can be measured with an ordinal. Our first well-order has order type \\$\omega\\$, the second one \\$\omega\cdot2\\$ and the third one is \\$\omega^2+1\\$

Your program will compare two positive integers, according to a well-ordering of your choice. That way your program will represent the order type of your well-order.

For more info on ordinals, visit the Wikipedia page for ordinals and ordinal arithmetic. For more ordinals, visit Googology Wiki. Also check out the previous infinite ordinal question on Code Golf.

## More ordinal examples

\\$\omega\\$ `1, 3, 2, 4, 5, 7, 6, 8, ...`

\\$\omega^2\\$ `1, 2, 4, 8, 16, ..., 3, 5, 6, 9, 10, 12, 17, 18, ..., 7, 11, 13, 14, 19, 21, 22, ..., 15, 23, 27, ..., ...` (popcount then value)

\\$\omega^2+\omega\\$ `2, 4, 8, 16, 32, ..., 3, 9, 27, 81, ..., 5, 25, 125, ..., ..., 1, 6, 10, 12, 14, ...`

\\$\omega^\omega\\$ `1, 2, 4, 8, 16, ..., 3, 6, 12, 24, 48, ..., 9, 18, 36, 72, ..., ..., 5, 10, 20, 40, 80, ..., 15, 30, ..., 45, ..., ..., ..., etc.` (reverse lexiographic ordering of the standard form)

# Rules

You must pick a well-ordering on \\$\mathbb{Z}^+\\$. A well ordering is a binary relation \\$\<\\$ such that for all distinct elements \\$a\\$, \\$b\\$, \\$c\\$, \\$a\<b\space\veebar\space b\<a\\$ and \\$a\<b\space\land\space b\<c\implies a\<c\\$ and also for every nonempty subset \\$S\\$ of \\$\mathbb{Z}^+\\$, there is a minimal element \\$m\\$, so that for every other member \\$n\\$ in \\$S\\$, \\$m\<n\\$.

Your program will receive two distinct positive integers \\$a\\$ and \\$b\\$ in some reasonable format. The program will output TRUE if \\$a\<b\\$ and FALSE otherwise. Instead of "TRUE" and "FALSE", you can choose any two distinct output strings, such as ("true", "false"), ("1", "0") and so on.

Instead of reading from stdin/cmdline and writing to sdtout, you can make a function that takes two integers. The function should still have only two possible (distinct) return values, although they don't have to be strings.

If your programming language has no built-in bignum support, you can assume that a native integer datatype has infinite range (doesn't overflow).

# Scoring

Your score is the tuple \\$(Value, Bytes)\\$ where \\$Value\\$ is the represented ordinal and \\$Bytes\\$ is the number of bytes in your program. For example, if you implement the ordinal \\$\omega^3+\omega\\$ in 6 bytes, your score is \\$(\omega^3+\omega, 6)\\$.

To compare scores we define a partial order \\$\ge\\$ so that \\$(v\_0, b\_0)\ge (v\_1, b\_1)\\$ iff \\$v\_0\ge v\_1\\$ and \\$b\_0\le b\_1\\$. A score \\$(v\_0, b\_0)\\$ is better than a score \\$(v\_1, b\_1)\\$ iff \\$(v\_0, b\_0)\ge (v\_1, b\_1)\\$ and the scores are not equal.

In other words, your submission is better than another submission, if you achieve more bang-for-buck. That is, you achieve a bigger ordinal with the same number of bytes, or achieve the same ordinal, with a smaller amount of bytes. And obviously if you achieve a bigger ordinal with fewer bytes, your submission is better.

This does mean that some scores can't be compared. For example, \\$(\omega\cdot 2, 2)\\$ and \\$(\omega^2, 4)\\$ are incomparable.

You are a winner if there is no submission that is better than yours. If there are two or more submissions with the exact same score, the one submitted first is the winner. Since some scores can't be compared with others, there can be multiple winners. You are free to make multiple submissions, and possibly have multiple winning ones.

# List of winning submissions

| Bytes | Value | Language and Author |
| --- | --- | --- |
| 1 | \\$\omega\\$ | Polyglot - community wiki |
| 6 | \\$\omega^\omega\\$ | Pyth - Anders Kaseorg |
| 12 | \\$\omega^\omega+1\\$ | Husk - Dominic van Essen |
| 17 | \\$\varepsilon\_0\\$ | Pyth - Anders Kaseorg |
| 208 | \\$\phi\_{\Omega^\omega}(0)\cdot\omega\\$ | Haskell - Grain Ghost |
| 218+2\\$n\\$ | \\$\phi\_{\Omega^\omega}(0)^n\cdot\omega\\$ | Haskell - Grain Ghost |

# Answer
# Haskell, \\$(\omega, 3)\\$

This solution is dead simple, really can't be beat in Haskell.

```
(<)

```

Try it online!

# Haskell, \\$(\omega+n,19+2\left\lfloor\log\_{10}(n+1)\right\rfloor)\\$

Here's a scheme to get \\$\omega + n\\$ for any \\$n\in\mathbb{N}\\$. Just replace the `9`s below with one more than \\$n\\$. This will make the first \\$n\\$ numbers bigger than all other numbers but otherwise compare normally.

```
x#y=(x<9,x)<(y<9,y)

```

Try it online!

Looks like the leader board should now have an infinite number of winners. However we can beat an infinite number of these pretty easily. Most of this can just be done by fiddling with things a little bit up until we hit 26 bytes. So I will present my scores for 21, 23 and 25 without individual commentary. They should be pretty clear modifications of the 19 byte case.

### 21 bytes, \\$\omega+98\\$

```
x#y=(x<99,x)<(y<99,y)

```

### 23 bytes, \\$\omega+387420488\\$

```
x#y=(x<9^9,x)<(y<9^9,y)

```

### 25 bytes, \\$\omega+9^{99}-1\\$

```
(.q).(<).q
q x=(x<9^99,x)

```

Luckily this wraps up by 26 we can get to a much larger ordinal:

# Haskell, \\$(\omega\cdot n,26+\left\lfloor\log\_{10}(n)\right\rfloor)\\$

*Thanks to the OP for pointing out that I didn't need division for this.*

Another scheme much like the last, replace `9` with the desired number.

```
(.q).(<).q
q x=(mod x 9,x)

```

Try it online!

Once again we can use kolmogorov complexity to improve some of these. Here's a few that are currently records for their respective program sizes.

### 28 bytes, \\$\omega\cdot 9^9\\$

```
(.q).(<).q
q x=(x`mod`9^9,x)

```

### 29 bytes, \\$\omega\cdot 9^{99}\\$

```
(.q).(<).q
q x=(x`mod`9^99,x)

```

### 30 bytes, \\$\omega\cdot 9^{9^9}\\$

```
(.q).(<).q
q x=(x`mod`9^9^9,x)

```

### 31 bytes, \\$\omega\cdot 9^{9^{99}}\\$

```
(.q).(<).q
q x=(x`mod`9^9^99,x)

```

### 32 bytes, \\$\omega\cdot 9^{9^{9^9}}\\$

```
(.q).(<).q
q x=(x`mod`9^9^9^9,x)

```

### 33 bytes, \\$\omega\cdot 9^{9^{9^{99}}}\\$

```
(.q).(<).q
q x=(x`mod`9^9^9^9,x)

```

# Haskell, \\$(\omega^\omega, 63)\\$

Implements the order for \\$\omega^\omega\\$ in the question.

```
n#1=[]
n#a|mod a n<1=n#div a n++[n]|m<-n+1=m#a
y=(.(2#))
f=y.y(<)

```

Try it online!

# Haskell, \\$(\phi\_{\Omega^\omega}(0)\cdot\omega,208)\\$

This implements the same ordinal as in cardboard\_box's answer. It's slightly bigger than the small Veblen ordinal \\$\phi\_{\Omega^\omega}(0)\\$.

This could certain be golfed more. I'm not sure that either the type or the instance are really necessary, but for now it puts Haskell back on the leaderboard.

```
data T=T[T]deriving Eq
instance Ord T where a<=b=a==b||a<b;T a<T b=any(T a<=)b||(all(<T b)a&&(l a,a)<(l b,b))
l=length
c x|odd x,(y,t)<-c$div x 2=(T t:)<$>c y|1>0=(div x 2,[])
g f x|(y,t)<-c x=f(T t,y)
g.g(<)

```

Try it online!

# Haskell, \\$(\phi\_{\Omega^\omega}(0)^n\cdot\omega,218+2n)\\$

This example code at 222 bytes, iterates the previous algorithm twice. Giving \\$\phi\_{\Omega^\omega}(0)^2\cdot\omega\\$.

```
data T=T[T]deriving Eq
instance Ord T where a<=b=a==b||a<b;T a<T b=any(T a<=)b||(all(<T b)a&&(l a,a)<(l b,b))
l=length
c x|odd x,(y,t)<-c$div x 2=(T t:)<$>c y|1>0=(div x 2,[])
g f x|(y,t)<-c x=(T t,f y)
r=g$g id
f=(.r).(<).r

```

Try it online!

Every time we add a `g$` to the front of the definition of `r` we add 1 to the power at the cost of two bytes.

---

## Haskell Leaderboard

~~Since Haskell has been complete removed from the main leaderboard,~~ for now I am maintaining a short list of Haskell winners here

| Bytes | Value | Author |
| --- | --- | --- |
| 3 | \\$\omega\\$ | Grain Ghost |
| 19 | \\$\omega+8\\$ | Grain Ghost |
| 21 | \\$\omega+98\\$ | Grain Ghost |
| 22 | \\$\omega\cdot 2\\$ | xnor |
| 24 | \\$\omega\cdot 4\\$ | xnor |
| 25 | \\$\omega\cdot 12\\$ | xnor |
| 26 | \\$\omega\cdot 32\\$ | xnor |
| 27 | \\$\omega\cdot 99\\$ | Grain Ghost |
| 28 | \\$\omega\cdot 9^9\\$ | Grain Ghost |
| 29 | \\$\omega\cdot 9^{99}\\$ | Grain Ghost |
| 30 | \\$\omega\cdot 9^{9^9}\\$ | Grain Ghost |
| 31 | \\$\omega\cdot 9^{9^{99}}\\$ | Grain Ghost |
| 32 | \\$\omega\cdot 9^{9^{9^9}}\\$ | Grain Ghost |
| 33 | \\$\omega\cdot 9^{9^{9^{99}}}\\$ | Grain Ghost |
| 34 | \\$\omega^{10}\\$ | xnor |
| 53 | \\$\omega^\omega\\$ | AnttiP |
| 208 | \\$\phi\_{\Omega^\omega}(0)\cdot\omega\\$ | Grain Ghost |
| 218+2\\$n\\$ | \\$\phi\_{\Omega^\omega}(0)^n\cdot\omega\\$ | Grain Ghost |
> 10 votes

# Answer
# Pyth, \\$(ω^ω, 6)\\$

```
>_PE_P

```

Try it online!

Compares the reversed prime factorizations of the two inputs.

# Pyth, \\$(ε\_0, 17)\\$

```
L_SmylP#U_dPb>yEy

```

Try it online!

```
L                     def y(b):
           Pb           prime factors of b
   m                    map over d:
         _d               -d
        U                 range [-d, …, -1]
      P#                  filter for (negated) primes
     l                    count
    y                     recursively call y
  S                     sort
 _                      reverse
             >yEyQ    y(second input) > y(first input)

```

The ordinal corresponding to each positive integer is given by

$$α(p\_{i\_0}p\_{i\_1} \dotsc p\_{i\_{c-1}}) = \sum\_k ω^{α(i\_k)}$$

where \\$p\_i\\$ is the \\$i\\$th prime, and the sum on the right is taken in nonincreasing order of \\$α(i\_k)\\$ (since ordinal addition isn’t commutative). This allows us to build any ordinal with a finitely long Cantor normal form. For example:

```
α(1) = 0,          y(1) = []
α(2) = 1,          y(2) = [[]]
α(4) = 2,          y(4) = [[], []]
α(8) = 3,          y(8) = [[], [], []]
α(16) = 4,         y(16) = [[], [], [], []]
α(3) = ω,          y(3) = [[[]]]
α(6) = ω + 1,      y(6) = [[[]], []]
α(12) = ω + 2,     y(12) = [[[]], [], []]
α(9) = ω·2,        y(9) = [[[]], [[]]]
α(18) = ω·2 + 1,   y(18) = [[[]], [[]], []]
α(27) = ω·3,       y(27) = [[[]], [[]], [[]]]
α(7) = ω^2,        y(7) = [[[], []]]
α(14) = ω^2 + 1,   y(14) = [[[], []], []]
α(21) = ω^2 + ω,   y(21) = [[[], []], [[]]]
α(49) = ω^2·2,     y(49) = [[[], []], [[], []]]
α(19) = ω^3,       y(19) = [[[], [], []]]
α(5) = ω^ω,        y(5) = [[[[]]]]
α(10) = ω^ω + 1,   y(10) = [[[[]]], []]
α(15) = ω^ω + ω,   y(15) = [[[[]]], [[]]]
α(35) = ω^ω + ω^2, y(35) = [[[[]]], [[], []]]
α(25) = ω^ω·2,     y(25) = [[[[]]], [[[]]]]
α(13) = ω^(ω + 1), y(13) = [[[[]], []]]
α(23) = ω^(ω·2),   y(23) = [[[[]], [[]]]]
α(17) = ω^ω^2,     y(17) = [[[[], []]]]
α(11) = ω^ω^ω,     y(11) = [[[[[]]]]]
α(31) = ω^ω^ω^ω,   y(31) = [[[[[[]]]]]]

```

# Pyth, \\$(ε\_0, 19)\\$

```
L_S.ey-bkx1_jb2>yEy

```

Explanation for this old answer, which is now obsolete, but may be of interest for porting to languages lacking prime-related builtins.
> 10 votes

# Answer
# Python 2, \\$\psi\_0(\Omega^{\Omega^\omega})\cdot\omega\\$ with respect to Buchholz's psi, 266 bytes

```
l=len
T=lambda i,s='(',d=1:T(i/2,s+['),','('][i%2],d+i*2%4-1)if d else(eval(s)[0],i)
L=lambda A,B:any(A==b or L(A,b)for b in B)or all(L(a,B)for a in A)and(l(A)-l(B),0)<(0,next((L(a,b)for a,b in zip(A,B)if a!=b),0))
def f(a,b):A,a=T(a);B,b=T(b);return(a,0)<(b,L(A,B))

```

Try it online!

At least I think that's how this ordinal is written. It's a little bigger than the Small Veblen ordinal.

`T` is a bijective function that maps natural numbers `n` to tuples `(tree,remainder)` of ordered trees and natural numbers. It does so by treating the reversed binary representation of the input as a sequence of `(`s and `)`s, prepended by an extra `(`. Once the initial `(` is given a matching `)`, the unused bits form the remainder. For example, `37` is `100101` in binary, which gets reversed to `101001` which becomes `( ()()) 1`, giving `(()())` as the tree and `1` as the remainder.

`L` is a well ordering of ordered trees, the ordinal of which is the small Veblen ordinal. It is taken from Jervell, Herman Ruge (2005), "Finite Trees as Ordinals" (which I found via the Wikipedia article linked above). I horizontally mirrored it because it made the code shorter.

`f` accepts 2 natural numbers, converts them to `(tree,remainder)` tuples, and compares these by remainder first, then by tree.

Numbers which map to tuples in the form `(tree, 0)` form the small Veblen ordinal.

Tuples in the form `(tree, 1)` come next, then `(tree, 2)`, `(tree, 3)` etc. for a total of \\$\omega\\$ copies of the small Veblen ordinal, which I think is written \\$\phi\_{\Omega^\omega}(0)\cdot\omega\\$.

Note: while I defined `f` in terms of non-negative integers, the ordinal doesn't change if you only use strictly positive integers.
> 6 votes

# Answer
# Polyglot, \\$(\omega, 1)\\$

Feel free to add languages to the list.

```
<

```

Try it in:

Also one byte in 05AB1E, but  instead of `<`. Outputs `0`/`1`.
> 5 votes

# Answer
# Python 3, \\$(\omega^2,28)\\$

```
lambda a,b:(a&-a,a)<(b&-b,b)

```

Try it online!

Old version

This orders by number of trailing zeros (of binary rep) first and then by the number itself.
> 4 votes

# Answer
## Haskell, \\$ \omega \cdot 2\\$, 22 bytes

```
(.q).(<).q
q=odd>>=(,)

```

Try it online!

Based off Grain Ghost's Haskell answers. The function `q` is pointfree for `q x=(odd x,x)`. That is, we sort numbers by whether they're odd, then the number itself, which gives the evens followed by the odds. We can generalize this idea as:

### Haskell, \\$ \omega \cdot 4\\$, 24 bytes

```
(.q).(<).q
q=gcd 6>>=(,)

```

Try it online!

Partitions numbers by the greatest common divisors with 6, which is one of `[1,2,3,6]`. In general, we can replace 6 with any number \\$c\\$, and get order type \\$ \omega \cdot \sigma(c)\\$, where \\$ \sigma(c)\\$ counts the divisors of \\$c\\$. For instance:

### Haskell, \\$ \omega \cdot 12\\$, 25 bytes

```
(.q).(<).q
q=gcd 60>>=(,)

```

Try it online!

For 3 digits, 840 gives \\$ \omega \cdot 32\\$ for 26 bytes. The optimal values of \\$c\\$ to use are Highly Composite Numbers.

---

## Haskell, \\$\omega^{10}\\$, 34 bytes

```
(.q).(<).q
q=scanl1 min.show>>=(,)

```

Try it online!

The helper `scanl1 min.show` takes the decimal representation of a number and computes the running minimum, resulting in a non-increasing sequence. For example, `45271` becomes `44521`. We then compare these representations lexicographically, tiebroken by the number itself.

Let's show that the non-decreasing finite lists of digits \\$0,\dots,9\\$ are in well-ordered, with order type \\$\omega^{10}\\$. The lexicographic comparison first checks which sequence has more 9's in the prefix, tiebroken by whichever is followed by more 8's, and so on down to which ends with more 0's. So, if we represent the list as \\$a\_9\\$ 9's followed by \\$a\_8\\$ 8's, and so on to \\$a\_0\\$ 0's, the comparison is equivalent to comparing \\$a\_9, a\_8, \dots, a\_0\\$ lexicographically. Each \\$a\_i\\$ is an arbitrary natural number, so this is exactly the order type \\$\omega^{10}\\$.

The `scanl min` operation suffices to obtain almost every non-increasing sequence of digits 0 through 9, as is seen by it leaving the numbers represented by these digits unchanged -- the only exception is sequences made of only 0's, but their omission doesn't affect the order type. Moreover, each such sequence is produced by a finite number of values, a subset of the numbers with that many digits, and it doesn't matter what the tiebreak is among these values as long as there are no ties. So, the order type produced by the main function is also \\$\omega^{10}\\$.

Sorting the digits in decreasing order would have also worked, but Haskell doesn't have a built-in sort. In other languages, sorting would likely be the way to go.

If we could remove the cap of 9 from the values of the digits, we'd get order type \\$\omega^{\omega}\\$
> 4 votes

# Answer
# Husk, \\$\omega\\$, 2 bytes

```
¬<

```

Try it online!

Boring single-omega solution: well-ordering is just normal integer order (example 1 in question).

---

# Husk, \\$\omega\\$+1, 7 bytes

```
¬F<σ7\0

```

Try it online!

Omega+1: well-ordering is integers starting at 1 in normal order, but missing 7, and finally with 7 last, so: 1,2,3,4,5,6,8,9,10,...,7.
Change the `7` in the code to select any other digit at the end.

---

# Husk, \\$\omega\\$.2, 11 bytes

```
¬F<m?o_\I%2

```

Try it online!

Odd numbers first, then even numbers, so: 1,3,5,7,...,2,4,6,8,... .

---

# Husk, \\$ω^ω\\$, 6 bytes

```
¬¤<(↔p

```

Try it online!

Port of Neil's omega^omega approach: gets the reversed () `p`rime factors of each `¤` argument, and compares them lexicographically (`<`), finally taking the logical NOT (`¬`) to ensure only two output values.

---

# Husk, \\$ω^ω\\$+1, 12 bytes

```
¬¤>?o↔pȯ;\←←

```

Try it online!

Lexicographic ordering of reversed prime factors of inputs minus 1, but finally with `1` last: subtract 1 () from each (`¤`) input, then if the result is falsey (zero), convert it to a list containing infinity (`ȯ;\←`), otherwise make a list of its reversed () `p`rime factors, before comparing them (`>`) and taking the logical NOT (`¬`).
> 3 votes

# Answer
# Charcoal, \\$ω^2\\$, 10 bytes

```
‹⟦ΣθＮ⟧⟦ΣηＮ

```

Try it online! Link is to verbose version of code. Orders by sum of digits, then regular ascending order, resulting in the following ordering:

`1, 10, 100, ..., 2, 11, 20, 101, 200, ..., 3, 12, 21, 30, 102, 111, 120, 201, 210, 300, ..., 4, 13, 22, 31, 40, 103, 112, 121, 130, 202, 211, 220, 301, 400 ..., ...`

# Charcoal, \\$ω^2\cdot 9\\$, 14 bytes

```
‹⟦⌈θΣθＮ⟧⟦⌈ηΣηＮ

```

Try it online! Link is to verbose version of code. Orders by greatest digit, then sum of digits, then regular ascending order, resulting in the following ordering:

`1, 10, 100, ..., 11, 101, ..., 111, ..., ... 2, 20, 200, ..., 12, 21, 102, 120, 201, 210, ..., 22, 112, 121, 202, 211, 220, ..., ... 9, 90, 900, ..., 91, 109, 190, 901, 910, ..., 92, 119, 191, 209, 290, 902, 911, 920, ..., ...`

# Charcoal, \\$ω^3\\$, 16 bytes

```
‹⟦ΣΣθΣθＮ⟧⟦ΣΣηΣηＮ

```

Try it online! Link is to verbose version of code. Orders by sum of digits of sum of digits, then sum of digits, then regular ascending order, resulting in the following ordering:

`1, 10, ..., 19, 28, 37, 46, 55, 64, 73, 82, 91, ..., ... 2, 11, 20, ..., 29, 38, 47, 56, 65, 74, 83, 92, ..., ... 3, 12, 21, 30, ..., 39, 48, 57, 66, 75, 84, 93, ..., ... 4, 13, 22, 31, 40, ..., 49, 58, 67, 76, 85, 94, ..., ...`

# Charcoal, \\$ω^ω\cdot 9\\$, 29 bytes

```
Ｆ²⊞υ⟦Ｎ⟧Ｗ›⌈Ｅυ⌊κ⁹Ｆυ⊞κΣ⌊κ›⮌⊟υ⮌⊟υ

```

Try it online! Link is to verbose version of code. Repeatedly sums the digits of the inputs until they both reach their digital root, then compares the results in reverse order from the digital root working back to the original input. Since there are 9 digital roots and a potentially arbitrary number of summation steps I think I have the correct value for this. For small inputs the ordering is the same as the previous version; it first diverges for 199, which for instance compares less than 99 here but not in the previous ordering.
> 3 votes

# Answer
# Retina 0.8.2, \\$ω^ω\\$, 54 bytes

```
\d+
$*
+`\b(11+)(\1)+\b
$1 1$#2$*
^(.+)(,\1|\b.*,\1\B)

```

Try it online! Link includes test cases. Explanation:

```
\d+
$*

```

Convert to unary.

```
+`\b(11+)(\1)+\b
$1 1$#2$*

```

Factorise with the smallest prime factors last.

```
^(.+)(,\1|\b.*,\1\B)

```

Compare lexicographically.
> 2 votes

# Answer
# Python 2, \\$\omega^{10}\\$, 48 bytes

```
lambda*l:cmp(*[(sorted(`n`)[::-1],n)for n in l])

```

Try it online!

Outputs `-1` for `<` and `+1` for `>`

Takes each number and sorts its digits in descending order, then compares lexicographically. This effectively compares the count of digit 9's, tiebroken by the number of count 8's, and so on down to 0's. This is all tiebroken by the value of the number itself.

This having order type \\$\omega^{10}\\$ follows the same argument as my Haskell \\$\omega^{10}\\$ answer, with sorting replacing taking the running minimum.
> 2 votes

# Answer
# Haskell, \\$\omega^\omega\\$,62 53 bytes

```
i#0=[i]
i#a=(i+1)#sum[1|'0'<-show a]++[a]
a&b=1#a<1#b

```

Try it online!

*-9 bytes thanks to xnor*

Conceptually, this transforms an integer into an infinite list, that is made by iterating `sum[1|'0'<-show a]`, which just counts the zeroes, until zero is reached. Then it's just zeroes after that. Then those lists are then compared in reverse lexicographic order.

To actually do that in practice, the lists are constructed in reverse, and the head of the list is it's own length. The "ideal" infinite lists have an infinite trail of zeroes, which are removed in the "practical" ones. These zeroes are accounted for with the length.

For example, the number `100_000_000_001` has the "ideal" representation `[100_000_000_001,10,1,0,0,0,...]` and the "practical" representation `[4, 1, 10, 100_000_000_001]`
> 2 votes

---
Tags: math, code-challenge, decision-problem, open-ended-function, busy-beaver
---


# Question
Title: Make an array of random 128 bit integers
Given an input value \\$n\\$, construct an array of \\$n\\$ random 128 bit (unsigned) integers. The integers should be uniformly random.

Your code can use any in built random number generation function it has or you can implement your own. Clearly this challenge is harder (and more fun) in lower level languages.

# Answer
# x86-64 machine code, 10 bytes

Fortunately, there is a built-in RNG. Requires the RDRAND instruction.

```
00000000: c1e1 020f c7f0 abe2 fac3                 ..........

```

Disassembled:

```
shl ecx, 2
label:
 rdrand eax
 stosd
 loop label
ret

```

Outputs to a pre-allocated buffer in `rdi`. `n` is passed in `ecx` (arrays with 2^30 elements and more are not supported).

Try it online! (a helper function is needed because of the unusual calling convention)
> 13 votes

# Answer
# Vyxal, 7 bytes

```
ƛ₇ƛ₀℅;B

```

Try it Online!

```
ƛ       # Map...
 ₇ƛ  ;  # Map 128 to...
   ₀℅   # Random choice from digits of 10
      B # Convert to base 10

```

Or if it's allowed not to complete within the lifetime of the universe, 5 bytes:

```
ƛ₇Eʁ℅

```

Try it Online!

```
ƛ     # Map...
 ₇E   # 2 ** 128
   ʁ  # Range (0...x)
    ℅ # Choose a random item

```

It's trying to generate a 2128-item array, do you think it's gonna finish any time soon?
> 4 votes

# Answer
# JavaScript (Node.js),  ~~72~~  70 bytes

*Saved 2 bytes thanks to @RedwolfPrograms*

The helper function `g` builds a 128-bit integer, one bit at a time. This seems a bit long...

```
n=>Array(n).fill(128n).map(g=k=>k--&&BigInt(Math.random()<.5)|2n*g(k))

```

Try it online!
> 4 votes

# Answer
# Befunge-98 (PyFunge), ~~57~~ 37 bytes

```
&'wa+0> #;\1-:9j;+1?;#*2\_$.1-:!#@_1j

```

Try it online! Note that the input has to have a trailing space because of a bug in the interpreter.

The part generating a random 128-bit number bit by bit is explained below:

```
'wa+0> #;\1-:9j;+1?;#*2\_\.@

```

Try it online!

```
'wa+                           push loop counter, initially 129
    0                          push initial number 0
     >                         if the IP is coming from the right, turn it around
       #;                      # skips the next instruction
         \                     swap to the loop counter
          1-:                  decrement it and push an additional copy
             9j                skip over the next 9 instructions
                        _      if the loop counter is 0, go right:
                         \.      swap to the number and print it
                           @     terminate the execution
                        _      else, go right:
                     *2\         swap to the number and multiply by 2
                  ?              go into a random direction, if up or down is selected, ? gets executed again
        ;          ;             if right is selected, jump to the next semicolon and continue with the next iteration
     > #;      ;+1               if left, increment the number and go to the next iteration

```

Animation with 9 instead of 128 bits:
> 3 votes

# Answer
# C (gcc), ~~68~~ 42 bytes

```
f(n,a)char*a;{for(n*=16;n--;)a[n]=rand();}

```

Try it online!

* takes an 0 array and the number requested as input
* the array I taken as \*char to be manipulated byte by byte so that we set every 8bit to rand() which is RAND\_MAX e.g. At least 32767 and thus guaranteed to affect every bit
* numbers printed as decimal thanks to this good answer on the topic I copy-pasted-adapted
> 3 votes

# Answer
# Julia 1.0, 18 bytes

```
!n=rand(UInt128,n)

```

Try it online!

sorry, ~~boring~~ useful built-in
> 3 votes

# Answer
# Python 2

**~~54~~ 53 bytes**: Try it online!

```
lambda n:map(randrange,[4**64]*n)
from random import*

```

**69 bytes**: Try it online!

```
lambda n:[int(os.urandom(i).encode('hex'),i)for i in[16]*n]
import os

```

---

# Python 3

**54 bytes**: Try it online!

```
lambda n:[*map(randbits,[128]*n)]
from secrets import*

```

**~~57~~ 56 bytes**: Try it online!

```
lambda n:[*map(randrange,[4**64]*n)]
from random import*

```

**70 bytes**: Try it online!

```
lambda n:[int.from_bytes(os.urandom(i),'big')for i in[16]*n]
import os

```
> 2 votes

# Answer
# Factor, ~~33~~ 31 bytes

```
[ [ 128 2^ random ] replicate ]

```

Try it online!

* `replicate` Create a sequence given a number of elements and a generating quotation.
* `128 2^` 2128
* `random` Return a uniformly random number (via Factor's default Mersenne Twister PRNG) from 0 to whatever number is on top of the data stack minus one.
> 2 votes

# Answer
# , ~~24~~ 22 bytes

*Edit: -1 byte thanks to pajonk*

```
runif(scan())*4^64%/%1

```

Try it online!

Output is an integer uniformly selected from the range `0`...`2^128-1`.
does not natively support 128-bit inteters, so the data type of the output is a floating-point representation (click here for a TIO link that dispays all the digits, instead of displaying in scientific notation). Note though that although 128-bit numbers can be represented using floating-point variables, rounding inaccuracies can occur when more than 53 bits are required.

If floating point output (with its associated rounding inaccuracies) isn't Ok, we can output the exact value in the form of a vector of binary digits for **35 bytes** (or flattened into a string of bits for 41 bytes).

If neither floating point nor binary output are Ok, then base- will struggle a bit, but we can still manage by constructing string of random `0`-`9` digits (so including leading zeros), and checking that its lexicographically smaller than `"340282366920938463463374607431768211456"`, for a whopping **~~117~~ 113 bytes**:
`for(i in 1:scan())show({while((a=Reduce(paste0,sample(0:9,39,T)))>"340282366920938463463374607431768211456")0;a})`
> 2 votes

# Answer
# PowerShell, ~~57 bytes~~ 41 bytes

```
@(1..$n|%{(Random 1.0)*("2*"*128+1|iex)})

```

**Explanation:** `1..$n` enumerates integers from 1 to $n, `%` is an alias to `ForEach-Object`, `Random` decimal between 0 and 1.0, multiply by 2^128 through this clever obfuscation. `@()` encapsulates the result in an array, save 3 bytes if a actual array isn't needed.

Try it online!

**Original (57 bytes):**

```
@(1..$n|%{(Get-Random -Mi 0.0 -Ma 1)*[Math]::Pow(2,128)})

```
> 2 votes

# Answer
# Wolfram Language (Mathematica), ~~25~~ 24 bytes

*–1 byte thanks to Bubbler!*

```
RandomInteger[4^64-1,#]&

```

Try it online!

I wrote this and even I can't find anything interesting to say about it
> 2 votes

# Answer
# JavaScript (Browser), 99 bytes

```
n=>crypto.getRandomValues(a=new BigUint64Array(n*2)).reduce((r,v,i)=>i&1?[v<<64n|a[i^1],...r]:r,[])

```

This feature is introduced eailer this month by this post. And it currently requires a recent version of Firefox / Chromium Nightly build to run.

It is a sad story that words `crypto`, `getRandomValues`, `BigUint64Array` are too long for golfing.

```
const f=

n=>crypto.getRandomValues(a=new BigUint64Array(n*2)).reduce((r,v,i)=>i&1?[v<<64n|a[i^1],...r]:r,[])

{
let len = 5;
let arr = f(len);
for (let i = 0; i < arr.length; i++) {
  console.log(arr[i] + '')
}
}
```
> 2 votes

# Answer
# Excel, 62 bytes

```
=MID(CONCAT((RANDARRAY(A1*128)>0.5)*1),SEQUENCE(A1,,,128),128)

```

Link to Spreadsheet

Excel doesn't handle 128 bit integers. What this returns is technically n strings of 128 random 1s and 0s, which could be interpreted as n 128 bit binary integers. If Excel did handle 128 bit integers, then answer would be `=RANDARRAY(A1,,,2^128-1,1)` which is 26 bytes.
> 2 votes

# Answer
# 05AB1E, 7 bytes

```
LεžyoÝΩ

```

No TIO, since it won't finish anyway.

**Explanation:**

```
L        # Push a list in the range [1, (implicit) input-integer]
 ε       # Map each to:
  žy     #  Push builtin 128
    o    #  Pop and push 2 to the power this 128
     Ý   #  Pop and push a list in the range [0, 2^128]
      Ω  #  Pop and push a random item from this list
         # (after which the result is output implicitly)

```
> 2 votes

# Answer
# MathGolf, 5 bytes

```
É♣ów]

```

Try it online.

**Explanation:**

```
É      # Loop the (implicit) input amount of times,
       # using the following three characters as inner code-block:
 ♣     #  Push builtin 128
  ó    #  Pop and push 2**128
   w   #  Pop and push a random integer in the range [0,2**128)
]      # After the loop, wrap the entire stack into an array
       # (after which the entire stack is output implicitly as result)

```
> 2 votes

# Answer
# Ruby, 29 Bytes

```
->n{n.times.map{rand 2**128}}

```

# Try It Online
> 1 votes

# Answer
# Raku, 17 bytes

```
{roll ^4**64: $_}

```

Try it online!

`^4**64` is the range of numbers \[0, 2¹²⁸). The `roll` method returns randomly selected numbers from that range, in the quantity of `$_`, the input argument.
> 1 votes

# Answer
# Scala, 49 bytes

```
def f(n:Int)=Seq.fill(n)(BigInt(128,util.Random))

```

Try it online!
> 1 votes

# Answer
# Racket `srfi/27`, 45 bytes

```
(for/list([i n])(*(random-real)(expt 2 128)))

```

Try it online!

depends on `srfi/27` package
> 1 votes

# Answer
# C (gcc), 59 bytes

```
f(n){int*a=malloc(n*16),i=0;for(;i<n*4;)a[i++]=rand();n=a;}

```

Try it online!
> 1 votes

# Answer
# Python 3.8 (pre-release), 56 bytes

```
lambda n:eval('randint(0,4**64),'*n)
from random import*

```

Try it online!

Doesn't work for `n=0`.
> 1 votes

# Answer
# Rust with `rand`, 59 bytes

```
|n|->Vec<u128>{vec![0;n].iter().map(|_|random()).collect()}

```

Try it on Rust Playground!

`vec![0;n]` is a built-in macro that generates a `Vec` of length `n` with all values initialized to `0`. While this macro does accept an expression as the first argument, unfortunately it only evaluates it once, not for each item. Otherwise everything from `.iter()` to the end wouldn't be needed.

I was excited when I realised Rust has native support for 128-bit integer primitives through `i128` and `u128`, but then I realised Rust's stdlib no longer includes RNG features, meaning we need the `rand` crate to handle RNG. `random()` is from the `rand` crate. Specifically `random()` is an alias for `thread_rng().gen()` and generates a random value of the given, or inferred type.
Thankfully, rust's type inference is good enough that, even though we only specify `u128` in the return type of the closure, it figures it out and calls `random::<u128>()`
> 1 votes

# Answer
# Jelly, 7 bytes

```
Ø⁷2*X’)

```

Try it online!

A monadic link taking a single argument and returning a list of random 128-bit unsigned integers of that length.

## Explanation

```
      ) | For each value from 1..n
Ø⁷      | 128
  2*    | 2 ** that
    X   | Random Int from 1 to that
     ’  | Subtract 1

```

If the output can be from 1 to \\$2^{128}\\$ rather than 0 to \\$2^{128} - 1\\$, which for practical purposes is almost the same given how unlikely it is to generate the extremes, I can shave off a byte.
> 0 votes

# Answer
# Perl 5, 51 bytes

```
sub{join('',map chr rand 256,1..16*pop)=~/.{16}/sg}

```

Try it online!

Creates n random 128 bit integers. Or n strings of 16 random 8 bit chars. How to print the array elements as decimal numbers can be seen by clicking the "Try it online" link.
> 0 votes

# Answer
# Japt, 7 bytes

```
ÇMq2pIÑ
Ç       // Create the range [0..U) where U is the input, then map each value to
 Mq     // a random non-negative integer smaller than
   2    // 2
    p   // to the power of
     IÑ // 64 * 2.

```

Try it here.
> 0 votes

# Answer
# CJam, ~~20~~ 19 bytes

```
ri{L{2mr+}128*2bN}*

```

Try it online!

# CJam, ~~27~~ 24 bytes (Old method)

```
ri{8,{G*YG#(mr\m<}%:+N}*

```

Try it online!

**Edit:** had a better idea using the "repeat N times" operator. Saved 3 characters.

**Edit 2:** tried a completely new algorithm. Saved 4 characters.

**Edit 3:** went for the string manipulation side of things. Saved 1 character.
> 0 votes

# Answer
# Charcoal, 10 bytes

```
ＩＥＮ‽Ｘ²¦¹²⁸

```

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

```
  Ｎ         Input integer
 Ｅ          Map over implicit range
    Ｘ²¦¹²⁸  2¹²⁸
   ‽        Random integer (0-indexed)
Ｉ           Cast to string
            Implicitly print

```
> 0 votes

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


title: rank and unrank arrays of integers

text:
# Question
Title: rank and unrank arrays of integers
Consider all arrays of \\$\ell\\$ non-negative integers in the range \\$0,\dots,m\\$. Consider all such arrays whose sum is exactly \\$s\\$. We can list those in lexicographic order and assign an integer to each one which is simply its rank in the list.

For example, take \\$\ell=7, s=5, m=4\\$, the list could look like:

```
(0, 0, 0, 0, 0, 1, 4)  rank 1
(0, 0, 0, 0, 0, 2, 3)  rank 2
(0, 0, 0, 0, 0, 3, 2)  rank 3
(0, 0, 0, 0, 0, 4, 1)  rank 4
(0, 0, 0, 0, 1, 0, 4)  rank 5
(0, 0, 0, 0, 1, 1, 3)  rank 6
(0, 0, 0, 0, 1, 2, 2)  rank 7
(0, 0, 0, 0, 1, 3, 1)  rank 8
(0, 0, 0, 0, 1, 4, 0)  rank 9
[...]
(3, 2, 0, 0, 0, 0, 0) rank 449
(4, 0, 0, 0, 0, 0, 1) rank 450
(4, 0, 0, 0, 0, 1, 0) rank 451
(4, 0, 0, 0, 1, 0, 0) rank 452
(4, 0, 0, 1, 0, 0, 0) rank 453
(4, 0, 1, 0, 0, 0, 0) rank 454
(4, 1, 0, 0, 0, 0, 0) rank 455

```

This challenge requires you to produce two pieces of code/functions.

* Given a rank, compute the corresponding array directly. Call this function `unrank()`
* Given an array, compute its rank. Call this function `rank()`

Your code should run in polynomial time. That is it shouldn't be brute force and more specifically it should take \\$O(\ell^a s^b m^c)\\$ time for fixed non-negative integers \\$a, b, c\\$. Any non-brute force method is likely to satisfy this requirement.

# Examples

```
unrank((7, 5, 4), 9) = (0, 0, 0, 0, 1, 4, 0)
rank((7, 5, 4), (4, 0, 0, 0, 0, 1, 0)) = 451
unrank((14,10, 8), 100001)  = (0, 0, 0, 1, 0, 0, 1, 3, 1, 2, 0, 0, 2, 0)
rank((14, 10, 8), (2, 0, 1, 1, 2, 0, 0, 0, 2, 1, 1, 0, 0, 0)) = 1000001

```

Your score will be the total size for your code

# Bounty notes

The bounty will be awarded to the answer with the best time complexity. Current best is \\$O(\ell s)\\$ time first by @loopywait (with help from Bubbler).

# Answer
# Charcoal, ~~116~~ 105 bytes

~~32~~ 26 bytes of code are shared between the two programs, although I'm currently counting this separately for each program:

```
⊞υＥ⊕η¬ιＦ⊖θ⊞υＥ⊕ηΣ✂…§υι⊕κ±⊕ζ

```

Explanation:

```
⊞υＥ⊕η¬ι

```

Start with a list of a `1` followed by `s` `0`s. This represents the count of arrays of length `0` with sums of `0` to `s`.

```
Ｆ⊖θ

```

Extend the list of lists up to arrays of length `l-1`.

```
⊞υＥ⊕ηΣ✂…§υι⊕κ±⊕ζ

```

For each sum of `0` to `s` calculate the number of arrays with that sum.

~~63~~ 57 bytes for `unrank`:

```
⊞υＥ⊕η¬ιＦ⊖θ⊞υＥ⊕ηΣ✂…§υι⊕κ±⊕ζＦ⮌υ«≔⁰δＷ¬›§ιηε«≧⁻§ιηε≦⊖η≦⊕δ»⟦Ｉδ

```

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

```
Ｆ⮌υ«

```

Loop over each element.

```
≔⁰δ

```

Start with a current element of zero.

```
Ｗ¬›§ιηε«

```

Repeat while there are still sufficient counts of shorter arrays:

```
≧⁻§ιηε

```

Subtract the count from the rank.

```
≦⊖η

```

Decrement the remaining sum.

```
≦⊕δ

```

Increment the current element.

```
»⟦Ｉδ

```

Output the current element.

~~53~~ 48 bytes for `rank`:

```
⊞υＥ⊕η¬ιＦ⊖θ⊞υＥ⊕ηΣ✂…§υι⊕κ±⊕ζＰＩΣＥε↨¹Ｅι§§⮌υκ⁻Σ✂εκθ¹λ

```

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

```
ＰＩΣＥε↨¹Ｅι§§⮌υκ⁻Σ✂εκθ¹λ

```

For each element in the array to rank, get the count of arrays of the remaining length with sums of between the remaining sum including and excluding the current element.

It's possible to replace the shared code with a 51 byte version that reduces the time complexity by using a sliding window to calculate the counts of arrays with specific lengths and sums.

```
≔Ｅ⊕η¬ιτＦθ«⊞υτ≔⟦⟧σ≔⁰δＦ⊕η«≧⁺§τκδ⊞σδ¿¬‹κζ≧⁻§τ⁻κζδ»≔στ»Ｆ⮌υ«≔⁰δＷ¬›§ιηε«≧⁻§ιηε≦⊖η≦⊕δ»⟦Ｉδ

```

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

```
≔Ｅ⊕η¬ιτＦθ«⊞υτ≔⟦⟧σ≔⁰δＦ⊕η«≧⁺§τκδ⊞σδ¿¬‹κζ≧⁻§τ⁻κζδ»≔στ»ＰＩΣＥε↨¹Ｅι§§⮌υκ⁻Σ✂εκθ¹λ

```

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

# Answer
# Python 3, 326,334 bytes (+8 to fix complexity @Bubbler)

```
def P(l,m,s,o):
 *r,o=0,o+m*o[-1:]
 for y,z in zip(o[:s+1],-~m*[0]+o):r[len(r):]=r[-1]+y-z,
 return l*o and P(l-1,m,s,r[1:])+[o]
def R(p,L):
 l,m,s=p;T=P(*p,[1,1]);r=0
 for t,l in zip(T,L):r+=t[s]-t[s-l];s-=l
 return r
def U(p,r):
 l,m,s,*L=p;T=P(*p,[1,0])
 for t in T:
  j=m
  while(t[s]<=r)*j:r-=t[s];s-=1;j-=1
  L+=[m-j]
 return L

```

Try it online!

Old version

Doesn't feel very short, but maybe a byte count of "only" 3x the golfy languages is acceptable.

If I'm not mistaken, both R and U are O(lm).\**Nonsense!\**O(ls) using @Bubbler's suggestion.

The function P creates generalised Pascal's triangles where new rows are generated by taking sums of m+1 elements of the current (m=1 in the original Pascal's triangle). Generalising binomial coefficients which count sums made out a total of of *l*-*s* 0s and *s* 1s, the entries of the generalised triangles count sums of 0s,1s,...,*m*s with *l* terms and sum *s*.

Implementation notes: The output contains a few padding elements on the right end for convenience. By passing \[1,0\] or \[1,1\] for *o* we can choose between the plain triangle (used by U) or the partial row sums (used by R). To limit complexity we calculate only the first s+1 terms in every row.
> 4 votes

# Answer
# Pari/GP, 142 bytes

```
r(l,s,m,a)=y=x^m++\(x-1);sum(i=1,l,t=a[i];polcoef(y%x^t*y^(l-i),t+s-=t))
u(l,s,m,q)=a=vector(l);for(i=1,l,until(r(l,s,m,a)>q,a[i]++);a[i]--);a

```

Try it online!

The rank is 0-indexed.
> 1 votes

---
Tags: code-golf, combinatorics, restricted-complexity
---