title: Write a formatted Morse code cheatsheet

text:
# Question
Title: Write a formatted Morse code cheatsheet
# Challenge:

Write a program that produces the following output:

```
. E   .. I   ... S   .... H
                     ...- V
             ..- U   ..-. F
                     ..--
      .- A   .-. R   .-.. L
                     .-.-
             .-- W   .--. P
                     .--- J
- T   -. N   -.. D   -... B
                     -..- X
             -.- K   -.-. C
                     -.-- Y
      -- M   --. G   --.. Z
                     --.- Q
             --- O   ---.
                     ----

```

This is a formatted table of the Morse codes of the letters from A to Z. Each column is separated by three spaces.

There are four missing slots, which are used by international character sets. Your program must write a space there.

The output must consist of ASCII spaces, dots, dashes, uppercase letters and newlines (either LF or CRLF) only.

Your program accepts no input.

The following is a sample Python program that produces the desired output:

```
b = "."
out = []
last = 0
ch = "EISHVUF ARL WPJTNDBXKCYMGZQO  "
cx = 0
while b:
    if last >= len(b):
        print("   ".join(out))
        out = ["   ", "    ", "     ", "      "][0:len(b) - 1]
    out.append(b + " " + ch[cx])
    cx += 1
    last = len(b)
    if len(b) < 4:
        b += "."
    elif b[-1] == ".":
        b = b[0:-1] + "-"
    else:
        i = len(b) - 1
        while b[i] == "-":
            i -= 1
            if i < 0:
                break
        if i < 0:
            break
        b = b[0:i] + "-"
print("   ".join(out))

```

This is , so the shortest answer in bytes wins.

# Answer
> 5 votes
# Jelly, 85 bytes

```
ØQj⁶“_ȦeƤbṅỌU@⁼Cq’œ?;⁶$⁺ṁ®L€€¤
4R2ṗ©ị⁾.-;€€⁶ż"¢;€€⁶$⁺W€€j"731Dẋ@⁶¤ZµKFṚ;⁶ẋ³¤ḣ29ṫ3Ṛµ€Y

```

A full program printing the cheat sheet.

**Try it online!**

### How?

*Note:* I do think there may be a way to trim this down by forming a list which formats correctly by use of the grid atom, `G`, but I can't quite work out how.

```
ØQj⁶“_ȦeƤbṅỌU@⁼Cq’œ?;⁶$⁺ṁ®L€€¤ - Link 1: get "letters" lists: no arguments
ØQ                             - Qwerty yield = ["QWERTYUIOP","ASDFGHJKL","ZXCVBNM"]
  j⁶                           - join with spaces = "QWERTYUIOP ASDFGHJKL ZXCVBNM"
    “_ȦeƤbṅỌU@⁼Cq’             - base 250 number = 23070726812742121430711954614
                  œ?           - lexicographical permutation at index = "ETIANMSURWDKGOHVF L PJBXCYZQ"
                       ⁺       - do this twice:
                      $        -   last two links as a monad
                    ;⁶         -     concatenate a space              = "ETIANMSURWDKGOHVF L PJBXCYZQ  "
                             ¤ - nilad followed by link(s) as a nilad:
                         ®     -   recall from registry (4R2ṗ from the Main link)
                          L€€  -   length for €ach for €ach = [[1,1],[2,2,2,2],[3,3,3,3,3,3,3,3],[4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4]]
                        ṁ      - mould like = ["ET","IANM","SURWDKGO","HVF L PJBXCYZQ  "]

4R2ṗ©ị⁾.-;€€⁶ż"¢;€€⁶$⁺W€€j"731Dẋ@⁶¤ZµKFṚ;⁶ẋ³¤ḣ29ṫ3Ṛµ€Y - Main link: no arguments
4R                                                     - range(4) = [1,2,3,4]
  2ṗ                                                   - Cartesian power with 2 = [[[1],[2]],[[1,1],[1,2],[2,1],[2,2]],...,[...,[2,2,2,2]]]
    ©                                                  - copy to register and yield
      ⁾.-                                              - literal ['.','-']
     ị                                                 - index into (makes all the codes, in four lists by length like reading the output top-bottom, left-right)
         ;€€⁶                                          - concatenate a space to each code
               ¢                                       - call last link (1) as a nilad (get the letters reordered as required)
             ż"                                        - zip left and right with zip dyad
                     ⁺                                 - do this twice:
                    $                                  -   last two links as a monad:
                ;€€⁶                                   -     concatenate a space to each code, letter pair
                      W€€                              - wrap each code, letter pair in a list
                                  ¤                    - nilad follwed by link(s) as a nilad:
                           731                         -   literal 731
                              D                        -   to decimal list = [7,3,1]
                               ẋ@⁶                     -   repeat a space = ["       ","   "," "]
                         j"                            - zip with dyad join
                                   Z                   - transpose
                                    µ              µ€  - for each:
                                     K                 -   join with spaces
                                      F                -   flatten
                                       Ṛ               -   reverse
                                            ¤          -   nilad followed by link(s) as a nilad:
                                         ⁶ẋ³           -     space repeated 100 times
                                        ;              -   concatenate
                                             ḣ29       -   head to 29 (make all "lines" the same length)
                                                ṫ3     -   tail from 3 (trim off two spaces from each line)
                                                  Ṛ    -   reverse
                                                     Y - join with newlines
                                                       - implicit print

```

# Answer
> 7 votes
# Python 3.6, ~~201~~ ~~197~~ ~~193~~ 187 bytes

```
for i in range(16):print('   '.join(i%k and' '*(2+j)or f'{i//k:0{j}b}'.replace(*'0.').replace(*'1-')+' '+'ETIANMSURWDKGOHVF L PJBXCYZQ  '[2**j-2+i//k]for j,k in zip((1,2,3,4),(8,4,2,1))))

```

Uses some formatting, unpacking and A000918 magic.

# Answer
> 5 votes
# Retina, 125 bytes

```
^
. EISHVUF_ARL_WPJ¶- TNDBXKCYMGZQO__
+m`^((.*?)([-.]+) )(\w)((\w)+?)(((?<-6>)\w)+)$
$2$3 $4   $3. $5¶$.1$*     $3- $7
T`\_`p

```

Try it online! Should be 121 bytes but I was too lazy to deal with the whitespace at the start and end. Explanation:

```
[blank line]
. EISHVUF_ARL_WPJ¶- TNDBXKCYMGZQO__

```

The letters whose code begins with `.` and `-` respectively are preloaded. (It is theoretically possible to avoid preloading the `.-` but it saves bytes this way.) `_`s are used instead of spaces as they are considered to be letters which makes them easier to match below.

```
+m`^((.*?)([-.]+) )(\w)((\w)+?)(((?<-6>)\w)+)$
$2$3 $4   $3. $5¶$.1$*     $3- $7

```

Here we split each line up into five pieces:

* The letters for prefixes, if any
* The current Morse code
* The current letter
* The first half of the remaining letters (their next character is `.`)
* The second half of the remaining letters (their next character is `-`)

The pieces are then reassembled onto two lines:

* The letters for prefixes, the current Morse code, the current letter, the Morse code with a `.` suffix, the first half of the remaining letters
* Spaces replacing the first three pieces, the Morse code with a `-` suffix, the second half of the remaining letters

The new lines follow the same format as the existing line, just with an extra Morse prefix and half as many letters remaining to process. This is then repeated until each line has only one letter.

```
_
  [single space]

```

The `_`s are then changed back into spaces.

# Answer
> 3 votes
## JavaScript (ES6), ~~154~~ ~~147~~ 145 bytes

```
f=(n=r='',d=i=k=0)=>(r+=n&&' '.repeat([d++&&3,21,13,6][i-(i=d-k)])+n+' '+'EISHVUF ARL WPJTNDBXKCYMGZQO  '[k++],d<4)?f(n+'.',d)&&f(n+'-',d):r+=`
`

o.innerHTML = f()
```

```
<pre id=o>
```

# Answer
> 2 votes
# PHP, 208 Bytes

```
<?=gzinflate(base64_decode("dZDJEQMhDAT/RNEJaHLwfd+38w/EWrRlu6gVnwZpGhWIGSCxqhCXoFgWhpa3jHtpasYtKOaZZwZ9z/OjCnEOim3imX7et2Y8guKYeR5aF+PqB4/tK8Q0KMbDnnWPeZamZmyCYpJ5Pu/V93y7qxCLoHgnXnf5qZnn/iGo9u1/Gf+XDw=="));

```

Try it online!

# PHP, 229 Bytes

```
<?=strtr("3E0.3I053S0.53H12 2.54V1254U05-3F12 25-4 1.4A0.-3R0.-.3L12 2.-.4 12.-4W0.63P12 2.64J
4T0-3N0-.3D0-53B12 2-54X12-.4K0-.-3C12 2-.-4Y1-4M063G06.3Z12 26.4Q1264O0-63 12 2-64 ",[$a="   ","
$a$a","$a $a",". ","- ","..","--"]);

```

Try it online!

# Answer
> 2 votes
# Perl 5, ~~158~~ 156 bytes

```
map{$a=sprintf'%04b',$_;map{$a=~/.{$_}/;print(-$'?' 'x$_:$&=~y/01/.-/r,' ',(' EISHVUF ARL WPJTNDBXKCYMGZQO  '=~/./g)[!-$'&&++$i],$_-4?'   ':"\n")}1..4}0..15

```

# Answer
> 2 votes
# APL (Dyalog), 92 bytes

Needs `⎕IO←0` which is default on many systems.

```
0 3↓¯1⌽⍕{' ',(16⍴1↑⍨16÷≢⍵)⍀'.-'[⍉2⊥⍣¯1⍳≢⍵],' ',⍪⍵}¨'ET' 'IANM' 'SURWDKGO' 'HVF L PJBXCYZQ  '

```

Try it online!

`{``}¨'``'` apply the following anonymous function to each of the strings:

`⍪⍵` make the argument into a column

`' ',` prepend a space (on each row)

`'.-'[``],` prepend the string after it has been indexed with:

`≢⍵` the length of the argument

the indices of that (0, 1, 2, …, *length*-1)

`2⊥⍣¯1` anti-base-2 (uses as many bits as needed)

transpose (from one representation in each column to one in each row)

`(``)⍀` expand by (insert blank rows as indicated by zeros in):

`≢⍵` the length of the argument

`16÷` divide sixteen by that

`1↑⍨` (over)take from one (makes a list of a one followed by 1-*n* zeros)

`16⍴` recycle that pattern until it has sixteen elements

`' ',` prepend a space

format (the list of tables into a single table, padding each with a space on each side)

`¯1⌽` rotate one step right (thus moving the trailing space to the front)

`0 3↓` drop zero rows and three columns (thus removing the three leading spaces)

# Answer
> 2 votes
# PHP, ~~184 183~~ 181 bytes

```
for(;$y<16;$y++,print str_pad(ltrim("$r
"),28," ",0))for($r="",$c="03231323"[$y&7];$c++<4;)$r.=strtr(sprintf("   %0${c}b ",$y>>4-$c),10,"-.")."EISHVUF ARL WPJTNDBXKCYMGZQO  "[$i++];

```

Run with `-nr` or try it online.

**breakdown**

```
for(;$y<16;$y++,                                    # loop through rows
    print str_pad(ltrim("$r\n"),28," ",0)               # 4. pad to 28 chars and print
    )
    for($r="",                                          # 1. result=empty
        $c="03231323"[$y&7];                            # 2. $c=bits in 1st code -1
        $c++<4;)                                        # 3. loop through columns
        $r.=strtr(sprintf("   %0${c}b ",$y>>4-$c),10,"-.")  # append morse code
            ."EISHVUF ARL WPJTNDBXKCYMGZQO  "[$i++];            # append letter

```

---

**-7 bytes with leading spaces**: Replace `ltrim("$r\n")` with `"$r\n"` and `28` with `31`.

**171 (= -10) bytes with trailing spaces**:

```
for(;$y<16;$y++)for(print str_pad("
",[0,7,14,22][$c="03231323"[$y&7]]);$c++<4;)echo strtr(sprintf("%0${c}b %s   ",$y>>4-$c,"EISHVUF ARL WPJTNDBXKCYMGZQO"[$i++]),10,"-.");

```

**breakdown** try it online

```
for(;$y<16;$y++)                                    # loop through rows
    for(
        print str_pad("\n",[0,7,14,22][             # 2. print left padding
            $c="03231323"[$y&7]                     # 1. $c=bits in 1st code -1
        ]);
        $c++<4;)                                        # 3. loop through columns
        echo                                                # print ...
            strtr(sprintf("%0${c}b %s   ",                  # 3. delimiting spaces
            $y>>4-$c,                                       # 1. morse code
            "EISHVUF ARL WPJTNDBXKCYMGZQO"[$i++]            # 2. letter
        ),10,"-.");

```

# Answer
> 1 votes
# Bubblegum, 133 bytes

