Supongamos que usamos las siguientes reglas para extraer una sola cadena de otra cadena, una que contiene solo caracteres imprimibles ASCII y se llama una *cadena. Si la cadena se agota antes de que el proceso se detenga, eso es un error, y el resultado del proceso no está definido en ese caso:

1. Empezar con d=1, s=""
2. Siempre que encuentres a *, multiplica dpor 2. Siempre que encuentres otro personaje, concatena al final de sy resta 1 de d. Si ahora d=0, deténgase y regreses

Ejemplos definidos :

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

Ejemplos indefinidos : (tenga en cuenta que la cadena vacía también sería uno de estos)

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

Su trabajo es tomar una cadena y devolver la cadena más *corta que produce esa cadena.

Ejemplos de programa :

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

Su programa debe manejar cualquier cadena que contenga al menos un carácter y solo *caracteres imprimibles que no sean ASCII. Nunca puede devolver cadenas para las cuales el proceso no está definido, ya que por definición no pueden producir NINGUNA cadena.

Se aplican las lagunas estándar y las reglas de E / S.

Pyth ( 36 27 bytes)

¡Gracias a Jakube por una mejora de 9 bytes! Actualmente no es tan bueno como la respuesta de muddyfish , pero lo que sea

KlzJ1VzWgKyJp\*=yJ)pN=tK=tJ

Banco de pruebas

Traducción a 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

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

Función recursiva que hace lo siguiente:

• Si des menor o igual que la longitud restante de la cadena dividida por 2:

  Añadir *a la salida y multiplicar dpor 2

• Más:

  Cambia la cadena y agrega a la salida, resta 1 de d.

Véalo en acción:

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>

Pyth, 29 27 (notado roto) 27 26 25 bytes

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

Explicación por venir.

Banco de pruebas

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

Esto aprovecha el patrón muy regular de las posiciones de las estrellas para generar la codificación correcta. Inicialmente probé una solución recursiva de fuerza bruta, pero en retrospectiva debería haber sido obvio que había una solución matemática más simple.

Esencialmente, siempre tendrá 2^floor(log_2(length))estrellas al comienzo de su salida y una estrella final después de los 2^ceil(log_2(length)) - lengthcaracteres (si eso resulta en al menos 1 carácter).

La versión (ligeramente) sin golf es la siguiente

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)

Al principio pensé que abcdetenía que ser así, *a**bcdepero resulta que **abc*defunciona igual de bien. Esto significa que la salida se construye fácilmente utilizando estrellas principales de piso (log₂ (longitud s)), más una estrella adicional para cadenas cuya longitud no es una potencia de dos.

Editar: ahorró 8 bytes calculando el número de estrellas principales de forma recursiva. Ahorré otros 3 bytes con cadenas de carcasa especial de longitud 1, para que pueda tratar las cadenas cuya longitud es una potencia de 2 como si tuviera una estrella principal adicional.

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

Igual que las otras respuestas, de verdad. Si EOF, genera una cadena vacía. Si la longitud restante es más de dos veces d, genera una estrella y el doble d. De lo contrario, muestre el siguiente carácter y reste uno de d.

Sin golf:

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