Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
    
Can we assume the input doesn't contain *? – Luis Mendo Mar 21 at 17:11
3  
@DonMuesli "only non-* ASCII printable characters" – FryAmTheEggman Mar 21 at 17:16
    
@FryAmTheEggman Thanks! – Luis Mendo Mar 22 at 12:27
up vote 3 down vote accepted

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
share|improve this answer
1  
Muddyfish's seems to have died... – Eᴀsᴛᴇʀʟʏ Iʀᴋ Mar 21 at 21:08

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>

share|improve this answer
1  
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 – Neil Mar 21 at 22:07
    
@Neil Great catch! Thanks – George Reith Mar 22 at 1:15

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

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

Explanation to come.

Test Suite

share|improve this answer

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);
}
share|improve this answer

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.

share|improve this answer

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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