```
000000: e0 01 be 00   7d 5d 00 17   08 05 23 e4   96 22 00 5d │ à.¾.}]....#ä.".]
000010: e5 e9 94 d3   78 24 16 ec   c1 c4 ad d8   6e 4d 41 e8 │ åé.Óx$.ìÁÄ.ØnMAè
000020: a3 a1 82 e6   f4 88 d9 85   6f ae 6b 93   aa 44 c8 e3 │ £¡.æô.Ù.o®k.ªDÈã
000030: 29 6f df 65   aa 4a f8 06   f5 63 1a 73   a7 e4 4d 19 │ )oßeªJø.õc.s§äM.
000040: 03 2c 87 59   7b df 27 41   4b b6 12 dd   7c e5 78 27 │ .,.Y{ß'AK¶.Ý|åx'
000050: 9c 9f 99 db   f6 8e 42 fd   43 68 48 46   37 da d7 21 │ ...Ûö.BýChHF7Ú×!
000060: a9 ca ea be   f4 57 e0 da   c1 16 97 ef   7a 0c e9 3c │ ©Êê¾ôWàÚÁ..ïz.é<
000070: 8e c2 b6 22   ca e4 e5 53   57 f0 f4 fb   a4 fb c0 a7 │ .Â¶"ÊäåSWðôû¤ûÀ§
000080: ec cd 6e 00   00                                      │ ìÍn..

```

Compressed as a LZMA stream.

# Answer
> 1 votes
# SOGL, ~~106~~ ~~105~~ 102 bytes

```
¹θΞk“r²{r³³a:IA2─l4;- 0*;+Ζ0.ŗΖ1-ŗø4∫BƧ| ⁵±+⁷b<?⁄@*}+;j;@3*+}±kkk≥x}¹±č┐"7ŗ◄∑f^│N≥Χ±⅜g,ιƨΛ.⌡׀¹*ΛβΧκ‘čŗ

```

### If prepending spaces are allowed, ~~102~~ 99 bytes

```
¹θΞk“r²{r³³a:IA2─l4;- 0*;+Ζ0.ŗΖ1-ŗø4∫BƧ| ⁵±+⁷b<?⁄@*}+;j;@3*+}±≥x}¹±č┐"7ŗ◄∑f^│N≥Χ±⅜g,ιƨΛ.⌡׀¹*ΛβΧκ‘čŗ

```

### 141 bytes, compression

```
Πa≤χ≥∫RωθΩ≡⅛QΨ═Λ9⁶Ul¹&╔²‘č"‼¼⁸Ƨ,9█ω½└╗«ωΤC¡ιΝ/RL⌡⁄1↑οπ∞b∑#⁵ø⁶‘č"⁵ ?∙«Σf⁾ƨ╤P1φ‛╤Β«╚Δ≡ΟNa1\÷╬5ŗķ§⁷D◄tFhžZ@š⁾¡M<╔↓u┌⁽7¡?v¦#DΘø⌡ ⁹x≡ō¦;⁵W-S¬⁴‘' n

```

just wanted to see how well could SOGL do with just compression (well it's got more than just compression, but it's 97% compressed strings)

# Answer
> 1 votes
# Ruby, ~~144 143~~ 141 bytes

```
k=0
16.times{|i|4.times{|j|$><<("%0#{j+1}b 9   "%(i>>3-j)).tr('109',(i+8&-i-8)>>3-j>0?'-.'+'  OQZGMYCKXBDNTJPW LRA FUVHSIE'[k-=1]:" ")}
puts}

```

**Ungolfed**

```
k=0                                                     #setup a counter for the letters
16.times{|i|                                            #16 rows
  4.times{|j|                                           #4 columns
    $><<("%0#{j+1}b 9   "%(i>>3-j)).                    #send to stdout a binary number of j+1 digits, representing i>>3-j, followed by a 9, substituted as follows.
      tr('109',(i+8&-i-8)>>3-j>0?                       #(i&-i) clears all but the least significant 1's bit of i. the 8's ensure a positive result even if i=0.
      '-.'+'  OQZGMYCKXBDNTJPW LRA FUVHSIE'[k-=1]:      #if the expression righshifted appropriately is positive, substitute 1and0 for -and. Substitute 9 for a letter and update counter.
      " ")}                                             #else substiture 1,0 and 9 for spaces.
puts}                                                   #carriage return after each row.

```

# Answer
> 1 votes
## JavaScript (205 bytes)

```
for(A='EISHVUF ARL WPJTNDBXKCYMGZQO     ',q=0,i=15;30>i++;){for(x=i.toString(2).replace(/(.)/g,a=>1>a?'.':'-'),o='',j=4;j--;)o+=(i%2**j?A.slice(-6+j):x.slice(1,5-j)+' '+A.charAt(q++))+'   ';console.log(o)}

```

```
for(A='EISHVUF ARL WPJTNDBXKCYMGZQO     ',q=0,i=15;30>i++;){for(x=i.toString(2).replace(/(.)/g,a=>1>a?'.':'-'),o='',j=4;j--;)o+=(i%2**j?A.slice(-6+j):x.slice(1,5-j)+' '+A.charAt(q++))+'   ';console.log(o)}
```

# Answer
> 1 votes
# C, ~~199~~ 195 bytes

```
#define P putchar
m;p(i,v){printf("%*s",i&1|!v?v*(v+11)/2:3,"");for(m=1<<v;m;m/=2)P(45+!(i&m));P(32);P("  ETIANMSURWDKGOHVF L PJBXCYZQ  "[i]);v<3?p(2*i,v+1):P(10);++i&1&&p(i,v);}main(){p(2,0);}

```

Live on coliru (with #include to avoid the warning message.)

*UPDATE*: Saved four characters by moving the "declaration" of `m` outside the function, as suggested by @zacharyT

Uses what seems to be a standard strategy: keep the letters in an array-encoded binary tree, so the children of element `i` are `2*i` and `2*i+1`. This tree is rooted at 2 rather than 1 because the arithmetic worked out a little shorter, I think. All the rest is golfing.

Ungolfed:

```
// Golfed version omits the include
#include <stdio.h>
// Golfed version uses the string rather than a variable.
char* tree = "  ETIANMSURWDKGOHVF L PJBXCYZQ  ";
/* i is the index into tree; v is the number of bits to print (-1) */
void p(int i, int v) {
  /* Golfed version omits all types, so the return type is int.
   * Nothing is returned, but on most architectures that still works although
   * it's UB.
   */
  printf("%*s", i&1 || !v ? v*(v+11)/2 : 3, "");
  /* v*(v+11)/2 is v*(v+1)/2 + 3*v, which is the number of spaces before the odd
   * element at level v. For even elements, we just print the three spaces which
   * separate adjacent elements. (If v is zero, we're at the margin so we
   * suppress the three spaces; with v == 0, the indent will be 0, too.
   *
   * Golfed version uses | instead of || since it makes no semantic difference.
   */

  /* Iterate over the useful bits at this level */
  for (int m=1<<v; m; m/=2) {
    /* Ascii '-' is 45 and '.' is 46, so we invert the tested bit to create the
     * correct ascii code.
     */
    putchar('-' + !(i&m));
  }
  /* Output the character */
  putchar(' ');
  putchar(tree[i]);
  /* Either recurse to finish the line or print a newline */
  if (v<3)
    p(2*i,v+1);
  else
    putchar('\n');
  /* For nodes which have a sibling, recurse to print the sibling */
  if (!(i&1))
    p(i+1, v);
}

int main(void) {
  p(2,0);
}

```

# Answer
> 1 votes
# Pyth, 106 bytes

```
DhNR.n.e+]++.[\.sllN::.Bk\0\.\1\-\ b*]*\ +2sllNt/16lNNjmj*3\ d.t[h"ET"h"IANM"h"SURWDKGO"h"HVF L PJBXCYZQ

```

Test it online!

**Explanation**

In a few words, what I do here is to generate the table column by column and then transpose the table before printing it. We notice that in a column, the morse codes for the letters can be represented as binary strings (replace `.` by `0` and `-` by `1`) when counting from zero to the index of the last letter in the column.

The algorithm relies on a function from which I give an example run below (for the second column):

```
1. Takes "IANM" as input
2. Generates the binary representations of zero up to len("IANM"): ["0", "1", "10", "11"]
3. Replace with dots and hyphens: [".", "-", "-.", "--"]
4. Pad with dots up to floor(log2(len("IANM"))): ["..", ".-", "-.", "--"]
5. Add the corresponding letters: [".. I", ".- A", "-. N", "-- M"]
6. After each element, insert a list of 16 / len("IANM") - 1 (= 3) strings containing only spaces of length floor(log2(len("IANM"))) + 2 (= 4):
    [".. I", ["    ", "    ", "    "], ".- A", ["    ", "    ", "    "], "-. N", ["    ", "    ", "    "], "-- M", ["    ", "    ", "    "]]
7. Flatten that list:
    [".. I", "    ", "    ", "    ", ".- A", "    ", "    ", "    ", "-. N", "    ", "    ", "    ", "-- M", "    ", "    ", "    "]
8. That's it, we have our second column!

```

**Code explanation**

I cut the code in two. The first part is the function described above, the second part is how I use the function:

```
DhNR.n.e+]++.[\.sllN::.Bk\0\.\1\-\ b*]*\ +2sllNt/16lNN

DhNR                                                      # Define a function h taking N returning the rest of the code. N will be a string
      .e                                             N    # For each character b in N, let k be its index
                      .Bk                                 # Convert k to binary
                     :   \0\.                             # Replace zeros with dots (0 -> .)
                    :        \1\-                         # Replace ones with hyphens (1 -> -)
            .[\.sllN                                      # Pad to the left with dots up to floor(log2(len(N))) which is the num of bits required to represent len(N) in binary
          ++                     \ b                      # Append a space and b
         ]                                                # Make a list containing only this string. At this point we have something like [". E"] or [".. I"] or ...
        +                           *]*\ +2sllNt/16lN     # (1) Append as many strings of spaces as there are newlines separating each element vertically in the table
    .n                                                    # At this point the for each is ended. Flatten the resulting list and return it

```

<sup>(1)</sup>: In the morse table, in the first column, there is seven lines after each line containing a letter ("E" and "T"). In the second column, it is three lines. Then one (third column), then zero (last column). That is `16 / n - 1` where `n` is the number of letters in the column (which is `N` in the code above). That what does the code at line <sup>(1)</sup>:

```
*]*\ +2sllNt/16lN

       sllN          # Computes the num of bits required to represent len(N) in binary
     +2              # To that, add two. We now have the length of a element of the current column
  *\                 # Make a string of spaces of that length (note the trailing space)
           t/16lN    # Computes 16 / len(N) - 1
*]                   # Make a list of that length with the string of spaces (something like ["    ", "    ", ...])

```

Alright, now we have a nice helpful function `h` which basically generates a table's column out of a sequence of characters. Let's use it (note the two trailing spaces in the code below):

```
jmj*3\ d.t[h"ET"h"IANM"h"SURWDKGO"h"HVF L PJBXCYZQ

           h"ET"                                        # Generate the first column
                h"IANM"                                 # Generate the second column
                       h"SURWDKGO"                      # Generate the third column
                                  h"HVF L PJBXCYZQ      # Generate the last column (note the two trailing spaces)
          [                                             # Make a list out of those columns
        .t                                              # Transpose, because we can print line by line, but not column by column
 mj*3\ d                                                # For each line, join the elements in that line on "   " (that is, concatenate the elements of the lines but insert "   " between each one)
j                                                       # Join all lines on newline

```

The code can still be shortened; maybe I'll come back on it later.

# Answer
> 0 votes
# JavaScript (ES7), ~~242~~ ~~240~~ 238 bytes

```
console.log([...'EISH000V00UF000 0ARL000 00WP000JTNDB000X00KC000Y0MGZ000Q00O 000 '].map((a,k)=>(n=>(a!='0'?(2**n+(k>>2)/2**(4-n)).toString(2).slice(-n).replace(/./g,c=>'.-'[c])+' '+a:'      '.slice(-n-2))+(n<4?'   ':'\n'))(k%4+1)).join``)

```

Try it online!

–2 bytes thanks to Zachary.

# Answer
> 0 votes
# C, 291 bytes

**Try Online**

```
char*i,*t=".aEc..aIc...aSc....aH/u...-aV/m..-aUc..-.aF/u..--/f.-aAc.-.aRc.-..aL/u.-.-/m.--aWc.--.aP/u.---aJ/-aTc-.aNc-..aDc-...aB/u-..-aX/m-.-aKc-.-.aC/u-.--aY/f--aMc--.aGc--..aZ/u--.-aQ/m---aOc---./u----";
s(n){while(n--)putchar(32);}f(){for(i=t;*i;i++)*i<97?putchar(*i-'/'?*i:10):s(*i-96);}

```

**How it works**

First I parsed the string in C, counting spaces which are less than 26 so I encoded them in small case letters `a, b, .. z` with **this little program**

```
for(char*i=t; *i; i++)
{
    if(*i == ' ') c++;
    else c = 0;

    if(i[1] != ' ' && c > 0) putchar('a'+c-1);
    else if(*i =='\n') putchar('/');
    else if(*i != ' ') putchar(*i);
}

```

Then I wrote a parser for that encoding, where `/` is a new line, and a small-case letter represent `t[i] - 'a'` spaces

```
int s(int n)
{
    while(n--) putchar(32);
}

f()
{
    for(char*i=t; *i; i++)
        if(*i < 'a')
            if(*i == '/') putchar('\n');
            else putchar(*i);
        else s(*i-'a'+1);
}

```

# Answer
> 0 votes
# Bash (with utilities), 254 bytes

```
tail -n+2 $0|uudecode|bzip2 -d;exit
begin 644 -
M0EIH.3%!6293631+'LX``&UV`%`P(`!``S____`@`(@:2!H#:@!ZFU'H@T](
MJ>H`'J``;4L>\%)R2H9TS-4WY[M(`"`@=((AJ")8HR^QFK?8RQO2B+W47&@`
M!"@$(!%Q,$'X:#+&>BI<RAC5.J53,S(%FFB!%A-*SM9TY&I8RFZJ9<D0H_B[
)DBG"A(&B6/9P
`
end

```

# Answer
> 0 votes
# Dyalog APL, 159 bytes (non-competing)

```
↑{X←⍵-1⋄Y←2*⍳4⋄R←Y+(Y÷16)×⍵-1⋄3↓∊{C←R[⍵]⋄'   ',(⍵⍴(1+0=1|C)⊃'    '({⍵⊃'.-'}¨1+(4⍴2)⊤X)),' ',((1+0=1|C)⊃' '((C-1|C)⊃' ETIANMSURWDKGOHVF L PJBXCYZQ  '))}¨⍳4}¨⍳16

```

# Answer
> 0 votes
# Deadfish~, 1329 bytes

```
{iiii}iiiiiic{d}ddddc{iiii}dddc{dddd}iiiccc{i}iiiicc{d}ddddc{iiii}ic{dddd}dccc{i}iiiiccc{d}ddddc{iiiii}ic{ddddd}dccc{i}iiiicccc{d}ddddc{iiii}c{dddddd}ddc{ii}ii{cc}c{i}iiiicccdc{d}dddc{iiiii}iiiic{{d}iii}ddddddc{ii}ii{c}ccc{i}iiiiccdc{d}dddc{iiiii}iiic{ddddd}dddccc{i}iiiiccdcic{d}ddddc{iiii}ddc{dddddd}c{ii}ii{cc}c{i}iiiiccdcc{d}dddcc{dd}ddc{ii}iicccccc{i}iiiicdc{d}dddc{iii}iiic{ddd}dddccc{i}iiiicdcic{d}ddddc{iiiii}c{ddddd}ccc{i}iiiicdcicc{d}ddddc{iiii}iiiic{dddddd}ddddddc{ii}ii{cc}c{i}iiiicdcicdc{d}dddcc{dd}ddc{ii}ii{c}ccc{i}iiiicdcc{d}dddc{iiiii}iiiiic{ddddd}dddddccc{i}iiiicdccic{d}ddddc{iiiii}ddc{{d}iii}c{ii}ii{cc}c{i}iiiicdccc{d}dddc{iiii}iic{dddddd}ddddc{iii}iiiiic{d}dddc{iiiii}iic{ddddd}ddccc{i}iiicic{d}ddddc{iiii}iiiiiic{dddd}ddddddccc{i}iiicicc{d}ddddc{iii}iiiiiic{ddd}ddddddccc{i}iiiciccc{d}ddddc{iii}iiiic{ddddd}ddddddc{ii}ii{cc}c{i}iiiciccdc{d}dddc{iiiii}iiiiiic{{d}ii}iic{ii}ii{c}ccc{i}iiicicdc{d}dddc{iiii}iiic{dddd}dddccc{i}iiicicdcic{d}ddddc{iii}iiiiic{dddddd}iiic{ii}ii{cc}c{i}iiicicdcc{d}dddc{iiiiii}dddc{{d}ii}ic{ii}iicccccc{i}iiicc{d}dddc{iiii}iiiiic{dddd}dddddccc{i}iiiccic{d}ddddc{iiii}dc{dddd}iccc{i}iiiccicc{d}ddddc{iiiiii}ddc{{d}ii}c{ii}ii{cc}c{i}iiiccicdc{d}dddc{iiiii}dc{{d}iii}dc{ii}ii{c}ccc{i}iiiccc{d}dddc{iiiii}dddc{ddddd}iiiccc{i}iiicccic{d}ddddcc{dd}ddc{ii}ii{cc}c{i}iiicccc{d}dddcc{dd}ddc

```

Try it online!

# Answer
> 0 votes
# Excel, 208 bytes

```
=LET(x,ROW(1:16)-1,d,{1,2,3,4},y,4-d,z,2^y,m,IF(MOD(x,z)=0,SUBSTITUTE(SUBSTITUTE(DEC2BIN(x/z,d),"0","."),"1","-")&" "&MID(" ETIANMSURWDKGOHVF L PJBXCYZQ",2^d+x/z,1),""),CONCAT(m&IF(y,REPT(" ",9-LEN(m)),"
")))

```

## Explanation

```
=LET(x,ROW(1:16)-1,                                    'x = {0..15} 0-indexed row
d,{1,2,3,4},                                           'd = {1..4} 1-indexed column length of code
y,4-d,                                                 'y = {3..0}
z,2^y,                                                 'z = {8,4,2,1}
m,IF(MOD(x,z)=0,                                       'm = if x%z = 0 then
                      DEC2BIN(x/z,y)                   '   binary representation of x/z length y
SUBSTITUTE(SUBSTITUTE(              ,"0","."),"1","-") '   change "0" to "." and "1" to "-"
&" "&MID(" ETIANMSURWDKGOHVF L PJBXCYZQ",2^d+x/z,1),   '   & " " & corresponding letter
""),                                                   '   else ""
CONCAT(m&IF(y,REPT(" ",9-LEN(m)),"                     'concatenate the elements of m and pad w/ spaces and line feeds
")))

```

---
Tags: code-golf, ascii-art, kolmogorov-complexity, morse
---


title: Calculate the cube root of a number

text:
# Question
Title: Calculate the cube root of a number
The goal of this code golf is to create a program or function that calculates and outputs the cube root of a number that's given as input.
The rules:

* No external resources
* No use of built-in cube root functions.
* No use of methods/operators that can raise a number to a power (that includes square root, 4th root, etc.).
* Your function/program must be able to accept floating-point numbers and negative numbers as input.
* If the cube root is a floating-point number, then round it to 4 numbers after the decimal point.
* This is a code golf, the shortest code in bytes wins.

Test cases:

```
27 --> 3
64 --> 4
1  --> 1
18.609625 --> 2.65
3652264 --> 154
0.001 --> 0.1
7  --> 1.9129

```

You can use all test cases above to test negative numbers (`-27 --> -3`, `-64 --> -4` ...)

# Answer
> 6 votes
# J: 16 characters

Loose translation of the Haskell answer:

```
-:@((%*~)+])^:_~

```

Test cases:

```
   -:@((%*~)+])^:_~27
3
   -:@((%*~)+])^:_~64
4
   -:@((%*~)+])^:_~1
1
   -:@((%*~)+])^:_~18.609625
2.65
   -:@((%*~)+])^:_~3652264
154
   -:@((%*~)+])^:_~0.001
