Wyzwanie

Twoim zadaniem jest zakodowanie liczby całkowitej jako ciągu znaków ASCII , a następnie pomyślne jej odkodowanie po losowym przetasowaniu tego ciągu.

Napiszecie dwa programy / funkcje , które będą nazywane Enkoderem i Dekoderem .

Enkoder

• Wejście: liczba całkowita $n$ mieści się w zakresie $[0,2^{31}-1]$ .
• Wyjście: string $s$ od ASCII znaków (niekoniecznie do druku).

Dekoder

• Dane wejściowe: losowa permutacja $s'$ ciągu $s$ .
• Dane wyjściowe: liczba całkowita $n$ .

Punktacja

Niech być maksymalna długość od s we wszystkich możliwych wartości n . Jeśli enkoder działa niedeterministycznie (co jest dozwolone, patrz poniżej), wówczas A będzie maksymalną długością s, która może wystąpić (ewentualnie ∞ ).$A$$s$$n$$A$$s$$\infty$

Niech $L_E$ jest długością kodera w bajtach i $L_D$ długościowego dekodera w bajtach.

Zatem twój wynik to $A\cdot(L_E+L_D)$ .

Zwycięstwo przyznawane jest do złożenia najniższego wyniku .

Limit czasu

Istnieje nieco arbitralny limit 1 minuty na czas wykonania zarówno Enkodera, jak i Dekodera dla pojedynczej skrzynki testowej (tj. Pojedynczej wartości $n$ ).

Celem jest uniknięcie rozwiązania, które okaże się brutalne w kodowaniu, poprzez wyliczenie wszystkich sekwencji o określonych właściwościach. Jeśli twoje rozwiązanie robi coś mądrzejszego, najprawdopodobniej będzie pasować do ograniczenia czasowego i zostanie uznane za prawidłowe. Podobnie, jeśli działa on na TIO dla niektórych losowo wybranych wartości $n$ , zostanie uznany za prawidłowy. W przeciwnym razie przetestuję to na moim komputerze, ale zauważ, że jeśli twoje rozwiązanie jest czystą brutalną siłą, prawie na pewno zawiedzie.

Zasady

• Koder i dekoder musi być napisana w tym samym języku .
• Dekoder wyjściowy musi określać prawidłowe całkowitą $n$ dla wszystkich możliwych permutacji $s'$ łańcucha $s$ zwrócony przez koder .
• Enkodera i dekodera są nie wolno informacji zakładowego w jakikolwiek sposób (np za pomocą zmiennych globalnych lub pliki).
• Wyjście enkodera nie musi być deterministyczne (to znaczy, to samo wejście $n$ może generować różne ciągi wyjściowe, jeśli enkoder jest uruchamiany wiele razy), ale dekoder musi zawsze odgadnąć poprawną liczbę całkowitą $n$ .
• Koder i dekoder może podjąć i przywrócić całkowitą $n$ w dowolny sposób (na przykład, jeśli $n=14$ jest w porządku w wejściowym być 14, "14"lub [1,4]).
• Koder może dać na wyjściu łańcuch $s$ albo drukowanie go na stdout lub przez powrót łańcuch, listę / układ znaków lub lista / tablicę liczb w zakresie $[0,127]$ ; zauważ, że Dekoder otrzyma jako dane wejściowe permutację $s$ zwróconą przez Enkoder , więc powinien zaakceptować ciąg $s'$ w tym samym formacie co $s$ .
• Standardowe luki są zabronione.
• Jeśli to możliwe, wyjaśnij, jak działa Twój kod i dlaczego wynik, który uważasz za prawidłowy.

Przykład

Załóżmy, że $n=14$ .

• Nadajnika odbiera 14jako wejścia. Może generować "qwerty".
• Dekoder odbiera permutacji "qwerty"jako dane wejściowe, na przykład "tweyqr". Musi być wyprowadzany 14(w dowolnym dogodnym formacie).

Koder może być zwracane [113,119,101,114,116,121], jak również, w przypadku których dekoder otrzymałby (na przykład) [116,119,101,121,113,114].

Zauważ, że ciąg zwracany przez Enkoder może również zawierać niedrukowalne znaki ASCII (ale zawsze w zakresie [0x00, ..., 0x7F]).

Galaretka , (17 bajtów + 18 bajtów) × długość 6 = 210 punktów

b36µỤỤ + × 3µŒ¿b3U + Ṣ

Ṣ: 3_J
Ṣ% 3Uḅ3–? Çḅ36

Wypróbuj online! (lub z dodatkowymi informacjami debugowania)

Mając okazję do rozwiązania tego wyzwania, mającego na celu spełnienie warunków zwycięstwa, pomyślałem, że byłoby interesujące, aby wybrać hipotetyczny alternatywny warunek zwycięstwa: golf golfowy, biorąc pod uwagę minimalną możliwą maksymalną długość wyniku.

Wyjaśnienie

Kodowanie

Pierwszym krokiem w kodowaniu jest przedstawienie danych wejściowych jako podstawy 36 ( b36). 36 ⁶ = 2176782336> 2147483647, więc wynik będzie maksymalnie 6 cyfr, z których każda mieści się w zakresie 0–35.

