Celem tego wyzwania jest znalezienie niemożliwie krótkiej realizacji następującej funkcji p, w wybranym przez ciebie języku. Oto kod C implementujący go (zobacz ten link TIO, który również drukuje jego wyniki) i zawierającą go stronę wikipedii .

unsigned char pi[] = {
    252,238,221,17,207,110,49,22,251,196,250,218,35,197,4,77,
    233,119,240,219,147,46,153,186,23,54,241,187,20,205,95,193,
    249,24,101,90,226,92,239,33,129,28,60,66,139,1,142,79,
    5,132,2,174,227,106,143,160,6,11,237,152,127,212,211,31,
    235,52,44,81,234,200,72,171,242,42,104,162,253,58,206,204,
    181,112,14,86,8,12,118,18,191,114,19,71,156,183,93,135,
    21,161,150,41,16,123,154,199,243,145,120,111,157,158,178,177,
    50,117,25,61,255,53,138,126,109,84,198,128,195,189,13,87,
    223,245,36,169,62,168,67,201,215,121,214,246,124,34,185,3,
    224,15,236,222,122,148,176,188,220,232,40,80,78,51,10,74,
    167,151,96,115,30,0,98,68,26,184,56,130,100,159,38,65,
    173,69,70,146,39,94,85,47,140,163,165,125,105,213,149,59,
    7,88,179,64,134,172,29,247,48,55,107,228,136,217,231,137,
    225,27,131,73,76,63,248,254,141,83,170,144,202,216,133,97,
    32,113,103,164,45,43,9,91,203,155,37,208,190,229,108,82,
    89,166,116,210,230,244,180,192,209,102,175,194,57,75,99,182,
};

unsigned char p(unsigned char x) {
     return pi[x];
}

Co jest p

pjest składnikiem dwóch rosyjskich standardów kryptograficznych, mianowicie funkcji skrótu Streebog i szyfru blokowego Kuźnyechik . W tym artykule (i podczas spotkań ISO) projektanci tych algorytmów twierdzili, że wygenerowali tablicę pi, wybierając losowe permutacje 8-bitowe.

Implementacje „niemożliwe”

Jest permutacji na 8 bitach. Dlatego dla danej losowej permutacji program, który ją implementuje, nie powinien wymagać mniej niż 1683 bitów.$256! \approx 2^{1684}$

Znaleźliśmy jednak wiele nienormalnie małych implementacji (które wymieniliśmy tutaj ), na przykład następujący program C:

p(x){unsigned char*k="@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8",l=0,b=17;while(--l&&x^1)x=2*x^x/128*285;return l%b?k[l%b]^k[b+l/b]^b:k[l/b]^188;}

który zawiera tylko 158 znaków, a zatem mieści się w 1264 bitach. Kliknij tutaj, aby zobaczyć, czy to działa.

Mówimy o „niemożliwie” krótkiej implementacji, ponieważ jeśli permutacja byłaby wynikiem losowego procesu (jak twierdzą jej projektanci), to taki program nie istniałby ( więcej szczegółów na tej stronie ).

Realizacja referencyjna

Bardziej czytelna wersja poprzedniego kodu C to:

unsigned char p(unsigned char x){
     unsigned char
         s[]={1,221,146,79,147,153,11,68,214,215,78,220,152,10,69},
         k[]={0,32,50,6,20,4,22,34,48,16,2,54,36,52,38,18,0};
     if(x != 0) {
         unsigned char l=1, a=2;
         while(a!=x) {
             a=(a<<1)^(a>>7)*29;
             l++;
         }
         unsigned char i = l % 17, j = l / 17;
         if (i != 0) return 252^k[i]^s[j];
         else return 252^k[j];
     }
     else return 252;
}

Tabela kjest taka, że k[x] = L(16-x)gdzie Ljest liniowy w tym sensie L(x^y)==L(x)^L(y), i gdzie, podobnie jak w C, ^oznacza XOR. Nie udało nam się jednak wykorzystać tej właściwości, aby skrócić nasze wdrożenie. Nie jesteśmy świadomi żadnej struktury, sktóra mogłaby pozwolić na prostszą implementację --- jednak jej dane wyjściowe są zawsze w polu podrzędnym, tj. gdzie potęgowanie odbywa się w polu skończonym. Oczywiście masz absolutną swobodę w stosowaniu prostszego wyrażenia, jeśli go znajdziesz!$s[x]^{16}=s[x]$s

Pętla while odpowiada ocenie dyskretnego logarytmu w polu skończonym z 256 elementami. Działa poprzez proste wyszukiwanie siłowe: zmienna fikcyjna ajest ustawiona na generator pola skończonego i jest mnożona przez ten generator, aż wynik będzie równy x. W takim przypadku mamy do czynienia lz dyskretnym dziennikiem x. Ta funkcja nie jest zdefiniowana w 0, stąd specjalny przypadek odpowiadający ifinstrukcji.