0.1
   -:@((%*~)+])^:_~7
1.91293

```

It works like this:

```
     (-:@((% *~) + ])^:_)~ 27
↔ 27 (-:@((% *~) + ])^:_) 27
↔ 27 (-:@((% *~) + ])^:_) 27 (-:@((% *~) + ])) 27
↔ 27 (-:@((% *~) + ])^:_) -: ((27 % 27 * 27) + 27)
↔ 27 (-:@((% *~) + ])^:_) 13.5185
↔ 27 (-:@((% *~) + ])^:_) 27 (-:@((% *~) + ])) 13.5185
↔ 27 (-:@((% *~) + ])^:_) -: ((27 % 13.5185 * 13.5185) + 13.5185)
↔ 27 (-:@((% *~) + ])^:_) 6.83313
...

```

In words:

```
half =. -:
of =. @
divideBy =. %
times =. *
add =. +
right =. ]
iterate =. ^:
infinite =. _
fixpoint =. iterate infinite
by_self =. ~

-:@((%*~)+])^:_~ ↔ half of ((divideBy times by_self) add right) fixpoint by_self

```

Not one of the best wordy translations, since there's a dyadic fork and a `~` right at the end.

# Answer
> 19 votes
# Haskell - 35

```
c n=(iterate(\x->(x+n/x/x)/2)n)!!99

```

Example runs:

```
c 27  =>  3.0
c 64  =>  4.0
c 1  =>  1.0
c 18.609625  =>  2.6500000000000004  # only first 4 digits are important, right?
c 3652264  =>  154.0
c 0.001  =>  0.1
c 7  =>  1.9129311827723892
c (-27)  =>  -3.0
c (-64)  =>  -4.0

```

Moreover, if you import `Data.Complex`, it even works on complex numbers, it returns one of the roots of the number (there are 3):

```
c (18:+26)  =>  3.0 :+ 1.0

```

The `:+` operator should be read as 'plus *i* times'

# Answer
> 8 votes
## SageMath, (69) 62 bytes

However, don't ever believe it will give you the result, it's very difficult to go randomly through all the numbers:

```
def r(x):
 y=0
 while y*y*y-x:y=RR.random_element()
 return "%.4f"%y

```

if you didn't insist on truncating:

```
def r(x):
 y=0
 while y*y*y-x:y=RR.random_element()
 return y

```

## SageMath, 12 bytes, if `exp` is allowed

Works for all stuff: positive, negative, zero, complex, ...

```
exp(ln(x)/3)

```

# Answer
> 5 votes
## Python - 62 bytes

```
x=v=input()
exec"x*=(2.*v+x*x*x)/(v+2*x*x*x or 1);"*99;print x

```

Evaluates to full floating point precision. The method used is Halley's method. As each iteration produces 3 times as many correct digits as the last, *99* iterations is a bit of overkill.

Input/output:

```
27 -> 3.0
64 -> 4.0
1 -> 1.0
18.609625 -> 2.65
3652264 -> 154.0
0.001 -> 0.1
7 -> 1.91293118277
0 -> 1.57772181044e-30
-2 -> -1.25992104989

```

# Answer
> 3 votes
## Javascript (55)

`function f(n){for(i=x=99;i--;)x=(2*x+n/x/x)/3;return x}`

**BONUS, General formulation for all roots**
`function f(n,p){for(i=x=99;i--;)x=x-(x-n/Math.pow(x,p-1))/p;return x}`

For cube root, just use `f(n,3)`, square root `f(n,2)`, etc... Example : `f(1024,10)` returns `2`.

**Explanation**
Based on Newton method :

Find : `f(x) = x^3 - n = 0`, the solution is `n = x^3`
The derivation : `f'(x) = 3*x^2`

Iterate :
`x(i+1) = x(i) - f(x(i))/f'(x(i)) = x(i) + (2/3)*x + (1/3)*n/x^2`

**Tests**

```
[27,64,1,18.609625,3652264,0.001,7].forEach(function(n){console.log(n + ' (' + -n + ') => ' + f(n) + ' ('+ f(-n) +')')})

27 (-27) => 3 (-3)
64 (-64) => 4 (-4)
1 (-1) => 1 (-1)
18.609625 (-18.609625) => 2.65 (-2.65)
3652264 (-3652264) => 154 (-154)
0.001 (-0.001) => 0.09999999999999999 (-0.09999999999999999)
7 (-7) => 1.912931182772389 (-1.912931182772389)

```

# Answer
> 3 votes
## Perl, 92 bytes

```
sub a{$x=1;while($d=($x-$_[0]/$x/$x)/3,abs$d>1e-9){$x-=$d}$_=sprintf'%.4f',$x;s/\.?0*$//;$_}

```
* The function `a` returns a string with the number without an unnecessary fraction part or insignificant zeroes at the right end.

Result:

```
              27 --> 3
             -27 --> -3
              64 --> 4
             -64 --> -4
               1 --> 1
              -1 --> -1
       18.609625 --> 2.65
      -18.609625 --> -2.65
         3652264 --> 154
        -3652264 --> -154
           0.001 --> 0.1
          -0.001 --> -0.1
               7 --> 1.9129
              -7 --> -1.9129
 0.0000000000002 --> 0.0001
-0.0000000000002 --> -0.0001
               0 --> 0
              -0 --> 0

```

Generated by

```
sub test{
    my $a = shift;
    printf "%16s --> %s\n", $a, a($a);
    printf "%16s --> %s\n", "-$a", a(-$a);
}
test 27;
test 64;
test 1;
test 18.609625;
test 3652264;
test 0.001;
test 7;
test "0.0000000000002";
test 0;

```