Następnie przekształcamy to w reprezentację zawierającą 6 różnych cyfr. Istnieje wiele możliwych algorytmów, ale jednym z nich jest dodanie 1 do najmniejszej cyfry, 2 do drugiej-najmniejszej, 3 do trzeciej-najmniejszej i tak dalej. Oznacza to, że jeśli dwie cyfry będą takie same, jedna z nich zostanie arbitralnie uznana za mniejszą, a zatem staną się inne; i oczywiście ten algorytm nie może spowodować, że dwie różne cyfry staną się takie same. Aby przedstawić to w Jelly, używamy Ụ(„sortuj indeksy według wartości”), aby uzyskać listę indeksów w posortowanej kolejności; Ụponownie, aby to odwrócić, skutecznie mapując każdy element oryginału do jego pozycji w posortowanej kolejności; iµ…+aby dodać oryginał do nowej listy. Wynik jest reprezentacją liczby wejściowej jako sześciu różnych cyfr w zakresie 1–41 (minimum 0 + 1, maksimum 35 + 6).

Następnie podzieliliśmy to na jeszcze jedną formę: posortowaną listę cyfr w zakresie 1–41, wraz z liczbą od 1 do 720, która reprezentuje, w której z 720 możliwych permutacji były cyfry. ( Œ¿I Ṣwyodrębnij numer permutacji i posortuj odpowiednio listę).

Na koniec konwertujemy liczbę od 1 do 720 na podstawę 3 ( b3), odwracamy ją ( U) i kodujemy sześć podstawowych 3 cyfr i sześć 1–41 cyfr, pakując je w jeden znak ASCII za pomocą odwrotnego divmod (wartość znak mod 3 to podstawowa 3 cyfra, wartość podzielona przez 3 to 1–41 cyfra). Możliwy zakres wyników to (1 × 3) + 0 = 3 co najmniej, i (41 × 3) + 2 = 125 maksymalnie, pasując do naszego zakresu ASCII. Pakowanie odbywa się za pośrednictwem ×3i +wraz z dodatkowym, µaby upewnić się, że każde polecenie działa na odpowiednim bicie danych. (Jest tu trochę sztuczki golfowej, polegającej na tym, że mnożymy przez 3 przed wyodrębnieniem permutacji; to oszczędza potrzeby wydawania bajtu na postać grupującą.)

Nawiasem mówiąc, powodem do odwrócenia liczby podstawowej 3 jest to, że może ona zawierać mniej cyfr niż liczba 1–41. (Nie może mieć więcej; najmniejsza liczba, dla której n !> 3 ⁿ jest nieco powyżej 6.) Galaretka skutecznie wstawia końcowe zera, dodając do siebie dwie liczby o różnych długościach, aby je dopasować; końcowe zera wpłynie na interpretację liczby, ale wiodące zera nie będzie, więc odwrotna jest używany w celu zapewnienia, że dodatkowe zera skończyć gdzieś, że nie będzie bałagan naszej odpowiedzi.

Rozszyfrowanie

Pierwszym krokiem w dekodowaniu jest wyodrębnienie dwóch liczb (podstawowej liczby 3 i liczby 1–41). Ich cyfry możemy łatwo odczytać za pomocą odpowiednio div ( :3) i modulo ( %3), ale jak sprawdzić, w jakiej kolejności są? Cóż, liczby 1–41 miały cyfry w posortowanej kolejności, a cyfry w odpowiednich pozycjach dwóch liczb były przechowywane w tych samych znakach; w ten sposób możemy ustalić, w jakiej kolejności numery 1–41 zostały wtasowane (patrząc na ich względne wartości) i wiemy, że cyfry liczby 3 muszą być przetasowane w ten sam sposób. W rzeczywistości, ponieważ znaki naszego kodowania ASCII są sortowane w ten sam sposób, co cyfry 1–41 (wszystkie były odrębne i mają większe znaczenie niż liczby podstawowe 3),Ṣ. Tak więc obie ekstrakcje rozpoczynają się od Ṣ, a następnie %3lub :3odpowiednio.

Podczas gdy cyfry 1–41 są nadal posortowane, mamy bardzo wygodny / zwięzły sposób powrotu do 0–35 cyfr podstawy 36; wystarczy odjąć 1 od pierwszego, 2 od drugiego, 3 od trzeciego i tak dalej. W Galaretce możemy to zrobić za pomocą _J(„odejmij indeks”).

Tymczasem w drugiej gałęzi dekodowania odwracamy cyfry liczby 3 z powrotem do porządku ( U) i przekształcamy ją z bazy 3 z powrotem w indeks permutacji za pomocą ḅ3.

Następnie możemy połączyć dwie gałęzie z œ?Ç; œ?oznacza „permute, biorąc pod uwagę ten wskaźnik permutacji”, i Çoznacza „wynik zastosowania powyższej linii”, tj. to mówi Jelly, aby uruchamiała obie linie osobno na tym samym wejściu.

Mamy teraz cyfry oryginalnego numeru, w bazie 36 (z powodu _J) i w oryginalnej kolejności (z powodu œ?), więc możemy po prostu wykonać ḅ36konwersję z bazy 36 z powrotem na jedną liczbę całkowitą.

Komentarz

TIO! powyższy link używa 312699167 jako numeru do zakodowania. Ta liczba w podstawie 36 jest [5, 6, 6, 8, 7, 35], a zatem pokazuje wszystkie aspekty kodowania: 35 testuje limit zakresu 0–127, który mamy; duplikat 6s testuje rozdzielczość identycznych cyfr w oryginalnej bazie 36; a fakt, że cyfry są prawie (ale nie do końca) posortowane, oznacza, że ​​liczba permutacji jest bardzo mała, co daje jej o wiele mniej cyfr niż podstawowa liczba 36, ​​a zatem pokazuje potrzebę odwrócenia jej przed dodaniem jej do oryginału.

