Załóżmy, że stosujemy następujące reguły, aby wyciągnąć pojedynczy ciąg z innego ciągu, który zawiera tylko znaki drukowalne ASCII i nazywany jest *ciągiem. Jeśli ciąg skończy się, zanim proces się zatrzyma, jest to błąd, a wynik procesu jest niezdefiniowany w takim przypadku:

1. Zacząć od d=1, s=""
2. Ilekroć napotkasz znak *, pomnóż dprzez 2. Ilekroć spotkasz inną postać, połącz ją do końca si odejmij 1 od d. Jeśli teraz d=0, zatrzymaj się i wróćs

Zdefiniowane przykłady :

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

Niezdefiniowane przykłady : (zauważ, że pusty ciąg również będzie jednym z nich)

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

Twoim zadaniem jest pobranie łańcucha i zwrócenie najkrótszego ciągu, *który go tworzy.

Przykłady programów :

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

Twój program powinien obsługiwać dowolny ciąg znaków zawierający co najmniej jeden znak i tylko *znaki drukowalne inne niż ASCII. Nigdy nie możesz zwrócić łańcuchów, dla których proces jest niezdefiniowany, ponieważ z definicji nie mogą tworzyć ŻADNYCH łańcuchów.

Obowiązują standardowe luki i reguły we / wy.

Pyth ( 36 27 bajtów)

Dzięki Jakube za ulepszenie o 9 bajtów! Obecnie nie jest tak dobra jak odpowiedź błotniaka , ale cokolwiek

KlzJ1VzWgKyJp\*=yJ)pN=tK=tJ

Pakiet testowy

Tłumaczenie na 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 bajtów

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

Funkcja rekurencyjna, która wykonuje następujące czynności:

• Jeśli djest mniejsza lub równa pozostałej długości ciągu podzielonej przez 2:

  Dołącz *do wyniku i pomnóż dprzez 2

• Jeszcze:

  Przesuń ciąg i dołącz do wyjścia, odejmij 1 od d.

Zobacz to w akcji:

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 (zauważono uszkodzenie) 27 26 25 bajtów

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

Wyjaśnienie, które nastąpi.

Pakiet testowy

C, 125 bajtów

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

Wykorzystuje to bardzo regularny wzór pozycji gwiazd, aby uzyskać prawidłowe kodowanie. Początkowo próbowałem rekurencyjnego rozwiązania bruteforce, ale z perspektywy czasu powinno być oczywiste, że istnieje prostsze rozwiązanie matematyczne.

Zasadniczo zawsze będziesz mieć 2^floor(log_2(length))gwiazdki na początku swojej produkcji, a ostatnią gwiazdkę za 2^ceil(log_2(length)) - lengthpostaciami (jeśli to da wynik co najmniej 1 postaci).

Wersja (nieco) niestrzeżona jest następująca

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 bajtów

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)

Na początku tak myślałem abcde musi być, *a**bcdeale okazuje się, że **abc*dedziała równie dobrze. Oznacza to, że moc wyjściową można łatwo skonstruować przy użyciu gwiazd wiodących na podłodze (log₂ (s.length)) oraz dodatkowej gwiazdy dla łańcuchów, których długość nie jest potęgą dwóch.

Edycja: Zapisano 8 bajtów, obliczając rekurencyjnie liczbę wiodących gwiazd. Kolejne 3 bajty zostały zapisane przez specjalne łańcuchy o długości 1, dzięki czemu mogę traktować łańcuchy o długości 2 jako dodatkową gwiazdę wiodącą.

Haskell, 68 bajtów

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

Tak samo jak inne odpowiedzi, naprawdę. Jeśli EOF, wypisz pusty ciąg. Jeśli pozostała długość jest ponad dwukrotnie d, wyślij gwiazdkę i podwój d. W przeciwnym razie wypisz następny znak i odejmij jedend .

Nie golfowany:

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