The calculation is based on Newton's method:

# Answer
> 2 votes
## PHP - 81 bytes

Iterative solution:

```
$i=0;while(($y=abs($x=$argv[1]))-$i*$i*$i>1e-4)$i+=1e-5;@print $y/$x*round($i,4);

```

# Answer
> 2 votes
## Javascript: 73/72 characters

This algorithm is lame, and exploits the fact that this question is limited to 4 digits after the decimal point. It is a modified version of the algorithm that I suggested in the sandbox for the purpose of reworking the question. It counts from zero to the infinite while `h*h*h<a`, just with a multiplication and division trick to handle the 4 decimal digits pecision.

```
function g(a){if(a<0)return-g(-a);for(h=0;h*h*h<1e12*a;h++);return h/1e4}

```

Edit, 4 years later: As suggested by Luis felipe De jesus Munoz, by using `**` the code is shorter, but that feature was not available back in 2014 when I wrote this answer. Anyway, by using it, we shave an extra character:

```
function g(a){if(a<0)return-g(-a);for(h=0;h**3<1e12*a;h++);return h/1e4}

```

# Answer
> 2 votes
## Java, 207 182 181

Sometimes when I play golf I have two many beers and play really really bad

```
class n{public static void main(String[]a){double d=Double.valueOf(a[0]);double i=d;for(int j=0;j<99;j++)i=(d/(i*i)+(2.0*i))/3.0;System.out.println((double)Math.round(i*1e4)/1e4);}}

```

Iterative Newton's Method of Approximation, runs 99 iterations.

Here is the unGolfed:

```
class n{
    public static void main(String a[]){
        //assuming the input value is the first parameter of the input
        //arguments as a String, get the Double value of it
        double d=Double.valueOf(a[0]);
        //Newton's method needs a guess at a starting point for the
        //iterative approximation, there are much better ways at
        //going about this, but this is by far the simplest. Given
        //the nature of the problem, it should suffice fine with 99 iterations
        double i=d;

        //make successive better approximations, do it 99 times
        for(int j=0;j<99;j++){
            i=( (d/(i*i)) + (2.0*i) ) / 3.0;
        }
        //print out the answer to standard out
        //also need to round off the double to meet the requirements
        //of the problem.  Short and sweet method of rounding:
        System.out.println( (double)Math.round(i*10000.0) / 10000.0 );
    }
}

```

# Answer
> 2 votes
# TI-Basic, ~~26~~ 24 bytes

```
Input :1:For(I,1,9:2Ans/3+X/(3AnsAns:End

```

# Answer
> 2 votes
# APL - 31

```
(×X)×+/1,(×\99⍴(⍟|X←⎕)÷3)÷×\⍳99

```

Uses the fact that `cbrt(x)=e^(ln(x)/3)`, but instead of doing naive  exponentiation, it computes `e^x` using Taylor/Maclaurin series.

Sample runs:

```
⎕: 27
3
⎕: 64
4
⎕: 1
1
⎕: 18.609625
2.65
⎕: 3652264
154
⎕: 0.001
0.1
⎕: 7
1.912931183
⎕: ¯27
¯3
⎕: ¯7
¯1.912931183

```

Seeing as there's a J answer in 16 characters, I must be really terrible at APL...

# Answer
> 2 votes
## Js 57 bytes

`f=(x)=>eval('for(w=0;w**3<1e12*x;w++);x<0?-f(-x):w/1e4')`

```
f=(x)=>eval('for(w=0;w**3<1e12*x;w++);x<0?-f(-x):w/1e4')
document.getElementById('div').innerHTML += f(-27) + '<br>'
document.getElementById('div').innerHTML += f(-64) + '<br>'
document.getElementById('div').innerHTML += f(-1) + '<br>'
document.getElementById('div').innerHTML += f(-18.609625) + '<br>'
document.getElementById('div').innerHTML += f(-3652264) + '<br>'
document.getElementById('div').innerHTML += f(-0.001) + '<br>'
document.getElementById('div').innerHTML += f(-7) + '<br><hr>'
document.getElementById('div').innerHTML += f(27) + '<br>'
document.getElementById('div').innerHTML += f(64) + '<br>'
document.getElementById('div').innerHTML += f(1) + '<br>'
document.getElementById('div').innerHTML += f(18.609625) + '<br>'
document.getElementById('div').innerHTML += f(3652264) + '<br>'
document.getElementById('div').innerHTML += f(0.001) + '<br>'
document.getElementById('div').innerHTML += f(7) + '<br>'
```

```
<div id="div"></div>
```

# Answer
> 1 votes
## Javascript - 157 characters

This function:

* Handle negative numbers.
* Handle floating-pointing numbers.
* Execute quickly for any input number.
* Has the maximum precision allowed for javascript floating-point numbers.

```
function f(a){if(p=q=a<=1)return a<0?-f(-a):a==0|a==1?a:1/f(1/a);for(v=u=1;v*v*v<a;v*=2);while(u!=p|v!=q){p=u;q=v;k=(u+v)/2;if(k*k*k>a)v=k;else u=k}return u}

```

Ungolfed explained version:

```
function f(a) {
  if (p = q = a <= 1) return a < 0 ? -f(-a)      // if a < 0, it is the negative of the positive cube root.
                           : a == 0 | a == 1 ? a // if a is 0 or 1, its cube root is too.
                           : 1 / f (1 / a);      // if a < 1 (and a > 0) invert the number and return the inverse of the result.

  // Now, we only need to handle positive numbers > 1.

  // Start u and v with 1, and double v until it becomes a power of 2 greater than the given number.
  for (v = u = 1; v * v * v < a; v *= 2);

  // Bisects the u-v interval iteratively while u or v are changing, which means that we still did not reached the precision limit.
  // Use p and q to keep track of the last values of u and v so we are able to detect the change.
  while (u != p | v != q) {
    p = u;
    q = v;
    k = (u + v) / 2;
    if (k * k * k > a)
      v=k;
    else
      u=k
  }

  // At this point u <= cbrt(a) and v >= cbrt(a) and they are the closest that is possible to the true result that is possible using javascript-floating point precision.
  // If u == v then we have an exact cube root.
  // Return u because if u != v, u < cbrt(a), i.e. it is rounded towards zero.
  return u
}

```

# Answer
> 1 votes
# PHP, 61

Based on Newton's method. Slightly modified version of Michael's answer:

```
for($i=$x=1;$i++<99;)$x=(2*$x+$n/$x/$x)/3;echo round($x,14);

```

It works with negative numbers, can handle floating point numbers, and rounds the result to 4 numbers after the decimal point if the result is a floating point number.

**Working demo**

# Answer
> 1 votes
# GameMaker Language, 51 bytes

```
for(i=x=1;i++<99;1)x=(2*x+argument0/x/x)/3;return x

```

# Answer
> 1 votes
# Smalltalk, 37

credit goes to mniip for the algorithm; Smalltalk version of his code:

input in n; output in x:

```
1to:(x:=99)do:[:i|x:=2*x+(n/x/x)/3.0]

```

or, as a block

```
[:n|1to:(x:=99)do:[:i|x:=2*x+(n/x/x)/3.0].x]

```

# Answer
> 1 votes
# Befunge 98 - Work in progress

This language does not support floating point numbers; this attempts to emulate them. It currently works for positive numbers that do not start with `0` after the decimal point (mostly). However, it only outputs to 2 decimal places.

```
&5ka5k*&+00pv
:::**00g`!jv>1+
/.'.,aa*%.@>1-:aa*

```

It works by inputting the part before the decimal point, multiplying that by `100000`, then inputting the part after the point and adding the two numbers together. The second line does a counter until the cube is greater than the inputted number. Then the third line extracts the decimal number from the integer.

If anyone can tell me why the third line only divides by `100` to get the correct values, please tell me.

IOs:

```
27.0       3 .0
64.0       4 .0
1.0        1 .0
18.609625  2 .65
0.001      0 .1
7.0        1 .91

0.1        0 .1

```

# Answer
> 0 votes
## Haskell: 99C

Can't beat @mniip in cleverness. I just went with a binary search.

```
c x=d 0 x x
d l h x
 |abs(x-c)<=t=m
 |c < x=d m h x
 |True=d l m x
 where m=(l+h)/2;c=m*m*m;t=1e-4

```

Ungolfed:

```
-- just calls the helper function below
cubeRoot x = cubeRoot' 0 x x

cubeRoot' lo hi x
    | abs(x-c) <= tol = mid           -- if our guess is within the tolerance, accept it
    | c < x = cubeRoot' mid hi x      -- shot too low, narrow our search space to upper end
    | otherwise = cubeRoot' lo mid x  -- shot too high, narrow search space to lower end
    where
        mid = (lo+hi)/2
        cubed = mid*mid*mid
        tol = 0.0001

```

# Answer
> 0 votes
## J 28

```
*@[*(3%~+:@]+(%*~@]))^:_&|&1

```

Using Newtons method, finding the root of `x^3 - X` the update step is `x - (x^3 - C)/(3*x^2)`, where x is the current guess, and C the input. Doing the maths on this one yields the ridiculously simple expression of `(2*x+C/x^2) /3` . Care has to be taken for negative numbers.

Implemented in J, from right to left:

1. `|` Take abs of both arguments, pass them on
2. `^:_` Do until convergence
3. `(%*~@])` is `C / x^2` (`*~ y` is equivalent to `y * y`)
4. `+:@]` is `2 x`
5. `3%~` divide by three. This yields the positive root
6. `*@[ * positive_root` multiplies positive root with the signum of C.

Test run:

```
   NB. give it a name:
   c=: *@[*(3%~+:@]+(%*~@]))^:_&|&1
   c 27 64 1 18.609625 3652264 0.001 7
3 4 1 2.65 154 0.1 1.91293

```

# Answer
> 0 votes
## AWK, 53 bytes

```
{for(n=x=$1;y-x;){y=x;x=(2*x+n/x/x)/3}printf"%.4g",y}

```

Example usage:

```
$ awk '{for(n=x=$1;y-x;){y=x;x=(2*x+n/x/x)/3}printf"%.4g",y}' <<< 18.609625
2.65$

```

Thanks go to @Mig for the `JavaScript` solution which this is derived from. It runs surprisingly quickly given that the `for` loop requires the iteration to stop changing.

# Answer
> 0 votes
# C, 69 bytes

```
i;float g(float x){for(float y=x;++i%999;x=x*2/3+y/3/x/x);return x;}

```

Just another implementation of Newton's method. Try it online!

# Answer
> 0 votes
# Stax, 10 bytesCP437

```
╘♀┘A╕äO¶∩'

```

Run and debug online!

## Explanation

Uses the unpacked version to explain.

```
gpJux*_+h4je
gp              Iterate until a fixed point is found, output the fix point
  Ju            Inverse of square
    x*          Multiplied by input
      _+h       Average of the value computed by last command and the value at current iteration
         4je    Round to 4 decimal digits

```

# Answer
> 0 votes
**JAVA Solution**

public BigDecimal cubeRoot(BigDecimal number) {

```
    if(number == null || number.intValue() == 0) return BigDecimal.ZERO;
    BigDecimal absNum = number.abs();
    BigDecimal t;
    BigDecimal root =  absNum.divide(BigDecimal.valueOf(3), MathContext.DECIMAL128);

    do {

        t = root;
        root = root.multiply(BigDecimal.valueOf(2))
                .add(absNum.divide(root.multiply(root), MathContext.DECIMAL128))
                .divide(BigDecimal.valueOf(3), MathContext.DECIMAL128);

    } while (t.toBigInteger().subtract(root.toBigInteger()).intValue() != 0);

    return root.multiply(number.divide(absNum), MathContext.DECIMAL128);
}

```

# Answer
> 0 votes
**Python Solution**

```
def cube_root(num):
    if num == 0:
        return 0

    t = 0
    absNum = abs(num)
    root = absNum/3

    while (t - root) != 0:
        t = root
        root = (1/3) * ((2 * root) + absNum/(root * root))

    return root * (num / absNum)

```

# Answer
> 0 votes
# MMIX, 44 bytes (11 instrs)

```
E0013FF0 48000002 E8018000 C1FF0100
1001FFFF 14010001 040101FF E401FFF0
11FF01FF 53FFFFFA F8020000

```

# Disassembly

```
cbrt    SETH  $1,#3FF0      // y = 1.
        BNN   $0,0F         // if(x >= 0) goto loop (ensuring sign is correct)
        ORH   $1,#8000      // y = fnabs(y) (bit tricks!)
0H      SET   $255,$1       // loop: prev = y
        FMUL  $1,$255,$255  // y = prev *. prev
        FDIV  $1,$0,$1      // y = x /. y
        FADD  $1,$1,$255    // y = y +. prev
        INCH  $1,#FFF0      // y = y /. 2. (bit tricks again)
        FCMPE $255,$1,$255  // prev = comp_eps(y, prev)
        PBNZ  $255,0B       // if(prev) goto loop
        POP   2,0           // return {y,x}