To naprawdę wygodne, jak wszystkie stałe tutaj pasują do siebie. 36 ⁶ jest tylko wystarczająco wysoki, aby zmieścić 2 ³¹ , 3 ⁶ jest tylko wystarczająco wysoki, aby zmieścić 6 !, a (36 + 6) × 3 jest tylko wystarczająco wysoki, aby zmieścić się w 128 możliwościach, które mamy. (Ostatnie ograniczenie tutaj jest najmniej restrykcyjne, ponieważ moglibyśmy użyć indeksowania 0 zamiast 1-indeksowania, aby użyć znaków z zakresu 0-2. Mimo to dałoby to wystarczająco dużo miejsca, aby użyć 37 jako podstawy niż 36.)

Galaretka , ( 4 3 bajty + 6 5 bajtów) × długość 8 = 80 64 punktów

b⁴Ę

ṢŻIḅ⁴

Wypróbuj online!

Galaretka , ( 2 1 bajt + 4 3 bajty) × długość 10 = 60 40 punktów

ZA

IŻI

Wypróbuj online!

Wyjaśnienie

Rozwiązanie 1

To używa innego algorytmu niż większość innych odpowiedzi. Zaczynamy od zakodowania wartości w systemie szesnastkowym ( b⁴), podobnie jak w przypadku innych odpowiedzi, a następnie pobieramy sumę sumaryczną ( Ä). Każde wejście będzie wyraźnie dawało inny wynik (ponieważ obie te operacje są odwracalne), a biorąc pod uwagę, że kodowanie szesnastkowe będzie zawierało co najwyżej 8 cyfr, których maksimum to 7 (dla 8-tej ostatniej cyfry) i 15 (dla ostatniej do 7- ostatnie cyfry), maksymalna liczba na liście wyników wyniesie 7+ (7 × 15) = 112, mniej niż 127 wymagana przez pytanie. Dodatkowo dane wyjściowe będą koniecznie posortowane, co pozwoli nam odwrócić losowanie.

W przypadku dekodera najpierw odwracamy odtwarzanie losowe za pomocą sort ( Ṣ); następnie odwróć sumę skumulowaną, przygotowując zero ( Ż) i biorąc różnicę między kolejnymi parami ( I); następnie przekonwertuj z powrotem z funkcji szesnastkowej ( ḅ⁴).

Rozwiązanie 2

Pytanie faktycznie pozwala nam wziąć dane wejściowe jako listę (przypuszczalnie dziesiętną) cyfr, dzięki czemu możemy „oszukać”, po prostu usuwając konwersję podstawową; maksymalna liczba użyta w danych wyjściowych wyniesie wówczas 2 + (9 × 9) = 83 (faktycznie 82, ponieważ 2999999999 jest poza zakresem, więc najgorszym możliwym wejściem jest 1999999999). Wynikowe kodowanie jest dość okropne w miarę kodowania tego problemu, ale ma tę zaletę, że jest bardzo zwięzłe w generowaniu, co przeważa nad szczegółowością kodowania.

Ta odpowiedź jest tak bardzo podobna do oszukiwania, że ​​nie jest to moje podstawowe rozwiązanie tego problemu, ale wydaje się, że warto ją dodać, ponieważ technicznie jest zgodna z zasadami i daje lepszy wynik.

Komentarz

Mam na myśli kilka algorytmów, aby uzyskać długość poniżej 8, ale wydaje się mało prawdopodobne, abyś mógł wdrożyć algorytm długości 7 w ≤9 bajtach (bez oszustwa) lub ≤5 bajtach (oszustwo), więc dzięki punktacji w pytaniu, to jest prawdopodobnie najlepszym sposobem na zrobienie tego. (Mógłbym jednak spróbować rozwiązania alternatywnego wyzwania „zminimalizowania długości kodowania”, tak dla zabawy).

W przeciwieństwie do niektórych rozwiązań, użycie 16 jako podstawy tutaj nie jest krytyczne; istnieje wiele innych liczb, które działałyby dla rozwiązania o długości 8 (np. 18). Wybrałem 16 dla pierwszego rozwiązania po prostu dlatego, że Jelly ma jednobajtowy sposób na przedstawienie tego, a inne realne bazy musiałyby zużywać wiele bajtów z programu. Oczywiście drugie rozwiązanie wymaga użycia 10 jako podstawy, aby wykorzystać lukę.

Dzięki @Dennis za wskazanie niektórych nowszych poleceń Jelly, które sprawiły, że ten algorytm jest jeszcze prostszy do napisania.

Język programowania Szekspira , 10 * (264 + 494) = 8650 7910 7580

Koder: 264 bajty

,.Ajax,.Ford,.Act I:.Scene I:.[Exeunt][Enter Ajax and Ford]Ajax:Open mind.Be you nicer zero?You be the sum ofyou the product ofthe sum ofI a big big pig the sum ofa big big big big cat a big big pig.If soSpeak thy.Ford:You are the sum ofyou a cat.If soLet usAct I.

Wypróbuj online!

Dekoder: 494

,.Ajax,.Ford,.Page,.Act I:.Scene I:.[Exeunt][Enter Ajax and Ford]Ajax:Open mind.Is you nicer a pig?If soRemember you.If soLet usAct I.Scene V:.Ford:Remember I.Ajax:Recall.Is you worse the sum ofPage twice the sum ofa big big cat a cat?If soYou be the difference betweenyou Page.If soOpen heart.If notlet usScene V.Scene X:.Ford:Recall.Ajax:Be I nicer zero?If soRemember I.If soLet usScene X.[Exit Ajax][Enter Page]Ford:You be the sum ofyou twice twice the sum ofa big big cat a pig.Let usAct I.

