Optimize imnotdeadfish

Question

Fluff

After taking a look at deadfish, I decided it sucked, so I came up with a new (and easier) variant of it: imnotdeadfish.

As with its predecessor, there are 4 commands and an accumulator which begins at 0:

+ # increment the accumulator
- # decrement the accumulator
s # square the accumulator
o # output the accumulator as an ascii char

The only difference between the languages (besides using + and -) is that if the accumulator ever goes out of range of 0 <= x < 256, the accumulator is taken mod 256. Ex: if the accumulator is at 255 and the command + is executed, it wraps to 0, and if, for example, it is at 0 and the command is -, the result would be 255.

An example program such as this: ++++s+so which would output !

Challenge

The problem with imnotdeadfish is that it's too easy, which means optimal solutions are not hard to find.

Given a string of characters, output the shortest code (which is not necessarily unique) in imnotdeadfish that prints the output. This should work for all inputs with chars between 0-255, but the testcases won't cover that.

Examples

input => output

Hello, World! => +++s+s-s-o++s+o+++++++oo+++o----ss++s+++os+s-o+++++s--o-s+++s--o+++o------o-s---sos+so
test          => ++s+ss+++o++s+o++s++o+o
aaaaaaaaaa    => +++s--ssoooooooooo

This is code-golf so the shortest program, in bytes, wins. (this is the program you write, not the resulting imnotdeadfish program, since those should be the same length)

Here is a reference implementation of imnotdeadfish (for testing - this is not a valid submission to this challenge).

Answer 1

JavaScript (ES6), 129 bytes

Expects an array of characters. Returns a string.

a=>a.map(c=>{for(k=0;c.charCodeAt(o='')^(g=x=>(o+="o+s-"[q=x&3],q)?g(x/4,n-=q-2||n-n*n,n&=255):n)(k++,n=r););r=n;O+=o},r=O='')&&O

Try it online!

Commented

a =>                     // a[] = input array
a.map(c =>               // for each character c in a[]:
  { for(                 //   loop:
      k = 0;             //     start with k = 0
      c.                 //     we'll stop as soon we've found a sequence
      charCodeAt(        //     producing the ASCII code of c
        o = ''           //     start each iteration with o = ''
      ) ^                //
      ( g = x =>         //     g is a recursive function which turns x
                         //     into a sequence of imnotdeadfish commands
        ( o +=           //       append to o:
            "o+s-"[      //         the symbol of the command q
              q = x & 3  //         with q = floor(x) mod 4
            ],           //
          q              //
        ) ?              //       if q is not equal to 0:
          g(             //         do a recursive call to g:
            x / 4,       //           divide x by 4
            n -=         //           update n:
              q - 2 ||   //             do +1 or -1 if q is not equal to 2
              n - n * n, //             otherwise, update n to n * n
            n &= 255     //           reduce n to a byte
          )              //         end of recursive call
        :                //       else (q = 0):
          n              //         stop here and return n
      )(k++, n = r);     //     initial call to g / increment k afterwards
    );                   //   end of for
    r = n;               //   update r to n
    O += o               //   append o to O
  },                     //
  r = O = ''             //   start with O = empty string and r zero'ish
) && O                   // end of map(); return O

Answer 2

Python 2 (PyPy), 166 bytes

p=0
S=''
for c in map(ord,input()):
 for i in range(4**14):
	d='';n=p
	while i:d+='+-s'[i%4-1:i%4];n=[n,n+1,n-1,n*n][i%4]%256;i/=4
	if n==c:S+=d+'o';p=c;break
print S

Try it online!