```

It is up to the caller to set a suitable value of `rE`. Much faster convergence may be arranged by essentially setting `y` up by dividing the exponent by 3, but that costs another four instructions (though in time it pays really quickly, since three `FDIV`s cost about the same amount as two `DIV`s):

```
cbrt    SLU  $1,$0,1    // 3B010001 shift left to erase sign
        INCH $1,#8020   // E4018020 unbias exponent
        DIV  $1,$1,3    // 1D010103 divide by 3 as integer; approximate cube root
        INCH $1,#7FE0   // E4017FE8 rebias exponent
        SRU  $1,$1,1    // 3F010101 shift right again

```

and then continue from the second line in the original.

If mispredicted branches are particularly expensive, I would also replace the second and third lines of the original with:

```
        ZSN $255,$0,1       // 71020001 $255 = ($0 neg? 1 : 0)
        SLU $255,$255,63    // 3B02023F $255 <<= 63
        OR  $1,$1,$255      // C0010102 $1 |= $255

```

This costs one more instruction, but is branchless.

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


title: Code the Levine sequence

text:
# Question
Title: Code the Levine sequence
# Introduction

* Note that I learned it from a Numberphile Video, where Neil Sloane explains it better. I recommend you to watch his Video. But for a quick Introduction:

The Levine Sequence is made from the Levine's Triangle, which is made as follows:
First you have \\$0\\$ ones, and \\$1\\$ twos.
Then you read the list backwards (right to left) and you have the same number of ones, as the \\$0\\$\\$th\\$ element of the list.
Then you have the same number of twos, as the \\$1\\$\\$th\\$ element of the list. That goes on and on, till the list ends. These are the first few rows:

```
ln[0]: 2
ln[1]: 11
ln[2]: 12
ln[3]: 112
ln[4]: 1123
ln[5]: 1112234
ln[6]: 11112223344567

```

Really, I don't think I've explained it good, so check out Neil's Video to learn more about it.

So, now, the Levine's Sequence. The \\$n\\$\\$th\\$ Term of the sequence (starting at \\$0\\$), is just the sum of the \\$n\\$\\$th\\$ row of the Levine's Triangle. These are the first few terms: 2, 2, 3, 4, 7, 14.
Then it just blows up.

Disclaimer: In the Numberphile video, also when you follow the steps I told, the \\$0\\$\\$th\\$ term is \\$2\\$. But in OEIS the first term is \\$1\\$. So I will accept both sequences.

# Rules

* The output must be printed to the program's output.
* The output must be in base 10 (outputting them in any other base is not allowed).
* Your program must *can* take input, the nth term.
* Outputting the integers with trailing / leading spaces is allowed.
* This is , so the shortest (original) code in each language wins!

I'm a bit free about this, so you can output just the \\$n\\$\\$th\\$ term, up to the \\$n\\$\\$th\\$ term, or even the whole sequence!

# Leaderboard

I liked the leaderboard thingy, so here it is again: This uses uses @manatwork's layout.

```
/* Configuration */

var QUESTION_ID = 222856; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 96037; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,]*[^\s,]),.*?(-?\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];

  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });

    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });

  });

  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;

    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    if (! /<a/.test(lang)) lang = '<i>' + lang + '</i>';
    lang = jQuery(lang).text().toLowerCase();

    languages[lang] = languages[lang] || {lang: a.language, user: a.user, size: a.size, link: a.link, uniq: lang};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.uniq > b.uniq) return 1;
    if (a.uniq < b.uniq) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
```

```
body { text-align: left !important}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/Sites/codegolf/all.css?v=617d0685f6f3">
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<div id="language-list">
  <h2>Winners by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td><a href="{{LINK}}">{{SIZE}}</a></td></tr>
  </tbody>
</table>
```

# Answer
# , 17 15 bytes

```
1#.0&(]|.##\)&2

```

Try it online!

-2 thanks to FrownyFrog!

On TIO, handles up to the 11th term `6837625106787` (where term 1 is `2`).

## how

J's "Copy" verb `#` is tailor made for this challenge:

```
   1 2 3 # 'abc'
abbccc

```

The rest is just mechanics needed to reverse and iterate:

* `0&(...)&2` Iterate `...` as many times as the input. This occurs as a result of a special rule J has for the bond `&` conjunction. The `&2` on the right hand side also sets the starting value of the iteration.
* `]...` Ignores the left argument of `0` (resulting from `0&`), and returns the result of `...`, which is processed as a single argument verb, because this entire phrase is a dyadic hook.
    + `|.##\` Reverse current list `|.`, and use it as a mask to duplicate `#` the numbers `1...<length of current list>`.
* `1#.` Sum the result of that iteration.
> 9 votes

# Answer
# Python 3, ~~91~~ ~~87~~ 85 bytes

```
f=lambda n,l=[2]:n and f(n-1,[n+1for n,e in enumerate(l[::-1])for _ in[0]*e])or l[-1]

```

Try it online!

Inputs \\$1\\$-based index \\$n\\$ and returns the \\$n^{\text{th}}\\$ element of the Levine Sequence starting at \\$1\\$.

### Explanation

Starts at `[2]` and successively computes the next row in Levine's Triangle. The last element in the \\$(n+2)^{\text{th}}\\$ row is equal to the sum of the \\$n^{\text{th}}\\$ row or the \\$n^{\text{th}}\\$ term of the Levine Sequence starting at \\$2\\$. By using a \\$1\\$-based index and starting the sequence at \\$1\\$ we simply return the last element in the \\$(n+1)^{\text{th}}\\$ row.
> 5 votes

# Answer
# , ~~49~~ 48 bytes

*Edit: -1 byte thanks to Giuseppe*

```
i=1:0;repeat{i=rep(seq(!i),rev(i));show(sum(i))}

```

Try it online!

Prints the infinite sequence (well, until it fails to allocate vector of size 25472.1 Gb at the 12th iteration...)
> 5 votes

# Answer
# Python 2, 62 bytes

*-3 bytes thanks to @xnor*

Outputs the Levine sequence indefinitely, starting at `1`.

```
a=[2]
while 1:i=len(a);print i;exec'a+=a.pop(i-1)*[i];i-=1;'*i

```

Try it online!
> 5 votes

# Answer
# Scratch, ~~734~~ 715 Bytes

-19 thanks to Lyxal!
Try it online!

Previously discussed, there doesn't seem to be a consensus on how to score Scratch code. I converted the code to scratchblocks4 and counted the characters:

```
when gf clicked
delete all of[B v
delete all of[E v
delete all of[T v
ask[]and wait
add(2)to[E v
add(1)to[T v
set[D v]to(1
repeat(answer
set[C v]to(0
A
repeat((item(length of [T v])of[T v])-(1
A
if<not<(R)=(item((length of[B v])-(1))of[B v])>>then
change[C v]by(()-(length of(D
change[D v]by(-1
delete(length of[B v])of[B v
A
end
end
set[D v]to(length of[B v
set[S v]to(
set[V v]to(1
set[t v]to(0
repeat(length of[B v
repeat(item(1)of[B v
set[S v]to(join(S)(V
end
change[V v]by(1
change[t v]by(item(1)of[B v
delete(1)of[B v
end
add(S)to[E v
add(t)to[T v
define A
set[R v]to(
repeat(length of(D
set[l v]to(item(length of[E v])of[E v
set[R v]to(join(letter((length of(l))-(C))of(l))(R
change[C v]by(1
end
add(R)to[B v

```

Alternatively, the program is 73 blocks:  Obviously, Scratch isn't the first choice for any serious program, but I enjoyed making this! Lyxal substituted `(item(length of[E v])of(E v` for a variable, saving 19 bytes.
> 5 votes

# Answer
# Wolfram Language (Mathematica), 71 bytes

prints the `n`th 0-indexed term

```
Tr@Nest[Join@@MapThread[Table,{Range@Length[a=#],Reverse@a}]&,{1,0},#]&

```

Try it online!
> 4 votes

# Answer
# Jelly, 7 bytes

```
2JxṚƊ¡S

```

Try it online!

Outputs the \\$n\\$th term.

## Explanation

```
2JxṚƊ¡S   Main monadic link
2         Start with 2
     ¡    Repeat n times
    Ɗ     (
 J          Indices (range [1..length])
  x         Repeat each item a number of times given by the corresponding item in
   Ṛ          The list reversed
    Ɗ     )
      S   Sum

```
> 4 votes

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

```
n=6;a=[2];for(;n-->0;a=a.reverse().reduce((v,e,i)=>v.concat(Array(e*1).fill(i+1)),[]));console.log(a.join(""))

```

Try it online!

Set `n` at the start to change which element of the sequence is calculated.

Unfortunately, this is a rather long answer, due to JavaScript's wordy array operator functions.
> 3 votes

# Answer
# Husk, 10 bytes

```
mΣ¡o`ṘN↔;2

```

Try it online!

Prints the infinite sequence. If you let it time out, you can see upto 11 terms.

## Explanation

```
mΣ¡o`ṘN↔;2
        ;2 start with [2]
  ¡o       create the next iteration by
       ↔   reversing it
    `Ṙ     and replicating each element(flipped arg)
      N    times each element in the natural numbers
mΣ         map each list to its sum

```
> 3 votes

# Answer
# Python 2, 82 bytes

```
x=[2]
exec'x=sum([v*[i]for i,v in enumerate(x[::-1],1)],[]);'*input()
print sum(x)

```

Prints the nth, 0-indexed, term.

**Try it online!**

---

Others at 82:

```
x=[2]
exec'i=1;x=x[::-1];exec"x+=x.pop(0)*[i];i+=1;"*len(x);'*input()
print sum(x)

```

```
x=[2]
exec'i=1;exec"x=x.pop()*[i]+x;i+=1;"*len(x);x=x[::-1];'*input()
print sum(x)

```

```
x=2,
exec'x=sum([v*(i,)for i,v in enumerate(x[::-1],1)],());'*input()
print sum(x)

```
> 3 votes

# Answer
# Haskell, ~~57~~ 55 bytes

* -2 bytes thanks to kops.

```
sum<$>iterate(!1)[2]
(x:y)!n=y!(n+1)++(n<$[1..x])
e!_=e

```

Try it online!

The whole Levine sequence.
> 3 votes

# Answer
# JavaScript (ES6), 81 bytes

Returns the \\$n\\$-th term, 0-indexed.

```
f=(n,a=[2])=>a.map(k=>A=n?[...Array(k).fill(++i),...A]:+A+k,i=A=[])&&n?f(n-1,A):A

```

Try it online!

### Commented

```
f = (               // f is a recursive function taking:
  n,                //   n = input
  a = [2]           //   a[] = Levine sequence
) =>                //
a.map(k =>          // for each value k in a[]:
  A =               //   compute A, which is either the updated Levine sequence
                    //   or the sum of the terms of the last sequence if this is
                    //   the last iteration:
    n ?             //     if n is not equal to 0:
      [ ...Array(k) //       build an array consisting of k entries
        .fill(++i), //       equal to i (which is first incremented)
        ...A        //       followed by the existing entries in A[]
      ]             //
    :               //     else:
      +A + k,       //       coerce A to a number and add k
  i = A = []        //   start with i = A = []
)                   // end of map()
&& n ?              // if n is not equal to 0:
  f(n - 1, A)       //   do a recursive call with n - 1 and a[] = A[]
:                   // else:
  A                 //   we're done: return A

```
> 3 votes

# Answer
# APL (Dyalog Unicode), 2̶3̶ 2̶2̶ 21 bytes

-1 thanks to @Razetime
-1 thanks to @User

```
+/{×⍵:/∘⍳∘⍴⍨⌽∇⍵-1⋄,2}
+/ ⍝ summation
 ×⍵: ⍝ conditional
   /∘⍳∘⍴⍨ ⍝ expand range 0 to length of L(n-1) inclusive
     ⌽∇⍵-1 ⍝ reverse L(n-1)
       ⋄ ⍝ statement separator (effectively an else clause)
         ,2 ⍝ return value

```

Try it online!
> 3 votes

# Answer
# 05AB1E, 15 bytes

```
1‚¸λRεN>yи}˜}εθ

```

Try it online!

prints the whole sequence forever

```
1     pushes 1 to the stack
‚     because there is no input, pairs 1 with itself, pushing [1, 1]
¸     listify, pushing [[1,1]]
λ     recursive environment, with [1, 1] as the base case
 R    reverse the implicit last value
 ε    and map each element to
  N>  index + 1
  y   that element
  и   repeated, pushes index + 1 repeated the element
 }
 ˜    flatten, to a flat list
}
ε     and for each such list
θ     take the last element

```
> 2 votes

# Answer
# Factor, 68 bytes

```
[ { 2 } swap [ reverse [ 1 + <array> ] map-index concat ] times Σ ]

