title: Generate random UUID

text:
# Question
Title: Generate random UUID
# I need a UUID. Your job is to generate one.

The canonical UUID (Universally Unique IDentifier) is a 32 digit hexadecimal number with hyphens inserted in certain points.The program should output 32 hex digits (128 bits), in the form of `xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx` (`8-4-4-4-12` digits), where `x` is a random hexadecimal number. Assuming that your language's PRNG is perfect, all valid outputs must have the same probability of being generated.

## TL;DR

Generate 32 random hexadecimal digits in the form `8-4-4-4-12` digits. Shortest code wins.

EDIT: Must be hexadecimal. Always generating decimal only is invalid. EDIT 2: No built-ins. These aren't GUIDs, just generic hex digits.

---

## Example output:

```
ab13901d-5e93-1c7d-49c7-f1d67ef09198
7f7314ca-3504-3860-236b-cface7891277
dbf88932-70c7-9ae7-b9a4-f3df1740fc9c
c3f5e449-6d8c-afe3-acc9-47ef50e7e7ae
e9a77b51-6e20-79bd-3ee9-1566a95d9ef7
7b10e43c-3c57-48ed-a72a-f2b838d8374b

```

Input, and standard loopholes are disallowed.

---

This is , so shortest code wins. Also, feel free to ask for clarifications.

# Answer
# Pyth, 20 bytes

```
j\-msm.HO16*4hdj83 3

```

Demonstration.

Encodes `[1, 0, 0, 0, 2]` as 83 in base 3, then adds one and multiplies by four to get the length of each segment. Then makes hex digits and joins on hyphens.
> 11 votes

# Answer
# CJam, ~~26~~ 25 bytes

```
8 4__C]{{Gmr"%x"e%}*'-}/;

```

Try it online in the CJam interpreter.

### How it works

```
8 4__C]{              }/   For each I in [8 4 4 4 12]:
        {         }*         Do I times:
         Gmr                   Pseudo-randomly select an integer between 0 and 15.
            "%x"e%             Apply hexadecimal string formatting.
                    '-       Push a hyphen-minus.
                        ;  Discard the last hyphen-minus.

```
> 8 votes

# Answer
# Julia, 80 bytes

```
h=hex(rand(Uint128),32)
print(h[1:8]"-"h[9:12]"-"h[13:16]"-"h[17:20]"-"h[21:32])

```

Generate a random 128-bit integer, get its hexidecimal representation as a string padded to 32 digits, and divide that into segments joined with dashes.

Thanks to ConfusedMr\_C and kvill for their help!
> 8 votes

# Answer
# Perl 5, 43 bytes

Saved 2 bytes thanks to @Xcali!

```
printf"%04x"."-"x/[2-5]/,rand 2**16for 1..8

```

Try it online!
> 5 votes

# Answer
# PowerShell, 77 69 67 bytes

```
((8,4,4,4,12)|%{((1..$_)|%{'{0:X}'-f(random(16))})-Join""})-Join"-"

```

edit: extraneous parens:

```
((8,4,4,4,12)|%{((1..$_)|%{('{0:X}'-f(random(16)))})-Join""})-Join"-"

```

edit: was able to remove the trailing .Trim("-") from the original:

```
(((8,4,4,4,12)|%{((1..$_)|%{('{0:X}'-f(random(16)))})+"-"})-Join"").Trim("-")

```

It may be clearer with some whitespace given the nature of the flags (-f and -Join). I would still like to lose the final Trim("-"):

```
(((8,4,4,4,12)|%{((1..$_)|%{('{0:X}' -f (random(16)))}) + "-"}) -Join "").Trim("-")

```

Or, using the built-in functionality (ala the C# answer above)

```
'{0}'-f[System.Guid]::NewGuid()

```

However, it seems a wee bit shortcut-y even if it comes in at 31 bytes.
> 5 votes

# Answer
# Python 2, ~~86~~ 84 bytes

```
from random import*;print'-'.join('%%0%ix'%i%randint(0,16**i-1)for i in[8,4,4,4,12])

```

This chains string formatters to make Python format the hex numbers uniquely for each segment.

Ungolfed:

```
import random

final = []
for i in [8, 4, 4, 4, 12]:               # Iterate through every segment
    max = (16 ** i) - 1                  # This is the largest number that can be
                                         # represented in i hex digits
    number = random.randint(0, max)      # Choose our random segment
    format_string = '%0' + str(i) + 'x'  # Build a format string to pad it with zeroes
    final.append(format_string % number) # Add it to the list

print '-'.join(final)                    # Join every segment with a hyphen and print

```

This could use some improvement, but I'm proud.
> 5 votes

# Answer
# PHP, 69 ~~72~~ ~~75~~ bytes

```
foreach([8,4,4,4,12]as$c)$r[]=rand(".1e$c","1e$c");echo join('-',$r);

```

This does not output hex digits (`a`, ... `f`). They are allowed, but not required by the question body.

No digit group starts with `0` (also not required).

*edit: saved 3 bytes thanks to @IsmaelMiguel*
> 4 votes

# Answer
# JavaScript, ES6, 106 bytes

```
"8-4-4-4-12".replace(/\d+/g, m => {t=0;for(i=0; i<m; i++) {t+=(Math.random()*16|0).toString(16)}return t})

```

Uses Regex replace. Treats the format string as a count for generating a hex char. Hoisting wherever I can; omitting semicolons where possible.
> 4 votes

# Answer
# C#, 65 Bytes

```
using System;class C{void Main(){Console.Write(Guid.NewGuid());}}

```

edit: Yes ! C# is shorter than another Language (besides Java) :)
> 3 votes

# Answer
# gawk, 86

```
BEGIN{for(srand();j++<32;printf(j~"^9|13|17|21"?"-":E)"%c",x+(x>10?87:48))x=rand()*16}

```

You can use this once every second to generate a unique random "UUID". This is because `srand()` uses the system time in seconds since epoch as argument if there is no argument given.

```
for n in `seq 100` do awk 'BEGIN{for(srand();j++<32;printf(j~"^9|13|17|21"?"-":E)"%c",x+(x>10?87:48))x=rand()*16}'; sleep 1; done

```

I think the awk part is rather elegant.

```
BEGIN{
    srand()
    for(;j++<32;) {
        x=rand()*16
        x+=(x>10?87:48)
        printf "%c", x
        if(j~"^8|12|16|20")printf "-"
    }
}

```

If you want to use it more often than once every second you can call it in bash like this. Note that the awk part is changed too.

```
echo `awk 'BEGIN{for(srand('$RANDOM');j++<32;printf(j~"^9|13|17|21"?"-":E)"%c",x+(x>10?87:48))x=rand()*16}'`

```

The `echo` is added there to print a new line every time.
> 3 votes

# Answer
# K5, 35 bytes

```
"-"/(0,8+4*!4)_32?`c$(48+!10),65+!6

```

To generate a hex alphabet I generate a character string (``c$`) from a list of digits (`48+!10`) and the first 6 capital letters (`65+!6`). An alternate way of generating the digits which is the same length is `,/$!10`.

With the string "0123456789ABCDEF" generated, the rest is simple. Select 32 random values from this set (`32?`), slice (`_`) the resulting string at `0 8 12 16 20` computed via `(0,8+4*!4)`, and then join the resulting string fragments with dashes (`"-"/`).

In action:

```
  "-"/(0,8+4*!4)_32?`c$(48+!10),65+!6
"9550E114-A8DA-9533-1B67-5E1857F355E1"

```
> 3 votes

# Answer
# , 63 bytes

```
x=sample(c(0:9,letters[1:6]),36,1);x[0:3*5+9]='-';cat(x,sep='')

```

Try it online!

The code first builds a 36 character random string, and then places the four hyphens. It outputs a UUID to stdout.
> 3 votes

# Answer
## Perl 6, 53 bytes

The obvious one:

```
say join '-',(0..9,'a'..'f').flat.roll(32).rotor(8,4,4,4,12)».join # 67

```

---

Translating the Perl 5 example using `printf`, results in code that is a bit shorter.

```
printf ($_='%04x')~"$_-"x 4~$_ x 3,(0..^4⁸).roll(8) # 53

```
> 2 votes

# Answer
# Kotlin, 175 bytes

```
fun main(a:Array<String>){
fun f()="0123456789abcdef".get((Math.random()*16).toInt())
var s=""
for(i in listOf(8,4,4,4,12)){
for(j in 1..i)
s+=f()
if(i!=12)s+="-"}
println(s)}

```

Try it online!

My first ever Kotlin program & PPCG submission
> 2 votes

# Answer
# APL (Dyalog Unicode), ~~115~~ 78 bytes

```
a←⊣,'-',⊢
H←⊃∘(⎕D,819⌶⎕A)¨16∘⊥⍣¯1
(H 8?16)a(H 4?16)a(H 4?16)a(H 4?16)a H 12?16

```

Try it online!

This is my first APL submission. Huge thanks to @Adám for bearing with me at the PPCG's APL chat and for the hexadecimal conversion function.

Thanks to @Zacharý for 1 byte

Edited to fix byte count.
> 2 votes

# Answer
# Japt, 32 bytes

```
[8,4,4,4,12]m@MqG**X sG ù0X} q"-

```

Try it online!
> 2 votes

# Answer
# Go, ~~119~~ 110 bytes

```
import(."math/rand";."fmt")
func f(){for j:=0;j<32;j++{if j>4&&j<24&&j%4<1{Print("-")}
Printf("%x",Int()%16)}}

```

Try it online!

* -9 by @The Thonnu
> 2 votes

# Answer
# Julia, 57,60 55 bytes

```
!n=bytes2hex(rand(UInt8,n))
join(.![4,2,2,2,6],-)|>show

```
* 57-\>60 a mistake
* 60-\>55 by @MarcMush and the broadcasting :-)

Attempt This Online!
> 2 votes

# Answer
## MATLAB/Octave , 95 bytes

```
a='-';b=strcat(dec2hex(randi(16,32,1)-1)');[b(1:8) a b(9:12) a b(13:16) a b(17:20) a b(21:32)]

```
> 1 votes

# Answer
## Perl, 51 bytes

```
say"xx-x-x-x-xxx"=~s/x/sprintf"%04x",rand 65536/reg

```

Requires perl5 \>= 5.10 I think. For the /r modifier and for say().
> 1 votes

# Answer
## C++, ~~194~~ ~~193~~ ~~221~~ ~~210~~ 201 bytes

+7 bytes thanks to Zacharý ( detected a `-` that should not be at the end )

```
#include<iostream>
#include<random>
#include<ctime>
#define L(a)for(int i=0;i<a;++i)std::cout<<"0123456789abcdef"[rand()%16];
#define P(a)printf("-");L(a)
void t(){srand(time(0));L(8)P(4)P(4)P(4)P(12)}

```

If someone has a way to get a different value every execution without changing `srand` and without including `<ctime>`, that would be great
> 1 votes

# Answer
# , ~~42 39 37~~ 27 bytes

```
echo'-'(8+5*i.4)},hfd?36#16

```

Try it online!
> 1 votes

# Answer
# Befunge-93, 97 bytes

```
v>4448v,+<    <
0*    :  >59*0^
62v0-1_$:|>*6+^
>^>41v < @^99<
v<*2\_$:54+` |
?0>+\1-^ v*68<>
>1^

```

Try it online!

I'm sure this can be shrunk, but this is my first try :)
> 1 votes

# Answer
# Bash, 67 bytes

```
for l in 4 2 2 2 6;{ o+=`xxd -p -l$l</dev/random`-;}
echo ${o::-1}

```
> 1 votes

# Answer
# C (gcc), ~~143~~ ~~110~~ ~~103~~ ~~96~~ 94 bytes

Golfed down to 94 bytes thanks to ceilingcat and Jonathan Frech.

```
(*P)()="\xf\x31À";*z=L"\10\4\4\4\14";main(n){for(;*z;*++z&&putchar(45))for(n=*z;n--;printf("%x",P()&15));}

```

Try it online!

Explanation:

```
/*
  P is a pointer to a function.
  The string literal contains actual machine code of the function:

  0F 31     rdtsc
  C3        ret

  0xc3 is the first byte of the UTF-8 representation of the character À
*/
(*P)() = "\xf\61À";

// encode uuid chunk lengths as literal characters
// we use wide characters with 'L' prefix because
// sizeof(wchar_t)==sizeof(int) for 64-bit gcc C on TIO
// so z is actually a zero-terminated string of ints
*z = L"\8\4\4\4\14"

main (n)
{
    for (
        ;

        // loop until we reach the trailing zero
        *z;

        // increase the pointer and dereference it
        *++z
             // and output a hyphen, if the pointer does not point at zero
             && putchar(45)
    )
        // output a random hex string with length pointed at by z
        for (n = *z; n--; printf ("%x", P()&15));
}

```
> 1 votes

# Answer
# C (gcc),  ~~94~~   ~~91~~  86 bytes

```
main(i){srand(&i);i=803912;for(;i--%16||(i/=16)&&printf("-");printf("%x",rand()%16));}

```

Try it online!

I would have liked to suggest this version in a comment to Max Yekhlakov (his answer), but unfortunately I do not have the 50 needed reputation points yet, so here is my answer.

`803912` is `C4448` in hexadecimal, it describes how the output should be formatted (`12-4-4-4-8`), it is reversed because least significant digits will be read first.

## Edits:

* saved 3 bytes thanks to Jonathan Frech
* saved 5 more bytes by replacing `srand(time(0))` with `srand(&i)`
> 1 votes

# Answer
# JavaScript REPL, 79 bytes

```
'66-6-6-6-666'.replace(/6/g,_=>(Math.random().toString(16)+'00000').slice(2,6))

```

Try it online!

`Math.random` may return `0`. Adding 5 zeros make the slicing get 4 `0`s
> 1 votes

# Answer
# Forth (gforth), 91 89 bytes

```
include random.fs
hex
: f 0 4 4 4 8 20 0 do dup i = if + ." -" then 10 random 1 .r loop ;

```

Try it online!

### Explanation

Changes the base to hexadecimal, then outputs numbers/segments of the appropriate length with dashes at specified intervals

### Code Explanation

```
include random.fs          \ include the random module
hex                        \ set the base to hexadecimal
: f                        \ start a new word definition
  0 4 4 4 8                \ enter the intervals to place dashes
  20 0 do                  \ start a counted loop from 0 to 0x20 (32 in decimal)
    dup i =                \ check if we are on a character that needs a dash
    if                     \ if we are
      +                    \ calculate the next character that gets a dash
      ." -"                \ output a dash
    then                   \ end the if block
    f random               \ get a random number between 0x0 and 0xf
    1 .r                   \ output it right-aligned in 1-character space
  loop                     \ end the loop
;                          \ end the word definition

```
> 1 votes

# Answer
# Java with Ten Foot Laser Pole v. 1.06, 126 bytes

```
String u(){return sj224.tflp.util.StringUtil.replace("aa-a-a-a-aaa","a",s->String.format("%04x",(int)(Math.random()*65536)));}

```

Tested with version 1.06 of the library, but this *should* work with any version 1.04 or newer.
> 1 votes

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

