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

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? Commented Oct 21, 2014 at 20:37
• @Calvin'sHobbies I don't think anyones getting that -100:) Commented Oct 21, 2014 at 20:41
• Related Commented Oct 21, 2014 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? Commented Oct 21, 2014 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) Commented Oct 21, 2014 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. Commented Oct 22, 2014 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
Commented Oct 22, 2014 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 Commented Oct 22, 2014 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 Commented Oct 22, 2014 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
Commented Oct 22, 2014 at 21:15

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


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? Commented Oct 21, 2014 at 21:04
• @MegaTom As I suggested in the comments: the sum of the lengths of all 256 numbers. Commented Oct 21, 2014 at 21:05
• in that case should you multiply the char count by 5 or something like that? otherwise it will soon be irrelevant. Commented Oct 21, 2014 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." Commented Oct 21, 2014 at 23:48
• @soktinpk no, you're hitting -1 with d, so that should print 0. Commented Oct 22, 2014 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). Commented Oct 22, 2014 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. Commented Oct 22, 2014 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. Commented Oct 22, 2014 at 8:50
• My output was actually wrong, because you can't make use of 256. Commented Oct 22, 2014 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. Commented Oct 23, 2014 at 0:47

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"  Commented Jun 19, 2015 at 11:59
• Thanks to proud haskeller for pointing to my misunderstanding. I've corrected program. Commented Jun 20, 2015 at 16:02

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