Supposons que nous utilisions les règles suivantes pour extraire une seule chaîne d'une autre chaîne, l'une contenant uniquement des caractères imprimables ASCII et appelée chaîne de caractères *. Si la chaîne s'épuise avant l'arrêt du processus, c'est une erreur et le résultat du processus n'est pas défini dans ce cas:

1. Commencer avec d=1, s=""
2. Chaque fois que vous rencontrez un *, multipliez dpar 2. Chaque fois que vous rencontrez un autre personnage, concaténez-le à la fin set soustrayez 1 de d. Si maintenant d=0, arrêtez et revenezs

Exemples définis :

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

Exemples indéfinis : (notez que la chaîne vide serait également l'une d'entre elles)

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

Votre travail consiste à prendre une chaîne et à renvoyer la chaîne la plus courte *qui produit cette chaîne.

Exemples de programme :

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

Votre programme doit gérer toute chaîne contenant au moins un caractère et uniquement des *caractères imprimables non ASCII. Vous ne pouvez jamais renvoyer de chaînes pour lesquelles le processus n'est pas défini, car par définition, elles ne peuvent produire AUCUNE chaîne.

Les failles standard et les règles d'E / S s'appliquent.

Pyth ( 36 27 octets)

Merci à Jakube pour une amélioration de 9 octets! Actuellement pas aussi bon que la réponse de muddyfish , mais peu importe

KlzJ1VzWgKyJp\*=yJ)pN=tK=tJ

Suite de tests

Traduction en 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 octets

f=(s,d=2)=>s?d>s.length?s[0]+f(s.slice(1),d-2):'*'+f(s,d*2):s

Fonction récursive qui effectue les opérations suivantes:

• Si dest inférieur ou égal à la longueur de chaîne restante divisée par 2:

  Ajouter *à la sortie et multiplier dpar 2

• Autre:

  Déplacez la chaîne et ajoutez à la sortie, soustrayez 1 de d.

Voyez-le en 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>

Pyth, 29 27 (cassé remarqué) 27 26 25 octets

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

Explication à venir.

Suite de tests

C, 125 octets

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

Cela profite du modèle très régulier de positions d'étoiles pour produire le codage correct. Au départ, j'ai essayé une solution récursive bruteforce, mais rétrospectivement, il aurait dû être évident qu'il existait une solution mathématique plus simple.

Essentiellement, vous aurez toujours des 2^floor(log_2(length))étoiles au début de votre sortie et une dernière étoile après les 2^ceil(log_2(length)) - lengthcaractères (si cela correspond à au moins 1 caractère).

La version (légèrement) non golfée est la suivante

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 octets

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)

Au début, je pensais que cela abcdedevait être, *a**bcdemais il s'avère que**abc*de fonctionne aussi bien. Cela signifie que la sortie est facilement construite à l'aide d'étoiles de tête (log₂ (s.length)), plus une étoile supplémentaire pour les cordes dont la longueur n'est pas une puissance de deux.

Modifier: 8 octets enregistrés en calculant le nombre d'étoiles principales de manière récursive. Enregistré 3 octets supplémentaires par des chaînes de boîtier spécial de longueur 1, afin que je puisse traiter les chaînes dont la longueur est une puissance de 2 comme ayant une étoile de tête supplémentaire.

Haskell, 68 octets

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

Identique aux autres réponses, vraiment. Si EOF, affichez une chaîne vide. Si la longueur restante est supérieure à deux fois d, émettez une étoile et double d. Sinon, sortez le caractère suivant et soustrayez-en un d.

Non golfé:

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