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 compressoraz decompressz poniższą specyfikacją:

^{* Prawdopodobnie nie używaj w kodzie produkcyjnym.}

compress

compresspobiera dwa ciągi w dowolnym dogodnym formacie i nakłada się na nie w jak największym stopniu. To jest szwracany 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

decompressoblicza 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 compressprzykł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 compressjest c=abcdi kodem decompressjest 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 compressi decompress 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.
• compressi decompresspowinien być w stanie obsługiwać ciągi znaków zawierające dowolne drukowalne znaki ASCII, a także wszystkie znaki użyte do zdefiniowania compressi decompress.
• Indeksy mogą być zerowane lub indeksowane jednokrotnie.
• Twoje programy lub funkcje nie muszą być tak naprawdę nazwane compressi decompress.

GNU Prolog, 105 punktów

s(U,L/M,C):-prefix(A,C),length(A,M),suffix(U,A),length(U,L).
o(A-B,C-X-Y):-length(C,_),s(A,X,C),s(B,Y,C).

(Wymaga to GNU Prolog, ponieważ prefixi suffixnie 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ę, októ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 ojest 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 podaszojeden 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:

| ?- o(X,Y).
X = []-[]
Y = []-0/0-0/0 ? ;

X = []-[]
Y = [_]-0/0-0/0 ? ;

X = []-[A]
Y = [A]-0/0-1/1 ? ;

…many lines later…

X = [A]-[B,A,C]
Y = [B,A,C]-1/2-3/3 ? ;

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,_)(„ Cma 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ści Cnad czymkolwiek innym. To gwarantuje, że mamy minimalną długość C. Kolejność ograniczeń sjest starannie dobierana, aby wyszukiwanie zajęło skończony czas dla każdej możliwej długości kandydata C; Ajest ograniczony przez C(nie wiemy C, ale znamy wartość docelową, jaką mamy dla jego długości), Mprzez A, Uprzez A, i Lprzez U, więc żadne z wyszukiwań nie może trwać przez nieograniczony czas.

Podczas dekompresji dane są przekazywane Cbezpoś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 definicja sjest bardzo nieefektywna podczas dekompresji; umieszczanie length(A,M)i length(U,L)pierwsze byłyby szybsze, ale przejście length(A,M)na początek może spowodować nieskończoną pętlę podczas kompresji, ponieważ ani żadna Aani nie Mjest w tym czasie ograniczona .)

Brachylog , 50 46 bajtów

{Ċ∧Lċ₂l∧Lgj:?z{tT∧?h~cṪhlI∧ṪbhTl:I+-₁:I↔}ᵐ:L}

Wypróbuj online!

Rozprężać:

~{Ċ∧Lċ₂l∧Lgj:?z{tT∧?h~cṪhlI∧ṪbhTl:I+-₁:I↔}ᵐ:L}

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):

{……………………………………………………………………}   Call that predicate the normal way (with swapped arguments
                                 for decompress)
   Ċ                           Input has two elements
   ∧Lċ₂l                       L is a string of any length (measuring its length forces it to
                                 take a specific length from 0 to +inf)
   ∧Lgj                        The list [L,L]
       :?z                     The list [[L, First elem of Input],[L,second elem of input]]
          {………………………………}ᵐ:L    Final output is the [M,L] where M is the result of mapping
                                 the predicate below on both elements of the zip
           tT                  The second element of the input is T
           ∧?h~cṪ              Anticoncatenate the first element of the input into [A,B,C]
           hlI                 I = length(A)
           ∧ṪbhTl:I+-₁         J = length(T) + I - 1
           :I↔                 Output = [I,J]

Galaretka , 58 50 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]

w³;w⁴$
0;J⁸ḣ;€
ç;ç@ÑẠ$ÐfLÐṂṪµ³,⁴L€ż@Ñ,

Dekompresja pobiera jeden argument (taką listę) i zwraca dwa * ciągi:

,
⁾ṫḣżFv
Ḣç€Ṫ

Nakładający się kod:

w³;w⁴$
0;J⁸ḣ;€
ç;ç@ÑẠ$ÐfLÐṂṪµ³,⁴L€ż@Ñ,
⁾ṫḣżFv
Ḣç€Ṫ

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 Yna 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?

ç;ç@ÑẠ$ÐfLÐṂṪµ³,⁴L€ż@Ñ, - Compression: stringA, stringB
ç                       - call the last link (2) as a dyad
  ç@                    - call the last link (2) as a dyad with reversed arguments
 ;                      - concatenate (gives all overlapping strings)
       Ðf               - filter keep:
      $                 -     last two links as a monad
    Ñ                   -         call the next link (1) as a monad
     Ạ                  -         All? (no zeros exist in that result)
          ÐṂ            - filter keep with minimal:
         L              -     length
            Ṫ           - tail (for when more than one exists)
             µ          - monadic chain separation (we now have the compressed string)
              ³,⁴       - [stringA, stringB]
                 L€     - length of €ach
                   ż@   - zip with reversed arguments with
                     Ñ  - next link (1) as a monad with the compressed string
                      , - paired with the compressed string

J0;⁸ḣ;€ - Link 2, possible overlaps: stringL, stringR
J       - range(length(stringL)) - [1,2,...,length(stringL)]
 0;     - zero concatenate       - [0,1,2,...,length(stringL)]
   ⁸    - stringL
    ḣ   - head (vectorises)      - [empty string, first char, first two, ..., stringL]
     ;€ - concatenate €ach with stringR

w³;w⁴$ - Link 1, substring indexes: stringX
w³     - first index of first program argument in stringX or 0 if not found
  ;    - concatenated with
     $ - last two links as a monad
   w⁴  -     first index of second program argument in stringX or 0 if not found

Ḣñ€Ṫ - Decompression: [[[startA, lengthA], [startB, lengthB]], compressedString], ?
Ḣ    - head - [[startA, lengthA], [startB, lengthB]]
   Ṫ - tail - compressedString
 ç€  - call the last link (2) as a dyad for €ach of the left list
     -- extra Y atom at TIO joins the resulting list of two strings with a line feed.

⁾ṫḣżFv - Link 2, extract a substring: [start, length], string
⁾ṫḣ    - string "ṫḣ"
   ż   - zip with [start, length] to yield [['ṫ', start],['ḣ', length]]
    F  - flatten, making a list of characters
     v - evaluate as Jelly code with the string as an argument
       - this evaluates as string.tail(start).head(length) yielding the substring

, - Link 1: only here to make an overlap with the compression program.