Instead of brute-forcing the entire program, we only do it in between each character (to speed it up so it doesn't take forever). We use a bitmask to search for all possible answers up to a length of 14 (which is the maximum length needed to find an answer, from my testing).

One thing to note is that the we brute-force four commands instead of three. The fourth command is a NOP (meaning it does nothing), which ensures that the bitmask runs through all possible lengths. The NOP is not actually included in the program.

It takes just one second to run all three test cases on TIO. Note that PyPy is used instead of CPython to speed up execution time.

Answer 3

Python 3, 190 bytes

def g(x,y):
	q=[(x,"")]
	for c,s in q:
		if c==y:return s
		for n,a in[(c+1,"+"),(c-1,"-"),(c*c,"s")]:
			q+=[(n%256,s+a)]
s=[*map(ord,input())]
for x,y in zip([0]+s,s):print(end=g(x,y)+"o")

Try it online!

-20 bytes thanks to ophact; I was initially using a "visited" set but I forgot to add to it in the first place so it seems like it's not too necessary for efficiency, it's more the choice to BFS over brute force.

This is, by far, not the golfiest approach, but it is relatively efficient. I could golf this down a lot by brute forcing but I wanted to go for a faster approach.

Answer 4

JavaScript (ES6), 140 bytes

a=>a.map(p=n=>(g=([m,o],...q)=>(p=m&255)-n.charCodeAt()?g[p]?g(...q):g(...q,g[p]=[p+1,o+'+'],[p-1,o+'-'],[p*p,o+'s']):o+'o')([p,''])).join``

Try it online!

Input array of characters, output a string.

Remove the g[p]?g(...q): would work in theory but actually result stack overflow. :(

a=> // input (as array of characters)
a.map(
p= // p&255 is the value of cell, initial to 0
n=> // for each character `n`
(g= // a recursive function apply bfs for shortest code output `n`
    // g is assigned each iteration, so g[p] (discussed later) is cleared
 ([m, // current value got
  o], // code for current value
  ...q // queue for bfs
 )=>
  (p= // let `p` memorize code of previous char
   m&255) // bit-wise and 255 for mod 256, works for negative numbers
  -n.charCodeAt()? // the value got equals to current char?
 // not equal
 g[p]? // value `p` had been searched before
  g(...q): // don't search it again
  g(...q,  // bfs with following items enqueue
    g[p]= // assign g[p] to something thuthy so we won't search it again
    [p+1,o+'+'], // +
    [p-1,o+'-'], // -
    [p*p,o+'s']): // s
 o+'o' // output this char
)([p,'']) // search starts from empty code output previous value
).join`` // join codes for each char

---

Python 3.9, 137 bytes

p=0
for n in input():
 q=[[p,'']]
 for p,o in q:
  if chr(p:=p%256)==n:print(end=o+'o');break
  q[:]+=[p+1,o+'+'],[p-1,o+'-'],[p*p,o+'s']

Try it online!

The TIO link is 139 bytes by changing the last line q[:] into q[-1:]. The code still works without the -1 there on my computer, it only takes much longer time (timeout on TIO). And I don't know why -1 may help the performance.

It is shorter than the mojibake like JavaScript.

---

Python 3.8, 162 bytes

p=0
for n in input():
 q,v=[[p,'']],[1]*256
 for p,o in q:
  if chr(p:=p%256)==n:print(end=o+'o');break
  q[:],v[p]=q+[[p+1,o+'+'],[p-1,o+'-'],[p*p,o+'s']]*v[p],0

Try it online!

And 162 bytes version for better performance.

Answer 5

JavaScript (V8), 187 bytes

-12 thanks to @Ausername

s=>eval('i=0;do{c=i.toString(4).padStart(Math.log2(++i)/2+1,0,o=""),(a=[...c]).reduce((r,x)=>[r+1,r+255,r*r,r,x^3||(o+=String.fromCharCode(r))][x]%256,0)}while(o!=s);a.map(d=>"+-so"[d])')

Try it online!

Description:

Shameless brute-forcing. Increments a number, and converts it to base 4. It then interprets it as imnotdeadfish, and stops as soon as the result is equal to the input. Add n to the first 0 for infinitely large inputs. Didn't do this because it causes TIO to error.

Answer 6

Jelly, 43 34 bytes

‘;’;²&255
OŻ¹Çi?ƬFiɗƝ’ḃ3ị“+-s”Up”o

Try it online!

A full program taking a string argument and printing the resulting program to STDOUT. For each pair of characters (prepended with a null byte) progressively extends a list by applying each of the three operations, preserving intermediate values, until the second integer is found. The position of the second integer in the flattened list is then base decoded into "+-s" and appended with "o" to yield the imnotdeadfish program.

Now works for longer inputs, because this is more efficient than the previous approach.

Full explanation to follow.

Answer 7

R, 174 bytes

\(x,p=paste0)p(mapply(\(y,z){l="";while(is.na(m<-match(z,y))){l=c(outer(l,c("+","-","s"),p));y=c(y+1,y-1,y^2)%%256};l[m]},c(0,(u=utf8ToInt(x))[-nchar(x)]),u),"o",collapse="")

Try it online!

A function that takes a string and returns the iamnotdeadfish program as a string

Answer 8

Charcoal, 77 bytes

≔⁰θＦＥＳ℅ι«≔Ｅ²⁵⁶⎇⁼κθω#ηＦ¹⁴ＦΦＬη¬⁼#§ηλＦ³«≔§⟦⊕λ⊖λ×λλ⟧μκ¿⁼#§ηκ§≔ηκ⁺§ηλ§+-s컧ηιo≔ιθ

Try it online! Link is to verbose version of code. Explanation:

≔⁰θ

Initialise the accumulator to zero.

ＦＥＳ℅ι«

Loop over the code points of the input.

≔Ｅ²⁵⁶⎇⁼κθω#η

Create an array of the command strings found so far (the empty string for the current accumulator and a marker # for all of the other values).

Ｆ¹⁴

Repeat enough times to ensure all possible values are covered. (I could save a byte by looping 1,000 times but that would make the code unusable on TIO. On the other hand repeating until we found the value we wanted would be faster still. Try it online!)

ＦΦＬη¬⁼#§ηλ

Loop over the values of the command strings found so far.

Ｆ³«

Loop over the three possible commands.

≔§⟦⊕λ⊖λ×λλ⟧μκ

Get the result of applying the command to the current value. No need to reduce modulo 256 here because Charcoal's array indexing is automatically cyclic.

¿⁼#§ηκ

If there is no command string for this value yet, then...

§≔ηκ⁺§ηλ§+-sμ

... save the new command string.

»§ηιo

Output the desired command string.

≔ιθ

Update the accumulator.

I also wrote a program to enumerate all possible snippets for all values. This version uses the results to solve the original problem in near-constant time.

≔Ｅ²⁵⁶Ｅ²⁵⁶⎇⁼ιλω#θ≔Ｅ²⁵⁶⟦⟦+﹪⊕κ²⁵⁶⟧⟦-﹪⊖κ²⁵⁶⟧⟧ηＦ²⁵⁶«Ｆ¬⁼ι﹪×ιι²⁵⁶⊞§ηι⟦s﹪×ιι²⁵⁶⟧Ｆ§ηι§≔§θι§κ¹§κ⁰»≔ＥηιζＷΦθ№κ#ＦＥι⌕κω«≔⟦⟧εＦ§ζκＦ§η§λ¹Ｆ⁼#§§θκ§μ¹«§≔§θκ§μ¹⁺§λ⁰§μ⁰⊞ε⟦⁺§λ⁰§μ⁰§μ¹⟧»¿ε§≔ζκε»≔⁰δＦＳ«≔℅ι駧θδιo≔ιδ

Try it online! Link is to verbose version of code.

Using that code I was able to find some trivia e.g. the longest snippets are from 0 or 128 to 180 or 181; these take 14 commands (not including the trailing o). For printable ASCII there are a number of equally longest snippets, but the most interesting worst case is from space to comma where it's not possible to improve on simply incrementing 12 times.

Answer 9

Julia 0.5, 119 bytes

^(s,l=0,L=[""])=s==""?s:any((i=l.==(b=Int[s[1]]);))?L[i][]"o"s[2:end]^b:^(s,[l+1;l+255;l.*l]%256,vec(L.*["+" "-" "s"]))

Try it online!

ungolfed:

function ^(s,l=0,L=[""])
    s == "" && return ""
    b = Int[s[1]]
    i = l .== b
    if any(i)
        return L[i][1] * "o" * ^(s[2:end], b)
    else
        return ^(s, [l.+1; l.+255; l.*l].%256, vec(L.*["+" "-" "s"]))
    end
end

Try it online!