```
import uuid;print(uuid.uuid4())

```

Try it online!

Python has an inbuilt package for this specific task. Enjoy :P
> 1 votes

# Answer
# Lua, 153 bytes

```
math.randomseed(os.time())a=load"b=({...})[1]return('%0'..b..'x'):format(math.random(0,16^b-1))"print(table.concat({a(8),a(4),a(4),a(4),a(8)..a(4)},"-"))

```

Try it online!
> 1 votes

# Answer
# Tcl, 95 bytes

```
time {append g [format %x[expr [incr i]%4|$i<7|$i>21?"":"-"] [expr int(rand()*16)]]} 32;puts $g

```

Try it online!

---

~~Tcl, 97 bytes
```
time {append g [format %x[expr [incr i]%4||$i<7||$i>21?"":"-"] [expr int(rand()*16)]]} 32;puts $g

```
Try it online!
~~

---

~~Tcl, 98 bytes
```
time {incr i;append g [format %x[expr $i%4||$i<7||$i>21?"":"-"] [expr int(rand()*16)]]} 32;puts $g

```
Try it online!
~~  ~~Tcl, 101 bytes
```
time {incr i;append g [format %x[expr !($i%4)&&$i>7&&$i<21?"-":""] [expr int(rand()*16)]]} 32;puts $g

```
Try it online!
Tcl, 104 bytes
```
proc D {n\ 4} {time {append g [format %x [expr int(rand()*16)]]} $n;set g}
puts [D 8]-[D]-[D]-[D]-[D 12]

```
Try it online!
~~
> 0 votes

# Answer
# Jelly, 17 bytes

```
ØhWẋ36X€”-“µÇŒð‘¦

```

Try it online!
> 0 votes

# Answer
# SmileBASIC, ~~65~~ 62 bytes

```
DEF G H?"-";:END
DEF H?HEX$(RND(65536),4);
END H G G G G H H H

```

I created a function to print 4 random hex digits: `DEF H?HEX$(RND(65536),4);:END` as well as 4 digits with a `-` after them: `DEF G:H?"-";:END`. Then it just has to call these functions a bunch of times.
> 0 votes

# Answer
# Chip, 109 + 5 = 114 bytes

Requires flags `-wc36`, causing +5 bytes

```
!ZZZZZZZZZZZZZZZZZZZZZZ
,-----.,+vv--^----^---z
?]]]--R\acd
?xx+-)\\b
?x+x-)\\c
?^xx\--\d
`-xx]v~\e
f*`)'`-\g

```

Try it online!

Generates 4 random bits (the four `?`'s) and converts to hex digits:

* `0x0` \- `0x9` =\> `0` \- `9`
* `0xa` \- `0xe` =\> `b` \- `f`
* `0xf` =\> `a`

...a bit unconventional, but it saved me some bytes at no expense to the distribution of outcomes.
> 0 votes

# Answer
# Ruby, ~~51~~ 47 + 14 = ~~65~~ 61 bytes

Run with `ruby -rsecurerandom` (+14 bytes)

```
[8,4,4,4,12].map{|n|SecureRandom.hex n}.join ?-

```

Returns output
> 0 votes

# Answer
# Java, ~~192~~ 181 bytes

```
interface T{static int t(){return (int)(Math.random()*65536);}static void main(String[]a){System.out.printf("aa-a-a-a-aaa".replaceAll("a","%04x"),t(),t(),t(),t(),t(),t(),t(),t());}}

```
> 0 votes

# Answer
## Octave, 106 105 103 99 96 bytes

```
function[]=f,g=@(l)[48:57,'a':'f'](randi(16,[1 l]));strjoin({g(8),g(4),g(4),g(4),g(12)},'-'),end

```

Try it Online
> 0 votes

# Answer
# Pyth, 34 bytes

```
VS32 aYO16)s.e?}km*d4r2 6+\-bb.HMY

```

Try it online!

trying to generate the indexes of where the "-" should go, and doing the replacement in a smaller way than hardcoding was an interesting challenge, and probably the hardest part.

### Explanation

```
VS32 aYO16)                          // for N in range(32), append a random number 0-15 to the list Y
                              .HMY   // convert each number in Y to its Hex equivalent
                 m*d4r2 6            // make an array (of indexes) containing [8 12 16 20]. *4 mapped over (range(2,6) -> [2,3,4,5])
            .e                       // enumerating map on the random hex list. For each digit, index is k and value is b.
              ?}k        +\-bb       // map onto each digit the ternary question "is index k in the array of idexes?"
                                     // if no, replace with b (the value that was already there), if yes replace it with "-b".
           s                         // "".join( ) to make the list into a string

```
> 0 votes

# Answer
# MBASIC, 92 bytes

```
1 FOR I=1 TO 32:PRINT HEX$(INT(RND*16));:IF I=8 OR I=12 OR I=16 OR I=20 THEN PRINT"-";
2 NEXT

```

Generates 32 "random" hex digits, adding a hyphen in the appropriate places.

Output:

```
D36A49D6-85AC-51DC-6D84-3BB1EB1A0816

```
> 0 votes

# Answer
# Pushy, 34 bytes

```
12N4448s$:Z15U&T)?39+;48+'.;L?45'.

```

**Try it online!**

```
12                                 \ Push 12 to stack
  N                                \ Remove printing delimiter (normally a newline)
   4448s                           \ Push 4448, then split into digits
                                   \ The stack is now [12, 4, 4, 4, 8]
        $                          \ While items left on stack:
         :                         \ (top item) times do:
          Z15U                     \    Push random(0, 15)
              &T)?                 \    If bigger than 10 (a hex digit):
                  39+;             \      Add 39 (offset from ASCII numbers to lowercase)
                      48+          \   Add 48, converting it into the correct character
                         '.        \   Print and pop this character
                           ;L?45'. \ Print a dash ('-'), unless stack is now empty.

```
> 0 votes

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

```
ŽΣÌε4*F15ÝΩh}J}'-ý

```

Outputs in uppercase.

Try it online.

**Explanation:**

```
ŽΣÌ                  # Push compressed integer 21113
   ε          }      # Pop and map over each of its digit:
    4*               #  Multiply the current digit by 4
      F     }        #  Pop and loop that many times:
       15Ý           #   Push a list in the range [0,15]
          Ω          #   Pop and pick a random number from it
           h         #   Convert it to hexadecimal
            }J       #  After the inner loop: Join the stack together
               }'-ý '# After the map: join the list with "-"-delimiter together
                     # (after which this string is output implicitly as result)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `ŽΣÌ` is `21113`.
> 0 votes

# Answer
# JavaScript (ES6), 79 bytes

```
a=>[8,4,4,4,12].map(g=e=>e?(16*Math.random()|0).toString(16)+g(e-1):"").join`-`

```
> 0 votes

# Answer
## Javascript (ES6) - 102 bytes

### UUID v4 compliant

A compaction of broofa's solution on Stackoverflow:

```
"10000000-1000-4000-8000-100000000000".replace(/[018]/g,s=>(s^Math.random()*256&15>>s/4).toString(16))

```
> 0 votes

# Answer
# Python 3, 103 bytes

```
from random import*;print(''.join(hex(randint(2**(i*3),2**(3*i+2)))[2:]+'-'for i in [8,4,4,4,12])[:33])

```

Try it online!

Is 100% improvable...
> 0 votes

# Answer
# Vyxal, 120 bitsv2, 15 bytes

```
8 4D₆Wk632ƈ∑ẇ\-j

```

Try it Online!

## Explained

```
8 4D₆Wk632ƈ∑ẇ\-j
8 4D₆W            # Push the list [8, 4, 4, 4, 64] to the stack
      k632ƈ∑      # Push a string of 32 random hex digits
            ẇ     # Wrap into slices of lengths in the first list. The 64 is used as a value to ensure that the last 12 slice is fully captured.
             \-j  # And join on "-"s

```

Created with the help of Luminespire.
> 0 votes

# Answer
# q, 13 bytes

Not sure if it violates *"No built-ins."* hoever it's not using the built-in method to generate a random GUID which would be `rand 0Ng`. Generates 16 random bytes and packs them into a guid.

```
0x0 sv 16?0x0

```

## Example

```
q)0x0 sv 16?0x0
8e204f8d-5a0b-b188-1131-4ff06efe824d

```
> 0 votes

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


# Question
Title: Output greater than without the previous character
For each character in your program, the program with that character removed must produce a number smaller than the program with the next character removed. Your base program isn't required to do anything, and may be invalid.

An example submission could be `abcd`, where `bcd` outputs 1, `acd` outputs 4, `abd` outputs 5, and `abc` outputs 11.

Your output can be in any format allowed by default (e.g. list of digits, unary string, etc.), but all of your programs must output in the same format.

This is , so the *longest* code in characters, not bytes, wins.

# Answer
> 11 votes
# 05AB1E, \\$\infty\\$ characters

```
20369141745912154102595617074602372501021979838148129261367042484187839780820875821640725982497528535478174327409769295405241482382746825238016107679706574234359475857846801942689179521875304719272368749439413187673971523039421241681202798017924924741462918745857212658216736782561383910642567545351659395459213287812390525XY20369141745912154102595617074602372501021979838148129261367042484187839780820875821640725982497528535478174327409769295405241482382746825238016107679706574234359475857846801942689179521875304719272368749439413187673971523039421241681202798017924924741462918745857212658216736782561383910642567545351659395459213287812390525M₁BD.VÁ.V

```

Try it online!

This technique is capable of generating arbitrarily long solutions, and given here is a 657 characters one.

When removing each character, this outputs

```
-20369141745912154102595617074602372501021979838148129261367042484187839780820875821640725982497528535478174327409769295405241482382746825238016107679706574234359475857846801942689179521875304719272368749439413187673971523039421241681202798017924924741462918745857212658216736782561383910642567545351659395459213287812390525000
-20369141745912154102595617074602372501021979838148129261367042484187839780820875821640725982497528535478174327409769295405241482382746825238016107679706574234359475857846801942689179521875304719272368749439413187673971523039421241681202798017924924741462918745857212658216736782561383910642567545351659395459213287812390524999
...
-20369141745912154102595617074602372501021979838148129261367042484187839780820875821640725982497528535478174327409769295405241482382746825238016107679706574234359475857846801942689179521875304719272368749439413187673971523039421241681202798017924924741462918745857212658216736782561383910642567545351659395459213287812390524679
-20369141745912154102595617074602372501021979838148129261367042484187839780820875821640725982497528535478174327409769295405241482382746825238016107679706574234359475857846801942689179521875304719272368749439413187673971523039421241681202798017924924741462918745857212658216736782561383910642567545351659395459213287812390524678
-20369141745912154102595617074602372501021979838148129261367042484187839780820875821640725982497528535478174327409769295405241482382746825238016107679706574234359475857846801942689179521875304719272368749439413187673971523039421241681202798017924924741462918745857212658216736782561383910642567545351659395459213287812390527
-20369141745912154102595617074602372501021979838148129261367042484187839780820875821640725982497528535478174327409769295405241482382746825238016107679706574234359475857846801942689179521875304719272368749439413187673971523039421241681202798017924924741462918745857212658216736782561383910642567545351659395459213287812390526
-20369141745912154102595617074602372501021979838148129261367042484187839780820875821640725982497528535478174327409769295405241482382746825238016107679706574234359475857846801942689179521875304719272368749439413187673971523039421241681202798017924924741462918745857212658216736782561383910642567545351659395459213287812390525
...
-20369141745912154102595617074602372501021979838148129261367042484187839780820875821640725982497528535478174327409769295405241482382746825238016107679706574234359475857846801942689179521875304719272368749439413187673971523039421241681202798017924924741462918745857212658216736782561383910642567545351659395459213287812390204
-20369141745912154102595617074602372501021979838148129261367042484187839780820875821640725982497528535478174327409769295405241482382746825238016107679706574234359475857846801942689179521875304719272368749439413187673971523039421241681202798017924924741462918745857212658216736782561383910642567545351659395459213287812390203
-3
01
625
997
998
20369141745912154102595617074602372501021979838148129261367042484187839780820875821640725982497528535478174327409769295405241482382746825238016107679706574234359475857846801942689179521875304719272368749439413187673971523039421241681202798017924924741462918745857212658216736782561383910642567545351659395459213287812390526
203691417459121541025956170746023725010219798381481292613670424841878397808208758216407259824975285354781743274097692954052414823827468252380161076797065742343594758578468019426891795218753047192723687494394131876739715230394212416812027980179249247414629187458572126582167367825613839106425675453516593954592132878123905259
203691417459121541025956170746023725010219798381481292613670424841878397808208758216407259824975285354781743274097692954052414823827468252380161076797065742343594758578468019426891795218753047192723687494394131876739715230394212416812027980179249247414629187458572126582167367825613839106425675453516593954592132878123905270
920369141745912154102595617074602372501021979838148129261367042484187839780820875821640725982497528535478174327409769295405241482382746825238016107679706574234359475857846801942689179521875304719272368749439413187673971523039421241681202798017924924741462918745857212658216736782561383910642567545351659395459213287812390525

```

## Explanation

This code has a pattern of `<number>XY<number>M₁BD.VÁ.V`, when `<number>` doesn't have any equal consecutive digits.

If one of `₁B` is removed then the code will output `01` or `625` respectively. Otherwise, the number will be base256 decoded and then run as an 05AB1E. This code inspects the stack, to detect which character was removed, if it wasn't one of `.VÁ.V`, output the correct number, and exit.

If the first `.` is removed, then `V` saves the code to the `Y` variable, which we can also detect and output `998`.

If the first `V` is removed, we get `.Á.V`, where  rotates the stack, so this is detected by inspection of the stack.

Otherwise, we leave `10N+20, 10N+9` on the stack after the first `.V`:

* If the `Á` was removed, then `10N+9` is executed and returns itself.
* If the `.` was removed, then `V` pops the `10N+9` and `10N+20` is returned.
* If the `V` was removed, `Á` rotates the top number, so the output is `rot(10N+9)`.

This is what the number base256 decodes to:

```
)D g4Qi D21 S èOsθ.ï><₄ * -(Y2Ê+,q} ¤.ïi θ>,q}D30Sè` ›iD 30Sè€Sø€ËO sà ₄*-,qB} D30Sè `‹iD30 Sè€S ø€ËOsà- ,q }àDsÌ10*s 9ªJ0i     a a  }

```

