18
\$\begingroup\$

Suppose we use the following rules to pull a single string from another string, one containing only ASCII printable characters and called an *-string. If the string runs out before the process halts, that is an error, and the result of the process is undefined in that case:

  1. Start with d=1, s=""
  2. Whenever you encounter a *, multiply d by 2. Whenever you encounter another character, concatenate it to the end of s and subtract 1 from d. If now d=0, halt and return s

Defined Examples:

d->d
769->7
abcd56->a
*abcd56->ab
**abcd56->abcd
*7*690->769
***abcdefghij->abcdefgh

Undefined Examples: (note that the empty string would be one of these as well)

*7
**769
*7*
*a*b
*

Your job is to take a string and return the shortest *-string that produces that string.

Program Examples:

7->7
a->a
ab->*ab
abcd->**abcd
769->*7*69

Your program should handle any string containing at least one character and only non-* ASCII printable characters. You can never return strings for which the process is undefined, since by definition they cannot produce ANY strings.

Standard loopholes and I/O rules apply.

\$\endgroup\$
  • \$\begingroup\$ Can we assume the input doesn't contain *? \$\endgroup\$ – Luis Mendo Mar 21 '16 at 17:11
  • 3
    \$\begingroup\$ @DonMuesli "only non-* ASCII printable characters" \$\endgroup\$ – FryAmTheEggman Mar 21 '16 at 17:16
3
\$\begingroup\$

Pyth (36 27 bytes)

Thanks to Jakube for a 9 byte improvement! Currently not as good as muddyfish's answer, but whatever

KlzJ1VzWgKyJp\*=yJ)pN=tK=tJ

Test Suite

Translation to python:

                            | z=input() #occurs by default
Klz                         | K=len(z)
   J1                       | J=1
     Vz                     | for N in z:
       WgKyJ                |   while K >= J*2:
            p\*             |     print("*", end="")
               =yJ          |     J=J*2
                  )         |     #end inside while
                   pN       |   print(N, end="")
                     =tK    |   K=K-1
                        =tJ |   J=J-1
\$\endgroup\$
  • 1
    \$\begingroup\$ Muddyfish's seems to have died... \$\endgroup\$ – Rɪᴋᴇʀ Mar 21 '16 at 21:08
5
\$\begingroup\$

JavaScript (ES6), 61 bytes

f=(s,d=2)=>s?d>s.length?s[0]+f(s.slice(1),d-2):'*'+f(s,d*2):s

Recursive function that does the following:

  • If d is less than or equal to remaining string length divided by 2:

    Append * to output and multiply d by 2

  • Else:

    Shift the string and append to output, subtract 1 from d.

See it in action:

f=(s,d=2)=>s?d>s.length?s[0]+f(s.slice(1),d-2):'*'+f(s,d*2):s

input.oninput = e => output.innerHTML = f(input.value);
<input id="input" type="text"/>
<p id="output"></p>

\$\endgroup\$
  • 1
    \$\begingroup\$ Save 2 bytes by working with double the value of d plus a futher byte by reversing the condition: f=(s,d=2)=>s?d>s.length?s[0]+f(s.slice(1),d-2):'*'+f(s,d*2):s \$\endgroup\$ – Neil Mar 21 '16 at 22:07
4
\$\begingroup\$

Pyth, 29 27 (Noticed broken) 27 26 25 bytes

+*\*sKllzXJ-^2.EKlzz?J\*k

Explanation to come.

Test Suite

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

C, 125 bytes

main(int q,char**v){++v;int i=1,n=strlen(*v);while(n>(i*=2))putchar(42);for(i-=n;**v;--i,++*v)!i&&putchar(42),putchar(**v);}

This takes advantage of the very regular pattern of star positions to output the correct encoding. Initially I tried a bruteforce recursive solution, but in retrospect it should have been obvious that there was a simpler mathematical solution.

Essentially you will always have 2^floor(log_2(length)) stars at the start of your output, and a final star after 2^ceil(log_2(length)) - length characters (if that works out to at least 1 character).

The (slightly) ungolfed version is as follows

main(int q,char**v){
   ++v;                         // refer to the first command line argument
   int i=1, n=strlen(*v);       // set up iteration variables

   while(n > (i*=2))            // print the first floor(log2(n)) '*'s
      putchar(42);

   for(i-=n;  **v;  --i, ++*v)  // print the string, and the final '*'
      !i&&putchar(42),putchar(**v);
}
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 88 77 bytes

f=(s,l=s.length,p=2)=>l<2?s:p<l?"*"+f(s,l,p*2):s.slice(0,p-=l)+"*"+s.slice(p)

At first I thought that abcde had to be *a**bcde but it turns out that **abc*de works just as well. This means that the output is readily constructed using floor(log₂(s.length)) leading stars, plus an additional star for strings whose length is not a power of two.

Edit: Saved 8 bytes by calculating the number of leading stars recursively. Saved a further 3 bytes by special-casing strings of length 1, so that I can treat strings whose length is a power of 2 as having an extra leading star.

\$\endgroup\$
0
\$\begingroup\$

Haskell, 68 bytes

f d[]=""
f d xs|length xs>=d*2='*':f(d*2)xs
f d(x:xs)=x:f(d-1)xs

Same as the other answers, really. If EOF, output an empty string. If length remaining is more than twice d, output a star and double d. Otherwise, output the next character and subtract one from d.

Ungolfed:

f d (  [])                    = ""
f d (  xs) | length xs >= d*2 = '*' : f (d*2) xs
f d (x:xs)                    =  x  : f (d-1) xs
\$\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.