# Goal:

Given any natural number k such that k<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 -> 1
• i -> 2
• i -> 3
• s -> 9
• i -> 10
• s -> 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 -> (Empty string, nothing, or error)
1 -> i
4 -> iis
8 -> iiisd
35 -> iisiisd
150 -> iiisiiisiiiiii
256 -> (Empty string, nothing, or error)

• Related, although weirdly a code-challenge Dec 30 '16 at 15:43
• I recommend you just say "input is guaranteed to be in the range 0-255" rather than including 256 in the test cases. also, should 0 be an empty string, not an error? Dec 30 '16 at 15:46
• This might be useful to test programs. Dec 30 '16 at 15:47
• For 150, iiissisisddd is two instructions shorter than the given solution. Dec 30 '16 at 15:50
• is ioiisddsio a valid output for 150? (+1 [1], print, +1 [2], +1 [3], ^2 [9], -1 [8], -1 [7], ^2 [49], +1 [50], print) Dec 30 '16 at 16:05

# Mathematica, 164 bytes

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


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&;Switch[#2,a[#+1],"i",a[#-1],"d",_,"s"]&@@@Partition[FindShortestPath[Graph[Join@@(Thread[#->a@{#+1,#-1,#^2}]&)/@0~Range~255],0,#],2,1]&


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.