Optimally reach a number in deadfish! Goal:
Given any natural number k such that k&lt;256, produce an deadfish program that gives the smallest solution possible.
Background:
Deadfish is a joke esoteric programming language. It has a single unsigned byte of memory, called the accumulator, initialized at 0. There are four commands which form a string.

i = accumulator += 1
d = accumulator -= 1
s = accumulator = accumulator * accumulator
o = print(accumulator)

For example, the string iiisis would produce 100, as this would be the memory after each command:

i -&gt; 1
i -&gt; 2
i -&gt; 3
s -&gt; 9
i -&gt; 10
s -&gt; 100

Specification:

Read a number through any reasonable means (from a file, STDIO, or a function argument), and output an optimal string of commands producing that number.
A solution is considered optimal if there are no solutions that use fewer commands.
Output through any reasonable means (to a file, STDIO, or a return value).
The accumulator may not exceed 256.

Examples:
0 -&gt; (Empty string, nothing, or error)
1 -&gt; i
4 -&gt; iis
8 -&gt; iiisd
35 -&gt; iisiisd
150 -&gt; iiisiiisiiiiii
256 -&gt; (Empty string, nothing, or error)
Mathematica, 164 bytes

a=#~Mod~256&amp;;Switch[#2,#+1,"i",a[#-1],"d",_,"s"]&amp;@@@Partition[FindShortestPath[Graph[Join@@(Thread[#-&gt;a@{#+1/.256-&gt;#,#-1,If[#&lt;16,#^2,#]}]&amp;)/@0~Range~255],0,#],2,1]&amp;


Anonymous function. Takes a number as input and returns a list of instructions as output. Previous solution before requirements were changed:

Mathematica, 148 bytes

a=#~Mod~256&amp;;Switch[#2,a[#+1],"i",a[#-1],"d",_,"s"]&amp;@@@Partition[FindShortestPath[Graph[Join@@(Thread[#-&gt;a@{#+1,#-1,#^2}]&amp;)/@0~Range~255],0,#],2,1]&amp;


Anonymous function. Takes a number as input and returns a list of instructions as output. First, the edges for a graph of value transitions are generated. Then, FindShortestPath is used to find the shortest path from 0 to the requested value. Finally, pairs of values are taken and compared to find the instructions used. All outputs of this program can be found here.