Jednym z mniej znanych paradygmatów programowania, który wydaje się raczej odpowiedni do gry w golfa kodowego, jest programowanie nakładające się (OOP) *. Pisząc częściowo identyczny kod, wiele bajtów można zapisać, po prostu nakładając identyczne części i pamiętając w pewien sposób, gdzie zaczynają się dwie oryginalne linie kodu. Twoim zadaniem jest napisanie dwóch nakładających się programów lub funkcji compress
oraz decompress
z poniższą specyfikacją:
* Prawdopodobnie nie używaj w kodzie produkcyjnym.
compress
compress
pobiera dwa ciągi w dowolnym dogodnym formacie i nakłada się na nie w jak największym stopniu. To jest s
zwracany ciąg o minimalnej długości, tak że oba ciągi wejściowe są podciągami s
. Dodatkowo zwracane są niektóre dane wyjściowe, które identyfikują indeksy początkowe i końcowe obu łańcuchów.
Przykłady: (Dokładny format IO zależy od Ciebie)
compress("abcd", "deab") -> "deabcd" ((2,5),(0,3))
compress("abcd", "bc") -> "abcd" ((0,3),(1,2))
compress("abc", "def") -> "abcdef" ((0,2),(3,5)) or "defabc" ((3,5),(0,2))
decompress
decompress
oblicza odwrotną funkcję compress
, która otrzymuje ciąg znaków i dwa indeksy początkowy i końcowy (w formacie, w którym są zwracane przez ciebie compress
), zwracają dwa oryginalne ciągi. Potrzebujesz tylko obsługiwać prawidłowe dane wejściowe. Poniższy równość należy przytrzymać przez wszystkich ciągów s1
, s2
:
(s1, s2) == decompress (compress (s1, s2))
Przykłady: (odwrotne compress
przykłady)
decompress "deabcd" ((2,5),(0,3)) -> "abcd" "deab"
decompress "abcd" ((0,3),(1,2)) -> "abcd" "bc"
decompress "abcdef" ((0,2),(3,5)) -> "abc" "def"
or (whichever version your "compress" generates)
decompress "defabc" ((3,5),(0,2)) -> "abc" "def"
Punktacja
Twój wynik to rozmiar ciągu zwracanego przez wywołanie compress("<code of compress>", "<code of decompress>")
. Ponieważ jest to golf golfowy, niższy wynik jest lepszy.
Przykład:
Załóżmy, że kodem twojej funkcji compress
jest c=abcd
i kodem decompress
jest d=efghi
. Potem compress("c=abcd", "d=efghi")
daje "c=abcd=efghi"
(i wskaźniki, ale te nie wpływają na punktację), więc wynik jest length "c=abcd=efghi" = 12
.
Dodatkowe zasady
- W duchu tego wyzwania twoje
compress
idecompress
muszą nakładać się na co najmniej jedną postać. Możesz to zrobić w trywialny sposób, dodając komentarz, ale pamiętaj, że spowoduje to zwiększenie wyniku i mogą istnieć krótsze rozwiązania wykorzystujące z natury nakładający się kod. compress
idecompress
powinien być w stanie obsługiwać ciągi znaków zawierające dowolne drukowalne znaki ASCII, a także wszystkie znaki użyte do zdefiniowaniacompress
idecompress
.- Indeksy mogą być zerowane lub indeksowane jednokrotnie.
- Twoje programy lub funkcje nie muszą być tak naprawdę nazwane
compress
idecompress
.
Odpowiedzi:
GNU Prolog, 105 punktów
(Wymaga to GNU Prolog, ponieważ
prefix
isuffix
nie są przenośne).Prolog ma jedną interesującą, ważną zaletę w tym wyzwaniu; możesz napisać funkcję do obsługi wielu wzorców wywołań (tj. nie tylko możesz podać funkcji, aby uzyskać odpowiednie wyjście, ale możesz dać tej funkcji wyjście, aby uzyskać odpowiednie wejście). Jako takie, możemy zdefiniować funkcję, która może obsługiwać zarówno kompresję, jak i dekompresję, co prowadzi do przesłania 105-bajtowego, który definiuje funkcję,
o
która działa w obie strony. (Nawiasem mówiąc, napisałem go głównie jako dekompresor - ponieważ jest prostszy - i dostałem kompresor „za darmo”.) Ogólnie rzecz biorąc, moglibyśmy oczekiwać bardzo krótkiego programu w Prologu do tego zadania, gdyby nie fakt, że jest tak źle przy obsłudze ciągów (zarówno pod względem brakujących prymitywów, jak i pod względem prymitywów o strasznie długich nazwach).Pierwszym argumentem
o
jest krotka ciągów znaków, np"abcd"-"deab"
. Drugi argument ma formę podobną"deabcd"-4/6-4/4
; jest to dość standardowa zagnieżdżona krotka i oznacza, że ciąg jest „deabcd”, pierwszy ciąg ma długość 4 i kończy się na szóstym znaku, drugi ciąg ma długość 4 i kończy się na czwartym znaku. (Zauważ, że ciąg znaków w GNU Prolog to tylko lista kodów znaków, co sprawia, że debugowanie jest denerwujące, ponieważ implementacja domyślnie preferuje drugą interpretację.) Jeśli podaszo
jeden argument, wyświetli drugi dla ciebie (działając jako kompresor, jeśli podasz pierwszy argument, i dekompresor, jeśli podasz drugi). Jeśli podasz oba argumenty, sprawdzi, czy skompresowana reprezentacja odpowiada podanym ciągom znaków. Jeśli podasz zero argumentów, wygeneruje dane wyjściowe w następujący sposób:Powyższy opis formatu I / O jest prawie w całości tylko opisem programu; w programie nie ma zbyt wiele. Jedyną subtelnością jest podpowiedź do zlecenia oceny; musimy upewnić się, że program nie tylko korzysta ze strategii wyszukiwania, która gwarantuje zakończenie, ale także generuje możliwie najkrótszy ciąg wyjściowy.
Podczas kompresji zaczynamy od
length(C,_)
(„C
ma długość”), co jest sztuczką, której użyłem w wielu odpowiedziach Prolog i Brachylog; jeśli jest to pierwsza rzecz, którą widzi Prolog, spowoduje to, że priorytetem będzie skrócenie długościC
nad czymkolwiek innym. To gwarantuje, że mamy minimalną długośćC
. Kolejność ograniczeńs
jest starannie dobierana, aby wyszukiwanie zajęło skończony czas dla każdej możliwej długości kandydataC
;A
jest ograniczony przezC
(nie wiemyC
, ale znamy wartość docelową, jaką mamy dla jego długości),M
przezA
,U
przezA
, iL
przezU
, więc żadne z wyszukiwań nie może trwać przez nieograniczony czas.Podczas dekompresji dane są przekazywane
C
bezpośrednio przez użytkownika. To znowu zapewnia, że program będzie działał w skończonym czasie, z powodu tej samej sekwencji ograniczeń. (Ludzie, którzy są świadomi kolejności oceny Prologa, zauważą, że definicjas
jest bardzo nieefektywna podczas dekompresji; umieszczanielength(A,M)
ilength(U,L)
pierwsze byłyby szybsze, ale przejścielength(A,M)
na początek może spowodować nieskończoną pętlę podczas kompresji, ponieważ ani żadnaA
ani nieM
jest w tym czasie ograniczona .)źródło
Brachylog ,
5046 bajtówWypróbuj online!
Rozprężać:
Wypróbuj online!
Zaoszczędzono 5 bajtów dzięki @ ais523
Wyjaśnienie
Dobrą stroną języków deklaratywnych jest to, że możemy ponownie użyć tego samego kodu do kompresji i dekompresji. W związku z tym kod dla kompresji jest dokładnie taki sam jak dla dekompresji , z dodatkowym
~
na początku.To
~
mówi Brachylog aby odwrócić kolejność argumentów (czyli wykorzystanie wejścia jako wyjście i wyjście jako wejście). Ponieważ kompres nie ma~
, faktycznie wykonuje predykat w standardowej kolejności. Ponieważ dekompresja ma tylko jeden, uruchamia ją z wejściem jako wyjściem i wyjściem jako wejście.W ten sposób możemy użyć tego samego kodu (modulo ten dodatek
~
) zarówno do kompresji, jak i dekompresji: kompresja zapewnia dwa łańcuchy jako dane wejściowe i zmienną jako dane wyjściowe, a dekompresja zapewnia indeksy i łańcuch danych jako dane wyjściowe, a zmienna jako dane wejściowe .Oczywiście oznacza to również, że musimy być trochę sprecyzowani na temat naszego kodu kompresującego, aby interpreter mógł uruchomić go „wstecz”. Dlatego sama sprężarka jest nieco długa.
Oto podział kodu dla Compress (a więc i dekompresji):
źródło
Galaretka ,
5850 bajtów-1 bajt dzięki ais523 (użyj
⁾
dla dwubajtowego ciągu)To może być całkiem gra w golfa ...
Kompresja pobiera dwa argumenty łańcuchowe i zwraca listę:
[[[startA, lengthA], [startB, lengthB]], compressedString]
Dekompresja pobiera jeden argument (taką listę) i zwraca dwa * ciągi:
Nakładający się kod:
Jeden indeksowany.
* może to nie być oczywiste ze względu na niejawne formatowanie wydruku przez Jelly, więc kod w TryItOnline połączony z powyższym ma dodatkowy bajt (a
Y
na końcu), aby wstawić między nimi linię do wydruku.Zacząłem od jednego programu, który używał głębokości pierwszego (lub jedynego) argumentu, aby zdecydować między kompresją a dekompresją, ale posiadanie nieużywanego łącza w kodzie dekompresyjnym (pierwsza linia), a pojedynczy nakładający się bajt jest krótszy o siedem bajtów .
W jaki sposób?
źródło
“ṫḣ”
można zagrać w golfa o 1 bajt, używając składni Jelly dla łańcuchów 2-znakowych.