Mnożenie przez generator może być postrzegane jako mnożenie przez w który jest następnie redukowany modulo do wielomianu . Rolą tego jest zapewnienie, że zmienna pozostaje na 8 bitach. Alternatywnie, możemy użyć , w którym to przypadku może być (lub dowolny inny typ całkowity). Z drugiej strony należy zacząć od tego, co musimy mieć, gdy jest równe 1.$X$$\mathbb{F}_2[X]$$X^8+X^4+X^3+X^2+1$unsigned charaa=(a<<1)^(a>>7)*(256^29)aintl=1,a=2l=255x

Więcej szczegółów na temat właściwości pprzedstawiono w naszym artykule , z podsumowaniem większości naszych optymalizacji w celu uzyskania poprzedniej krótkiej implementacji.

Zasady

Zaproponuj program, który implementuje funkcję pw mniej niż 1683 bitach. Im krótszy program, tym bardziej nienormalny, dla danego języka, krótszy jest lepszy. Jeśli twój język ma Kuznyechik, Streebog lub pjako wbudowany, nie możesz ich używać.

Miarą używaną do określenia najlepszej implementacji jest długość programu w bajtach. W naszej pracy naukowej używamy długości bitów, ale dla uproszczenia trzymamy się tu bajtów.

Jeśli język nie ma jasnego pojęcia funkcji, argumentu lub wyjścia, kodowanie jest do ciebie, aby określić, ale sztuczki jak kodowania wartości pi[x]jak xsą oczywiście zabronione.

Przedłożyliśmy już dokument badawczy z naszymi ustaleniami na ten temat. Jest dostępny tutaj . Jeśli jednak zostanie opublikowany w miejscu naukowym, chętnie uznamy autorów najlepszych wdrożeń.

Nawiasem mówiąc, dzięki xnor za pomoc w przygotowaniu tego pytania!

Zestaw AMD64 (78 bajtów lub 624 bitów kodu maszynowego)

uint8_t SubByte (uint8_t x) {
    uint8_t y, z;
    uint8_t s [] =
      {1 221,146,79,147,153,11,68,214,215,78,220,152,10,69};

    uint8_t k [] =
      {0,32,50,6,20,4,2, 2,44,48,16,2,54,36,52,38,18,0};

    jeśli (x) {
      dla (y = z = 1; (y = (y << 1) ^ ((y >> 7) * 29))! = x; z ++);
      x = (z% 17);
      z = (z / 17);
      x = (x)? k [x] ^ s [z]: k [z];
    }
    zwraca x ^ 252;
}

64-bitowy zestaw x86

    ; 78 bajtów zestawu AMD64
    ; odzhan
    bity 64

    % ifndef BIN
      globalny SubBytex
    % endif

