4
\$\begingroup\$

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)
\$\endgroup\$
  • 9
    \$\begingroup\$ Related, although weirdly a code-challenge \$\endgroup\$ – Sp3000 Dec 30 '16 at 15:43
  • 2
    \$\begingroup\$ 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? \$\endgroup\$ – FlipTack Dec 30 '16 at 15:46
  • 4
    \$\begingroup\$ This might be useful to test programs. \$\endgroup\$ – nedla2004 Dec 30 '16 at 15:47
  • 2
    \$\begingroup\$ For 150, iiissisisddd is two instructions shorter than the given solution. \$\endgroup\$ – LegionMammal978 Dec 30 '16 at 15:50
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ – Gabriel Benamy Dec 30 '16 at 16:05
1
\$\begingroup\$

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.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.