This code isn't especially interesting, but notice that there are a lot of spaces there which were inserted by trial-and-error to make sure there aren't any equal consecutive digits (because in that case we can't know which was removed).

`<number>XY<number>M` leaves `<number>` at top of the stack even after one character removal: If `M` was removed, then it's obvious, otherwise at least one instance of `<number>` must be valid, and it will be the bigger one, which `M` (which pushes the biggest number on the stack) will push.

# Answer
> 5 votes
# Wolfram Alpha, 12 characters

*Slight modification of the trivial solution in the community wiki, works for all languages that support superscript numbers as exponentiation*

```
10⁹⁸⁷⁶⁵⁴³²¹⁰

```

```
0⁹⁸⁷⁶⁵⁴³²¹⁰  -> 0
1⁹⁸⁷⁶⁵⁴³²¹⁰  -> 1
10⁸⁷⁶⁵⁴³²¹⁰  -> 10^876543210
...

10⁹⁸⁷⁶⁵⁴³²¹  -> 10^987654321

```

Try it online

# Answer
> 4 votes
# Languages with implicit output - 10 characters

```
9876543210

```

876543210 \< 976543210 \< 986543210 \< 987543210 \< 987643210 \< 987653210 \< 987654210 \< 987654310 \< 987654320 \< 987654321.

This works in languages such as Vyxal, Thunno 2, 05AB1E, Japt, PHP, the list goes on. You can edit in your favorite language here if you really want but it's not necessary.

Don't upvote this! It took very little effort. Instead, upvote clever answers in languages that don't abuse this trick.

# Answer
> 4 votes
# , 13 characters

```
10^9876543210

```

Attempt This Online!

Languages (like R) that use `^` for exponentiation can gain 1 byte using a slight modification of bsoelch's slight modification of noodle man's CW answer.

# Answer
> 2 votes
# Jelly, ~~13~~ 14 bytes

```
10*9876543210H

```

Try it online!

Based on @DominicVanEssen’s R solution in turn based on @bsoelch’s Wolfram Alpha solution. However, now adds one extra monad (`H`) to the end.

Note the TIO link shows all possible ways of removing a byte but is based on a shorter version of the code since the massive exponentiation times out. Given enough compute and memory it would work as intended.

---
Tags: code-bowling, radiation-hardening
---


title: Short Deadfish Numbers

text:
# Question
Title: Short Deadfish Numbers
Deadfish is one of the best known non Turing-complete programming languages. It has only one accumulator (which starts at 0) to store data, and only four commands:

```
i - Increment the accumulator
s - Square the accumulator
d - Decrement the accumulator
o - Output the accumulator

```

A Deadfish program may look like:

```
iiisdo

```

And that would print:

```
8

```

---

# The challenge

Create a program that will input a number and output Deadfish code to display the number.(Or make a function that takes the number as a parameter and returns the code.) It must work for any integer from `0` to `255`

## Goal

Try to make your code make the shortest code possible to generate the given number. For example:

```
iiiiiiiiio

```

and

```
iiiso

```

each print `9`, but the second is shorter.

# Scoring

Your score is:

```
The number of characters in your source code +
The sum of the lengths of your output for all numbers from 1-255
-100 if the language you chose is Deadfish :)

```

Lowest score wins!

---

In the original challenge I only had the sum of 6 numbers(9,17,99,100 and 123). This was from me wanting to not make everyone test for every number, and I wanted the shortest code to be relevant. Then I realized that programmers are good at making scripts to test things like that, and I would rather have this be a contest for best algorithm with golfing as a tiebreaker.

Therefor I changed this, as suggested by Martin Büttner.

# Answer
# Perl, ~~132~~ 131 bytes + 2036 bytes = 2167

Includes +2 for `-lp`

Run with the target number on STDIN, e.g.

```
perl -lp deadfish.pl <<< 160

```

deadfish.pl:

```
@;=map{s%(o)|(s)|(i|d)|%$_-=e cmp$3.e;$_*=$_-16&&$_ if$2;$1&&$_%eg;@$_=$`;grep/id|di/^y/o//<4,<{o,s,d,i}$`>}~~o,@;until$\="@$_"}{

```

The grep is a filter to constrain the exponential explosion a bit (though this program still needs 2 GB for the hard cases). It also works without but I can't run it on my hardware like that except for the easy cases. But in principle this `110=108+2` byte program works too:

```
@;=map{s%(o)|(s)|(i|d)|%$_-=e cmp$3.e;$_*=$_-16&&$_ if$2;$1&&$_%eg;@$_=$`;<{o,s,d,i}$`>}$a,@;until$\="@$_"}{

```

Output list:

```
1   io
2   iio
3   iiio
4   iiso
5   iisio
6   iisiio
7   iisiiio
8   iiisdo
9   iiiso
10  iodo
11  ioo
12  ioio
13  ioiio
14  ioiso
15  ioisio
16  iisso
17  iissio
18  iissiio
19  ioiiso
20  iioddo
21  iiodo
22  iioo
23  iioio
24  iioso
25  iiosio
26  iiosiio
27  iiosiiio
28  iioisdo
29  iioiso
30  iiiodddo
31  iiioddo
32  iiiodo
33  iiioo
34  iiioio
35  iiioiio
36  iisiiso
37  iisiisio
38  iiiosdo
39  iiioso
40  iisosso
41  iisossio
42  iisoddo
43  iisodo
44  iisoo
45  iisoio
46  iisoiio
47  iisoiiio
48  iisodsdo
49  iisodso
50  iisiiisio
51  iisiiisiio
52  iisiodddo
53  iisioddo
54  iisiodo
55  iisioo
56  iisioio
57  iisioiio
58  iisioiiio
59  iisioddso
60  iiisdsddddo
61  iiisdsdddo
62  iiisdsddo
63  iiisdsdo
64  iiisdso
65  iiisdsio
66  iisiioo
67  iisiioio
68  iisiioiio
69  iisiioiiio
70  iiisdsiiiiiio
71  iiisdsiiiiiiio
72  iisiiiodddddo
73  iisiiioddddo
74  iisiiiodddo
75  iisiiioddo
76  iisiiiodo
77  iisiiioo
78  iisiiioio
79  iiissddo
80  iiissdo
81  iiisso
82  iiissio
83  iiissiio
84  iiissiiio
85  iiissiiiio
86  iiisdoddo
87  iiisdodo
88  iiisdoo
89  iiisdoio
90  iiisodddddsso
91  iiisodddddssio
92  iiisodddddddo
93  iiisoddddddo
94  iiisodddddo
95  iiisoddddo
96  iiisodddo
97  iiisoddo
98  iiisodo
99  iiisoo
100 iodoo
101 iodoio
102 iodoiio
103 iodoiiio
104 iodoiiso
105 iodoiisio
106 iodoiisiio
107 iiisiodddo
108 iiisioddo
109 iiisiodo
110 ioodo
111 iooo
112 iooio
113 iooiio
114 iooiso
115 iooisio
116 ioisso
117 ioissio
118 ioissiio
119 iooiiso
120 ioioddo
121 ioiodo
122 ioioo
123 ioioio
124 ioioso
125 ioiosio
126 ioiosiio
127 ioiosiiio
128 ioioisdo
129 ioioiso
130 ioiiodddo
131 ioiioddo
132 ioiiodo
133 ioiioo
134 ioiioio
135 ioiioiio
136 ioisiiso
137 ioisiisio
138 ioiiosdo
139 ioiioso
140 ioisosso
141 ioisossio
142 ioisoddo
143 ioisodo
144 ioisoo
145 ioisoio
146 ioisoiio
147 ioisoiiio
148 ioisodsdo
149 ioisodso
150 iissdoiso
151 iissdoisio
152 ioisiodddo
153 ioisioddo
154 ioisiodo
155 ioisioo
156 ioisioio
157 ioisioiio
158 ioisioiiio
159 ioisioddso
160 iissoso
161 iissosio
162 iissosiio
163 ioiisdsdo
164 ioiisdso
165 ioiisdsio
166 ioisiioo
167 ioisiioio
168 ioisiioiio
169 iissdddso
170 iissiodso
171 iissiodsio
172 iissiodsiio
173 iissiodsiiio
174 ioisiiiodddo
175 ioisiiioddo
176 ioisiiiodo
177 ioisiiioo
178 ioisiiioio
179 ioiissddo
180 ioiissdo
181 ioiisso
182 ioiissio
183 ioiissiio
184 ioiissiiio
185 ioiissiiiio
186 ioiisdoddo
187 ioiisdodo
188 ioiisdoo
189 ioiisdoio
190 iissiiiodddso
191 iissddsdddddo
192 iissddsddddo
193 iissddsdddo
194 iissddsddo
195 iissddsdo
196 iissddso
197 iissddsio
198 ioiisodo
199 ioiisoo
200 iioddoo
201 iioddoio
202 iioddoiio
203 iioddoiiio
204 iioddoiiso
205 iioddoiisio
206 iioddoiisiio
207 iioddoiisiiio
208 iioddoiiisdo
209 iioddoiiiso
210 iioisio
211 iiodoo
212 iiodoio
213 iiodoiio
214 iiossddo
215 iiossdo
216 iiosso
217 iiossio
218 iiossiio
219 iiossiiio
220 iiooddo
221 iioodo
222 iiooo
223 iiooio
224 iiooso
225 iioosio
226 iioosiio
227 iioosiiio
228 iiooisdo
229 iiooiso
230 iioiodddo
231 iioioddo
232 iioiodo
233 iioioo
234 iioioio
235 iioioiio
236 iiosiiso
237 iiosiisio
238 iioiosdo
239 iioioso
240 iiososso
241 iiosossio
242 iiosoddo
243 iiosodo
244 iiosoo
245 iiosoio
246 iiosoiio
247 iiosoiiio
248 iiosodsdo
249 iiosodso
250 iiosiiisio
251 iiosiiisiio
252 iiosiodddo
253 iiosioddo
254 iiosiodo
255 iiosioo
```
> 3 votes

# Answer
# ES6 JavaScript 2126 + 311 = 2437 score

```
m=Math;s=n=>[b=m.min(m.sqrt(n)+.5|0,15),n-b*b];f=n=>(n<0?'d':'i').repeat(m.abs(n));g=(n,t)=>n<4?f(n):g((t=s(n))[0])+'s'+f(t[1]);q=n=>((x=g(n)).length>(z=[...n+''].map((k,i,a)=>i?(a[i-1]==a[i]?'':(y=f((l=s(k))[0]-a[i-1])+(l[0]?'s':'')+f(l[1])).length>m.abs(Q=a[i]-a[i-1])?f(Q):y):g(k)).join('o')).length?z:x)+'o'

```

Semi-commented:

```
m = Math; // Keep a reference to math
// This function returns the closest perfect square and the distance from that square to the number
// E.g. s(10) --> [3, 1] because 3^2 + 1 = 10
s = n => [b = m.min(m.sqrt(n) + .5 | 0, 15), n - b * b];
// This creates a bunch of "d"s or "i"s
// E.g. f(3) --> "iii" or f(-2) --> "dd"
f = n => Array(m.abs(n) + 1).join(n < 0 ? 'd' : 'i');
// This constructs the number as a number rather than by digit
g = (n, t) => n < 4 ?
              // If n is less than 4, then we can just increment in normally (base case)
              f(n) :
              // Otherwise, build the square root recursively and shift
              g((t = s(n))[0]) + 's' + f(t[1]);
// This maps based on digits (constructs the number by digit)
// This has now been removed and replaced inline because it is only used once
d = n => (a = [...(n + '')]).map((k, i) => i ? (a[i - 1] == a[i] ? '' : f((l = s(k))[0] - a[i - 1]) + (l[0] ? 's' : '') + f(l[1])) : g(k)).join('o');
// For the official function, compare the digit-method and nondigit-method and return the best one
q = n => ((x = g(n)).length > (z = d(n)).length ? z : x) + 'o'

```

This takes advantage of the fact that in deadfish, you can print more than one character.

Example: `10` compiles to `iodo` which is "print one, decrement, print zero."

Usage:

```
q(10) // --> iodo
q(16) // --> iisso

```

Here's json data of output:

```
{
    "0": "o",
    "1": "io",
    "2": "iio",
    "3": "iiio",
    "4": "iiso",
    "5": "iisio",
    "6": "iisiio",
    "7": "iiisddo",
    "8": "iiisdo",
    "9": "iiiso",
    "10": "iodo",
    "11": "ioo",
    "12": "ioio",
    "13": "ioiio",
    "14": "ioiso",
    "15": "iissdo",
    "16": "iisso",
    "17": "iissio",
    "18": "iissiio",
    "19": "ioiiso",
    "20": "iioddo",
    "21": "iiodo",
    "22": "iioo",
    "23": "iioio",
    "24": "iioso",
    "25": "iisiso",
    "26": "iisisio",
    "27": "iisisiio",
    "28": "iioisdo",
    "29": "iioiso",
    "30": "iiiodddo",
    "31": "iiioddo",
    "32": "iiiodo",
    "33": "iiioo",
    "34": "iiioio",
    "35": "iiioiio",
    "36": "iisiiso",
    "37": "iisiisio",
    "38": "iiiosdo",
    "39": "iiioso",
    "40": "iisoddddo",
    "41": "iisodddo",
    "42": "iisoddo",
    "43": "iisodo",
    "44": "iisoo",
    "45": "iisoio",
    "46": "iisoiio",
    "47": "iisoiiio",
    "48": "iisodsdo",
    "49": "iisodso",
    "50": "iiisddsio",
    "51": "iiisddsiio",
    "52": "iisiodddo",
    "53": "iisioddo",
    "54": "iisiodo",
    "55": "iisioo",
    "56": "iisioio",
    "57": "iisioiio",
    "58": "iisioiiio",
    "59": "iisioddso",
    "60": "iiisdsddddo",
    "61": "iiisdsdddo",
    "62": "iiisdsddo",
    "63": "iiisdsdo",
    "64": "iiisdso",
    "65": "iiisdsio",
    "66": "iisiioo",
    "67": "iisiioio",
    "68": "iisiioiio",
    "69": "iisiioiiio",
    "70": "iiisdsiiiiiio",
    "71": "iiisdsiiiiiiio",
    "72": "iiisddodddddo",
    "73": "iiisddoddddo",
    "74": "iiisddodddo",
    "75": "iiisddoddo",
    "76": "iiisddodo",
    "77": "iiisddoo",
    "78": "iiissdddo",
    "79": "iiissddo",
    "80": "iiissdo",
    "81": "iiisso",
    "82": "iiissio",
    "83": "iiissiio",
    "84": "iiissiiio",
    "85": "iiissiiiio",
    "86": "iiisdoddo",
    "87": "iiisdodo",
    "88": "iiisdoo",
    "89": "iiisdoio",
    "90": "iiissiiiiiiiiio",
    "91": "iiisoddddddddo",
    "92": "iiisodddddddo",
    "93": "iiisoddddddo",
    "94": "iiisodddddo",
    "95": "iiisoddddo",
    "96": "iiisodddo",
    "97": "iiisoddo",
    "98": "iiisodo",
    "99": "iiisoo",
    "100": "iodoo",
    "101": "iodoio",
    "102": "iodoiio",
    "103": "iodoiiio",
    "104": "iodoiiso",
    "105": "iodoiisio",
    "106": "iodoiisiio",
    "107": "iodoiiisddo",
    "108": "iodoiiisdo",
    "109": "iodoiiiso",
    "110": "ioodo",
    "111": "iooo",
    "112": "iooio",
    "113": "iooiio",
    "114": "iooiso",
    "115": "iooisio",
    "116": "iooisiio",
    "117": "iooiisddo",
    "118": "iooiisdo",
    "119": "iooiiso",
    "120": "ioioddo",
    "121": "ioiodo",
    "122": "ioioo",
    "123": "ioioio",
    "124": "ioioso",
    "125": "ioiosio",
    "126": "ioiosiio",
    "127": "ioioisddo",
    "128": "ioioisdo",
    "129": "ioioiso",
    "130": "ioiiodddo",
    "131": "ioiioddo",
    "132": "ioiiodo",
    "133": "ioiioo",
    "134": "ioiioio",
    "135": "ioiioiio",
    "136": "ioiioiiio",
    "137": "ioiiosddo",
    "138": "ioiiosdo",
    "139": "ioiioso",
    "140": "ioisoddddo",
    "141": "ioisodddo",
    "142": "ioisoddo",
    "143": "ioisodo",
    "144": "ioisoo",
    "145": "ioisoio",
    "146": "ioisoiio",
    "147": "ioisoiiio",
    "148": "ioisodsdo",
    "149": "ioisodso",
    "150": "ioisiodddddo",
    "151": "ioisioddddo",
    "152": "ioisiodddo",
    "153": "ioisioddo",
    "154": "ioisiodo",
    "155": "ioisioo",
    "156": "ioisioio",
    "157": "ioisioiio",
    "158": "ioisioiiio",
    "159": "ioisioddso",
    "160": "ioisiioddddddo",
    "161": "ioisiiodddddo",
    "162": "ioisiioddddo",
    "163": "ioisiiodddo",
    "164": "ioisiioddo",
    "165": "ioisiiodo",
    "166": "ioisiioo",
    "167": "ioisiioio",
    "168": "iissdddsdo",
    "169": "iissdddso",
    "170": "iissdddsio",
    "171": "iissdddsiio",
    "172": "iissdddsiiio",
    "173": "iissdddsiiiio",
    "174": "ioiisddodddo",
    "175": "ioiisddoddo",
    "176": "ioiisddodo",
    "177": "ioiisddoo",
    "178": "ioiisddoio",
    "179": "ioiisddoiio",
    "180": "ioiisdoddddddddo",
    "181": "ioiisdodddddddo",
    "182": "ioiisdoddddddo",
    "183": "ioiisdodddddo",
    "184": "ioiisdoddddo",
    "185": "ioiisdodddo",
    "186": "ioiisdoddo",
    "187": "ioiisdodo",
    "188": "ioiisdoo",
    "189": "ioiisdoio",
    "190": "iissddsddddddo",
    "191": "iissddsdddddo",
    "192": "iissddsddddo",
    "193": "iissddsdddo",
    "194": "iissddsddo",
    "195": "iissddsdo",
    "196": "iissddso",
    "197": "iissddsio",
    "198": "ioiisodo",
    "199": "ioiisoo",
    "200": "iioddoo",
    "201": "iioddoio",
    "202": "iioddoiio",
    "203": "iioddoiiio",
    "204": "iioddoiiso",
    "205": "iioddoiisio",
    "206": "iioddoiisiio",
    "207": "iioddoiiisddo",
    "208": "iioddoiiisdo",
    "209": "iioddoiiiso",
    "210": "iiododo",
    "211": "iiodoo",
    "212": "iiodoio",
    "213": "iiodoiio",
    "214": "iiodoiso",
    "215": "iiodoisio",
    "216": "iiodoisiio",
    "217": "iiodoiisddo",
    "218": "iiodoiisdo",
    "219": "iiodoiiso",
    "220": "iiooddo",
    "221": "iioodo",
    "222": "iiooo",
    "223": "iiooio",
    "224": "iiooso",
    "225": "iissdso",
    "226": "iissdsio",
    "227": "iissdsiio",
    "228": "iiooisdo",
    "229": "iiooiso",
    "230": "iioiodddo",
    "231": "iioioddo",
    "232": "iioiodo",
    "233": "iioioo",
    "234": "iioioio",
    "235": "iioioiio",
    "236": "iioioiiio",
    "237": "iioiosddo",
    "238": "iioiosdo",
    "239": "iioioso",
    "240": "iiosoddddo",
    "241": "iiosodddo",
    "242": "iiosoddo",
    "243": "iiosodo",
    "244": "iiosoo",
    "245": "iiosoio",
    "246": "iiosoiio",
    "247": "iiosoiiio",
    "248": "iiosodsdo",
    "249": "iiosodso",
    "250": "iiosiodddddo",
    "251": "iiosioddddo",
    "252": "iiosiodddo",
    "253": "iiosioddo",
    "254": "iiosiodo",
    "255": "iiosioo"
}

```

That was generated by this code:

```
var c = {}, result = 0;
for (var i = 0; i <= 255; ++i) result += (c[i] = q(i)).length;

```

which prints `result = (the result)` and `c =` the thing above.

This gets a remarkably high score despite being pretty simple. It searches for the nearest perfect square, calculates the square root of that perfect square, adds 's', and increments/decrements appropriately.

Old version which didn't use the fact that "10" = "print one, print zero"

```
m=Math;s=n=>[b=m.sqrt(n)+.5|0,n-b*b];f=(n)=>Array(m.abs(n)+1).join('id'[+(n<0)]);g=(n,t)=>n<4?f(n):g((t=s(n))[0])+'s'+f(t[1]);q=n=>g(n)+'o'

```
> 9 votes

# Answer
# Haskell, ~~2200~~ ~~2177~~ 2171 = 2036 + 135

```
f n=[s|s<-l,s%0==show n]!!0
l="":[c:x|x<-l,c<-"iosd"]
(h:s)%n|h<'e'=s%(n-1)|h<'j'=s%(n+1)|h<'p'=show n++s%n|n==16=s%0|0<1=s%(n^2)
x%_=x

```

this works by having an infinite list of all deadfish programs, sorted by their length, accompanied by the internal state and the output. the function `f` searches the list and returns the first entry that matches.

this approach allows for for multiple `o` in each resulting code, but does not restrict it to either printing all the digits separately, or printing the whole number at once. for example, here 216 has the code of `iiosso`.

**Edit:**
according to the spec, when the state is 256 (but not 257) it is made into a 0. now my code takes this into account. for example, 160 is `iissoso`.

this has a few efficiency problems; because `l` is a top-level list, all the elements of `l` which have been evaluated stay in memory, and so runtime will probably be out of memory at some point.

to calculate the score, I made an equivalent-but-less-memory-heavy version.

my more-efficient code works by recomputing the list on every application of `f`, so that the garbage collector can throw the already searched part of the list away. in a sense, this is breadth-first search using laziness.

the more-efficient code also adds some more constraints to the elements of the list - it filters out all codes that contain `id` or `di`, or contains an `s` when the state is smaller than 2.

**Edit:**
I moved the `g` function from the top level to being a helper function to `f'`, so now `g` filters codes that printed something which isn't a prefix of our wanted number. now the code is much faster.

the more-efficient code:

```
f' n=[reverse s|(s,_,r)<-l,r==show n]!!0 where
    l=("",0,""):l>>= \(i,s,r)->filter g[('i':i,s+1,r),('o':i,s,r++show s),('s':i,if s==16 then 0 else s*s,r),('d':i,s-1,r)]
    g('i':'d':_,_,_)=False
    g('d':'i':_,_,_)=False
    g('i':'i':_,4,_)=False
    g('s':_,1,_)=False
    g("s",_,_)=False
    g("si",_,_)=False
    g(i,s,r)=s<256&&s>=0&&isPrefixOf r (show n)

```

note the more-efficient code will not have the same results because the programs traverse all the possible codes in different order. however, they will output codes of the same length. also, switching `c:x` with `x++[c]` makes the programs equivalent.

with this code i was able to compute all the programs in ~~52~~ 0.81 seconds.

**Edit:**
apparently this is the best answer! i noticed it just now, so far from when this was asked...

the results:

```
1   io
2   iio
3   iiio
4   iiso
5   iisio
6   iisiio
7   iiisddo
8   iiisdo
9   iiiso
10  iodo
11  ioo
12  ioio
13  ioiio
14  ioiso
15  iissdo
16  iisso
17  iissio
18  iissiio
19  ioiiso
20  iioddo
21  iiodo
22  iioo
23  iioio
24  iioso
25  iiosio
26  iiosiio
27  iioisddo
28  iioisdo
29  iioiso
30  iiioisso
31  iiioddo
32  iiiodo
33  iiioo
34  iiioio
35  iiioiio
36  iisiiso
37  iiiosddo
38  iiiosdo
39  iiioso
40  iisosso
41  iisossio
42  iisoddo
43  iisodo
44  iisoo
45  iisoio
46  iisoiio
47  iisoiiio
48  iisodsdo
49  iisodso
50  iiisddsio
51  iiisddsiio
52  iisiodddo
53  iisioddo
54  iisiodo
55  iisioo
56  iisioio
57  iisioiio
58  iisioiiio
59  iisioddso
60  iiisdsddddo
61  iiisdsdddo
62  iiisdsddo
63  iiisdsdo
64  iiisdso
65  iiisdsio
66  iisiioo
67  iisiioio
68  iisiioiio
69  iisiioiiio
70  iiisdsiiiiiio
71  iiisdsiiiiiiio
72  iiisddodddddo
73  iiisddoddddo
74  iiisddodddo
75  iiisddoddo
76  iiisddodo
77  iiisddoo
78  iiissdddo
79  iiissddo
80  iiissdo
81  iiisso
82  iiissio
83  iiissiio
84  iiissiiio
85  iiissiiiio
86  iiisdoddo
87  iiisdodo
88  iiisdoo
89  iiisdoio
90  iiisodddddsso
91  iiisodddddssio
92  iiisodddddddo
93  iiisoddddddo
94  iiisodddddo
95  iiisoddddo
96  iiisodddo
97  iiisoddo
98  iiisodo
99  iiisoo
100 iodoo
101 iodoio
102 iodoiio
103 iodoiiio
104 iodoiiso
105 iodoiisio
106 iodoiisiio
107 iiisiodddo
108 iiisioddo
109 iiisiodo
110 ioodo
111 iooo
112 iooio
113 iooiio
114 iooiso
115 ioissdo
116 ioisso
117 ioissio
118 ioissiio
119 iooiiso
120 ioioddo
121 ioiodo
122 ioioo
123 ioioio
124 ioioso
125 ioiosio
126 ioiosiio
127 ioioisddo
128 ioioisdo
129 ioioiso
130 ioiioisso
131 ioiioddo
132 ioiiodo
133 ioiioo
134 ioiioio
135 ioiioiio
136 ioisiiso
137 ioiiosddo
138 ioiiosdo
139 ioiioso
140 ioisosso
141 ioisossio
142 ioisoddo
143 ioisodo
144 ioisoo
145 ioisoio
146 ioisoiio
147 ioisoiiio
148 ioisodsdo
149 ioisodso
150 iissdoiso
151 iissdoisio
152 ioisiodddo
153 ioisioddo
154 ioisiodo
155 ioisioo
156 ioisioio
157 ioisioiio
158 ioisioiiio
159 ioisioddso
160 iissoso
161 iissosio
162 iissosiio
163 ioiisdsdo
164 ioiisdso
165 ioiisdsio
166 ioisiioo
167 ioisiioio
168 iissdddsdo
169 iissdddso
170 iissiodso
171 iissiodsio
172 iissiodsiio
173 iissiodsiiio
174 iissiodsiiso
175 ioiisddoddo
176 ioiisddodo
177 ioiisddoo
178 ioiissdddo
179 ioiissddo
180 ioiissdo
181 ioiisso
182 ioiissio
183 ioiissiio
184 ioiissiiio
185 ioiissiiiio
186 ioiisdoddo
187 ioiisdodo
188 ioiisdoo
189 ioiisdoio
190 iissiiiodddso
191 iissddsdddddo
192 iissddsddddo
193 iissddsdddo
194 iissddsddo
195 iissddsdo
196 iissddso
197 iissddsio
198 ioiisodo
199 ioiisoo
200 iioddoo
201 iioddoio
202 iioddoiio
203 iioddoiiio
204 iioddoiiso
205 iioddoiisio
206 iioddoiisiio
207 iioddoiiisddo
208 iioddoiiisdo
209 iioddoiiiso
210 iioisio
211 iiodoo
212 iiodoio
213 iiodoiio
214 iiossddo
215 iiossdo
216 iiosso
217 iiossio
218 iiossiio
219 iiossiiio
220 iiooddo
221 iioodo
222 iiooo
223 iiooio
224 iiooso
225 iioosio
226 iioosiio
227 iiooisddo
228 iiooisdo
229 iiooiso
230 iioioisso
231 iioioddo
232 iioiodo
233 iioioo
234 iioioio
235 iioioiio
236 iiosiiso
237 iioiosddo
238 iioiosdo
239 iioioso
240 iiososso
241 iiosossio
242 iiosoddo
243 iiosodo
244 iiosoo
245 iiosoio
246 iiosoiio
247 iiosoiiio
248 iiosodsdo
249 iiosodso
250 iioisddsio
251 iioisddsiio
252 iiosiodddo
253 iiosioddo
254 iiosiodo
255 iiosioo

```
> 6 votes

# Answer
## Mathematica, ~~254~~ 165 characters + 3455 = 3620

```
f@n_:=n;g@0="";l={f@0=0};h=If[f@#>f@i&&#<256&&#>0,f@#=f@i+1;g@#=g@i<>#2;l~AppendTo~#]&;While[l!={},i=#&@@l;l=Rest@l;h[i+1,"i"];h[i-1,"d"];h[i*i,"s"];];g@Input[]<>"o"

```

Less golf:

```
f@n_ := n;
g@0 = "";
l = {f@0 = 0};
h = If[f@# > f@i && # < 256 && # > 0,
    f@# = f@i + 1;
    g@# = g@i <> #2;
    l~AppendTo~#] &;
While[l != {},
  i = # & @@ l;
  l = Rest@l;
  h[i + 1, "i"];
  h[i - 1, "d"];
  h[i*i, "s"];
  ];
g@Input[] <> "o"

```

I believe the resulting numbers are optimal. This is doing a breadth-first search over all 256 numbers, keeping track of the shortest way it has found to represent each number. The search is building a sort of lookup table in the function `g` which is then applied to the input.

For reference, here are all 255 results:

```
io
iio
iiio
iiso
iisio
iisiio
iisiiio
iiisdo
iiiso
iiisio
iiisiio
iiisiiio
iissdddo
iissddo
iissdo
iisso
iissio
iissiio
iissiiio
iissiiiio
iissiiiiio
iisisdddo
iisisddo
iisisdo
iisiso
iisisio
iisisiio
iisisiiio
iisisiiiio
iisisiiiiio
iisisiiiiiio
iisiisddddo
iisiisdddo
iisiisddo
iisiisdo
iisiiso
iisiisio
iisiisiio
iisiisiiio
iisiisiiiio
iisiisiiiiio
iisiisiiiiiio
iisiisiiiiiiio
iisiiisdddddo
iisiiisddddo
iisiiisdddo
iisiiisddo
iisiiisdo
iisiiiso
iisiiisio
iisiiisiio
iisiiisiiio
iisiiisiiiio
iisiiisiiiiio
iisiiisiiiiiio
iisiiisiiiiiiio
iiisdsdddddddo
iiisdsddddddo
iiisdsdddddo
iiisdsddddo
iiisdsdddo
iiisdsddo
iiisdsdo
iiisdso
iiisdsio
iiisdsiio
iiisdsiiio
iiisdsiiiio
iiisdsiiiiio
iiisdsiiiiiio
iiisdsiiiiiiio
iiissdddddddddo
iiissddddddddo
iiissdddddddo
iiissddddddo
iiissdddddo
iiissddddo
iiissdddo
iiissddo
iiissdo
iiisso
iiissio
iiissiio
iiissiiio
iiissiiiio
iiissiiiiio
iiissiiiiiio
iiissiiiiiiio
iiissiiiiiiiio
iiissiiiiiiiiio
iiissiiiiiiiiiio
iiisisddddddddo
iiisisdddddddo
iiisisddddddo
iiisisdddddo
iiisisddddo
iiisisdddo
iiisisddo
iiisisdo
iiisiso
iiisisio
iiisisiio
iiisisiiio
iiisisiiiio
iiisisiiiiio
iiisisiiiiiio
iiisisiiiiiiio
iiisisiiiiiiiio
iiisisiiiiiiiiio
iiisisiiiiiiiiiio
iiisisiiiiiiiiiiio
iiisiisdddddddddo
iiisiisddddddddo
iiisiisdddddddo
iiisiisddddddo
iiisiisdddddo
iiisiisddddo
iiisiisdddo
iiisiisddo
iiisiisdo
iiisiiso
iiisiisio
iiisiisiio
iiisiisiiio
iiisiisiiiio
iiisiisiiiiio
iiisiisiiiiiio
iiisiisiiiiiiio
iiisiisiiiiiiiio
iiisiisiiiiiiiiio
iiisiisiiiiiiiiiio
iiisiisiiiiiiiiiiio
iiisiisiiiiiiiiiiiio
iiisiiisddddddddddo
iiisiiisdddddddddo
iiisiiisddddddddo
iiisiiisdddddddo
iiisiiisddddddo
iiisiiisdddddo
iiisiiisddddo
iiisiiisdddo
iiisiiisddo
iiisiiisdo
iiisiiiso
iiisiiisio
iiisiiisiio
iiisiiisiiio
iiisiiisiiiio
iiisiiisiiiiio
iiisiiisiiiiiio
iiisiiisiiiiiiio
iiisiiisiiiiiiiio
iiisiiisiiiiiiiiio
iiisiiisiiiiiiiiiio
iiisiiisiiiiiiiiiiio
iiisiiisiiiiiiiiiiiio
iissdddsddddddddddddo
iissdddsdddddddddddo
iissdddsddddddddddo
iissdddsdddddddddo
iissdddsddddddddo
iissdddsdddddddo
iissdddsddddddo
iissdddsdddddo
iissdddsddddo
iissdddsdddo
iissdddsddo
iissdddsdo
iissdddso
iissdddsio
iissdddsiio
iissdddsiiio
iissdddsiiiio
iissdddsiiiiio
iissdddsiiiiiio
iissdddsiiiiiiio
iissdddsiiiiiiiio
iissdddsiiiiiiiiio
iissdddsiiiiiiiiiio
iissdddsiiiiiiiiiiio
iissdddsiiiiiiiiiiiio
iissddsddddddddddddddo
iissddsdddddddddddddo
iissddsddddddddddddo
iissddsdddddddddddo
iissddsddddddddddo
iissddsdddddddddo
iissddsddddddddo
iissddsdddddddo
iissddsddddddo
iissddsdddddo
iissddsddddo
iissddsdddo
iissddsddo
iissddsdo
iissddso
iissddsio
iissddsiio
iissddsiiio
iissddsiiiio
iissddsiiiiio
iissddsiiiiiio
iissddsiiiiiiio
iissddsiiiiiiiio
iissddsiiiiiiiiio
iissddsiiiiiiiiiio
iissddsiiiiiiiiiiio
iissddsiiiiiiiiiiiio
iissddsiiiiiiiiiiiiio
iissdsdddddddddddddddo
iissdsddddddddddddddo
iissdsdddddddddddddo
iissdsddddddddddddo
iissdsdddddddddddo
iissdsddddddddddo
iissdsdddddddddo
iissdsddddddddo
iissdsdddddddo
iissdsddddddo
iissdsdddddo
iissdsddddo
iissdsdddo
iissdsddo
iissdsdo
iissdso
iissdsio
iissdsiio
iissdsiiio
iissdsiiiio
iissdsiiiiio
iissdsiiiiiio
iissdsiiiiiiio
iissdsiiiiiiiio
iissdsiiiiiiiiio
iissdsiiiiiiiiiio
iissdsiiiiiiiiiiio
iissdsiiiiiiiiiiiio
iissdsiiiiiiiiiiiiio
iissdsiiiiiiiiiiiiiio
iissdsiiiiiiiiiiiiiiio
iissdsiiiiiiiiiiiiiiiio
iissdsiiiiiiiiiiiiiiiiio
iissdsiiiiiiiiiiiiiiiiiio
iissdsiiiiiiiiiiiiiiiiiiio
iissdsiiiiiiiiiiiiiiiiiiiio
iissdsiiiiiiiiiiiiiiiiiiiiio
iissdsiiiiiiiiiiiiiiiiiiiiiio
iissdsiiiiiiiiiiiiiiiiiiiiiiio
iissdsiiiiiiiiiiiiiiiiiiiiiiiio
iissdsiiiiiiiiiiiiiiiiiiiiiiiiio
iissdsiiiiiiiiiiiiiiiiiiiiiiiiiio
iissdsiiiiiiiiiiiiiiiiiiiiiiiiiiio
iissdsiiiiiiiiiiiiiiiiiiiiiiiiiiiio
iissdsiiiiiiiiiiiiiiiiiiiiiiiiiiiiio
iissdsiiiiiiiiiiiiiiiiiiiiiiiiiiiiiio

```
> 5 votes

# Answer
## C, 433 code + 3455 output = 3888

## C++, 430 code + 3455 output = 3885

And now for something completely different.

I used the output from Martin's Mathematica answer (updated on October 23rd as it was wrong for 240+ before). My output is the same 3455 characters. I analyzed patterns in the output and discovered that \[0,255\] can be represented by this sequence:

1. 0-3 `i`s
2. 0-2 `s`s
3. 0-3 `i`s or `d`s
4. 0-1 `s`s
5. 0-14 `i` or 0-16 `d`s
6. 1 `o`

The next step was to carefully construct these five columns (`c` through `g` in the code below). I used negative numbers to indicate `d` instead of `i` in columns `e` and `g`. Then, it turns out that the results work mostly like a counter in the `g` column, since each row `u` usually removes one `d` or adds one `i` relative to the previous row (`v`). There are 15 exceptions, which are stored in `x` (the indexes) and `b` (the five columns, packed into an integer which only requires 14 bits to store the maximum `10832`).

For example, the first "exception" is the very first row, where we want zero characters apart from the terminating `o`. So `x[0]` is `0`, and `b[0]` is `544`, which when unpacked is ("little endian" style, since `g` is the counting column) `{ 32, 0, 4, 0, 0 }`. We always subtract 32 from `g` and 4 from `e` to make the unsigned bit-fields work (i.e. those two columns represent negative numbers conceptually when `d` is required instead of `i`, but in the implementation the values are offset to avoid actual negative numbers).

Here's a table showing how the first ten numbers work (blanks are zeros):

```
n   text    c   d   e   f   g
0   o
1   io                      1
2   iio                     2
3   iiio                    3
4   iiso    2   1
5   iisio   2   1           1
6   iisiio  2   1           2
7   iisiiio 2   1           3
8   iiisdo  3   1          -1
9   iiiso   3   1

```

You can see that `g` mostly just increments by one for each new row, but some rows (0, 4, 8, ..., which I briefly hoped to find in OEIS) "reset" the sequence, meaning `g` takes on some new value and at least one other column is modified as well.

The code character count excludes whitespace except the mandatory newline before each `#` and space after `unsigned` and `int`. You can save 3 characters by compiling as C++ instead of C, replacing `<stdio.h>` with `<cstdio>`, and `*(int*)&u` with `(int&)u`.

```
#include <stdio.h>

struct { unsigned g:6, f:1, e:3, d:2, c:2; } u;

int
  x[] = { 0,4,8,13,22,32,44,57,72,92,112,134,157,182,210,256 },
  b[] = { 544,9760,13855,9821,9949,10076,10203,13785,13911,14040,14167,14294,10452,10578,10705,10832 };

int main()
{
  int n,i=0,q=0;
  scanf("%d", &n);
  while(i++ <= n) {
    ++u.g;
    if (i > x[q])
      *(int*)&u = b[q++];
  }

#define m(p, q) while (p) putchar(#q[0]);

  m(u.c--, i)
  m(u.d--, s)
  m(u.e++ < 4, d)
  m(--u.e > 4, i)
  m(u.f--, s)
  m(u.g++ < 32, d)
  m(--u.g > 32, i)
  puts("o");
}

```

A fun fact about this code: an earlier version used an array of 256 unions instead of just `u` and `v`. That version caused GCC 4.7.2 to generate an internal compiler error! GCC 4.9 fixed it, however, and the above code works with either version.
> 5 votes

# Answer
# Picat 516 + 2060 = 2576

It is somewhat modified version of Sergey Dymchenko program. This version outputs more compact deadfish programs.

```
import planner.
final((N,N))=>true.
action((N,A),B,M,C)?=>B=(N,A+1),M=i,C=1.
action((N,A),B,M,C)?=>A!=16,A<N,B=(N,A*A),M=s,C=1.
action((N,A),B,M,C)?=>A>0,B=(N,A-1),M=d,C=1.
r([X,Y|Z],A)?=>(r([Y|Z],R),A=[X|R];X!=['0'],r([(X++Y)|Z],R),A=R).
r([],A)=>A=[]. r([N],A)=>A=[N]. lf(X)=[X].
table(+,-,min) fs(N,M,L)=>r(map(lf,N.to_string()),X),Np:=0,Pp:=[],
foreach(Y in X)N:=Y.to_integer(),best_plan((N,Np),P),Np:=N,Pp:=Pp++P++[o]
end,L=Pp.length(),M=Pp. main=>foreach(X in 1..255)fs(X,P,L),printf("%s",P) end.

```

As far as I understood "lengths of outputs" sentence, it means that I should sum output without new-line chars.

Use:

```
picat filename.pi

```

1-255 Codes:

```
picat filename.pi | wc -c

2060

```

## Performance:

```
cat /proc/cpuinfo # 4 cores with HT = virtual 8 cores

processor   : 0
vendor_id   : GenuineIntel
cpu family  : 6
model       : 42
model name  : Intel(R) Core(TM) i7-2600K CPU @ 3.40GHz
stepping    : 7
physical id : 0
siblings    : 8
core id     : 1
cpu cores   : 4
apicid      : 2
cpu MHz     : 1600.000
cache size  : 8192 KB
...
bogomips    : 6819.33
...

```

Version of program to measure time:

```
import planner.
import sys.
final((N,N))=>true.
action((N,A),B,M,C)?=>B=(N,A+1), M=i, C=1.
action((N,A),B,M,C)?=>A!=16, A<N, B=(N,A*A), M=s, C=1.
action((N,A),B,M,C)?=>A>0, B=(N,A-1), M=d, C=1.
r([X,Y|Z],A)?=>(r([Y|Z],R),A=[X|R];r([(X++Y)|Z],R),A=R).
r([],A)=>A=[]. r([N],A)=>A=[N]. lf(X)=[X].
table(+,-,min) fs(N,M,L)=>r(map(lf,N.to_string()),X),Np:=0,Pp:=[],
foreach(Y in X)N:=Y.to_integer(),best_plan((N,Np),P),Np:=N,Pp:=Pp++P++[o]
end,L=Pp.length(),M=Pp. go=>foreach(X in 1..255)fs(X,P,L),printf("%d %s",X,P),nl end.
main=>time2(go).

```

Result:

```
picat filename.pi

...

251 iiosioddddo
252 iiosiodddo
253 iiosioddo
254 iiosiodo
255 iiosioo

CPU time 2.2 seconds. Backtracks: 0

```

Full output:

```
1 io
2 iio
3 iiio
4 iiso
5 iisio
6 iisiio
7 iiisddo
8 iiisdo
9 iiiso
10 iodo
11 ioo
12 ioio
13 ioiio
14 ioiso
15 ioisio
16 iisso
17 iissio
18 ioiisdo
19 ioiiso
20 iioddo
21 iiodo
22 iioo
23 iioio
24 iioso
25 iiosio
26 iiosiio
27 iioisddo
28 iioisdo
29 iioiso
30 iiiodddo
31 iiioddo
32 iiiodo
33 iiioo
34 iiioio
35 iiioiio
36 iisiiso
37 iiiosddo
38 iiiosdo
39 iiioso
40 iisoddddo
41 iisodddo
42 iisoddo
43 iisodo
44 iisoo
45 iisoio
46 iisoiio
47 iisoiiio
48 iisodsdo
49 iisodso
50 iiisddsio
51 iisioddddo
52 iisiodddo
53 iisioddo
54 iisiodo
55 iisioo
56 iisioio
57 iisioiio
58 iisioiiio
59 iisioddso
60 iiisdsddddo
61 iiisdsdddo
62 iiisdsddo
63 iiisdsdo
64 iiisdso
65 iisiiodo
66 iisiioo
67 iisiioio
68 iisiioiio
69 iisiioiiio
70 iiisdsiiiiiio
71 iiisddoddddddo
72 iiisddodddddo
73 iiisddoddddo
74 iiisddodddo
75 iiisddoddo
76 iiisddodo
77 iiisddoo
78 iiisddoio
79 iiissddo
80 iiissdo
81 iiisso
82 iiissio
83 iiissiio
84 iiissiiio
85 iiisdodddo
86 iiisdoddo
87 iiisdodo
88 iiisdoo
89 iiisdoio
90 iiisodddddddddo
91 iiisoddddddddo
92 iiisodddddddo
93 iiisoddddddo
94 iiisodddddo
95 iiisoddddo
96 iiisodddo
97 iiisoddo
98 iiisodo
99 iiisoo
100 iodoo
101 iodoio
102 iodoiio
103 iodoiiio
104 iodoiiso
105 iodoiisio
106 iodoiisiio
107 iiisiodddo
108 iiisioddo
109 iiisiodo
110 ioodo
111 iooo
112 iooio
113 iooiio
114 iooiso
115 iooisio
116 ioisso
117 ioissio
118 iooiisdo
119 iooiiso
120 ioioddo
121 ioiodo
122 ioioo
123 ioioio
124 ioioso
125 ioiosio
126 ioiosiio
127 ioioisddo
128 ioioisdo
129 ioioiso
130 ioiiodddo
131 ioiioddo
132 ioiiodo
133 ioiioo
134 ioiioio
135 ioiioiio
136 ioisiiso
137 ioiiosddo
138 ioiiosdo
139 ioiioso
140 ioisoddddo
141 ioisodddo
142 ioisoddo
143 ioisodo
144 ioisoo
145 ioisoio
146 ioisoiio
147 ioisoiiio
148 ioisodsdo
149 ioisodso
150 ioiisddsio
151 ioisioddddo
152 ioisiodddo
153 ioisioddo
154 ioisiodo
155 ioisioo
156 ioisioio
157 ioisioiio
158 ioisioiiio
159 ioisioddso
160 ioiisdsddddo
161 ioiisdsdddo
162 ioiisdsddo
163 ioiisdsdo
164 ioiisdso
165 ioisiiodo
166 ioisiioo
167 ioisiioio
168 ioisiioiio
169 iissdddso
170 iissdddsio
171 iissdddsiio
172 iissdddsiiio
173 ioiisddoddddo
174 ioiisddodddo
175 ioiisddoddo
176 ioiisddodo
177 ioiisddoo
178 ioiisddoio
179 ioiissddo
180 ioiissdo
181 ioiisso
182 ioiissio
183 ioiissiio
184 ioiissiiio
185 ioiisdodddo
186 ioiisdoddo
187 ioiisdodo
188 ioiisdoo
189 ioiisdoio
190 iissddsddddddo
191 iissddsdddddo
192 iissddsddddo
193 iissddsdddo
194 iissddsddo
195 iissddsdo
196 iissddso
197 ioiisoddo
198 ioiisodo
199 ioiisoo
200 iioddoo
201 iioddoio
202 iioddoiio
203 iioddoiiio
204 iioddoiiso
205 iioddoiisio
206 iioddoiisiio
207 iioddoiiisddo
208 iioddoiiisdo
209 iioddoiiiso
210 iiododo
211 iiodoo
212 iiodoio
213 iiodoiio
214 iiodoiso
215 iiossdo
216 iiosso
217 iiossio
218 iiossiio
219 iiodoiiso
220 iiooddo
221 iioodo
222 iiooo
223 iiooio
224 iiooso
225 iioosio
226 iioosiio
227 iiooisddo
228 iiooisdo
229 iiooiso
230 iioiodddo
231 iioioddo
232 iioiodo
233 iioioo
234 iioioio
235 iioioiio
236 iiosiiso
237 iioiosddo
238 iioiosdo
239 iioioso
240 iiosoddddo
241 iiosodddo
242 iiosoddo
243 iiosodo
244 iiosoo
245 iiosoio
246 iiosoiio
247 iiosoiiio
248 iiosodsdo
249 iiosodso
250 iioisddsio
251 iiosioddddo
252 iiosiodddo
253 iiosioddo
254 iiosiodo
255 iiosioo

```
> 4 votes

# Answer
# Prolog, 621 + 2036 - 100 = 2557

Here is a backward search, memoization solution in Prolog:

```
x(N,R):-between(1,inf,D),y(N,O,M),z(M,O,D,L),!,reverse([o|L],R).
:-dynamic t/4.
z(N,O,D,L):-t(N,O,D,L),!,L\==s.
z(N,O,D,L):-u(N,O,D,L),!,assertz(t(N,O,D,L)).
z(N,O,D,_):-assertz(t(N,O,D,s)),fail.
u(N,O,0,[]):-!,N=0,O=0.
u(N,O,D,[C|L]):-E is D-1,member(C,[s,o,i,d]),v(C,N,O,M,P),z(M,P,E,L),!.
v(s,N,O,M,O):-(N=0->M=16;H is sqrt(N),M is truncate(H),H is float(M)).
v(o,N,O,N,P):-y(O,P,R),R=N,!.
v(i,N,O,M,O):-(N=0->M=255;M is N-1).
v(d,N,O,M,O):-M is N+1.
y(N,0,N):-N<10,!.
y(N,P,R):-divmod(N,10,D,M),(P=D,R=M;y(D,P,Q),Q\==0,R is Q*10+M).
w:-between(1,255,N),x(N,L),atom_chars(A,L),write(A),nl,fail.
w.
:-initialization(w).

```

Dry run takes only 0.055 seconds! Numbered output lines:

```
1 io
2 iio
3 iiio
4 iiso
5 iisio
6 iisiio
7 iisiiio
8 iiisdo
9 iiiso
10 iodo
11 ioo
12 ioio
13 ioiio
14 ioiso
15 ioisio
16 iisso
17 iissio
18 ioiisdo
19 ioiiso
20 iioddo
21 iiodo
22 iioo
23 iioio
24 iioso
25 iiosio
26 iiosiio
27 iiosiiio
28 iioisdo
29 iioiso
30 iiioisso
31 iiioddo
32 iiiodo
33 iiioo
34 iiioio
35 iiioiio
36 iisiiso
37 iiiosddo
38 iiiosdo
39 iiioso
40 iisosso
41 iisossio
42 iisoddo
43 iisodo
44 iisoo
45 iisoio
46 iisoiio
47 iisoiiio
48 iisodsdo
49 iisodso
50 iisiodsso
51 iisiodssio
52 iisiodddo
53 iisioddo
54 iisiodo
55 iisioo
56 iisioio
57 iisioiio
58 iisioiiio
59 iisioddso
60 iisiioddsso
61 iiisdsdddo
62 iiisdsddo
63 iiisdsdo
64 iiisdso
65 iisiiodo
66 iisiioo
67 iisiioio
68 iisiioiio
69 iisiioiiio
70 iisiiiodddsso
71 iisiiiodddssio
72 iisiiiodddddo
73 iisiiioddddo
74 iisiiiodddo
75 iisiiioddo
76 iisiiiodo
77 iisiiioo
78 iisiiioio
79 iiissddo
80 iiissdo
81 iiisso
82 iiissio
83 iiissiio
84 iiissiiio
85 iiisdodddo
86 iiisdoddo
87 iiisdodo
88 iiisdoo
89 iiisdoio
90 iiisodddddsso
91 iiisodddddssio
92 iiisodddddddo
93 iiisoddddddo
94 iiisodddddo
95 iiisoddddo
96 iiisodddo
97 iiisoddo
98 iiisodo
99 iiisoo
100 iodoo
101 iodoio
102 iodoiio
103 iodoiiio
104 iodoiiso
105 iodoiisio
106 iodoiisiio
107 iiisiodddo
108 iiisioddo
109 iiisiodo
110 ioodo
111 iooo
112 iooio
113 iooiio
114 iooiso
115 iooisio
116 ioisso
117 ioissio
118 iooiisdo
119 iooiiso
120 ioioddo
121 ioiodo
122 ioioo
123 ioioio
124 ioioso
125 ioiosio
126 ioiosiio
127 ioiosiiio
128 ioioisdo
129 ioioiso
130 ioiioisso
131 ioiioddo
132 ioiiodo
133 ioiioo
134 ioiioio
135 ioiioiio
136 ioisiiso
137 ioiiosddo
138 ioiiosdo
139 ioiioso
140 ioisosso
141 ioisossio
142 ioisoddo
143 ioisodo
144 ioisoo
145 ioisoio
146 ioisoiio
147 ioisoiiio
148 ioisodsdo
149 ioisodso
150 iissdoiso
151 iissdoisio
152 ioisiodddo
153 ioisioddo
154 ioisiodo
155 ioisioo
156 ioisioio
157 ioisioiio
158 ioisioiiio
159 ioisioddso
160 iissoso
161 iissosio
162 iissosiio
163 ioiisdsdo
164 ioiisdso
165 ioisiiodo
166 ioisiioo
167 ioisiioio
168 ioisiioiio
169 iissdddso
170 iissiodso
171 iissiodsio
172 iissiodsiio
173 iissiodsiiio
174 iissiodsiiso
175 ioisiiioddo
176 ioisiiiodo
177 ioisiiioo
178 ioisiiioio
179 ioiissddo
180 ioiissdo
181 ioiisso
182 ioiissio
183 ioiissiio
184 ioiissiiio
185 ioiisdodddo
186 ioiisdoddo
187 ioiisdodo
188 ioiisdoo
189 ioiisdoio
190 iissiiiodddso
191 iissddsdddddo
192 iissddsddddo
193 iissddsdddo
194 iissddsddo
195 iissddsdo
196 iissddso
197 ioiisoddo
198 ioiisodo
199 ioiisoo
200 iioddoo
201 iioddoio
202 iioddoiio
203 iioddoiiio
204 iioddoiiso
205 iioddoiisio
206 iioddoiisiio
207 iioddoiisiiio
208 iioddoiiisdo
209 iioddoiiiso
210 iiododo
211 iiodoo
212 iiodoio
213 iiodoiio
214 iiodoiso
215 iiossdo
216 iiosso
217 iiossio
218 iiossiio
219 iiodoiiso
220 iiooddo
221 iioodo
222 iiooo
223 iiooio
224 iiooso
225 iioosio
226 iioosiio
227 iioosiiio
228 iiooisdo
229 iiooiso
230 iioioisso
231 iioioddo
232 iioiodo
233 iioioo
234 iioioio
235 iioioiio
236 iiosiiso
237 iioiosddo
238 iioiosdo
239 iioioso
240 iiososso
241 iiosossio
242 iiosoddo
243 iiosodo
244 iiosoo
245 iiosoio
246 iiosoiio
247 iiosoiiio
248 iiosodsdo
249 iiosodso
250 iiosiodsso
251 iiosiodssio
252 iiosiodddo
253 iiosioddo
254 iiosiodo
255 iiosioo

```
> 3 votes

# Answer
# JavaScript (E6) 141+3455=3596

Recursive function looking for the closest square root, but avoiding 16 as 16\*16=256 will be changed to 0. Many other answer don't get this point.

```
F=(t,s='o',o='i')=>
  t>3?(
    q=Math.sqrt(t)|0,
    r=q+1,
    q-16?r-16||++r:--q,
    d=t-q*q,e=r*r-t,
    e<=d&&(o='d',d=e,++q),
    F(q,'s'+o.repeat(d)+s)
  ):o.repeat(t)+s

```

**Test** In FireFox/FireBug console

```
for(l=0,i=1;i<256;++i)o=F(i),l+=o.length,console.log(i,o),l

```

*Output*

```
1 io
2 iio
3 iiio
4 iiso
5 iisio
6 iisiio
7 iiisddo
8 iiisdo
9 iiiso
10 iiisio
11 iiisiio
12 iiisiiio
13 iissdddo
14 iissddo
15 iissdo
16 iisso
17 iissio
18 iissiio
19 iissiiio
20 iissiiiio
21 iisisddddo
22 iisisdddo
23 iisisddo
24 iisisdo
25 iisiso
26 iisisio
27 iisisiio
28 iisisiiio
29 iisisiiiio
30 iisisiiiiio
31 iisiisdddddo
32 iisiisddddo
33 iisiisdddo
34 iisiisddo
35 iisiisdo
36 iisiiso
37 iisiisio
38 iisiisiio
39 iisiisiiio
40 iisiisiiiio
41 iisiisiiiiio
42 iisiisiiiiiio
43 iiisddsddddddo
44 iiisddsdddddo
45 iiisddsddddo
46 iiisddsdddo
47 iiisddsddo
48 iiisddsdo
49 iiisddso
50 iiisddsio
51 iiisddsiio
52 iiisddsiiio
53 iiisddsiiiio
54 iiisddsiiiiio
55 iiisddsiiiiiio
56 iiisddsiiiiiiio
57 iiisdsdddddddo
58 iiisdsddddddo
59 iiisdsdddddo
60 iiisdsddddo
61 iiisdsdddo
62 iiisdsddo
63 iiisdsdo
64 iiisdso
65 iiisdsio
66 iiisdsiio
67 iiisdsiiio
68 iiisdsiiiio
69 iiisdsiiiiio
70 iiisdsiiiiiio
71 iiisdsiiiiiiio
72 iiisdsiiiiiiiio
73 iiissddddddddo
74 iiissdddddddo
75 iiissddddddo
76 iiissdddddo
77 iiissddddo
78 iiissdddo
79 iiissddo
80 iiissdo
81 iiisso
82 iiissio
83 iiissiio
84 iiissiiio
85 iiissiiiio
86 iiissiiiiio
87 iiissiiiiiio
88 iiissiiiiiiio
89 iiissiiiiiiiio
90 iiissiiiiiiiiio
91 iiisisdddddddddo
92 iiisisddddddddo
93 iiisisdddddddo
94 iiisisddddddo
95 iiisisdddddo
96 iiisisddddo
97 iiisisdddo
98 iiisisddo
99 iiisisdo
100 iiisiso
101 iiisisio
102 iiisisiio
103 iiisisiiio
104 iiisisiiiio
105 iiisisiiiiio
106 iiisisiiiiiio
107 iiisisiiiiiiio
108 iiisisiiiiiiiio
109 iiisisiiiiiiiiio
110 iiisisiiiiiiiiiio
111 iiisiisddddddddddo
112 iiisiisdddddddddo
113 iiisiisddddddddo
114 iiisiisdddddddo
115 iiisiisddddddo
116 iiisiisdddddo
117 iiisiisddddo
118 iiisiisdddo
119 iiisiisddo
120 iiisiisdo
121 iiisiiso
122 iiisiisio
123 iiisiisiio
124 iiisiisiiio
125 iiisiisiiiio
126 iiisiisiiiiio
127 iiisiisiiiiiio
128 iiisiisiiiiiiio
129 iiisiisiiiiiiiio
130 iiisiisiiiiiiiiio
131 iiisiisiiiiiiiiiio
132 iiisiisiiiiiiiiiiio
133 iiisiiisdddddddddddo
134 iiisiiisddddddddddo
135 iiisiiisdddddddddo
136 iiisiiisddddddddo
137 iiisiiisdddddddo
138 iiisiiisddddddo
139 iiisiiisdddddo
140 iiisiiisddddo
141 iiisiiisdddo
142 iiisiiisddo
143 iiisiiisdo
144 iiisiiiso
145 iiisiiisio
146 iiisiiisiio
147 iiisiiisiiio
148 iiisiiisiiiio
149 iiisiiisiiiiio
150 iiisiiisiiiiiio
151 iiisiiisiiiiiiio
152 iiisiiisiiiiiiiio
153 iiisiiisiiiiiiiiio
154 iiisiiisiiiiiiiiiio
155 iiisiiisiiiiiiiiiiio
156 iiisiiisiiiiiiiiiiiio
157 iissdddsddddddddddddo
158 iissdddsdddddddddddo
159 iissdddsddddddddddo
160 iissdddsdddddddddo
161 iissdddsddddddddo
162 iissdddsdddddddo
163 iissdddsddddddo
164 iissdddsdddddo
165 iissdddsddddo
166 iissdddsdddo
167 iissdddsddo
168 iissdddsdo
169 iissdddso
170 iissdddsio
171 iissdddsiio
172 iissdddsiiio
173 iissdddsiiiio
174 iissdddsiiiiio
175 iissdddsiiiiiio
176 iissdddsiiiiiiio
177 iissdddsiiiiiiiio
178 iissdddsiiiiiiiiio
179 iissdddsiiiiiiiiiio
180 iissdddsiiiiiiiiiiio
181 iissdddsiiiiiiiiiiiio
182 iissdddsiiiiiiiiiiiiio
183 iissddsdddddddddddddo
184 iissddsddddddddddddo
185 iissddsdddddddddddo
186 iissddsddddddddddo
187 iissddsdddddddddo
188 iissddsddddddddo
189 iissddsdddddddo
190 iissddsddddddo
191 iissddsdddddo
192 iissddsddddo
193 iissddsdddo
194 iissddsddo
195 iissddsdo
196 iissddso
197 iissddsio
198 iissddsiio
199 iissddsiiio
200 iissddsiiiio
201 iissddsiiiiio
202 iissddsiiiiiio
203 iissddsiiiiiiio
204 iissddsiiiiiiiio
205 iissddsiiiiiiiiio
206 iissddsiiiiiiiiiio
207 iissddsiiiiiiiiiiio
208 iissddsiiiiiiiiiiiio
209 iissddsiiiiiiiiiiiiio
210 iissddsiiiiiiiiiiiiiio
211 iissdsddddddddddddddo
212 iissdsdddddddddddddo
213 iissdsddddddddddddo
214 iissdsdddddddddddo
215 iissdsddddddddddo
216 iissdsdddddddddo
217 iissdsddddddddo
218 iissdsdddddddo
219 iissdsddddddo
220 iissdsdddddo
221 iissdsddddo
222 iissdsdddo
223 iissdsddo
224 iissdsdo
225 iissdso
226 iissdsio
227 iissdsiio
228 iissdsiiio
229 iissdsiiiio
230 iissdsiiiiio
231 iissdsiiiiiio
232 iissdsiiiiiiio
233 iissdsiiiiiiiio
234 iissdsiiiiiiiiio
235 iissdsiiiiiiiiiio
236 iissdsiiiiiiiiiiio
237 iissdsiiiiiiiiiiiio
238 iissdsiiiiiiiiiiiiio
239 iissdsiiiiiiiiiiiiiio
240 iissdsiiiiiiiiiiiiiiio
241 iissdsiiiiiiiiiiiiiiiio
242 iissdsiiiiiiiiiiiiiiiiio
243 iissdsiiiiiiiiiiiiiiiiiio
244 iissdsiiiiiiiiiiiiiiiiiiio
245 iissdsiiiiiiiiiiiiiiiiiiiio
246 iissdsiiiiiiiiiiiiiiiiiiiiio
247 iissdsiiiiiiiiiiiiiiiiiiiiiio
248 iissdsiiiiiiiiiiiiiiiiiiiiiiio
249 iissdsiiiiiiiiiiiiiiiiiiiiiiiio
250 iissdsiiiiiiiiiiiiiiiiiiiiiiiiio
251 iissdsiiiiiiiiiiiiiiiiiiiiiiiiiio
252 iissdsiiiiiiiiiiiiiiiiiiiiiiiiiiio
253 iissdsiiiiiiiiiiiiiiiiiiiiiiiiiiiio
254 iissdsiiiiiiiiiiiiiiiiiiiiiiiiiiiiio
255 iissdsiiiiiiiiiiiiiiiiiiiiiiiiiiiiiio
3455

```
> 2 votes

# Answer
# Picat, 242 code + 3455 output = 3697

See http://picat-lang.org/ for info about Picat.

```
import planner. final((N,N))=>true. action((N,A),B,M,C)?=>B=(N,A+1),M=i,C=1. action((N,A),B,M,C)?=>A!=16,A<N,B=(N,A*A),M=s,C=1. action((N,A),B,M,C)?=>A>0,B=(N,A-1),M=d,C=1. main([X])=>N=X.to_integer(),best_plan((N,0),P),printf("%w\n",P++[o]).

```

Less golf:

```
import planner.
final((N,N))=>true.
action((N,A),B,M,C)?=>B=(N,A+1),M=i,C=1.
action((N,A),B,M,C)?=>A!=16,A<N,B=(N,A*A),M=s,C=1.
action((N,A),B,M,C)?=>A>0,B=(N,A-1),M=d,C=1.
main([X])=>N=X.to_integer(),best_plan((N,0),P),printf("%w\n",P++[o]).

```
> 2 votes

# Answer
# Python 3, 3455 + 182 bytes = 3637

```
from heapq import*
def f(x):
	q=[(0,0,"")]
	while 1:
		l,s,c=heappop(q)
		if s==x:return c+"o"
		for n,i in[(s+1,"i"),(s-1,"d"),(s*s,"s")]:
			if(n+1)*(n-256):heappush(q,(l+1,n,c+i))

```

Try it online!

This finds the optimal way to generate the number itself. It is not optimal if you allow partial outputting.
> 2 votes

# Answer
**APL: 80 + 3456 = 3536**

```
⌽'o',{⍵<4:⍵⍴'i'⋄(b/'ids'),∇(-⊃b)+b[2]+⍵*÷1+3⊃b←(⍵>240)⌽⊃(>,<,=)/|⍵-2*⍨(⌈,⌊)⍵*.5}

```

**Explanation:** (corrected after edc65's note, thanks)

⍵\<4:⍵⍴'i' If argument is less than 3, replicate "i" that many times

(⌈,⌊)⍵\*.5 ⍵ is the argument, take square root and take the ceiling and the floor

|⍵-2\*⍨ elevate those ceiling and floor to power 2, remove argument, and make positive

b←⊃(\>,\<,=)/ get a boolean vector with a\>b, a

(⍵\>240)⌽ To avoid going to 256, do "i" for numbers over 240, instead of ^2

b/'ids' use that boolean to take either i, d or s and append it to the solution with ,

,∇(-⊃b)+b\[2\]+⍵\*÷1+3⊃b Recursively call the function with argument -b +b\[2\] elevated to the power (inverse of b\[3\]+1)

*Can count output with:*

```
 +/⊃,/⍴¨(⌽'o',{⍵<4:⍵⍴'i'⋄(b/'ids'),∇(-⊃b)+b[2]+⍵*÷1+3⊃b←(⍵>240)⌽⊃(>,<,=)/|⍵-2*⍨(⌈,⌊)⍵*.5})¨¯1+⍳256

```

¨ applies the function to each number 0-255

+/⊃,/⍴¨ counts total number of elements

Again, you can try all of the above on TryApl.org

**BTW:** It's 3456 and not 3455 because I'm considering 0 too, as I think the problem was asking. If It's 1-255 then the score is 80+3455 = 3535
> 1 votes

# Answer
# Python 3 – 4286 + 168 = 4454

Not a too serious one, but extremely simple. Just finds the best one of adding to 0, a square, a 4<sup>th</sup> power ~~and an 8<sup>th</sup> power~~.

**EDIT:** Golfed 75 bytes, the 8<sup>th</sup> power did nothing

**EDIT 2:** Removed some bytes in order to correctly implement `d`. Score increased, though.

```
i=int(input())
s=round(i**.5)
q=round(s**.5)
o=round(q**.5)
a,b,c,d=i-256if i>127else i,i-s*s,i-q**4,i-o**8
print(sorted([(a*'i'if a>0else'd'*-a)+'o',s*'i'+'s'+(b*'i'if b>0else'd'*-b)+'o',q*'i'+'ss'+(c*'i'if c>0else'd'*-c)+'o',o*'i'+'sss'+(d*'i'if d>0else'd'*-d)+'o'],key=len)[0])

```

# Python 3 – 2594 + 201 = 2795

This one uses a kind of depth-first search to find the shortest program. I added some (unnecessary?) optimizations to it, so I could get the result; this way it doesn't have to run that many paths. Might try to remove some of them. Doesn't beat the JS one as it uses smart tricks like multiple `o`'s.

**EDIT:** Golfed off 93 bytes, I apparently had a crapton of useless code left there by development. Also removed everything I found unnecessary so far. Here I come, JS.

**EDIT 2:** Golfed off another 8 bytes. That `return` was unnecessary.

**EDIT 3:** Golfed an additional 5 bytes. Now that we got rid of that one wo could just put an `elif` instead of the other `return`.

**EDIT 4:** Corrected the functionality of `d`. Size increased by 1 byte, score by some bytes.

```
def f(i,s,h):
 global x,p
 if h==a:p+=[i]
 elif s<x[h]:x[h]=s;f(i+'s',s+1,h*h%256);f(i+'i',s+1,(h+1)%256);f(i+'d',s+1,max(h-1,0))
a,p=int(input()),[];x=[a]*256;f('',0,0);print(sorted(p,key=len)[0]+'o')

```
> 1 votes

# Answer
# JavaScript (Node.js), 86 bytes, optimal output by brute-forcing

```
f=(n,a='',b=a,c,...s)=>n^b?f(n,...s,a+'i',b,-~c,a+'d',b,~-c,a+'s',b,c*c,a+'o',b+c,c):a

```

Try it online!
> 1 votes

# Answer
# Python 2712 = 2608 + 104

Code:

```
v=lambda i:reduce(lambda x,y:(int(y),x[1]+['d','i'][int(y)>x[0]]*abs(int(y)-x[0])+"o"),str(i),(0,""))[1]

```

Use:

```
v(20)  -> 'iioddo'
v(250) -> 'iioiiiodddddo'

```

0-255 Code:

```
len(reduce(lambda x,y:x+v(y),range(256),"")) -> 2608

```
> 0 votes

# Answer
## CJam, ~~2436 2392 2296~~ 2173 (74 characters + 2099)

```
"叴噯撘桜᪍뾀戠냞霳㈨嵃畯㓱눿裸㺯蛙㡟激떍䑜㦘啟䂳嗳溘桠㼼ᗎ윆꘶英贈袄瞦㺣樅휏╴෼瓵ꃴ︥㷮싎ꗞ冺憳딕礕䀘䬴卺㽅鬞庘䲵"2G#b129b:c~

```

Which translates to:

```
r_(sa\a+{},\1/{{i_L\[_Tm3>{{__mqi:NN*-N)_*@-_@e<_@=_N+:N;'d'i?*+'s+N_Z3e>>}g}*T-_0<'d'i?\z*\2$3<'s*-W%'o]s\:Z:T;}%s0:T;3:Z;}:A~\A]_:,_$0=#=

```

Tries to optimize the Deadfish code length by choosing the shortest path to reach each digit of the number.

Thanks Martin for the Unicode translation

Here is the complete list of code

```
1:io
2:iio
3:iiio
4:iiso
5:iisio
6:iisiio
7:iiisddo
8:iiisdo
9:iiiso
10:iodo
11:ioo
12:ioio
13:ioiio
14:ioiiio
15:ioisio
16:ioisiio
17:ioiisddo
18:ioiisdo
19:ioiiso
20:iioddo
21:iiodo
22:iioo
23:iioio
24:iioiio
25:iioiiio
26:iiosiio
27:iioisddo
28:iioisdo
29:iioiso
30:iiiodddo
31:iiioddo
32:iiiodo
33:iiioo
34:iiioio
35:iiioiio
36:iiioiiio
37:iiiosddo
38:iiiosdo
39:iiioso
40:iisoddddo
41:iisodddo
42:iisoddo
43:iisodo
44:iisoo
45:iisoio
46:iisoiio
47:iisoiiio
48:iisodsdo
49:iisodso
50:iisiodddddo
51:iisioddddo
52:iisiodddo
53:iisioddo
54:iisiodo
55:iisioo
56:iisioio
57:iisioiio
58:iisioiiio
59:iisioddso
60:iisiioddddddo
61:iisiiodddddo
62:iisiioddddo
63:iisiiodddo
64:iisiioddo
65:iisiiodo
66:iisiioo
67:iisiioio
68:iisiioiio
69:iisiioiiio
70:iiisddodddddddo
71:iiisddoddddddo
72:iiisddodddddo
73:iiisddoddddo
74:iiisddodddo
75:iiisddoddo
76:iiisddodo
77:iiisddoo
78:iiisddoio
79:iiisddoiio
80:iiisdoddddddddo
81:iiisdodddddddo
82:iiisdoddddddo
83:iiisdodddddo
84:iiisdoddddo
85:iiisdodddo
86:iiisdoddo
87:iiisdodo
88:iiisdoo
89:iiisdoio
90:iiisodddddddddo
91:iiisoddddddddo
92:iiisodddddddo
93:iiisoddddddo
94:iiisodddddo
95:iiisoddddo
96:iiisodddo
97:iiisoddo
98:iiisodo
99:iiisoo
100:iodo
101:ioo
102:ioio
103:ioiio
104:ioiiio
105:ioisio
106:ioisiio
107:ioiisddo
108:ioiisdo
109:ioiiso
110:ioodo
111:iooo
112:iooio
113:iooiio
114:iooiiio
115:iooisio
116:ioisso
117:ioissio
118:iooiisdo
119:iooiiso
120:ioioddo
121:ioiodo
122:ioioo
123:ioioio
124:ioioiio
125:ioisiso
126:ioiosiio
127:ioioisddo
128:ioioisdo
129:ioioiso
130:ioiiodddo
131:ioiioddo
132:ioiiodo
133:ioiioo
134:ioiioio
135:ioiioiio
136:ioisiiso
137:ioiiosddo
138:ioiiosdo
139:ioiioso
140:ioiiioddddo
141:ioiiiodddo
142:ioiiioddo
143:ioiiiodo
144:ioiiioo
145:ioiiioio
146:ioiiioiio
147:ioiiioiiio
148:ioiiiodsdo
149:ioiiiodso
150:ioiisddsio
151:ioisioddddo
152:ioisiodddo
153:ioisioddo
154:ioisiodo
155:ioisioo
156:ioisioio
157:ioisioiio
158:ioisioiiio
159:ioisioddso
160:ioiisdsddddo
161:ioiisdsdddo
162:ioiisdsddo
163:ioiisdsdo
164:ioiisdso
165:ioisiiodo
166:ioisiioo
167:ioisiioio
168:ioisiioiio
169:ioisiioiiio
170:ioiisdsiiiiiio
171:ioiisddoddddddo
172:ioiisddodddddo
173:ioiisddoddddo
174:ioiisddodddo
175:ioiisddoddo
176:ioiisddodo
177:ioiisddoo
178:ioiisddoio
179:ioiissddo
180:ioiissdo
181:ioiisso
182:ioiissio
183:ioiissiio
184:ioiissiiio
185:ioiisdodddo
186:ioiisdoddo
187:ioiisdodo
188:ioiisdoo
189:ioiisdoio
190:ioiisodddddddddo
191:ioiisoddddddddo
192:ioiisodddddddo
193:ioiisoddddddo
194:ioiisodddddo
195:ioiisoddddo
196:ioiisodddo
197:ioiisoddo
198:ioiisodo
199:ioiisoo
200:iioddo
201:iiodo
202:iioo
203:iioio
204:iioiio
205:iioiiio
206:iiosiio
207:iioisddo
208:iioisdo
209:iioiso
210:iiododo
211:iiodoo
212:iiodoio
213:iiodoiio
214:iiossddo
215:iiossdo
216:iiosso
217:iiossio
218:iiossiio
219:iiodoiiso
220:iiooddo
221:iioodo
222:iiooo
223:iiooio
224:iiooiio
225:iiosiso
226:iioosiio
227:iiooisddo
228:iiooisdo
229:iiooiso
230:iioiodddo
231:iioioddo
232:iioiodo
233:iioioo
234:iioioio
235:iioioiio
236:iiosiiso
237:iioiosddo
238:iioiosdo
239:iioioso
240:iioiioddddo
241:iioiiodddo
242:iioiioddo
243:iioiiodo
244:iioiioo
245:iioiioio
246:iioiioiio
247:iioiioiiio
248:iioiiodsdo
249:iioiiodso
250:iioisddsio
251:iioisddsiio
252:iioiiiodddo
253:iioiiioddo
254:iioiiiodo
255:iioiiioo

```

Try it online here:
> -1 votes

---
Tags: code-challenge, code-generation, deadfish
---


title: Complement an infinite list

text:
# Question
Title: Complement an infinite list
In this challenge, we define the *complement* of a list of positive integers as all positive integers not included in that list. For example, the complement of the even numbers `[2, 4, 6, 8...]` is the odd numbers `[1, 3, 5, 7...]`. Your challenge is to, given a monotonically increasing, infinite list of positive integers, return its complement.

Infinite lists may be input/output as:

* Streams from/to stdin/stdout
* Native infinite list / iterator / generator / etc objects
* Functions that take an index and return an item of the list

Additionally, you may take an index n along with the infinite list and return the nth item of the list's complement. For all options, you may use 0-indexing or 1-indexing, and your output format does not need to be the same as your input format.

## Testcases

```
2, 4, 6, 8... (even numbers) => 1, 3, 5, 7...
1, 4, 9, 16... (squares) => 2, 3, 5, 6, 7...
2, 3, 5, 7, 11... (primes) => 1, 4, 6, 8...
3, 6, 9, 12... (multiples of 3) => 1, 2, 4, 5, 7...
1, 3, 6, 10... (triangle numbers) => 2, 4, 5, 7...

```

# Answer
# Python (no imports), 52 bytes

*-3 bytes, thanks to xnor*

```
def f(s,x=0):
 for y in s:yield from range(x+1,x:=y)

```

Attempt This Online!

*input/output as generator*
> 13 votes

# Answer
# 05AB1E, 7 bytes

```
∞.i_ƶ0K

```

Try it online!, or try all testcases

I feel like 6 bytes should definitely be possible, but I can't find it. `м` doesn't work for infinite lists, and `∞ʒ.i_` doesn't work for some reason ):

## Explanation

```
∞       # [1, 2, 3, ...]
.i      # for each, check whether it appears on the input
_       # bool not
ƶ       # multiply by the 1-based index
0K      # and remove zeros

```
> 6 votes

# Answer
# Scratch 3, 138 bytes

*-9 bytes by att*

```
define
forever
set[b v]to(
ask()and wait
add(answer)to[a v
repeat(answer
change[b v]by(1
if<not<[a v]contains(b)?>>then
say(b
add(b)to[a v

```

Attempt This Online! | Test it on Scratchblocks!

Continuously prompts for input while printing out the missing integers.
> 6 votes

# Answer
# Haskell + hgl, 19 bytes

```
nt~<<pa(ef<P1)<(0:)

```

## Explanation

* `(0:)` add a zero to the front of the list
* `pa` map over consecutive elements of a list ...
* `ef<P1` range excluding the initial element
* `nt~<` concat map removing the last element of each range.

## Reflection

There are some things that can be improved

* `K0` is nominally a shortcut for `(0:)` but it has issues with type ambiguity here. That should be investigated.
* This really wants an exclusive range, having to use `P1` and `nt` is a really big waste. There should be various exclusive ranges for `Enum`s.
* This could use a `pa` with a concat, but I'm not sure how reusable that would be.
* Overall there could just be operations for monotonic lists. A function to determine if something is an element of a monotonic list would probably be useful here and elsewhere.
> 6 votes

# Answer
# Vyxal, 53 bitsv2, 6.625 bytes

*-10 bits by lyxal*

```
£Þ∞'¥ḟu=

```

```
£Þ∞'¥ḟu=
 Þ∞'      # Filter list of positive integers by
     ḟ    # Index of integer
£   ¥     # in input list
      u=  # is -1 (not in input)

```

Try it Online!
> 5 votes

# Answer
# Haskell, 30 bytes

```
(1%)
p%(h:t)=[p..h-1]++(h+1)%t

```

Try it online!

**33 bytes:**

```
f l=do(a,b)<-zip(0:l)l;[a+1..b-1]

```

**34 bytes**

```
f l=[n|n<-[1..],all(/=n)$take n l]

```

Try it online!
> 5 votes

# Answer
# , 54 bytes

```
g=\(f,i,j=1,k=1,l=f(k)>j)`if`(i,g(f,i-l,j+1,k+!l),j-1)

```

Attempt This Online!

Input & output as functions that take an index and return an item of the list

---

# , 48 bytes

```
repeat{if((y=scan(,,1))>T)cat(T:(y-1),'');T=y+1}

```

Attempt This Online!

Takes input from STDIN or the R console, and outputs the non-inclusive ranges between successive input values to STDOUT or the R console.
> 4 votes

# Answer
# x86 machine code, 13 bytes

This is basically a function that would be part of a device driver: it repeatedly reads the same address, so that should be an MMIO register for a PCIe device that accepts an input sequence. It outputs via port I/O to a specified port number (perhaps on the same PCIe device). Or more realistically, this runs in a VM where the hypervisor handles these streams. In C for the x86-64 System V ABI, `void complement_sequence(int dummy, volatile int *input, uint16_t output_portnum)` (except this is 32-bit code.)

IDK how justifiable it is to do binary I/O to MMIO and an IO port; it could save bytes incrementing pointers if used for finite challenges, and is not usable as a function on data in memory. But an infinite series requires I/O, if we pretend that 32-bit fixed-width integers didn't actually cap the input + output size as 4 x 2^32 bytes = 16 GiB, which x86-64 can easily handle. I don't plan to use this (or C `volatile int*`) for any finite challenges.

```
               ;; MMIO address in ESI for input
               ;; I/O port number in DX for output (or pointer in EDI for MMIO)
               complement_sequence:
 31C0            xor   eax, eax      ; start as if last value written or considered for writing was 0
                                     ; So we output (0, first_seq_num) non-inclusive on both ends
                .next_seq:
 8B0E            mov   ecx, [esi]   ; next sequence number
 A8              db  0xa8  ; opcode for test al, imm8 works like a forward jump by 1 byte  ;  jmp .entry
               .write:              ; do {
 EF              out  dx, eax         ; 1-byte instruction skipped on first iteration
                .entry:                ; entry point for first inner iteration
 40              inc  eax              ; ++next_write
 39C8            cmp  eax, ecx
 75FA            jne  .write        ; } while(next_write != next_seq);
 EBF5            jmp  .next_seq
          ; no ret, we never return

```

Tested with a debugger locally, after replacing `out` with `stosd` and adding `add esi, 4` after the load. Then I can pass it pointers to arrays in memory, and `display (int[15])outbuf` as I `si` in GDB.

---

Less golfed is 14 bytes, without the partial-instruction hack for loop entry skipping the 1-byte `out dx, eax`. The code above does that by using the opcode for a 2-byte `test al, imm8` as equivalent to a 1-byte jmp forward, consuming the first byte as an immediate so it doesn't run on entry to the loop, only on subsequent iterations.

```
;; MMIO address in ESI for input
;; I/O port number in DX for output (or pointer in EDI for MMIO)
complement_sequence_less_golfed:
  xor   eax, eax      ; start as if last value written or considered for writing was 0
                      ; So we output (0, first_seq_num) non-inclusive on both ends
 .next_seq:
  mov   ecx, [esi]   ; next sequence number
  jmp .entry
.write:              ; do {
  out  dx, eax         ; or  mov  [edi], eax for MMIO
 .entry:
  inc  eax               ; ++next_write
  cmp  eax, ecx
  jne  .write        ; } while(next_write != next_seq);
  jmp  .next_seq
; no ret needed, this is a noreturn function

```

Algorithm: start with `i = 0;` (EAX)

* x = input from sequence (ECX)
* `for ( ; ++i != x ; ) { out(i); }`
* leave the loop with i == x, so i = previous sequence number.
* repeat, getting a new `x`. (With `i` the same.)

This feels like a lot of `jmp` instructions, like maybe there's a better branch layout I'm not seeing. But with 2 nested loops, one of which might have run 0 iterations of part of the body, I guess this is reasonable.
> 4 votes

# Answer
# Python, 79 bytes

```
lambda x,j=0:(i for i in count()if i-j or(j:=next(x))*0)
from itertools import*

```

Attempt This Online!
> 3 votes

# Answer
# JavaScript, ~~49~~ 48 bytes

```
function*(L,P=0){for(v of L)while(++P<v)yield P}

```

Try it online!

Takes an iterable and returns an iterable. Starts from 1.

-1 thanks to bsoelch.
> 3 votes

# Answer
# Jelly, 9 bytes

```
‘rƓṪḷṄ€Ɗß

```

Try it online!

A full program that reads an infinite list from STDIN and outputs an infinite list to STDOUTbof the complement.

## Explanation

```
‘         | Increment by 1 (will start from an implicit zero)
 rƓ       | Range from this to the next number from STDIN
       Ɗ  | Following as a monad using this range as an argument
   Ṫ      | Tail
    ḷ     | Left value (I.e. the tail above) rather than:
     Ṅ€   | - Output all of the remaining values in the range to STDOUT separated by new lines
        ß | Recursively call the link again

```
> 3 votes

# Answer
# Ruby, ~~58 ...~~ 35 bytes

```
->g{->n{b=0;n+=1until g[b+=1]>n;n}}

```

Try it online!

Accept a generator function in input, returns a function.
> 2 votes

# Answer
# Minecraft Data Pack via Lectern, 202 bytes

```
@function a:b
scoreboard players add a  1
function a:a
execute if score o  = a  run scoreboard players add i  1
execute if score o  > a  run tellraw @a {"score":{"name":"a","objective":""}}
function a:b

```

The function is `a:b`.

Takes input as a function `a:a`, which takes in `i <empty>` the 0-based index of an element and returns it, and outputs all numbers to chat.

Assumes the objective `<empty>` exists but no values in it do.

Might be invalid, because while `<empty>` is a valid objective, it requires weird workarounds from the function to work with it because it can't appear at the end of commands.

This is how you'd have the squares as input, for example:

```
@function a:a
scoreboard objectives add temp dummy
execute store result score i temp run scoreboard players add i  1
scoreboard players remove i  1
execute store result score o  run scoreboard players operation i temp *= i temp

```
> 2 votes

# Answer
# Charcoal, 19 bytes

```
ＷＮＦ…⊕↨υ⁰↨⊞Ｏυι⁰«ＩκＤ⎚

```

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

```
ＷＮ

```

Keep inputting numbers while they're positive. (Which they should always be, but it does also mean that if you try this interactively you can enter `0` to quit.)

```
Ｆ…⊕↨υ⁰↨⊞Ｏυι⁰«

```

Push the input number to the predefined list, but make a range between the previous number (defaulting to `0`) and the current number, and loop over that range.

```
ＩκＤ⎚

```

Output the current number eagerly so that it will appear before the next input.

I output each number individually because outputting a range fails if it is empty. Maybe I should make `Dump();` do nothing if the canvas is completely empty?
> 2 votes

# Answer
# Headass, 22 bytes

```
{{D+^(U)}:{PD+^(R):};}

```

I'll be honest, I have no idea how infinite input streams work, and I have no idea whether either implementation of the language supports it, but the actual language itself takes input similarly to brainfuck and doesn't have any issues with getting infinite input, so this is at least theoretically correct... let me know if that's an issue :P

If you want to test it out with infinite output, you'll have to use my online interpreter and run this command:

```
srun('{{D+^(U)}:{PD+^(R):};}',...list)

```

with `list` replaced by the list of your choice. With the speed this program runs at, you're probably going to start seeing outputs at around 3000-4000 so keep that in mind if you're inputting something finite / short.

For a version which halts at the end of input (in case you just want to try it out), try this modified version;

```
{{D+^(U)}:{PD+^(R):};N()}

```

Try It Online!

Make sure input isn't empty or of the form 1,2...n or else it will freeze :P DSO doesn't have a time limit, and those input cases are nontrivial to fix. This has no bearing on the validity of the actual program as it relates to the challenge.

### Explanation

```
{{D+^(U)}:{PD+^(R):};}  full program
{                   ;}  while(true)
 {D+^(U)}:                do {} while(++i == nextinput())
           P              do {print(i)}
          { D+^(R):}      while(++i == currentinput())

```
> 2 votes

# Answer
# Python, 50 bytes

```
lambda s,*i:(n for z in s if{n:=len(i:={*i,z})}-i)

```

Attempt This Online!

Test harness borrowed from @bsoelch.

## How?

For each prefix of the given sequence checks whether it contains its length. If not yields the length.
> 2 votes

# Answer
# MaybeLater, 68 bytes

```
wheni is*{if(i<n)printi elsen=readline0when0spass i++}n=readline0i=1

```

Try it online!
> 1 votes

# Answer
# Befunge-98 (PyFunge), 39 bytes

```
1>:&\->:3j>;#_;\:.1+\1-3jj'<;$1+3jj!'<

```

Try it online!
Takes input in the form `1 3 5 7` ... and outputs in the same form. You will need to manually interrupt the TIO program to see the result, since the program doesn't terminate (it assumes infinite input).

## Explanation

*I have replaced the unprintable character with the letter R (since it is supposed to be the character with ascii value 18, and R is the 18th letter of the alphabet)*

```
1>:&\->:3j>;#_;\:.1+\1-3jjR'<;$1+3jj!'<    Program
1                                          Push 1
 >                               3jj!'<    Repeat forever (the j!' is read backwards and
                                           makes the IP jump 33 cells back to the start)
  :&                                       Duplicate top of stack and read input
    \-                                     Swap top two elements and then get difference
      >:3j>;#_;        3jjR'<;             Inner loop (Repeat until top of stack is 0)
       :3j                                 Duplicate top of stack then jump to _
          >;#_;              ;             If top of stack is not 0, continue looping,
                                           otherwise jump out of loop
               \:                          Swap then Duplicate
                 .                         Pop and output
                  1+                       Increment
                    \1-                    Swap then decrement
                       3jjR'<              Return to start of loop (the unprintable
                                           character has ascii value of 18, which is how
                                           far the IP jumps)
                              $1+          Pop and increment
                                 3jj!'<    Return to start of main loop (the j!' is read
                                           backwards and makes the IP jump 33 cells back
                                           to the start, since ! has ascii value of 33)

```
> 0 votes

# Answer
# brainfuck, 35 bytes

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

```

Try it online!

Note that this inputs and returns raw bytes rather than ascii numbers, and it runs forever regardless of EOF, so TIO isn't the best way to demo it. You can use my own Brainfuck interpreter and pipe the input/output through atob.py and btoa.py.
> 0 votes

# Answer
# JavaScript (SpiderMonkey), 35 bytes

```
g=>f=(n,i=0)=>g(i)>n+i?n+i:f(n,i+1)

```

Try it online!

Input and output as function
> 0 votes

---
Tags: code-golf, sequence, array
---