SubBytex:
    mov al, 252
    jecxz L2; jeśli (x) {
    zadzwoń do L0
k:
    db 0xfc, 0xdc, 0xce, 0xfa, 0xe8, 0xf8, 0xea, 0xde, 
    db 0xcc, 0xec, 0xfe, 0xca, 0xd8, 0xc8, 0xda, 0xee, 0xfc
s:
    db 0x01, 0xdd, 0x92, 0x4f, 0x93, 0x99, 0x0b, 0x44, 
    db 0xd6, 0xd7, 0x4e, 0xdc, 0x98, 0x0a, 0x45
L0:
    pop rbx
    mov al, 1; y = 1
    cdq; z = 0
L1:
    inc dl; z ++
    add al, al; y = y + y
    jnc $ + 4; pomiń XOR, jeśli nie nosisz
    Xor al. 29;
    cmp al, cl; jeśli (y! = x) masz L1
    jne L1    

    xchg eax, edx; eax = z
    cdq; edx = 0
    mov cl, 17; al = z / 17, dl = z% 17
    div ecx

    mov cl, [rbx + rax + 17]; cl = s [z]
    xlatb; al = k [z]
    test dl, dl; jeśli (x == 0) mam L2
    jz L2
    xchg eax, edx; al = x
    xlatb; al = k [x]
    xor al, cl; al ^ = s [z]
L2:
    gnić

Zdemontowany 64-bitowy kod

00000000 B0FC mov al, 0xfc
00000002 67E348 jecxz 0x4d
00000005 E820000000 wywołanie qword 0x2a
; k [] = 0xfc, 0xdc, 0xce, 0xfa, 0xe8, 0xf8, 0xea, 0xde,
; 0xcc, 0xec, 0xfe, 0xca, 0xd8, 0xc8, 0xda, 0xee, 0xfc
; s [] = 0x01, 0xdd, 0x92, 0x4f, 0x93, 0x99, 0x0b, 0x44,
; 0xd6, 0xd7, 0x4e, 0xdc, 0x98, 0x0a, 0x45
0000002A 5B pop rbx
0000002B B001 mov al, 0x1
0000002D 99 cdq
0000002E FEC2 inc dl
00000030 00C0 add al, al
00000032 7302 jnc 0x36
00000034 341D xor al, 0x1d
00000036 38C8 cmp al, kl
00000038 75F4 jnz 0x2e
0000003A 92 xchg eax, edx
0000003B 99 cdq
0000003C B111 mov cl, 0x11
0000003E F7F1 div ecx
00000040 8A4C0311 mov cl, [rbx + rax + 0x11]
00000044 D7 xlatb
00000045 84D2 test dl, dl
00000047 7404 jz 0x4d
00000049 92 xchg eax, edx
0000004A D7 xlatb
0000004B 30C8 xor al, kl
0000004D C3 ret

32-bitowy zestaw x86

    ; 72 bajty zestawu x86
    ; odzhan
    bity 32

    % ifndef BIN
      globalny SubBytex
      globalny _SubBytex
    % endif

SubBytex:
_SubBytex:
    mov al, 252
    jecxz L2; jeśli (x) {
    zadzwoń do L0
k:
    db 0xfc, 0xdc, 0xce, 0xfa, 0xe8, 0xf8, 0xea, 0xde, 
    db 0xcc, 0xec, 0xfe, 0xca, 0xd8, 0xc8, 0xda, 0xee, 0xfc
s:
    db 0x01, 0xdd, 0x92, 0x4f, 0x93, 0x99, 0x0b, 0x44, 
    db 0xd6, 0xd7, 0x4e, 0xdc, 0x98, 0x0a, 0x45
L0:
    pop ebx
    mov al, 1; y = 1
    cdq; z = 0
L1:
    inc edx; z ++
    add al, al; y = y + y
    jnc $ + 4; pomiń XOR, jeśli nie nosisz
    Xor al. 29;
    cmp al, cl; jeśli (y! = x) masz L1
    jne L1    
    xchg eax, edx; al = z
    aam 17; al | x = z% 17, ah | z = z / 17
    mov cl, ah; cl = z
    cmove eax, ecx; if (x == 0) al = z else al = x
    xlatb; al = k [z] lub k [x]
    jz L2; jeśli (x == 0) mam L2
    xor al, [ebx + ecx + 17]; k [x] ^ = k [z]
L2:
    gnić

Zdemontowany 32-bitowy kod

00000000 B0FC mov al, 0xfc
00000002 E345 jecxz 0x49
00000004 E820000000 połączenie dword 0x29
; k [] = 0xfc, 0xdc, 0xce, 0xfa, 0xe8, 0xf8, 0xea, 0xde,
; 0xcc, 0xec, 0xfe, 0xca, 0xd8, 0xc8, 0xda, 0xee, 0xfc
; s [] = 0x01, 0xdd, 0x92, 0x4f, 0x93, 0x99, 0x0b, 0x44,
; 0xd6, 0xd7, 0x4e, 0xdc, 0x98, 0x0a, 0x45
00000029 5B pop ebx
0000002A B001 mov al, 0x1
0000002C 99 cdq
0000002D 42 inc edx
0000002E 00C0 add al, al
00000030 7302 jnc 0x34
00000032 341D xor al, 0x1d
00000034 38C8 cmp al, kl
00000036 75F5 jnz 0x2d
00000038 92 xchg eax, edx
00000039 D411 aam 0x11
0000003B 88E1 mov cl, ah
0000003D 0F44C1 cmovz eax, ecx
00000040 D7 xlatb
00000041 7404 Jz 0x47
00000043 32440B11 xor al, [ebx + ecx + 0x11]
00000047 C3 ret

CJam ,72 67 66 63 bajty

ri{_2md142*^}es*]2#~Hmd{5\}e|Fm2b"Ý0$&Ü™ÖD�’
˜×EO“N".*Lts:^i

es* powtarza coś według aktualnego znacznika czasu, który jest dużą liczbą, a jego ukończenie zajęłoby zbyt dużo czasu.

Rzeczywista wersja testowa, 64 bajty:

ri{_2md142*^}256*]2#~Hmd{5\}e|Fm2b"Ý0$&Ü™ÖD�’
˜×EO“N".*Lts:^i

00000000: 7269 7b5f 326d 6431 3432 2a5e 7d32 3536  ri{_2md142*^}256
00000010: 2a5d 3223 7e48 6d64 7b35 5c7d 657c 466d  *]2#~Hmd{5\}e|Fm
00000020: 3262 22dd 3024 2612 dc99 d644 0092 0b0a  2b".0$&....D....
00000030: 98d7 454f 934e 0122 2e2a 4c74 733a 5e69  ..EO.N.".*Lts:^i

