Suponha que usemos as regras a seguir para extrair uma única string de outra, uma contendo apenas caracteres imprimíveis ASCII e chamada de *-string. Se a sequência acabar antes que o processo pare, isso é um erro e o resultado do processo é indefinido nesse caso:

1. Começar com d=1, s=""
2. Sempre que encontrar um *, multiplique dpor 2. Sempre que encontrar outro personagem, concatene-o até o final se subtraia 1 de d. Se agora d=0, pare e retornes

Exemplos definidos :

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

Exemplos indefinidos : (observe que a string vazia também seria uma dessas)

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

Seu trabalho é pegar uma sequência e retornar a *sequência mais curta que produz essa sequência.

Exemplos de programas :

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

Seu programa deve manipular qualquer sequência que contenha pelo menos um caractere e apenas *caracteres imprimíveis não ASCII. Você nunca pode retornar strings para as quais o processo é indefinido, pois, por definição, eles não podem produzir QUALQUER strings.

Aplicam-se brechas padrão e regras de E / S.

Pitão ( 36 27 bytes)

Obrigado a Jakube por uma melhoria de 9 bytes! Atualmente não é tão bom quanto a resposta de muddyfish , mas seja qual for

KlzJ1VzWgKyJp\*=yJ)pN=tK=tJ

Suíte de teste

Tradução para 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

Função recursiva que faz o seguinte:

• Se dfor menor ou igual ao comprimento restante da string dividido por 2:

  Acrescente *à saída e multiplique dpor 2

• Outro:

  Mude a string e acrescente à saída, subtraia 1 de d.

Veja em ação:

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 ( Percebido ) 27 26 25 bytes

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

Explicação para vir.

Suíte de teste

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

Isso tira proveito do padrão muito regular de posições em estrela para gerar a codificação correta. Inicialmente, tentei uma solução recursiva de força bruta, mas, em retrospecto, deveria ter sido óbvio que havia uma solução matemática mais simples.

Essencialmente, você sempre terá 2^floor(log_2(length))estrelas no início de sua produção e uma estrela final após os 2^ceil(log_2(length)) - lengthcaracteres (se isso der pelo menos 1 caractere).

A versão (ligeiramente) não destruída é a seguinte

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)

No começo eu pensei que abcdetinha que ser, *a**bcdemas acontece que **abc*defunciona tão bem. Isso significa que a saída é prontamente construída usando estrelas principais de piso (log₂ (s.length)), além de uma estrela adicional para seqüências de caracteres cujo comprimento não é uma potência de duas.

Editar: salvou 8 bytes calculando o número de estrelas principais recursivamente. Salvei mais 3 bytes com cadeias de caracteres especiais de comprimento 1, para que eu possa tratar as cordas cujo comprimento é uma potência de 2 como tendo uma estrela principal extra.

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

O mesmo que as outras respostas, na verdade. Se EOF, produza uma sequência vazia. Se o comprimento restante for mais do que duas vezes d, produza uma estrela e duas vezes d. Caso contrário, imprima o próximo caractere e subtraia um d.

Ungolfed:

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