Wypróbuj online!

To była rzecz.

Koder koduje każdą cyfrę jako cyfrę plus indeks cyfry razy dwanaście. Dekoder przechowuje wszystkie dane wejściowe w pamięci Forda, a następnie zapętla się nad licznikiem, wysyłając i usuwając każdą cyfrę niższą niż licznik * 12 + 10.

Wyjaśnienie:

Enkoder

,.Ajax,.Ford,.Act I:.Scene I:.      Boilerplate introducing the two characters
[Exeunt][Enter Ajax and Ford]       Enter the two characters Ajax and Ford
                                    Ford will be handling the input
                                    Ajax will be the counter
Ajax:Open mind.                     Set Ford to the next character of input
Be you nicer zero?                  Check if it is EOF
You be the sum of                   Set Ford to the sum of 
    you                             His original value (48 to 58)
    the product of                 
          the sum of               
              I                     Ajax's value
              a big big pig         Minus 4 (this handles the offset of 48)
          the sum of                Multiplied by
              a big big big big cat 2^4
              a big big pig.        + -2^2 = 12
                                    This essentially sets Ford to (F+12*(A-4))
If soSpeak thy.                      If not EOF, print Ford's value
Ford:You are the sum ofyou a cat.   Increment Ajax's value
If soLet usAct I.                   If not EOF, Repeat again.

Dekoder

,.Ajax,.Ford,.Page,.Act I:.Scene I:.  Boilerplate introducing three characters
                                      Ajax is the spare stack
                                      Ford is the storage stack
                                      Puck is the counter, increasing by 12
[Exeunt][Enter Ajax and Ford]            Enter Ajax and Ford onto the stage
Ajax:Open mind.                          Get the next character of input
Is you nicer a pig?                      If not EOF
If soRemember you.                         Store the value in Ford's memory
If soLet usAct I.                          And repeat the loop
Scene V:.                                Otherwise move to the next scene
Ford:Remember I.                         Store Ford's value (initially -1 from EOF) in Ajax's memory
Ajax:Recall.                             Get the next value from Ford's memory
Is you worse the sum of                  Is the value smaller than
        Puck                                  Puck's value
        twice the sum ofa big big cat a cat?  + 10 ?
                                              i.e. is it the next digit?
If soYou be the difference betweenyou Puck.   If so, subtract Puck's value from Ford
If soOpen heart.                              And print Ford's value
If notlet usScene V.                     If that was not the digit, repeat
Scene X:.
Ford:Recall.                             Get the next value from Ajax's memory
Ajax:Be I nicer zero?                    Until the -1
If soRemember I.                         Returning the values to Ford's memory
If soLet us Scene X.                     Repeat until Ajax's memory is exhausted
[Exit Ajax][Enter Page]                  Swap Ajax and Page
Ford:You be the sum of                   Set Puck's value to
              you                        Puck +   
              twice twice the sum of     2*2*(
                           a big big cat      4
                           a pig.             -1) = 12
Let usAct I.                             And start from the beginning again, having removed one number

Python 2.7, 31 * (52 + 37) = 2759

Koder ( 69 52 bajtów):

lambda n:[chr(i)if n&(1<<i)else""for i in range(32)]

Dekoder ( 41 37 bajtów):

lambda s:sum([1<<(ord(c))for c in s])

Przechowuje wszystkie niezerowe bity w liczbie wejściowej jako wartości ascii. Wartość znaku ascii przechowuje pozycję ustawionego bitu. Na przykład wartość „a” oznacza, że ​​ustawiony jest 97 bit.

Kilka ulepszeń, dzięki @ Delfad0r

Wypróbuj online!

Stax , wynik 8 × (10 + 9) = 152

Enkoder, 10 bajtów

Ç·MÉJ'♀τ│½

Uruchom i debuguj