Wypróbuj online!

Wypróbuj wszystkie online!

Aby uruchomić ten kod (na komputerze z systemem Linux), musisz dodać linię en_US.ISO-8859-1 ISO-8859-1do /etc/locale.geni uruchomić locale-gen. Następnie możesz użyć:

LANG=en_US.ISO-8859-1 java -jar cjam.jar <source file>

Lub możesz wypróbować tę równoważną 72-bajtową wersję UTF-8:

00000000: 7269 7b5f 326d 6431 3432 2a5e 7d32 3536  ri{_2md142*^}256
00000010: 2a5d 3223 7e48 6d64 7b35 5c7d 657c 466d  *]2#~Hmd{5\}e|Fm
00000020: 3262 22c3 9d30 2426 12c3 9cc2 99c3 9644  2b"..0$&.......D
00000030: 00c2 920b 0ac2 98c3 9745 4fc2 934e 0122  .........EO..N."
00000040: 2e2a 4c74 733a 5e69                      .*Lts:^i

Wyjaśnienie

ri               e# Read input.
{_2md142*^}      e# Copy and divide by 2. If remainder is 1, xor 142.
es*]             e# Repeat a lot of times and wrap all results in an array.
2#               e# Find the first occurrence of 2, -1 if not found.
~                e# Increment and negate.
Hmd              e# Divmod 17. Both the quotient and remainder would be negated.
{5\}e|           e# If remainder = 0, return 5, quotient instead.
Fm2b             e# Subtract 15 from the remainder and expand in base 2.
                 e# In CJam, base conversion only applies to the absolute value.
"...".*          e# Filter 221, 48, 36, 38, 18 by the bits.
                 e# 221, the characters after 18
                 e#   and 18 itself in case quotient - 15 = -15 won't change.
Lt               e# Remove the item s[quotient] xor 220.
                 e# Quotient is 0, 5 or a negative integer from the end,
                 e#   which doesn't overlap with the previously filtered items.
s                e# Flatten, because some characters become strings after the process.
:^i              e# Reduce by xor and make sure the result is an integer.

Znaki w ciągu to:

• 221. Zobacz poniżej.
• 48, 36, 38, 18. Jest to liniowy rozkład k oparty na charakterystyce L w pytaniu.
• 220, wartość wypełniacza dla tablicy s, gdy używana jest tylko tablica k.
• Xor 220 tablicy odwrócony, z wyjątkiem ostatniego elementu lub pierwszego elementu przed odwróceniem, którym jest 221 na początku łańcucha.

Galaretka 71 59 bajtów

H^142ƊHḂ?Ƭi2d17U⁸⁴;$Ḣ?$CµṪạ⁴B¬T;;6ị“Œ0$&ØŀWð⁺Ṫ\ḢĠVı⁻¹]°Ẇ‘^/

Wypróbuj online!

Sprawdź wszystkie możliwości

Teraz przepisane przy użyciu przerobionej wersji sprytnej odpowiedzi CJam jimmy23013, więc pamiętajcie o tym! Używa tylko 472 bitów (28,0% naiwnego podejścia). @ jimmy23013 również zapisał kolejny bajt!

Wyjaśnienie

Scena 1

         Ƭ        | Repeat the following until no new entries:
       Ḃ?         | - If odd:
     Ɗ            |   - Then following as a monad:
H                 |     - Halve
 ^142             |     - Xor 142
      H           |   - Else: Halve
          i2      | Index of 2 in this list

Etap 2

d17           | Divmod 17
          $   | Following as a monad:
   U          | - Reverse order
        Ḣ?    | - If head (remainder from divmod) non-zero:
    ⁸         |   - Then: left argument [quotient, remainder]
     ⁴;$      |   - Else: [16, quotient]
           C  | Complement (1 minus)
            µ | Start a new monadic chain

Etap 3

Ṫ                   | Tail (Complement of remainder or quotient from stage 2)
 ạ⁴                 | Absolute difference from 16
   B                | Convert to binary
    ¬               | Not
     T              | Indices of true values
      ;             | Concatenate (to the other value from stage 2)
       ;6           | Concatenate to 6
         ị“Œ...Ẇ‘   | Index into [19,48,36,38,18,238,87,24,138,206,92,197,196,86,25,139,129,93,128,207]
                 ^/ | Reduce using xor

Oryginalne podejście

Galaretka , 71 66 bajtów

H^142ƊHḂ?Ƭi2d:j@“ÐḌ‘ɗ%?17ị"“p?Ä>4ɼḋ{zẉq5ʂċ¡Ḅ“`rFTDVbpPBvdtfR@‘^ƒ17

Wypróbuj online!

Sprawdź wszystkie możliwości