```

Try it online!

## Explanation:

It's a quotation (anonymous function) that takes an integer from the data stack as input and puts an integer (the nth term of the Levine sequence) on the data stack as output. Assuming `4` is on top of the stack when this quotation is called...

* `{ 2 }` Push a sequence to the stack containing one element, `2`.

**Stack:** `4 { 2 }`
* `swap` Swap two objects (because `times` needs access to the `4` later).

**Stack:** `{ 2 } 4`
* `[ reverse [ 1 + <array> ] map-index concat ]` Push a quotation for `times` to use later. This is a quotation that produces the next row of the Levine's Triangle from the previous one.

**Stack:** `{ 2 } 4 [ reverse [ 1 + <array> ] map-index concat ]`
* `times` Call a quotation a certain number of times. Inside the quotation now for the first iteration...

**Stack:** `{ 2 }`
* `reverse` Reverse a sequence.

**Stack:** `{ 2 }`
* `[ 1 + <array> ]` Push a quotation for `map-index` to use later.

**Stack:** `{ 2 } [ 1 + <array> ]`
* `map-index` Take a sequence and a quotation and apply the quotation to each element of the sequence, collecting the results into a new sequence of the same length. However, it also places the index of the element on top of the stack. Inside the quotation now for the first iteration...

**Stack:** `2 0`
* `1` Push `1`.

**Stack:** `2 0 1`
* `+` Add.

**Stack:** `2 1`
* `<array>` Create an array from a count and an element.

**Stack:** `{ 1 1 }`
* Now `map-index` has exhausted its elements. Since we are mapping numbers to arrays, the result will be an array of arrays.

**Stack:** `{ { 1 1 } }`
* `concat` Concatenate a sequence of sequences together into one sequence.

**Stack:** `{ 1 1 }`
* Now we have produced the second row of Levine's Triangle. `times` will run the quotation three more times...

**Stack:** `{ 1 1 2 3 }`
* `Σ` Sum a sequence.

**Stack:** `7`
> 2 votes

# Answer
# Python 3, 316 bytes

```
print(*[11,12,112,1123],sep="\n");n="11|2|3";x=2;t="";j=0
while 1:
 for y,z in enumerate(''.join([str(w)[::-1] for w in n.split("|")[1:][::-1]])):
  t+=str(y+1)*int(z)
  if j==0:t+="|"
  j+=1;k=y+2
 n=t+''.join(map(lambda z:'|'+str(z),list(range(k,k+(len(n)-len(n.lstrip('1')))))))
 print(n.replace("|",""));t="";j=0

```

Try it online!

In one word, horrible
> 1 votes

# Answer
# Charcoal, 29 bytes

```
⊞υ²ＦＮ«≔⟦⟧θＦＬυＦ§⮌υκ⊞θ⊕κ≔θυ»ＩΣυ

```

Try it online! Link is to verbose version of code. 0-indexed, I think? Explanation:

```
⊞υ²

```

Start with `[2]`.

```
ＦＮ«

```

Repeat `n` times.

```
≔⟦⟧θ

```

Start a new list.

```
ＦＬυ

```

Iterate up to the length of the previous list.

```
Ｆ§⮌υκ

```

Repeat according to the value in the reversed list.

```
⊞θ⊕κ

```

Push the next integer to the list.

```
≔θυ

```

Copy the new list to the previous list.

```
»ＩΣυ

```

Print the final sum.
> 1 votes

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

function that take n and output A\[n\]

```
f=(n,a=[2],q=a.length)=>n?f(n-1,a.flatMap(n=>Array(a[--q]).fill(++i),i=0)):q

```

Try it online!

# JavaScript (Node.js), 77 bytes

output all A\[i\]

```
for(a=[2];;a=a.flatMap(n=>Array(a[--q]).fill(i++)))i=!console.log(q=a.length)

