# Length-encode a string

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.

• Can we assume the input doesn't contain *? Mar 21, 2016 at 17:11
• @DonMuesli "only non-* ASCII printable characters" Mar 21, 2016 at 17:16

# 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>

• 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, 2016 at 22:07

## Pyth, 2927 (Noticed broken) 2726 25 bytes

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


Explanation to come.

Test Suite

# 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

• Muddyfish's seems to have died... Mar 21, 2016 at 21:08

## 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);
}


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

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