Monadyczny link lub pełny program, który pobiera pojedynczy argument i zwraca odpowiednią wartość pi[x]. Jest to 536 bitów, czyli mniej niż jedna trzecia naiwnego przechowywania pi.

Zapisane 3 bajty za pomocą metody znajdowania lod jimmy23013 za CJam odpowiedź więc należy upvote że jeden zbyt!

Wyjaśnienie

Scena 1

         Ƭ        | Repeat the following until no new entries:
       Ḃ?         | - If odd:
     Ɗ            |   - Then following as a monad:
H                 |     - Halve
 ^142             |     - Xor 142
      H           |   - Else: Halve
          i2      | Index of 2 in this list

Etap 2

         %?17  | If not divisible by 17
d              | - Then divmod 17
        ɗ      | - Else following as a dyad (using 17 as right argument)
 :             |   - Integer divide by 17
  j@“ÐḌ‘       |   - Join the list 15,173 by the quotient

Etap 3

ị"“p...Ḅ“`...@‘     | Index into two compressed lists of integers using the output from stage 2 (separate list for each output from stage 2). The third output from stage 2 will be left untouched
               ^ƒ17 | Finally reduce using Xor and 17 as the first argument

C (gcc) , 157 148 140 139 bajtów

Niewielka poprawa w stosunku do przykładu C.

l,b=17,*k=L"@`rFTDVbpPBvdtfR@";p(x){for(l=256;--l*~-x;)x=2*x^x/128*285;return l%b?k[l%b]^"\xcer?\4@6\xc8\t{|\3q5\xc7\n"[l/b]-b:k[l/b]^188;}

Wypróbuj online!

C (gcc) , 150 142 127 126 bajtów

To zależy od dziwactwa gcc i x86 oraz UTF-8.

l,*k=L"@`rFTDVbpPBvdtfR@";p(x){for(l=256;--l*~-x;)x=2*x^x/128*285;x=l%17?k[l%17]^L"½a.ó/%·øjkò`$¶ù"[l/17]:k[l/17]^188;}

Wypróbuj online!

Dzięki @XavierBonnetain za -1 i mniej niezdefiniowane zachowanie.

05AB1E , 101 100 98 97 95 94 bajtów

U•α">η≠ε∍$<Θγ\&@(Σα•₅вV₁[<ÐX*Q#X·₁%Xžy÷Ƶ¹*₁%^₁%U}D17©%DĀiYsès®÷•¾#kôlb¸ù,-ó"a·ú•₅вë\Ƶ∞s®÷Y}sè^

-3 bajty dzięki @Grimy .

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

Stąd funkcja C portu Xaviera Bonnetaina (wersja 1106 bitów) , z tym samym ulepszeniem @ceilingcat wprowadzonym w jego odpowiedzi C, aby zaoszczędzić 3 bajty, więc pamiętaj, aby go głosować!

U                    # Store the (implicit) input in variable `X`
•α">η≠ε∍$<Θγ\&@(Σα• "# Push compressed integer 20576992798525946719126649319401629993024
 ₅в                  # Converted to base-255 as list:
                     #  [64,96,114,70,84,68,86,98,112,80,66,118,100,116,102,82,64]
   V                 # Pop and store this list in variable `Y`
₁                    # Push `i` = 256
 [                   # Start an infinite loop:
  <                  #  Decrease `i` by 1
   Ð                 #  Triplicate `i`
    X*Q              #  If `i` multiplied by `X` is equal to `i` (i==0 or X==1):
       #             #   Stop the infinite loop
  X·₁%               #  Calculate double(`X`) modulo-256
                     #  (NOTE: all the modulo-256 are to mimic an unsigned char in C)
  Xžy÷               #  Calculate `X` integer-divided by builtin integer 128,
      Ƶ¹*            #  multiplied by compressed integer 285,
         ₁%          #  modulo-256
  ^                  #  Bitwise-XOR those together
   ₁%                #  And take modulo-256 again
  U                  #  Then pop and store it as new `X`
 }D                  # After the loop: Duplicate the resulting `i`
   17©               # Push 17 (and store it in variable `®` without popping)
      %              # Calculate `i` modulo-17
       D             # Duplicate it
        Āi           # If it's NOT 0:
          Ysè        #  Index the duplicated `i` modulo-17 into list `Y`
          s®÷        #  Calculate `i` integer-divided by 17
          •¾#kôlb¸ù,-ó"a·ú•
                    "#  Push compressed integer 930891775969900394811589640717060184
           ₅в        #  Converted to base-255 as list:
                     #   [189,97,46,243,47,37,183,248,106,107,242,96,36,182,249]
         ë           # Else (`i` == 0):
          \          #  Discard the duplicated `i` modulo-17, since we don't need it
          Ƶ∞         #  Push compressed integer 188
          s®÷        #  Calculate `i` integer-divided by 17
          Y          #  Push list `Y`
         }s          # After the if-else: swap the integer and list on the stack
           è         # And index the `i` modulo/integer-divided by 17 into the list
            ^        # Then Bitwise-XOR the top two together
                     # (after which the top of the stack is output implicitly as result)

