tło
Ruch do przodu transformacji (MTF) jest kodowanie danych algorytm przeznaczony do poprawy wydajności metod kodowania entropijnego.
W algorytmie kompresji bzip2 jest on stosowany po transformacji Burrows – Wheeler (jak widać w Burrows, Wheeler i Back ), w celu przekształcenia grup powtarzających się postaci w małe, łatwo kompresowalne nieujemne liczby całkowite.
Definicja
Na potrzeby tego wyzwania zdefiniujemy wersję MTF do wydruku ASCII w następujący sposób:
Biorąc pod uwagę ciąg wejściowy s , wziąć pustą tablicę R , string d wszystkich znaków ASCII (0x20 do 0x7E) i powtarzać następujące informacje dla każdego znaku c z s :
Dołącz indeks c in d do r .
Przenieś c na przód d , tj. Usuń c z d i wstaw do końca.
Na koniec bierzemy elementy r jako indeksy w oryginalnym d i pobieramy odpowiednie znaki.
Przykład krok po kroku
INPUT: "CODEGOLF"
0. s = "CODEGOLF"
d = " !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
r = []
1. s = "ODEGOLF"
d = "C !\"#$%&'()*+,-./0123456789:;<=>?@ABDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
r = [35]
2. s = "DEGOLF"
d = "OC !\"#$%&'()*+,-./0123456789:;<=>?@ABDEFGHIJKLMNPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
r = [35 47]
3. s = "EGOLF"
d = "DOC !\"#$%&'()*+,-./0123456789:;<=>?@ABEFGHIJKLMNPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
r = [35 47 37]
4. s = "GOLF"
d = "EDOC !\"#$%&'()*+,-./0123456789:;<=>?@ABFGHIJKLMNPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
r = [35 47 37 38]
5. s = "OLF"
d = "GEDOC !\"#$%&'()*+,-./0123456789:;<=>?@ABFHIJKLMNPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
r = [35 47 37 38 40]
6. s = "LF"
d = "OGEDC !\"#$%&'()*+,-./0123456789:;<=>?@ABFHIJKLMNPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
r = [35 47 37 38 40 3]
7. s = "F"
d = "LOGEDC !\"#$%&'()*+,-./0123456789:;<=>?@ABFHIJKMNPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
r = [35 47 37 38 40 3 45]
8. s = ""
d = "FLOGEDC !\"#$%&'()*+,-./0123456789:;<=>?@ABHIJKMNPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
r = [35 47 37 38 40 3 45 41]
OUTPUT: "COEFH#MI"
Zadanie
Napisz program lub funkcję, która implementuje drukowalną MTF ASCII (jak zdefiniowano powyżej).
Przypadki testowe
Input: Programming Puzzles & Code Golf
Output: Prpi"do lp%((uz rnu&3!P/o&$U$(p
Input: NaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaN BATMAN!
Output: Na! !! !! !! !! !! !! !! !! !! !! !! !! !! !! !!"DDUP"%'
Input: Two more questions and I have bzip2 in less than 100 bytes!
Output: Twp#o"si$sv#uvq(u$(l#o#W!r%w+$pz,xF%#,"x(. #0--'$GG ".z(**:
Dodatkowe zasady
Nie można użyć żadnego wbudowanego operatora, który oblicza MTF ciągu.
Twój kod może wydrukować końcowy znak nowej linii, jeśli wybierzesz STDOUT jako wynik.
Twój kod musi działać na każdym wprowadzeniu 1000 lub mniej znaków drukowalnych ASCII (0x20 do 0x7E).
Obowiązują standardowe zasady gry w golfa. Najkrótsze przesłanie w bajtach wygrywa.
źródło
Odpowiedzi:
CJam, 20
Wypróbuj online
Wyjaśnienie:
źródło
Struś ,
4645 znakówNie mam numeru wersji w nagłówku, ponieważ tak naprawdę jest to tylko ostatni zatwierdzenie . Dodałem
O
operatora (kod ascii do łańcucha) po wydaniu najnowszej wersji (ale jeszcze przed opublikowaniem tego wyzwania).Wyjaśnienie:
źródło
Python 3, 88
Wykorzystuję kilka pomysłów z mojego rozwiązania CJam.
-4 bajty należą do Sp3000 :)
źródło
SWI-Prolog,
239197189 bajtówPrzykład:
a(`Two more questions and I have bzip2 in less than 100 bytes!`).
wyniki:(a
true .
potem oczywiście)Uwaga: twoja wersja SWI-Prolog musi być jedną z nowszych, w których backquote
`
reprezentuje ciągi kodów. Ciągi kodu były reprezentowane przez podwójne cudzysłowy"
w starszych wersjach.źródło
Python 2,
137110104Nie było trudne do wdrożenia, ale może nadal można grać w golfa?
Wypróbuj tutaj
źródło
e=d=map(chr,range(32,127))
w Pythonie 2, choć musisz ją ulepszyć,e
aby obsługiwała listę.e=[e.pop(n)]+e
, ale to nie działa. Dlaczego?e=d=
, więc kiedy wyskakujesz ze
, wyskakujesz równieżd
. Spróbowaćd=e[:]
.n=e.index(ord(c));r+=chr(n+32);
i upuścićd
Pyth, 24 bajty
Demonstracja. Uprząż testowa.
Pierwszy kawałek.
JK>95CM127
tworzy niezbędną listę i zapisuje ją wJ
orazK
.~J+d-Jd
wykonuje aktualizację listy, a jednocześniexL ... z
odwzorowuje znaki wejściowe na ich pozycje na liście. Na koniecs@LK
konwertuje te indeksy na znaki z oryginalnej listy.źródło
Haskell, 120 bajtów
Przykład użycia:
f "CODEGOLF"
->"COEFH#MI"
Jak to działa:
#
jest funkcją indeksu, która zwraca pozycjęe
ins
(nie może używać natywnego Haskell zelemIndex
powodu drogiegoimport
). Główna funkcjaf
podąża za wzorem zagięcia, w którym aktualizuje ciąg pozycjid
i ciąg wynikur
podczas przechodzenia przez ciąg wejściowy.źródło