13
\$\begingroup\$

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 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).

\$\endgroup\$
3
  • 3
    \$\begingroup\$ Sandbox: codegolf.meta.stackexchange.com/questions/2140/… \$\endgroup\$
    – Underslash
    Jun 3 at 20:46
  • \$\begingroup\$ --ss+so is a shorter one for !, found by my program :p \$\endgroup\$ Jun 3 at 21:13
  • \$\begingroup\$ @RedwolfPrograms yep, I think it's included in the Hello, World! test case, I was just too lazy to actually create a shortened version there :P \$\endgroup\$
    – Underslash
    Jun 3 at 21:21
6
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ eval(a+c+1),+A -> c+1- -a,A \$\endgroup\$
    – tsh
    Jun 4 at 5:06
  • \$\begingroup\$ It should be &255 , not %256 to handle negative numbers. \$\endgroup\$
    – user100690
    Jun 4 at 8:23
  • \$\begingroup\$ @ophact You're right. And using Buffer() was not a good idea anyway, so I've done a complete rewrite. \$\endgroup\$
    – Arnauld
    Jun 4 at 13:05
4
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ That's smart to use a nop in order to iterate through all possibilities. Although, you can get performant code even when completely bruteforcing it. Good answer though +1 \$\endgroup\$
    – Underslash
    Jun 4 at 1:44
  • \$\begingroup\$ I agree with 14 being the maximum length (from either 0 or 128 to 180 or 181 in my testing). \$\endgroup\$
    – Neil
    Jun 4 at 10:57
4
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ This program doesn't optimize ! correctly, the shortest output is --ss+so, but this adds an extraneous +- before the o. (commented in chat already but this seems like a better place) \$\endgroup\$ Jun 3 at 21:24
  • \$\begingroup\$ @RedwolfPrograms Oops, thanks. Made it slightly less efficient (constant factor) and saved 3 bytes :P \$\endgroup\$
    – hyper-neutrino
    Jun 3 at 21:31
  • \$\begingroup\$ Do you need the set v? It seems to stay constant. \$\endgroup\$
    – user100690
    Jun 4 at 5:29
  • \$\begingroup\$ @ophact I was supposed to use it to cut down my search space for efficiency but it doesn't seem to really matter, apparently. thanks lol \$\endgroup\$
    – hyper-neutrino
    Jun 4 at 5:37
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ Does this time out on TIO for longer inputs, or am I doing something wrong? \$\endgroup\$
    – Underslash
    Jun 4 at 16:13
  • \$\begingroup\$ @Underslash times out for longer inputs on TIO, though there’s no reason otherwise it shouldn’t work for unlimited inputs \$\endgroup\$ Jun 4 at 17:43
  • \$\begingroup\$ how exactly does it time out? A naive brute force attempt can do < 1 second for any length really \$\endgroup\$
    – Underslash
    Jun 4 at 19:04
  • \$\begingroup\$ @Underslash because it’s very inefficient. It starts at 0, converts it into a base 3 number using ‘²’ as the digits, runs that as a program and checks the output. If that fails, it increases to 1 and does the same. Unlike some of the other answers, this means that just for the letter H it has to try 10105 separate programs, and it times out on character 173. \$\endgroup\$ Jun 4 at 20:20
  • 1
    \$\begingroup\$ @Underslash thanks. I’ve actually now changed tack to a more efficient approach that also takes fewer bytes! \$\endgroup\$ Jun 4 at 22:00
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 77 bytes

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

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

≔⁰θ

Initialise the accumulator to zero.

FES℅ι«

Loop over the code points of the input.

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

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).

F¹⁴

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!)

FΦLη¬⁼#§ηλ

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

F³«

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.

≔E²⁵⁶E²⁵⁶⎇⁼ιλω#θ≔E²⁵⁶⟦⟦+﹪⊕κ²⁵⁶⟧⟦-﹪⊖κ²⁵⁶⟧⟧ηF²⁵⁶«F¬⁼ι﹪×ιι²⁵⁶⊞§ηι⟦s﹪×ιι²⁵⁶⟧F§ηι§≔§θι§κ¹§κ⁰»≔EηιζWΦθ№κ#FEι⌕κω«≔⟦⟧εF§ζκF§η§λ¹F⁼#§§θκ§μ¹«§≔§θκ§μ¹⁺§λ⁰§μ⁰⊞ε⟦⁺§λ⁰§μ⁰§μ¹⟧»¿ε§≔ζκε»≔⁰δFS«≔℅ι駧θδι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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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