16|E{i16*+m Full program, implicit input
16|E        Get hexadecimal digits
    {     m Map:
     i16*+    Add 16 * loop index
            Implicit output as string

Koder wysyła ciąg w rosnącej kolejności.

Dekoder, 9 bajtów

üL∟n╫k∞‼9

Uruchom i debuguj

o{16%m16|E Full program, implicit input
o          Sort string
 {16%m     Module each element by 16
      16|E Interpret as array of hex digits

05AB1E , 8 maksymalna długość * (8 + 7) bajtów = 120

Enkoder (8)

hεHN16*+

Wypróbuj online!

Dekoder (7)

{16%hJH

Wypróbuj online!

Używa tej samej techniki co wastl i Jonathan .

Python 3 , 8 * (45 + 38) = 664

Koder (45 bajtów):

lambda n:[16*i+(n>>4*i)%16 for i in range(8)]

Dekoder (38 bajtów):

lambda l:sum(x%16<<x//16*4 for x in l)

Wypróbuj online!

JavaScript (ES6), 8 * (40 + 32) = 576

Koder wyprowadza tablicę $0$ do $8$liczby całkowite. Dekoder ma taki sam format jak wejście.

Enkoder (40 bajtów)

E=(n,k=0)=>n?[k|n&15,...E(n>>4,k+16)]:[]

Dekoder (32 bajty)

s=>s.map(c=>s|=c%16<<(c/4&~3))|s

Próbny

Wypróbuj online!

W jaki sposób?

Dane wejściowe są podzielone na 8 bloków po 4 bity, a każdy blok jest kodowany 1 z 16 możliwych znaków. Najbardziej znaczący bit ostatniego bloku nigdy nie jest ustawiony.

       3222222222211111111110000000000
bit:   0987654321098765432109876543210
       \_/\__/\__/\__/\__/\__/\__/\__/
block:  7  6   5   4   3   2   1   0

block #0 is encoded with char. 00 to 0F (NUL to SI)
block #1 is encoded with char. 10 to 1F (DLE to ES)
block #2 is encoded with char. 20 to 2F (' ' to '/')
block #3 is encoded with char. 30 to 3F ('0' to '?')
block #4 is encoded with char. 40 to 4F ('@' to 'O')
block #5 is encoded with char. 50 to 5F ('P' to '_')
block #6 is encoded with char. 60 to 6F ('`' to 'o')
block #7 is encoded with char. 70 to 77 ('p' to 'w')

Galaretka , (8 + 9) bajtów * 8 maksymalna długość = 136

b⁴+J’Ɗ⁴¡

Enkoder (stopka formatuje listę tak, jak by ją wyrazić Python)

Ṣ_J‘Ɗ⁴¡ḅ⁴

Dekoder

Teoretycznie możliwe jest uzyskanie maksymalnej długości sześciu, czy można to zrobić w 22 bajtach lub mniej?

Od tego czasu jest to niemożliwe przy maksymalnej długości pięciu $\sum_{i=0}^{i=5}\binom{127+i}{127}=321402081< 2^{31}-1$

W jaki sposób?

Od $2^{31}-1$jest kodowalny jako 8 cyfr szesnastkowych ( 7ffffffflub [7,15,15,15,15,15,15,15]) możemy następnie dodać liczony od zera indeks każdej cyfry szesnastkowej pomnożonej przez 16, aby zapewnić, że taka konwersja jest zawsze posortowana, zachowując nawet najdalszą z prawej strony wartość (tj [7,15,15,15,15,15,15,15] + [0,16,32,48,64,80,96,112] = [7,31,47,63,79,95,111,127].). Dekodowanie następnie odwraca ten sam proces.

Enkoder :

b⁴+J’Ɗ⁴¡ - Link: integer, n    e.g. 1234
 ⁴       - literal 16               16          
b        - convert to base          [4,13,2]
       ¡ - repeat...
      ⁴  - ...16 times:
     Ɗ   -   last 3 links as a monad:
   J     -     range of length        [1,2,3]     iter 2    iter 3    ...  iter 16
  +      -     add                    [5,15,5]   [5,16,7]   [5,17,9]  ...  [5,30,35]
    ’    -     decrement              [4,14,4]   [4,15,6]   [4,16,8]  ...  [4,29,34]
         -                                                                 [4,29,34]

Dekoder :

Ṣ_J‘Ɗ⁴¡ḅ⁴ - Link: list of integers   e.g. [29,34,4]
Ṣ         - sort                          [4,29,34]
      ¡   - repeat...
     ⁴    - ...16 times:
    Ɗ     -   last 3 links as a monad:
  J       -     range of length           [1,2,3]
 _        -     subtract                  [3,27,31]   [3,26,29]   [3,25,27]  ...  [3,12,1]
   ‘      -     increment                 [4,28,32]   [4,27,30]   [4,26,28]  ...  [4,13,2] 
        ⁴ - literal 16                    16
       ḅ  - from base                     1234

Język programowania Szekspira , 31 * (472 + 383 379 344) = 26505 26381 25296

Poprzedni wynik: 16909322 * (246 + 217) = 7829016086

To wciąż bardzo wysoka wartość, ale jest to najniższa wartość, o której mogę teraz myśleć.

Enkoder:

,.Ajax,.Ford,.Act I:.Scene I:.[Enter Ajax and Ford]Ajax:Remember a pig.Ford:Listen tothy.Scene V:.Ajax:Remember the remainder of the quotient betweenI a big cat.Ford:You be the quotient betweenyou a big cat.Be you nicer zero?If solet usScene V.Remember a pig.Scene X:.Ajax:Recall.Ford:Am I worse zero?If notremember I.If notlet usScene X.Ajax:You zero.Scene L:.Ford:Recall.Ajax:You be the sum ofyou a cat.Am I nicer zero?If sospeak thy.Am I worse zero?If notlet usScene L.

Wypróbuj online!

Dekoder:

,.Ajax,.Ford,.Page,.Act I:.Scene I:.[Exeunt][Enter Ajax and Ford]Ajax:You cat.Ford:Open mind.Remember the sum ofyou I.Scene V:.Ajax:Am I nicer a cat?If soyou be twice you.Ford:If soyou be the sum ofyou a pig.If solet usScene V.[Exit Ford][Enter Page]Page:Recall.Ajax:Am I worse a cat?If notyou be the sum ofyou Ford.If notlet usAct I.Open heart

Wypróbuj online!

Zasadniczo, jeśli ciąg zawiera znak z kodem ASCII (n + 1), ustawiana jest n-ta cyfra binarna.

Python 3, (208 bajtów + 200 bajtów) * 6 długość = 2448

Wypróbuj online!(zawiera oba, dodatkowy bajt to nowa linia między nimi).

-4 bajty (wynik -24) dzięki wykorzystaniu pustej listy (co pozwoliło rozpocząć więcej rzeczy od 0)

Koder (208 bajtów)

def E(n,h=128):
    T=lambda n,d:n*T(n+1,d-1)//d if d>1else d and n or 1
    d=l=0
    s=[]
    while n>=T(h,d):
        n-=T(h,d)
        d+=1
    for i in range(d):
        while n>=T(h-l,d+~i):
            n-=T(h-l,d+~i)
            l+=1
        s+=[l]
    return s

Dekoder (200 bajtów)

def D(s):
    T=lambda n,d:n*T(n+1,d-1)//d if d>1else d and n or 1
    s.sort()
    l=0
    d=len(s)
    n=sum(T(128,D)for D in range(d))
    for i in s:
        for j in range(l,i):
            n+=T(128-j,d-1)
        l=i
        d-=1
    return n

Obserwacje:

• Tasowanie można bezstratnie odwrócić w przypadku ściśle nie rosnących (tj. Posortowanych) list.

• Ściśle rosnące listy numeryczne o tej samej długości można całkowicie uporządkować (tak jak w Pythonie).

• Możemy zdefiniować, że listy są najpierw uporządkowane według długości, aby utworzyć całkowitą kolejność wszystkich posortowanych list.

• Możemy utworzyć indeksowalną sekwencję tych list, jeśli zdefiniujemy, że jedynymi prawidłowymi wartościami na liście są liczby całkowite od 0do 127włącznie (tj. Istnieje skończona liczba prawidłowych list o długości L).

Strategia:

• Koder: Biorąc pod uwagę liczbę N, znajdź Nprawidłową listę, która nie jest rosnąca.

• Dekoder: Biorąc pod uwagę (przetasowaną) prawidłową listę, posortuj ją i zwróć jej indeks w sekwencji prawidłowych list.

Wspólne objaśnienie kodu:

• T=lambda n,d:n*T(n+1,d-1)//d if d>1else d and n or 1

• Oblicz liczbęn th d-simplex

  • Bo d=0zawsze1

  • Dla d=1, n(liczba kropek w linii kropek o długości n)

  • dla d=2,$\sum_{i=1}^{n} i$, (liczba kropek w trójkącie kropek o długości boku n)

  • dla d=3,$\sum_{j=1}^n \sum_{i=1}^{j} i$, (liczba kropek w czworościanie kropek o długości boku n)

Objaśnienie enkodera:

• def E(n,h=128): d=l=0, s=[]

• nto liczba wejściowa, hto „wysoka wartość” (tj. najwyższa dozwolona liczba + 1), dto długość, jaką będzie wyjście, sto wynik, lto „niska wartość” (od 0, wyjaśnione później)

• while n>=T(h,d):, n-=T(h,d),d+=1

• Istnieją T(h,d)prawidłowe dlisty długości , a nasze obliczenia są łatwiejsze, jeśli njest indeksem względem listy [0]*d(w indeksie 0) zamiast faktycznego indeksu, więc nodpowiednio zmniejszamy . To również dostosowuje d(długość), aby była poprawna dla podanego n.

• for i in range(d):

• Skutecznie: „dla i+1numeru th na liście”

  • Tutaj wyjaśnię l„niską wartość”

  • Po umieszczeniu numeru na liście, nie może być on umieszczony na liście nie mniejszej niż liczba (aby zachować porządek), podobnie ljak ostatni numer, który został dodany do listy.

  • while n>=T(h-l,d+~i):, n-=T(h-l,d+~i),i+=1

  • Jeśli njest za duży, aby go zakodować lprzy tej „cyfrze”, dostosuj nodpowiednio i zwiększajl

  • s+=[l]

  • Zakoduj nza pomocą ltej „cyfry”.

  • Na początku mamy hopcje, które „cyfrę” wprowadzić, ale kiedy wstawimy „cyfrę” (do której jest przypisana l), ograniczamy się do h-lopcji na następną „cyfrę”.

  • Początkowo istniały T(h,d)prawidłowe listy, ale dodaliśmy „cyfrę” l, zmniejszając liczbę „cyfr” pozostałych do d-1i liczbę ważnych następnych „cyfr” do h-l, więc liczba prawidłowych list po tym wynosiT(h-l,d-1)

Objaśnienie dekodera:

• def D(s):, s.sort(),l=0 ,d=len(s)

• sjest (tasowaną) listą wejściową, więc s.sort()jest; lto „niska wartość” ( h„wysoka wartość” to po prostu literały 128s w kodzie, aby zapisać bajty), nto liczba wyjściowa, dto długość.

• n=sum(T(128,D)for D in range(d))

• Dostosuj ndo punktu w sekwencji[0]*length

• for i in s:

• Dla każdej cyfry:

  • for j in range(l,i):, n+=T(128-j,d-1)

  • Dostosuj ndo punktu w sekwencji[...prevdigits, thisdigit, 0...]

    • l=i: Ustaw „niską wartość” na najnowszą cyfrę

    • d-=1: Zmniejsz długość, ponieważ użyliśmy cyfry

• return n: Po ndostosowaniu dla wszystkich cyfr jest to poprawna liczba; zwróc to.

Przepraszam, jeśli nie jest to jasne, ale oto moja oryginalna wersja debugowania bez klucza. Wypróbuj online! , który nie korzysta z pustej listy, więc jest 1 wyłączony ze wszystkich liczb użytych w tej wersji

Rubin , (36 + 29 bajtów) * 8, wynik 520

Kodować:

->n{(0..7).map{|x|(n>>x*=4)%16+x*4}}

Wypróbuj online!

Rozszyfrować:

->a{a.sum{|x|x%16<<(x/4&28)}}

Wypróbuj online!

Jak to działa:

Liczba jest kodowana przy użyciu 4-bitowych fragmentów i 3-bitowego indeksu.

Dekoder pobiera tablicę wejściową i ponownie umieszcza każdy skubek na swoim miejscu.

Węgiel drzewny , wynik 10 * (10 + 15) = 250.

Wykorzystuje dziesiętny; poprzednie bazowe rozwiązanie oparte na 16 uzyskało 328 296 264.

Może generować znaki niedrukowalne. W szczególności trudno jest wprowadzić postać 10 na węgiel drzewny.

Enkoder, 10 bajtów:

⭆⮌Ｓ℅⁺Ｉι×χκ

Wypróbuj online! Link jest do pełnej wersji kodu.

Dekoder, 15 bajtów:

ＩΣＥＳ×﹪℅ιχＸχ÷℅ιχ

Wypróbuj online! Link jest do pełnej wersji kodu.

Wersja wykorzystująca wyniki liczb całkowitych 360 296 (podstawa 16; liczba dziesiętna to 310):

Koder, 19 bajtów:

ＮθＩＥ⁸⁺﹪÷θＸ¹⁶ι¹⁶×¹⁶ι

Wypróbuj online! Link jest do pełnej wersji kodu.

Dekoder, 18 bajtów:

ＩΣＥＥ⁸Ｎ×﹪ι¹⁶Ｘ¹⁶÷ι¹⁶

Wypróbuj online! Link jest do pełnej wersji kodu.

Wersja wykorzystująca znaki do wydrukowania uzyskała wynik 360 (było 416 384 368 w bazie 16):

Koder, 19 bajtów:

⭆⮌Ｓ℅⁺Ｉι×χ⁺κ×⁵⊕׳÷κ⁵

Wypróbuj online! Link jest do pełnej wersji kodu.

Dekoder, 17 bajtów:

Ｆθ⊞υ⌈Φθ¬№υκ⭆υ﹪℅ιχ

Wypróbuj online! Link jest do pełnej wersji kodu.

Brachylog , 17 + 18 bajtów * 8 długość = 280

Enkoder:

ḃ₁₆I∧7⟧₁;Iz₁~ḃ₁₆ᵐ

Dekoder:

ḃ₁₆I∧7⟧₁;Iz₁~ḃ₁₆ᵐp

P można dodać na końcu enkodera bez efektu. Dekoder jest uruchamiany przez umieszczenie wyniku (losowego) jako wyjścia i uzyskanie oryginalnej liczby na wejściu.

Gdyby istniał (prawidłowo wdrożony) predykat sumarycznych, wynik mógłby spaść do 20

Wypróbuj online!

05AB1E , wynik: (2 + 2 bajty ) * 11 maksymalna długość = 44

Enkoder (2 bajty ):

.¥

Wypróbuj online.

Dekoder (2 bajty ):

{¥

Wypróbuj online.

Wejście enkodera i wyjście dekodera to lista cyfr.

Port drugiej odpowiedzi galaretki @ ais523 .

Wyjaśnienie:

.¥    # Undelta (automatically prepends a 0)
      #  i.e. [3,0,4,7,8,2,0,1,9] → [0,3,3,7,14,22,24,24,25,34]

{     # Sort
      #  i.e. [14,7,22,25,24,3,0,24,34,3] → [0,3,3,7,14,22,24,24,25,34]
 ¥    # Deltas
      #  i.e. [0,3,3,7,14,22,24,24,25,34] → [3,0,4,7,8,2,0,1,9]

Ponieważ .¥wstawia zero na wyjście, długość wyjścia to długość wejścia + 1. Od$2^{31}-1$ ma długość 10 cyfr, maksymalna długość wyniku to 11.

Gol> <> , 8 * (14 + 13) = 216

Koder Wypróbuj online! , 14 bajtów:

I8FfPSD8*L+o|;

Dekoder Wypróbuj online! , 13 bajtów:

iEh8SD4*2$X*+

Ponieważ może to generować niedrukowalne znaki ascii, a tym samym zadzierać z dekoderem, istnieje teraz wersja wykorzystująca liczby na wyjściu / wejściu:

Koder Wypróbuj online! , 14 bajtów:

I8FfPSD8*L+N|;

Dekoder Wypróbuj online! , 13 bajtów:

IEh8SD4*2$X*+

Kodowanie:

Kodowanie polega na rozbiciu podanej liczby na 8 x 4-bitowe fragmenty. Te fragmenty są następnie przesuwane w prawo o 3 bity, a pierwotna lokalizacja fragmentu jest dołączana na końcu jako liczba od 0 do 7. W ten sposób kodowanie wygląda następująco:

0AAAABBB
 |__|    -> the original part of the number
     |_| -> the position of the chunk inside the original number 0 = LSB and 7 = MSB

Perl 6 , 10 * (10 + 12) = 340 220

Enkoder:

{^@_ Z~@_}

Dekoder:

{.sort X%10}

Wypróbuj online!

Funkcja enkodera zamyka każdą cyfrę indeksem 0 liczby. Następnie koder sortuje listę liczb i otrzymuje modulo o 10, innymi słowy druga cyfra liczby.

Łącznie jest to 10, ponieważ to maksymalna długość 2 ³¹ -1.

Haskell , 10 * (23 + 51) = 740

Oto program, który koduje, tasuje, dekoduje i sprawdza wartości: Wypróbuj online!

Koder, 23 bajty

zipWith((+).(10*))[0..]

Wypróbuj online!

Dekoder, 51 bajtów

map snd.sortOn fst.map(`divMod`10)
import Data.List

Wypróbuj online!

Wyjaśnienie

Ponieważ wolno nam używać danych wejściowych jako cyfr dziesiętnych, użyjemy tego. Koder odwzorowuje każdą występującą cyfrę 10*index + digit, pamiętaj, że wszystkie digits będą [0..9]obecne, abyśmy mogli odwrócić powyższe za pomocądivMod . Po przywróceniu indeksów i cyfr jest to tylko kwestia sortowania według wskaźników i pozbycia się ich.

Rozwiązanie powinno działać dla wartości do $2^{31} - 1 = 2147483647$ który ma 10 cyfr, więc otrzymamy maksymalny punkt kodowy $9 \cdot 9 = 81 < 128$. Również każda cyfra zostanie przekonwertowana na „znak”, więc otrzymamy maksymalną długość 10.

Łuska , 10 * (7 + 8) = 150

Prosty port mojego rozwiązania Haskell tylko z tą obserwacją $10 \cdot 9 = 90 < 128$(Łuska Njest oparta na 1):

Enkoder, 7 bajtów

zo+*10N

Wypróbuj online!

Dekoder, 8 bajtów

m→Ö←m‰10

Wypróbuj online!

APL (Dyalog Unicode) ,$L_E+L_D=36; A=8 \rightarrow 288$.

d←{16⊥n-16×⍳≢n←⍵[⍋⍵]}
e←(⊢+16×⍳∘≢)16⊥⍣¯1⊢

Wypróbuj online! (zawiera 5 dodatkowych bajtów dla przypisań i nowego wiersza).

Używa ⎕IO←0

W jaki sposób:

(⊢+16×⍳∘≢)16⊥⍣¯1⊢ ⍝ Encoder; input 1234
          16⊥⍣¯1⊢ ⍝ Convert input to base 16 → 4 13 2
      ⍳∘≢          ⍝ [0..length of the list-1] → 0 1 2
   16×             ⍝ times 16 → 0 16 32
 ⊢+                ⍝ plus the original list → 4 29 34

{16⊥n-16×⍳≢n←⍵[⍋⍵]} ⍝ Decoder; input ⍵ → 34 4 29
              [⍋⍵]  ⍝ Grade ⍵ up → 2 0 1
             ⍵      ⍝ Index ⍵ with that list → 4 29 34
           n←       ⍝ assign that to n
      16×⍳≢         ⍝ 16×[0..length(n)-1] → 0 16 32
    n-              ⍝ subtract that from n → 4 13 2
 16⊥                ⍝ Decode from base 16 → 1234

PHP, 8 * (44 + 53) = 776

enkoder, 44 bajty:

for(;$n=&$argn;$n>>=4)echo$n&15|16*$i++," ";

wyświetla listę liczb całkowitych oddzielonych spacjami. Uruchom jako potok z -nR.

maksymalnie 8 bajtów z 4 bitami danych (dolny skrawek) i 3 bity wagowe (górny skrawek).

Po prostu: umieść
każdą cyfrę szesnastkową we własnym znaku i użyj górnej połowy bajtu, aby zapisać pozycję cyfry.

przykład:

1457893891( 0x56e5b203) Zmieni się
0x03, 0x10, 0x22, 0x3b, 0x45, 0x5e, 0x66, 0x75
→3 16 34 59 69 94 102 117

dekoder, 53 bajty:

while($i++<8)$n+=(15&$x=$argv[$i])<<($x>>4)*4;echo$n;

lub

while($i++<8)$n+=(15&$x=$argv[$i])<<($x/4&~3);echo$n;

lub

for(;$i<9;$x=$argv[++$i])$n+=$x%16<<($x/4&~3);echo$n;

weź liczby całkowite z argumentów wiersza poleceń. Uruchom z -nr.

Wypróbuj je online .

Python 2 , 10 * (68 + 54) = 1220

e=lambda n:"".join(chr(int(`i`+j))for i,j in enumerate(`n`)if j<'L')
d=lambda s:int("".join(`ord(c)%10`for c in sorted(s)))

Wypróbuj online!

EDYCJA: Dzięki Jo King za wskazówki - nie jestem pewien, dlaczego przesunąłem się o 32, z perspektywy czasu.

Koduje pozycję i wartość każdego miejsca jako pojedynczy znak, zaczynając od [spacja] (pozycja 0, wartość 0) bajt NUL 0x0.

Dekoduje:

• sortowanie ciągu (Python sortuje znaki według ich wartości porządkowej)
• konwertuje każdy znak na jego wartość porządkową
• pobiera ostatnią cyfrę każdej liczby całkowitej porządkowej
• łączy liczby całkowite w ciąg
• konwertuje połączony ciąg z powrotem na int

C (gcc) , 10 * 112 = 1120

c,i;e(i,s)char*s;{for(c=1;i;c+=10,i/=10)*s++=c+i%10;*s=0;}
d(char*s){for(i=0;c=*s++;i+=--c%10*pow(10,c/10));s=i;}

Wypróbuj online!

Mam zmienne globalne, ale tak naprawdę nie przekazują żadnych informacji między dwiema funkcjami. Deklaracja zmiennej dla cjest używana w obu funkcjach, oszczędzając mi 2 bajty długości kodu.

Wersja, która używa drukowalnego ASCII tylko dla kary 3 5 bajtów, jest tutaj:

c,i;e(i,s)char*s;{for(c=32;i;c+=10,i/=10)*s++=c+i%10;*s=0;}
d(char*s){for(i=0;c=*s++;i+=(c-=32)%10*pow(10,c/10));s=i;}

Dzięki @ceilingcat za poprawę o 70 punktów.