Length-encode a string

Question

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:

Start with d=1, s=""
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.

\$\begingroup\$ Can we assume the input doesn't contain *? \$\endgroup\$

Luis Mendo
– Luis Mendo

2016-03-21 17:11:06 +00:00
Commented Mar 21, 2016 at 17:11 — Luis Mendo
– Luis Mendo, Commented Mar 21, 2016 at 17:11
\$\begingroup\$ @DonMuesli "only non-* ASCII printable characters" \$\endgroup\$

FryAmTheEggman
– FryAmTheEggman

2016-03-21 17:16:30 +00:00
Commented Mar 21, 2016 at 17:16 — FryAmTheEggman
– FryAmTheEggman, Commented Mar 21, 2016 at 17:16

George Reith · Accepted Answer · 2016-03-22 01:14:23Z

5

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>

edited Mar 22, 2016 at 1:14

answered Mar 21, 2016 at 21:21

George Reith

2,5341 gold badge15 silver badges16 bronze badges

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
– Neil

2016-03-21 22:07:17 +00:00
Commented Mar 21, 2016 at 22:07

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

4

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

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

Explanation to come.

Test Suite

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Mar 21, 2016 at 18:33

Blue

28.8k8 gold badges53 silver badges101 bronze badges

Add a comment |

Community · Accepted Answer · 2017-04-13 12:38:59Z

3

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

edited Apr 13, 2017 at 12:38

CommunityBot

1

answered Mar 21, 2016 at 19:04

K Zhang

7,2861 gold badge11 silver badges13 bronze badges

1

\$\begingroup\$ Muddyfish's seems to have died... \$\endgroup\$

Riker
– Riker

2016-03-21 21:08:18 +00:00
Commented Mar 21, 2016 at 21:08

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

Neil · Accepted Answer · 2016-03-21 21:56:03Z

1

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.

edited Mar 21, 2016 at 21:56

answered Mar 21, 2016 at 21:37

Neil

184k12 gold badges76 silver badges290 bronze badges

Add a comment |

MathematicalOrchid · Accepted Answer · 2016-03-22 14:45:07Z

1

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

answered Mar 22, 2016 at 14:45

MathematicalOrchid

1,70111 silver badges9 bronze badges

Add a comment |

Jordan · Accepted Answer · 2022-11-02 19:39:35Z

1

Ruby, 58 bytes

F=->a,s="",d=1{x,*y=a
d<1?s:x==?*?F[y,s,d*2]:F[y,s+x,d-1]}

Attempt This Online!

answered Nov 2, 2022 at 19:39

Jordan

12k1 gold badge36 silver badges57 bronze badges

Add a comment |

Stack Exchange Network

Length-encode a string

7 Answers 7

JavaScript (ES6), 61 bytes

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

Pyth (36 27 bytes)

C, 125 bytes

JavaScript (ES6), 88 77 bytes

Ruby, 58 bytes

Your Answer

Hot Network Questions

Length-encode a string

7 Answers 7

JavaScript (ES6), 61 bytes

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

Pyth (36 27 bytes)

C, 125 bytes

JavaScript (ES6), 88 77 bytes

Ruby, 58 bytes

Your Answer

Sign up or log in

Post as a guest

Related

Hot Network Questions