Zobacz tę końcówkę 05AB1E kopalni (sekcje Jak skompresować dużych liczb całkowitych? I jak skompresować list całkowitych? ) , Aby zrozumieć, dlaczego •α">η≠ε∍$<Θγ\&@(Σα•jest 20576992798525946719126649319401629993024; •α">η≠ε∍$<Θγ\&@(Σα•₅вjest [64,96,114,70,84,68,86,98,112,80,66,118,100,116,102,82,64]; Ƶ¹jest 285; •¾#kôlb¸ù,-ó"a·ú•jest 930891775969900394811589640717060184; •¾#kôlb¸ù,-ó"a·ú•₅вjest [189,97,46,243,47,37,183,248,106,107,242,96,36,182,249]; i Ƶ∞jest 188.

Stax , 65 64 62 59 58 bajtów

ç∙¼≥2▼Uó╤áπ╙º┐╩♫∟öv◘≥δ♦Θ╫»─kRWÑâBG")≥ö0╥kƒg┬^S ΔrΩ►╣Wü Ü╕║

Uruchom i debuguj

Niestety, ten program używa instrukcji, które wewnętrznie używają niektórych przestarzałych instrukcji stax. Właśnie zapomniałem zaktualizować ich implementację. Powoduje to wyświetlenie fałszywych ostrzeżeń, ale wyniki są nadal poprawne.

Jest to inspirowane doskonałą odpowiedzią jimmy23013 . Niektóre części zostały zmienione, aby lepiej pasowały do ​​stax.

Programy Stax napisane w drukowanym ASCII mają alternatywną reprezentację, która zapisuje nieco więcej niż 1 bit na bajt, ponieważ jest tylko 95 drukowanych znaków ASCII.

Oto reprezentacja ascii tego programu sformatowana pod kątem „czytelności” z komentarzami.

{                       begin block
  2|%142*S              given n, calculate (n/2)^(n%2*142)
                         - this seems to be the inverse of the operation in the while loop
gu                      use block to generate distinct values until duplicate is found
                         - starting from the input; result will be an array of generated values
2I^                     1-based index of 2 in the generated values
17|%                    divmod 17
c{Us}?                  if the remainder is zero, then use (-1, quotient) instead
~                       push the top of the main stack to the input stack for later use
"i1{%oBTq\z^7pSt+cS4"   ascii string literal; will be transformed into a variant of `s`
./o{H|EF                interpret ascii codes as base-94 integer
                         - this is tolerant of digits that exceed the base
                        then encode big constant as into base 222 digits
                         - this produces an array similar to s
                         - 0 has been appended, and all elements xor 220
@                       use the quotient to index into this array
"jr+R"!                 packed integer array literal [18, 38, 36, 48]
F                       for each, execute the rest of the program
  ;                     peek from the input array, stored earlier
  v                     decrement
  i:@                   get the i-th bit where i is the iteration index 0..3
  *                     multiply the bit by value from the array literal
  S                     xor with result so far
                        after the loop, the top of the stack is printed implicitly

Uruchom ten

Zmodyfikowana wersja do uruchomienia dla wszystkich wejść 0..255

Python 3 , 151 bajtów

f=lambda x,l=255,k=b'@`rFTDVbpPBvdtfR@':f(x*2^x//128*285,l-1)if~-x*l else[k[l%17]^(0x450a98dc4ed7d6440b99934f92dd01>>l//17*8&255),k[l//17]][l%17<1]^188

Wypróbuj online!

Funkcja, która implementuje permutację. Kod używa tylko 7-bitowych znaków ASCII.

Koduje się kjako bajtowanie Pythona 3, przeniesione ^64do zakresu do wydrukowania. Natomiast sjest zakodowany jako podstawa-256 cyfr stałej numerycznej, a cyfry są wyodrębniane jako [number]>>[shift]*8&255. Było to krótsze niż kodowanie sw ciągu ze względu na wymaganą liczbę znaków specjalnych, nawet przy optymalnym przesunięciu, ^160aby je zminimalizować.

Obliczenia w dzienniku dyskretnym są wykonywane wstecz. Aktualizacja x=x*2^x//128*285zapętla się w grupie cyklicznej, symulując pomnożenie przez generator, aż osiągnie tożsamość x=1. Log dyskretny rozpoczynamy od l=255(długości cyklu) i zmniejszamy go przy każdej iteracji. Aby obsłużyć x=0sprawę i sprawić, aby nie zapętlała się na zawsze, kończymy również kiedy l=0, co powoduje, że x=0mapowanie do l=0określonego.

Python 2 przegrywa z brakiem miłych testów, więc musimy to zrobić map(ord,...)(ArBo zapisał tutaj bajt). To pozwala nam używać /raczej niż //do dzielenia liczb całkowitych.

Python 2 , 156 bajtów

f=lambda x,l=255,k=map(ord,'@`rFTDVbpPBvdtfR@'):f(x*2^x/128*285,l-1)if~-x*l else[k[l%17]^(0x450a98dc4ed7d6440b99934f92dd01>>l/17*8&255),k[l/17]][l%17<1]^188

Wypróbuj online!

JavaScript (ES6), 139 bajtów

Podobne do wersji Node.js, ale przy użyciu znaków spoza zakresu ASCII.

f=(x,l=256,b=17,k=i=>"@`rFTDVbpPBvdtfR@¬p?â>4¦é{zãq5§è".charCodeAt(i))=>--l*x^l?f(x+x^(x>>7)*285,l):l%b?k(l%b)^k(b+l/b)^b:k(l/b)^188

Wypróbuj online!

JavaScript (Node.js) ,  149  148 bajtów

Na podstawie implementacji C Xaviera Bonnetaina (która jest tutaj przedstawiona ).

f=(x,l=256,b=17,k=i=>Buffer("@`rFTDVbpPBvdtfR@,p?b>4&i{zcq5'h")[~~i]|3302528>>i-b&128)=>--l*x^l?f(x+x^(x>>7)*285,l):l%b?k(l%b)^k(b+l/b)^b:k(l/b)^188

Wypróbuj online!

Kodowanie

W oryginalnej odpowiedzi Xaviera tabele s[]i k[]są przechowywane w następującym ciągu:

"@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8"
 \_______________/\__________________________________/
         k                         s

Pierwsze 17 znaków to reprezentacje ASCII, k[i] XOR 64a kolejne 15 znaków to reprezentacje ASCII s[i-17] XOR 173lub s[i-17] XOR 64 XOR 17 XOR 252.

k[i] XOR 64s[i-17] XOR 173$126$$128$

Oto, co otrzymujemy:

original value : 172 112  63 226  62  52 166 233 123 122 227 113  53 167 232
subtract 128?  :   1   0   0   1   0   0   1   1   0   0   1   0   0   1   1
result         :  44 112  63  98  62  52  38 105 123 122  99 113  53  39 104
as ASCII       : "," "p" "?" "b" ">" "4" "&" "i" "{" "z" "c" "q" "5" "'" "h"

110010011001001$25801$

$128$

| 3302528 >> i - b & 128

$s$

Uwaga: To tylko dodatkowa uwaga, niezwiązana z powyższymi odpowiedziami.

$s$

$\{1, 11, 79, 146\}$

console.log(
  [ 0b0001, 0b1100, 0b1000, 0b0100, 0b1001, 0b1010, 0b0010, 0b0110,
    0b1110, 0b1111, 0b0101, 0b1101, 0b1011, 0b0011, 0b0111
  ].map(x =>
    [ 1, 11, 79, 146 ].reduce((p, c, i) =>
      p ^= x >> i & 1 && c,
      0
    )
  )
)

Wypróbuj online!

C # (interaktywny kompilator Visual C #) , 141 bajtów

x=>{var k="@`rFTDVbpPBvdtfR@¬p?â>4¦é{zãq5§è";int l=256,b=17;for(;--l*x!=l;)x=2*x^x/128*285;return l%b>0?k[l%b]^k[b+l/b]^b:k[l/b]^188;}

Tylko port przykładowego rozwiązania, przeniesiony do C #.

Wypróbuj online!

Python 3 , 182 bajty

def p(x,t=b'@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8',l=255,d=17):
 if x<2:return 252-14*x
 while~-x:x=x*2^(x>>7)*285;l-=1
 return(188^t[l//d],d^t[l%d]^t[d+l//d])[l%d>0]

Wypróbuj online!

Python nie wygra tutaj pierwszej nagrody, ale wciąż jest to 10-bajtowy golf najlepszego programu Python tutaj .

Python 3 , 176 bajtów

p=lambda x,l=255,t=b'@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8',d=17:2>x<l>254and-14*x+252or(p(x*2^(x>>7)*285,l-1)if~-x else(188^t[l//d],d^t[l%d]^t[d+l//d])[l%d>0])

Wypróbuj online!

Jako lambda ma jeszcze sześć bajtów mniej. Boli mnie to, że muszę go użyć if... else, ale nie widzę innej opcji zwarcia, biorąc pod uwagę, że 0 jest możliwą odpowiedzią.

Python 3 , 173 bajtów

p=lambda x,l=255,t=bytes('@`rFTDVbpPBvdtfR@¬p?â>4¦é{zãq5§è','l1'),d=17:2>x<l>254and-14*x+252or(p(x*2^(x>>7)*285,l-1)if~-x else(188^t[l//d],d^t[l%d]^t[d+l//d])[l%d>0])

Wypróbuj online!

Jeszcze krótszy w bajtach (choć nie jestem pewien co do bitów, ponieważ nie jest to już czysty ASCII), dzięki uprzejmości ovs.

Rdza , 170 163 bajtów

|mut x|{let(k,mut l)=(b"QqcWEUGsaASguewCQ\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8",255);while l*x!=l{x=2*x^x/128*285;l-=1}(if l%17>0{l+=289;k[l%17]}else{173})^k[l/17]}

Wypróbuj online!

To jest port mojego rozwiązania w C, z nieco innym ciągiem, który nie wymaga XOR 17. Oczekuję, że większość rozwiązań opiera się na ciągu „@ 'rFTDVbpPBvdtfR @ \ xacp? \ Xe2> 4 \ xa6 \ xe9 {z \ xe3q5 \ xa7 \ xe8 "również można poprawić (wystarczy zmienić ciąg, usunąć xor 17 i xor 173 zamiast 188).

Usunąłem jedno z przeglądów, warunkowo dodając 17*17je l, podobnie jak my (mniej więcej) w rozwiązaniu kodu maszynowego ARM.

Rdza ma wnioskowanie typu i zamykanie, ale jej rzutowania (nawet dla boolanów lub między liczbami całkowitymi) są zawsze jawne, zmienność musi być zaznaczona, nie ma operatora trójskładnikowego, operacji na liczbach całkowitych, domyślnie, paniki przy przepełnieniu i operacji mutacji ( l+=1) zwraca jednostkę. Nie udało mi się uzyskać krótszego rozwiązania z iteratorami, ponieważ zamknięcia + mapowanie wciąż są dość szczegółowe.

To sprawia, że ​​Rust jest dość złym wyborem do gry w golfa. Niemniej jednak, nawet w języku, który kładzie nacisk na czytelność i bezpieczeństwo w stosunku do zwięzłości, jesteśmy zdecydowanie zbyt niscy.

Aktualizacja: użyto anonimowej funkcji z sugestii manatwork.

05AB1E , 74 bajty

₄FÐ;sÉiƵf^])2k>17‰Dθ_i¦16š}<(Rć16α2в≠ƶ0Kì6ª•5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•ƵŠвs<è.«^

Port pierwszej odpowiedzi galaretki @NickKennedy . Ja pracuje na porcie @ jimmy23013 „s CJam odpowiedź bezpośrednio , ale byłem już na 78 bajtów i jeszcze naprawić błąd, więc byłoby większe. Jednak na pewno można jeszcze trochę grać w golfa.

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

₄F              # Loop 1000 times:
  Ð             #  Triplicate the current value
                #  (which is the implicit input in the first iteration)
   ;            #  Halve it
    s           #  Swap to take the integer again
     Éi         #  If it's odd:
       Ƶf^      #   Bitwise-XOR it with compressed integer 142
]               # Close the if-statement and loop
 )              # Wrap all values on the stack into a list
  2k            # Get the 0-based index of 2 (or -1 if not found)
    >           # Increase it by 1 to make it 1-based (or 0 if not found)
     17‰        # Take the divmod-17 of this
Dθ_i    }       # If the remainder of the divmod is 0:
    ¦16š        #  Replace the quotient with 16
         <      # Decrease both values by 1
          (     # And then negate it
R               # Reverse the pair
 ć              # Extract head; push head and remainder-list
  16α           # Get the absolute difference between the head and 16
     2в         # Convert it to binary (as digit-list)
       ≠        # Invert booleans (0 becomes 1; 1 becomes 0)
        ƶ       # Multiply all by their 1-based indices
         0K     # And remove all 0s
           ì    # And prepend this in front of the remainder-list
            6ª  # And also append a trailing 6
•5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•
                # Push compressed integer 29709448685778434533295690952203992295278432248
  ƵŠв           # Converted to base-239 as list:
                #  [19,48,36,38,18,238,87,24,138,206,92,197,196,86,25,139,129,93,128,207]
     s          # Swap to take the earlier created list again
      <         # Subtract each by 1 to make them 0-based
       è        # And index them into this list
.«^             # And finally reduce all values by bitwise XOR-ing them
                # (after which the result is output implicitly)

Zobacz tę końcówkę 05AB1E kopalni (sekcje Jak skompresować dużych liczb całkowitych? I jak skompresować list całkowitych? ) , Aby zrozumieć, dlaczego Ƶfjest 142; •5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•jest 29709448685778434533295690952203992295278432248, ƵŠjest 239; i •5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•ƵŠвjest [19,48,36,38,18,238,87,24,138,206,92,197,196,86,25,139,129,93,128,207].