Optimally reach a number in deadfish!

4

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)

Julian Lachniet

Posted 2016-12-30T15:40:05.403

Reputation: 3 216

Question was closed 2016-12-30T18:40:03.023

9Related, although weirdly a code-challenge – Sp3000 – 2016-12-30T15:43:03.063

2I 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? – FlipTack – 2016-12-30T15:46:04.153

4This might be useful to test programs. – nedla2004 – 2016-12-30T15:47:12.193

2For 150, iiissisisddd is two instructions shorter than the given solution. – LegionMammal978 – 2016-12-30T15:50:43.663

1is ioiisddsio a valid output for 150? (+1 [1], print, +1 [2], +1 [3], ^2 [9], -1 [8], -1 [7], ^2 [49], +1 [50], print) – Gabriel Benamy – 2016-12-30T16:05:12.947

@GabrielBenamy The challenge says that the number must be in memory, not printed. Also, the official interpreter prints a newline after each number, which would render that solution invalid. (This was discussed in the previous very similar challenge, where it was decided that it was valid in order to keep existing answers valid, though.)

– PurkkaKoodari – 2016-12-30T16:15:32.157

LegionMammal978: 1, 2, 3, 9, 10, 11, 12, 144, 145, 146, 147, 148, 149, 150 – Julian Lachniet – 2016-12-30T16:24:24.907

@JulianLachniet iiissisisddd gives the shorter sequence 1, 2, 3, 9, 81, 82, 68, 69, 153, 152, 151, 150. – LegionMammal978 – 2016-12-30T16:37:11.643

82 -> 68 what the heck? – Julian Lachniet – 2016-12-30T16:53:11.453

@JulianLachniet You state that the accumulator is an unsigned byte. 82^2 = 6724 ≡ 68 (mod 256). – LegionMammal978 – 2016-12-30T17:02:28.337

You cannot go outside of the range. See edit to original post – Julian Lachniet – 2016-12-30T17:09:40.680

1Editing a question so that it invalidates an already-existing answer is bad practice. – Gabriel Benamy – 2016-12-30T18:22:28.187

1What should the output be for 254? – LegionMammal978 – 2016-12-30T18:36:43.133

Answers

1

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.

LegionMammal978

Posted 2016-12-30T15:40:05.403

Reputation: 15 731