# 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.

• How is doing this in Deadfish possible if it takes no input? Oct 21 '14 at 20:37
• @Calvin'sHobbies I don't think anyones getting that -100:) Oct 21 '14 at 20:41
• Related Oct 21 '14 at 22:43
• Does deadfish handle integers larger than 255? E.g. can we calculate 256 and subtract one? How is overflow handled? Is 16^2 = 0 or 16^2 = 256 or 16^2 = error? Oct 21 '14 at 22:55
• @soktinpk If you hit -1 OR 256, then it gets reset to 0. But if you hit a number bigger than 256 by squaring then it's unchanged, e.g. 17^2 = 289. (see the esolang page) Oct 21 '14 at 23:13

# 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'

• You appear to have gotten the effect of the d operation wrong - if it decrements to -1, it gets reset to 0, not 255.
– Doorknob
Oct 22 '14 at 3:04
• I think you misunderstood what o does; it outputs the accumulator and a newline. iodo outputs 1\n0\n, not 10.
– Gabe
Oct 22 '14 at 4:51
• Invalid for many numbers (due to 256 and -1 -> 0). Example 255 iissdo: i:1,i:2,s:4,s:16,s:256->0,d:-1->0,output 0 Oct 22 '14 at 10:35
• @Gabe the wiki page for Deadfish does not mention that a newline will also be printed when doing o. Neither does many compilers (in different languages) print a new line with o Oct 22 '14 at 12:41
• @Optimizer: I think the newline is implied. I don't know all 60+ languages that have versions on the wiki page, but it looks like all the ones I can read do it: Bash, C (the reference implementation), C#, C++, Clever, C64 BASIC, Go, Haskell, HTML/JS, Java, Obfuscated C, OCaml, Pascal, Perl, Python, R, Ruby, Rust, Scheme, Seed7, Stackstack, Unofficial MagicKit Assembler, VB.NET, WTFZOMFG. The important thing is that this answer generates programs that don't work on the reference implementation.
– Gabe
Oct 22 '14 at 21:15

## 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

• I am not certain I like the scoring that much myself...do you have a better idea for how to do it? Oct 21 '14 at 21:04
• @MegaTom As I suggested in the comments: the sum of the lengths of all 256 numbers. Oct 21 '14 at 21:05
• in that case should you multiply the char count by 5 or something like that? otherwise it will soon be irrelevant. Oct 21 '14 at 21:08
• @soktinpk I read "if you hit a number bigger than 256 by squaring" as n > 256 not n ≥ 256. And that's also in line with the esolang page: " Although the comment in the C implementation states /* Make sure x is not greater then [sic] 256 */, the implementation sets the value to zero if and only if value == -1 || value == 256." Oct 21 '14 at 23:48
• @soktinpk no, you're hitting -1 with d, so that should print 0. Oct 22 '14 at 9:05

## 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 is
2. 0-2 ss
3. 0-3 is or ds
4. 0-1 ss
5. 0-14 i or 0-16 ds
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.

• The program has to input the number, not iterate over [0...255] (replace for(...) with scanf - this would decrease character count). Oct 22 '14 at 8:19
• Also, maybe replacing C99 by a more relaxed language could get rid of #include, and maybe you could make the struct inside the union unnamed. Oct 22 '14 at 8:21
• @anatolyg: thanks, I fixed the program to take a number from stdin instead of always printing [0,255]. The for loop is still required due to the way I compute the result. This plus unnaming the struct saved 5 characters; another 2 were saved by changing == to > and removing the trailing newline. :) The program is only fully valid in C99, because main does not explicitly return a value; removing the #include results in an error due to scanf() now. Oct 22 '14 at 8:50
• My output was actually wrong, because you can't make use of 256. Oct 22 '14 at 10:53
• @MartinBüttner: thank you for the comment. I've updated the lookup tables in my code to match your new output in [240,255]. This cost me a few characters because many constants grew from 4 to 5 bytes, not to mention the output is longer now, but at least it's correct now. I also changed the title from "C99" to "C" since I no longer make use of C99-specific features. Oct 23 '14 at 0:47

# Haskell, 22002177 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


# 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 # 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  • Is the last example you gave supposed to print 255? If so, it seems you didn't understand the o operation - it prints the current number, bit doesn't reset it, so ioio would print "12"  and not "11"  Jun 19 '15 at 11:59 • Thanks to proud haskeller for pointing to my misunderstanding. I've corrected program. Jun 20 '15 at 16:02 # 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  # 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]).  # 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 4th power and an 8th power. EDIT: Golfed 75 bytes, the 8th 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')  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 -b1 +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 • Invalid for many numbers (due to 256 and -1 -> 0). Example 255 iisssdo: i:1,i:2,s:4,s:16,s:256->0,d:-1->0,output 0 Oct 22 '14 at 11:20 • Didn't know about the 256->0. I'll try again later. Thanks for pointing that out. Oct 22 '14 at 13:29 • APL . . . trolling ASCII peasants since <whenever> Oct 22 '14 at 16:56 # 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. • If this finds the optimal solution shouldn't it score 2036+codelength as the other optimal answers? – Leo Apr 14 '21 at 7:52 • @Leo I'll edit mine. This is the optimum if you output the number by generating the number and appending o without printing partial results Apr 14 '21 at 7:52 # 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  ## 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: • Now, about the o command writing a newline ... Oct 22 '14 at 13:38 • @edc65 I checked the wiki page. I did not find anywhere that o prints newline. All compilers also were simply printing without new line. Oct 22 '14 at 13:43 • The language spec is nearly not-existing so anything goes. But looking at the compilers code... C printf("%d\n",x); C# Console.WriteLine(x) GO fmt.Println(x) pascal WRITELN(val); python print accumulator (no comma) bash echo$no;; (no -n) Oct 22 '14 at 15:04
• I think we need OP to clearly state this in the question then. Oct 22 '14 at 15:25
• There is a bug in your program. All the codes 100-109 200-209 seem to ignore the 0 Oct 29 '14 at 17:02