```

Try it online!
> 1 votes

# Answer
# Pyth, 28 bytes

```
J[2)W1K_JsK=JYFklK=+J*@Kk[hk

```

Try it online!

Prints the infinite sequence.

# Explanation

```
J[2)      # Initialize J to [2]
W1        # While 1...
K_J       # Initialize K to reverse of J
sK        # Print the sum of elements of K
=JY       # Y is an empty list by default. Set J to it.
FklK      # For loop from 0 till length of K, with iterator as k
@Kk       # k'th element of K
[hK       # A list containing only k+1
*         # Repeats the sequence specified number of times.
=+J       # Append that to J.

```
> 1 votes

# Answer
# Scala 3, 84 bytes

```
Seq.iterate(Seq(2),_){s=>s.reverse.zip(1 to s.sum)flatMap(Seq.fill(_)(_))}map(_.sum)

```

Try it in Scastie!

Outputs the first n items.

## Infinite list + nth element, 85 bytes

```
Stream.iterate(Seq(2)){s=>s.reverse.zip(1 to s.sum)flatMap(Seq.fill(_)(_))}map(_.sum)

```

Try it in Scastie!

Here is an infinite Stream that also acts as a function giving the nth element, but it's a byte longer.
> 1 votes

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


title: Gelatin integer metagolf

text:
# Question
Title: Gelatin integer metagolf
Gelatin is a worse version of Jelly. It is a tacit programming language that always takes a single integer argument and that has 7 (or maybe 16) commands.

## Gelatin

Gelatin programs will always match the following regex:

```
^[+_DSa\d~]*$

```

i.e. they will only contain `+_DSa0123456789~` characters. The commands in Gelatin are:

* Digits return their value (`0` is \\$0\\$, `1` is \\$1\\$ etc.) Digits are stand alone, so `10` represents \\$1\\$ and \\$0\\$, not \\$10\\$
* `a` returns the argument passed to the Gelatin program
* `D` takes a left argument and returns it minus one (decremented)
* `S` takes a left argument and returns it's square
* `+` takes a left and a right argument and returns their sum
* `_` takes a left and a right argument and returns their difference (subtract the right from the left)
* `~` is a special command. It is always preceded by either `+` or `_` and it indicates that the preceding command uses the same argument for both the left and the right.

Each command - aside from `~` \- in Gelatin has a fixed *arity*, which is the number of arguments it takes. Digits and `a` have an arity of \\$0\\$ (termed *nilads*), `D` and `S` have an arity of \\$1\\$ (termed *monads*, no relation) and `+` and `_` have an arity of \\$2\\$ (termed *dyads*)

If `+` or `_` is followed by a `~`, however, they become *monads*. This affects how the program is parsed.

Tacit languages try to avoid referring to their arguments as much as possible. Instead, they compose the functions in their code so that, when run, the correct output is produced. How the functions are composed depends on their arity.

Each program has a "flow-through" value, `v` and an argument `ω`. `v` is initially equal to `ω`. We match the start of the program against one of the following arity patterns (earliest first), update `v` and remove the matched pattern from the start. This continues until the program is empty:

* **2, 1**: This is a dyad `d`, followed by a monad `M`. First, we apply the monad to `ω`, yielding `M(ω)`. We then update `v` to be equal to `d(v, M(ω))`.
* **2, 0**: This is a dyad `d`, followed by a nilad `N`. We simply update `v` to be `d(v, N)`
* **0, 2**: The reverse of the previous pattern, `v` becomes `d(N, v)`
* **2**: The first arity is a dyad `d`, and it's not followed by either a monad or a nilad as it would've been matched by the first 2. Therefore, we set `v` to be `d(v, ω)`
* **1**: The first arity is a monad `M`. We simply set `v` to be `M(v)`

For example, consider the program `+S+~_2_` with an argument `5`. The arities of this are `[2, 1, 1, 2, 0, 2]` (note that `+~` is one arity, `1`). We start with `v = ω = 5`:

* The first 2 arities match pattern **2, 1** (`+S`), so we calculate `S(ω) = S(5) = 25`, then calculate `v = v + S(ω) = 5 + 25 = 30`
* The next arity matches pattern **1** (`+~`). `+~` means we add the argument to itself, so we double it. Therefore, we apply the monad to `v`, updating it to `v = v + v = 30 + 30 = 60`
* The next arity pattern is **2, 0** (`_2`), which just subtracts 2, updating `v` to `v = v - 2 = 60 - 2 = 58`
* Finally, the last arity pattern is **2** (`_`), meaning we update `v` to be `v = v - ω = 58 - 5 = 53`.
* There are now no more arity patterns to match, so we end the program

At the end of the program, Gelatin outputs the value of `v` and terminates.

In a more general sense, `+S+~_2_` is a function that, with an argument \\$\omega\\$, calculates \\$2(\omega + \omega^2) - 2 - \omega = 2\omega^2 + \omega - 2\\$.

However, `S+~+_2` is one byte shorter, which is our goal in this challenge.

---

Given an integer \\$n\\$ and a target integer \\$m\\$, you should output a valid Gelatin program that takes \\$n\\$ as input and outputs \\$m\\$. A valid Gelatin program is one where the arities always follow the five patterns above (so not `S1S`, or `123`, etc.), and one that matches the described regex above.

However, this is not a challenge. Instead, your program will be scored on how short the generated Gelatin programs are for a set of 20 randomly generated inputs where \\$-9999 \le n \le 9999\\$. The shortest combined length wins.

I will be testing the submissions in order to get a final score. If your program times out on TIO for \\$|n-m| \> 500\\$, please provide testing instructions. If, for whatever reason, you program fails to produce a correct output for any of the scoring cases, I cannot score your program and it is disqualified. This includes time and memory limitations, so please make your metagolfers somewhat efficient.

The MD5 hash of the list of inputs, in the form of a list of newline separated lines like `n m`, is

```
91e5dd2ab754ce0d96590f8f161e675b

```

You can use the following test cases to test your answer. They have no bearing on your final score. You are under no obligation to golf your generating code.

This is a very naïve attempt, that simply adds or subtracts \\$9\\$ until it's within \\$9\\$ of the target, where it adds/subtracts the remaining gap. It scores 292 on the test cases, and 3494 on the scoring cases. You should aim to beat this at the very least.

## Test cases

```
   n     m
   7     2
  -8     7
   2     2
   1    -7
   2     1
   0    30
 -40    66
   5   -15
 -29    18
  24   -33
 187    -3
 417   512
-101  -108
 329   251
  86   670

```

# Answer
> 5 votes
# Python 3, score 135

```
DYAD_MONAD = 0
DYAD_NILAD = 1
NILAD_DYAD = 2
DYAD = 3
MONAD = 4

nilads = {
	**{str(i): (lambda i: lambda argument: i)(i) for i in range(10)},
	"a": lambda argument: argument
}

monads = {
	"D": lambda x: x - 1,
	"S": lambda x: x * x,
	"+~": lambda x: x + x,
	"_~": lambda x: 0
}

dyads = {
	"+": lambda x, y: x + y,
	"_": lambda x, y: x - y
}

commands = {
	DYAD_MONAD: {
		d + m: (lambda D, M: lambda a, x: D(x, M(a)))(D, M)
	for d, D in dyads.items() for m, M in monads.items()},
	DYAD_NILAD: {
		d + n: (lambda D, N: lambda a, x: D(x, N(a)))(D, N)
	for d, D in dyads.items() for n, N in nilads.items()},
	NILAD_DYAD: {
		n + d: (lambda D, N: lambda a, x: D(N(a), x))(D, N)
	for d, D in dyads.items() for n, N in nilads.items()},
	DYAD: {
		d: (lambda D: lambda a, x: D(x, a))(D)
	for d, D in dyads.items()},
	MONAD: {
		m: (lambda M: lambda a, x: M(x))(M)
	for m, M in monads.items()}
}

import heapq

def f(n, m):

	# STATE VECTOR
	#
	# [current gelatin program length, current value, current gelatin program, last group type]

	def update(argument, pq, seen, state_vector, arity_config):
		length, value, program, last_type = state_vector
		for key, f in commands[arity_config].items():
			newval = f(argument, value)
			if abs(newval) > 20*abs(n)+abs(m) < abs(newval-n*n): continue
			if newval in seen: continue
			seen.add(newval)
			heapq.heappush(pq, (length + len(key), newval, program + key, arity_config))

	initial = (0, n, "", -1) # initially, the program is empty (so has length 0), the value is n, and there was no last group; -1 suffices to avoid breaking the check
	pq = [initial] # priority queue. we'll use heapq to keep the shortest program at the front so it's *guaranteed* to be an optimal solution
	seen = set()
	while True:
		length, value, program, last_type = sv = heapq.heappop(pq) # get the current shortest program; ties are ordered by value so this has no guarantee to be optimal in speed
# 		print(length, value, program, last_type)
# ^ DEBUGGING OUTPUT
		if value == m:
			return program
		if last_type != DYAD: # to prevent issues with 2 | 1 becoming 2,1 and 2 | 0,2 becoming 2,0 | 2, we will not allow 1 ... or 0 2 ... following a dyad
			update(n, pq, seen, sv, MONAD)
			update(n, pq, seen, sv, NILAD_DYAD)
		update(n, pq, seen, sv, DYAD_MONAD)
		update(n, pq, seen, sv, DYAD_NILAD)
		update(n, pq, seen, sv, DYAD)

score = 0

while True:
	try:
		n, m = map(int, input().split())
		output = f(n, m)
		print(output)
		score += len(output)
	except:
		print("FINAL SCORE:", score)
		break

```

Try it online!

Basically a rip-off of hyper-neutrino's initial answer, but with a branch cut based on the magnitude of current value:

```
if abs(newval) > 20*abs(n)+abs(m) < abs(newval-n*n): continue

```

First, let's list all the possible one-step operations for Gelatin (no-ops and duplicate operations are ignored):

```
input = x, current = v

2 1: +a  +D    +S    ++~  _a  _D    _S    _+~
     v+x v+x-1 v+x^2 v+2x v-x v-x+1 v-x^2 v-2x
2 0: +1 .. +9 _1 .. _9
0 2: 0_ .. 9_
1  : D   S   +~ _~
     v-1 v^2 2v 0

```

Now, there are very limited number of operations that can reduce the magnitude of the current number. Assuming `x` is positive, there are `v-d` (where `1<=d<=9`), `v-x`, `v-2x`, and `v-x^2`. Squaring tends to overshoot the numbers significantly, and if it can't get close to the target number by using a small number of these steps, there is no reason to consider that branch.

I initially thought that `v-x^2` is useless and it's fine to prune anything that goes over `some_const*abs(n)`, but soon found that `v-x^2` is useful in some special cases like `100 1881` where it can be solved in 5 bytes only by going through a number close to `n^2`: `9+S_S`.

If allowing single use of `_S` turns out to be insufficient, I can always extend the condition like

```
if all(abs(newval - n*n*i) > (20-2*i)*abs(n)+abs(m) for i in range(5)): continue

```

at the cost of increased running time and memory usage. I think it won't `MemoryError` for any reasonable constant instead of 5 in `range(5)`.

# Answer
> 2 votes
# Python 3, score 238

In order to run without running out of memory, I had to make it somewhat suboptimal :( there's probably a better heuristic for this.

```
DYAD_MONAD = 0
DYAD_NILAD = 1
NILAD_DYAD = 2
DYAD = 3
MONAD = 4

nilads = {
    **{str(i): (lambda i: lambda argument: i)(i) for i in range(10)},
    "a": lambda argument: argument
}

monads = {
    "D": lambda x: x - 1,
    "S": lambda x: x * x,
    "+~": lambda x: x + x,
    "_~": lambda x: 0
}

dyads = {
    "+": lambda x, y: x + y,
    "_": lambda x, y: x - y
}

commands = {
    DYAD_MONAD: {
        d + m: (lambda D, M: lambda a, x: D(x, M(a)))(D, M)
    for d, D in dyads.items() for m, M in monads.items()},
    DYAD_NILAD: {
        d + n: (lambda D, N: lambda a, x: D(x, N(a)))(D, N)
    for d, D in dyads.items() for n, N in nilads.items()},
    NILAD_DYAD: {
        n + d: (lambda D, N: lambda a, x: D(N(a), x))(D, N)
    for d, D in dyads.items() for n, N in nilads.items()},
    DYAD: {
        d: (lambda D: lambda a, x: D(x, a))(D)
    for d, D in dyads.items()},
    MONAD: {
        m: (lambda M: lambda a, x: M(x))(M)
    for m, M in monads.items()}
}

def heuristic(diff, length):
    return (diff * length ** 3)

import heapq

# STATE VECTOR
#
# [heuristic value, current value, desired, current gelatin program, last group type]

def update(argument, pq, seen, state_vector, arity_config):
    _, value, desired, program, last_type = state_vector
    for key, f in commands[arity_config].items():
        newval = f(argument, value)
        if newval in seen: continue
        seen.add(newval)
        heapq.heappush(pq, (heuristic(abs(newval - desired), len(program + key)), newval, desired, program + key, arity_config))

def f(n, m):
    initial = (heuristic(abs(n - m), 0), n, m, "", -1) # initially, the program is empty (so has length 0), the value is n, and there was no last group; -1 suffices to avoid breaking the check
    pq = [initial] # priority queue. we'll use heapq to keep the shortest program at the front so it's *guaranteed* to be an optimal solution
    seen = set()
    while True:
        _, value, desired, program, last_type = sv = heapq.heappop(pq) # get the current shortest program; ties are ordered by value so this has no guarantee to be optimal in speed
#         print(_, value, desired, program, last_type)
# ^ DEBUGGING OUTPUT
        if value == m:
            return program
        if last_type != DYAD: # to prevent issues with 2 | 1 becoming 2,1 and 2 | 0,2 becoming 2,0 | 2, we will not allow 1 ... or 0 2 ... following a dyad
            update(n, pq, seen, sv, MONAD)
            update(n, pq, seen, sv, NILAD_DYAD)
        update(n, pq, seen, sv, DYAD_MONAD)
        update(n, pq, seen, sv, DYAD_NILAD)
        update(n, pq, seen, sv, DYAD)

score = 0

while True:
    try:
        n, m = map(int, input().split())
        output = f(n, m)
        print(output)
        score += len(output)
    except:
        print("FINAL SCORE:", score)
        break

```

Try it online!

---
Tags: integer, metagolf, jelly
---


title: Draw the arc of a ball

text:
# Question
Title: Draw the arc of a ball
Draw the parabolic trajectory of a thrown ball.

The input is the ball's initial upward velocity, a positive integer `v`. Every second, the ball moves `1` space right and `v` spaces vertically, and then `v` decreases by `1` to due to gravity. So, the upward velocity eventually steps down from `v` to `0` and down to `-v`, finally falling back down to its initial height.

The ball's positions trace a parabola. At horizontal position `x`, its height is `y=x*(2*v+1-x)/2`, with `(0,0)` the ball's initial position at the bottom left.

Output ASCII art of the ball's trajectory with `O`'s on the coordinates it ever occupies. The output should be a single multi-line piece of text, not an animation of the path over time.

The output should have no leading newlines and at most one trailing newline. The bottom line should be flush with the left edge of the screen, i.e. have no extra leading spaces. Trailing spaces are OK. You may assume the output line width fits in the output terminal.

v=1

```
 OO
O  O

```

v=2

```
  OO
 O  O

O    O

```

v=3

```
   OO
  O  O

 O    O

O      O

```

v=4

```
    OO
   O  O

  O    O

 O      O

O        O

```

v=10

```
          OO
         O  O

        O    O

       O      O

      O        O

     O          O

    O            O

   O              O

  O                O

 O                  O

O                    O

```

Related: Bouncing ball simulation

---

**Leaderboard:**

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

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

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

# Answer
# Charcoal, ~~18~~ ~~16~~ 13 bytes

-3 bytes thanks to @Neil!

```
Ｆ⊕Ｎ«←OＭ⊕ι↓»‖Ｃ

```

## Explanation

```
Ｆ⊕Ｎ«        »    For ι (implicitly from 0) to (1 + input as number)
       ←O          Print O, with print direction rotated 180 degrees
         Ｍ⊕ι↓     Move 1+ ι units down

                ‖Ｃ Reflect (in the default direction, right), leaving original intact

```

Try it online! Link is to verbose code.
> 17 votes

# Answer
# C, ~~93~~ 92

(Note, someone got to 87 in the comments)

```
y,n;f(s){for(y=0;y<=s;){printf("%*c%*c",s-y+1,79,y*2+1,79);for(n=++y;s+1-n&&n--;)puts("");}}

```

Try it online!

---

Readable:

```
y,n;f(s){
    for(y=0;y<=s;){
        printf("%*c%*c",s-y+1,79,y*2+1,79);
        for(n=++y;s+1-n&&n--;)puts("");
    }
}

```

---

Notes:

I can collapse both for loops into just one for loop by iterating the total number of lines outputted, which is given by the formula: `n*-~n/2+1`

```
y,n,r;f(s){
    for(r=s,y=n=0;r<s*-~s/2+1;)
        y==n?printf("%*c%*c",s-y+1,79,y*2+1,79),y=0,++n:r++,y++,puts("");
}

```

But it ends up being even more bytes than just using two seperate for-loops
> 6 votes

# Answer
# GNU sed, 41

* Score includes +1 from `-r` flags to sed.

```
s/$/OO/
:
s/(\s*) O( *)O$/&\n\1O \2 O/
t

```

Input is in unary, as a string of spaces - the length of string is the input.

Try it online.
> 5 votes

# Answer
# Python 2, 65 bytes

```
f=lambda n,x=0:(n and f(n-1,x+1)or'')+'\n'*n+' '*x+'O'+'  '*n+'O'

```

Try it online!
> 5 votes

# Answer
# Python 2, 76 bytes

```
x=input()
for i in range(x):print' '*(x-i),'O'+' '*i*2+'O'+'\n'*(i-x+1and i)

```

Pretty simple. The `i-x+1and i` is to prevent a bunch of trailing newlines.
> 4 votes

# Answer
# MATL, ~~19~~ 17 bytes

```
Q:tqYsQ79Z?PtPv!c

```

Try it at MATL Online! Or verify all test cases.

### Explanation

```
Q        % Implicitly input v. Add 1
:        % Push [1 2 ... v+1]
tq       % Duplicate and subtract 1: pushes [0 1 ... v]]
Ys       % Cumulative sum: gives [0 1 3 6 ...]
Q        % Add 1: gives [1 2 4 7 ...]
79       % Push 79 (ASCII for 'O')
Z?       % Create sparse matrix from column indices [1 2 3 4 ...],
         % row indices [1 2 4 7 ...], and data 79
P        % Flip vertically
tP       % Duplicate, flip vertically
v        % Concatenate the two matrices vertically
!        % Transpose
c        % Convert to char. Implicitly display. Char 0 is shown as space

```
> 4 votes

# Answer
# 05AB1E, ~~18~~ 14 bytes

Saved 4 bytes thanks to *Adnan*

```
ƒ¶N×'ONúRÂJ}.c

```

Try it online!

**Explanation**

```
ƒ                   # for N in [0 ... input]
 ¶N×                # push N newlines
    'O              # push "O"
      Nú            # pad with N spaces in front
        RÂ          # reverese and create a reversed copy
          J         # join everything to a string
           }        # end loop
            .c      # pad lines until centered

```
> 4 votes

# Answer
# JavaScript (ES6), ~~98~~ ~~92~~ ~~89~~ ~~84~~ 78 bytes

*(-20 bytes thanks to Arnauld!)*

```
f=(v,i=0)=>i>v?"":" "[r="repeat"](v-i)+0+" "[r](2*i)+0+`
`[r](i++<v&&i)+f(v,i)

```

A recursive solution. This is also my first *ever* answer in JavaScript, so please be gentle! I am still learning all this neat language has to offer, so golfing tips are very much appreciated. :)

## Test Snippet

You may need to scroll to see the entire output.

```
f=(v,i=0)=>i>v?"":" "[r="repeat"](v-i)+0+" "[r](2*i)+0+`
`[r](i++<v&&i)+f(v,i)
```

```
<input id=i min=1 type=number><button onclick=alert(f(document.getElementById("i").value))>Submit</button>
```
> 4 votes

# Answer
# Bash, 76 bytes

```
for((n=$1+1;--n;));{
yes ''|head -$n
r=$r›${n}AO
t=›${n}BO$t
}
echo O${r}O$t

```

Only works in a terminal since it uses ANSI escape sequences.  represents the CSI byte (**0x9b**).

### Test run

```
$ # The terminal's encoding must be set to ISO-8859-1.
$
$ xxd -g 1 arc.sh
0000000: 66 6f 72 28 28 6e 3d 24 31 2b 31 3b 2d 2d 6e 3b  for((n=$1+1;--n;
0000010: 29 29 3b 7b 0a 79 65 73 20 27 27 7c 68 65 61 64  ));{.yes ''|head
0000020: 20 2d 24 6e 0a 72 3d 24 72 9b 24 7b 6e 7d 41 4f   -$n.r=$r.${n}AO
0000030: 0a 74 3d 9b 24 7b 6e 7d 42 4f 24 74 0a 7d 0a 65  .t=.${n}BO$t.}.e
0000040: 63 68 6f 20 4f 24 7b 72 7d 4f 24 74              cho O${r}O$t
$
$ bash arc.sh 1
 OO
O  O
$ bash arc.sh 2
  OO
 O  O

O    O
$ bash arc.sh 3
   OO
  O  O

 O    O

O      O
$ bash arc.sh 4
    OO
   O  O

  O    O

 O      O

O        O

```
> 4 votes

# Answer
# RProgN 2, 37 bytes

```
x=0xR{y@xy-` *`o` y2**`o...2y{[` };};

```

Getting in with my kind-of-golfy language before the proper golfy langauges jump in.

## Explained

```
x=              # Set 'x' to the input
0xR{            # For everything between the input and 0
    y@          # Set the iteration value to y, for this function only.
    xy-` *      # Subtract y from x, repeat the string " " that many times.
    `o          # Push an "o" to the stack.
    ` y2**      # Push 2*y " "'s to the stack
    `o          # Push another "o" to the stack
    ...         # Concatenate the parts of this string together, giving us the two balls.
    2y{[` };    # For all numbers between 2 and y, add a newline.
};              #

```

Try it online!
> 3 votes

# Answer
# Retina, 35

* 2 bytes saved thanks to @MartinEnder

Port of my sed answer:

```
.+
$* OO
+`(\s*) (O *)O$
$&¶$1O $2 O

```

Try it online.
> 3 votes

# Answer
## Retina, ~~29~~ 19 bytes

```
 ?
$.`$*¶$&$'O$`$`O

```

Try it online!

Takes input in unary as a run of spaces. Port of my JavaScript answer. Edit: Saved 10 bytes thanks to @MartinEnder♦.
> 3 votes

# Answer
# R, 89 bytes

```
a=2*v+3
x=matrix(" ",a,v^2+1)
for(k in 0:v)x[c(1-k,k+2)+v,k^2+1]="o"
x[a,]="\n"
cat(x,sep="")

```
* Create a matrix of spaces (the variable a is the width of this matrix, saving a couple of bytes)
* Fill in "o"s at the required locations, working from the top of the arc downwards and outwards
* Add a newline at the end of each matrix row
* Collapse the matrix down to a single string and print

This is my first attempt at golfing, comments welcome...
> 3 votes

# Answer
# Röda, ~~53~~ 52 bytes

```
f n{seq 0,n|{|i|["
"*i," "*(n-i),"O"," "*i*2,"O"]}_}

```

Try it online!

Usage: `main { f(5) }`

Ungolfed version:

```
function f(n) {
    seq(0, n) | for i do
        push("\n"*i, " "*(n-i), "O", " "*i*2, "O")
    done
}

```
> 3 votes

# Answer
# Befunge, ~~75~~ 73 bytes

```
<vp00:&
1<-1_:v#\+55:g01\-g01g00" O"1\*2g01" O"1p0
#@_\:v>$$:!
1\,:\_^#:-

```

Try it online!

The first line reads in the velocity, *v*, and saves a copy in memory. The second line then counts down from *v* to zero, with the index *i*, and on each iteration pushes a sequence of character/length pairs onto the stack.

```
Length  Character
-----------------
1       'O'
i*2     ' '
1       'O'
v-i     ' '
i       LINEFEED

```

This sequence represents a kind of run-length encoding of the required output in reverse. The last two lines then simply pop these character/length pairs off the stack, outputting *length* occurrences of each *character*, until the stack is empty.
> 2 votes

# Answer
# Java 8, ~~129~~ ~~124~~ 109 bytes

Golfed:

```
v->{String s="",t="";for(int j,y=0;y<=v;++y){for(j=0;j<v;++j)s+=j<y?"\n":" ";s+="o"+t+"o";t+="  ";}return s;}

```

Try it online!

Ungolfed:

```
public class DrawTheArcOfABall {

  public static void main(String[] args) {
    for (int i = 1; i < 6; ++i) {
      System.out.println(f(v -> {
        String s = "", t = "";
        for (int j, y = 0; y <= v; ++y) {
          for (j = 0; j < v; ++j) {
            s += (j < y ? "\n" : " ");
          }
          s += "o" + t + "o";
          t += "  ";
        }
        return s;
      } , i));
      System.out.println();
      System.out.println();
    }
  }

  private static String f(java.util.function.IntFunction<String> f, int v) {
    return f.apply(v);
  }
}

```
> 2 votes

# Answer
# 05AB1E, ~~18~~ 13 bytes

```
ÝηROÂ«ð×'O«ζ»

```

Try it online!

```
Ý                # [0..n]
 €LRO            # [0.sum(), 0..1.sum(), ..., 0..n-1.sum(), 0..n.sum()]
     Â«          # Mirror image the array [0, 0..n.sum(), 0]
       ð×'O«     # Push that many spaces with an O appended to it.
            .B   # Pad small elements with spaces to equal largest element length.
              ø» # Transpose and print.

```
> 2 votes

# Answer
# VBA, ~~124~~ ~~112~~ ~~85~~ ~~88~~ ~~66~~ ~~63~~ 59 bytes

```
For i=0To[A1]:?Space([A1]-i)"O"Space(2*i)"O"String(i,vbCr):Next

```

Saved 29 bytes in total thanks to Taylor Scott

This must be run the in VBA Immediate window and print the result in the same.

Expanded / Formatted, it becomes:

```
For i=0 To [A1]
   Debug.Print Space([A1]-i) & "O" & Space(2*i) & "O" & String(i,vbCr)
Next

```

(It turns out that concatenation in a print command is automatic without an operator.)
> 2 votes

# Answer
## Haskell, 69 bytes

```
r=replicate
f n=[0..n]>>= \a->r a '\n'++r(n-a)' '++'O':r(2*a)' '++"O"

```

Usage example: `f 3` -\> `" OO\n O O\n\n O O\n\n\nO O"`. Try it online!.
> 2 votes

# Answer
# MATLAB, 114 Bytes

```
function p(v),for i=0:v,fprintf([repmat(' ',1,v-i),'o',repmat(' ',1,2*i),'o',repmat('\n',1,(i*(i~=v)+1))]);end,end

```

ungolfed:

```
function p(v)
   for i=0:v
       fprintf([repmat(' ',1,v-i),'o',repmat(' ',1,2*i),'o',repmat('\n',1,(i*(i~=v)+1))]);
   end
end

```
> 2 votes

# Answer
# Jelly, ~~17~~ 16 bytes

```
‘Ḷ+\Ṛ⁶ẋ;€”Om0z⁶Y

```

**Try it online!**

### How?

```
‘Ḷ+\Ṛ⁶ẋ;€”Om0z⁶Y - Main link: v         e.g. 3
‘                - increment: v+1            4
 Ḷ               - lowered range             [0,1,2,3]
  +\             - reduce with addition      [0,1,3,6]
    Ṛ            - reverse                   [6,3,1,0]
     ⁶           - a space                   ' '
      ẋ          - repeat (vectorises)       ['      ','   ',' ','']
       ;€        - concatenate each with
         ”O      -     an 'O'                ['      O','   O',' O','O']
           m0    - concatenate reflection    ['      O','   O',' O','O','O','O ','O   ','O      ']
             z⁶  - transpose with space fill ['   OO   ','  O  O  ','        ',' O    O ','        ','        ','O      O']
               Y - join with line feeds      ['   OO   \n  O  O  \n        \n O    O \n        \n        \nO      O']
                 - implicit print

```
> 1 votes

# Answer
## JavaScript (ES6), 87 bytes

```
f=
n=>' '.repeat(n+1).replace(/./g,"$`#$'O$`$`O").replace(/ *#/g,s=>[...s].fill``.join`
`)
```

```
<input type=number min=0 oninput=o.textContent=f(+this.value)><pre id=o>
```

Nonrecursive solution. Indexing requirement was annoying, both in the above and the following 62-byte (I don't know whether it would result in a shorter Retina port) recursive solution:

```
f=n=>~n?` `.repeat(n)+`OO`+f(n-1).replace(/^ *O/gm,`
$&  `):``

```
> 1 votes

# Answer
# PHP, 76 bytes

```
for(;$argn>=0;$s.="  ")echo($r=str_repeat)("
",$i++),$r(" ",$argn--),o,$s,o;

```

Run with `echo <v> | php -nR '<code>'` or test it online.

loops `$argn` down from input to `0` and `$i` up from 0;
prints - in that order - in each iteration

* `$i` newlines (none in the first iteration)
* left padding: `$argn` spaces
* left ball: `o`
* inner padding: `2*$i` spaces
* right ball: `o`
> 1 votes

# Answer
# , ~~23~~ 19 bytes

```
2éoÀñYço/^2á O
HPJ>

```

Try it online!

Explain

```
2éo            " Insert two 'o's
   Àñ          " <Arg> times repeat
     Y         " Yank the current (top) line.  This is always '\s*oo'
      ço/      " On every line that matches 'o'
         ^     " Go to the first non-whitespace character (the 'o')
          2á   " Append two spaces (between the two 'o's
             O " Add a blank line on top of the current one
H              " Go to the first line
 P             " Paste in front ('\s*oo')
  J            " Join this line with the blank line immediately after it
   >           " Indent once

```
> 1 votes

# Answer
## Perl 5, 48 bytes

**47 bytes code + 1 for `-n`.**

```
$_++;print$/x$-,$"x$_,O,$"x($-++*2),O while$_--

```

Try it online!
> 1 votes

# Answer
# MathGolf, 17 bytes

```
r{n*íï- *'oï *+_x

```

Try it online!

## Explanation

```
r                   range(0, n)
 {                  start block or arbitrary length
  n                 newline char, or map array with newlines
   *                pop a, b : push(a*b)
    í               get total number of iterations of for loop
     ï              index of current loop, or length of last loop
      -             pop a, b : push(a-b)
                    space character
        *           pop a, b : push(a*b)
         '          push single character
          o         print TOS without popping
           ï        index of current loop, or length of last loop
                    space character
             *      pop a, b : push(a*b)
              +     pop a, b : push(a+b)
               _    duplicate TOS
                x   reverse int/array/string

```
> 1 votes

# Answer
# , 29 bytes

```
[:|:@(,~|.)' O'#~1,.~i.+/\@,]

```

Try it online!

Turned out very similar to Razetime's APL answer, though solved independently. I tried about 3 other approaches before realizing this one would be shortest.
> 1 votes

# Answer
# Stacked, ~~67~~ 63 bytes

```
args 0#1+:@x:>{!n x\-1-' '*'O'+n 2*' '*+'O'+x 1-n!=n*LF*+out}"!

```

Initial attempt, 67 bytes

```
args 0# :@v 1+2*:>[:v:+1+\-2/*' '*'O'+''split]"!fixshape tr rev out

```

Full program. Generates something like:

```
('O'
 ' ' 'O'
 ' ' 'O'
 'O')

```

Which is the padded, transposed, reversed, and outputted.
> 0 votes

# Answer
## Batch, 163 bytes

```
@set l=@for /l %%i in (1,1,%1)do @call
@set s=
%l% set s= %%s%%
@set t=
%l%:c&for /l %%j in (2,1,%%i)do @echo(
:c
@echo %s%O%t%O
@set s=%s:~1%
@set t=  %t%

```
> 0 votes

# Answer
## Ruby, 52 bytes

```
->x{(0..x).map{|a|$><<$/*a+' '*(x-a)+?O+' '*a*2+?O}}

```

No trailing newline (allowed by the rules: "*at most one trailing newline*")
> 0 votes

# Answer
# AHK, 93 bytes

```
m=0
n=1
f=%1%-1
Loop,%1%{
r=%r%{VK20 %f%}O{VK20 %m%}O{`n %n%}
m+=2
n++
f--
}
FileAppend,%r%,*

```

If I could figure out how to do math inside of repeating keystrokes, that'd be great.
\- `VK20` equates to a space
\- `FileAppend` outputs to `stdout` if the filename is `*`
> 0 votes

# Answer
# Haskell, 77 bytes

```
n!x=[1..n]>>x
-1#i=[]
x#i=(x-1)#(i+1)++x!"\n"++i!" "++'O':(2*x)!" "++"O"
(#0)

```

Try it online! Usage: `(#0) 5`
> 0 votes

# Answer
# Python 2, 59 bytes

```
f=lambda n,r='O':(r*n and f(n-1,' '+r))+'\n'*n+r+'  '*n+'O'

```

Try it online!
> 0 votes

# Answer
# Pyth, 26 bytes

```
VyhQ=+Y+*Zd\O=+ZQ=tQ)j_.tY

```

Try it Online

### Explanation

```
VyhQ=+Y+*Zd\O=+ZQ=tQ)j_.tY
                            Implicit Q=input() (speed), Z=0 (position), Y=[].
VyhQ                )       For N in [0,...,2Q+2]...
       +*Zd\O               ... prepend Z spaces to 'O'...
    =+Y                     ... add that line to Y...
             =+ZQ=tQ        ... then update position and speed.
                     j_.tY  Combine the lines to form the parabola.

```
> 0 votes

# Answer
# APL (Dyalog Unicode), ~~27~~ 25 bytes

```
(⌽,⊢)⍉↑↑∘'O'¨1,1-1↓+\⍳⎕+1

```

Try it online!

-2 bytes from kritixilithos at the APL Orchard.

-2 bytes from Adám.

## Explanation

```
 (⌽,⊢)⍉↑↑∘'O'¨1,1-1↓+\⍳⎕+1
                      ⍳⎕+1  range 1 - n+1
                    +\      cumulative sum over each element
                  1↓        drop the first value (0)
                1-          subtract 1 from each value
              1,            prepend 1 to it.
             ¨              for each element,
        ↑∘'O'               prepend(element-1) spaces to 'O'.
       ↑                    convert to matrix
      ⍉                     transpose
 (⌽,⊢)                      prepend its reverse (palindromize).

```
> 0 votes

---
Tags: code-golf, ascii-art, physics
---