Цель этой задачи - найти невероятно короткую реализацию следующей функции pв выбранном вами языке. Вот код C, реализующий его (см. Эту ссылку TIO, которая также печатает его выходные данные) и страницу википедии, содержащую его.

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];
}

Что такое p

pявляется составной частью двух российских криптографических стандартов, а именно хеш-функции Streebog и блочного шифра Kuznyechik . В этой статье (и во время совещаний ISO) разработчики этих алгоритмов утверждали, что они генерировали массив pi, выбирая случайные 8-битные перестановки.

«Невозможные» реализации

Есть $256! \approx 2^{1684}$ перестановок на 8 бит. Следовательно, для данной случайной перестановки не следует ожидать, что программе, которая ее реализует, потребуется менее 1683 битов.

Однако мы нашли несколько аномально небольших реализаций (которые мы перечислим здесь ), например, следующую программу на 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;}

который содержит только 158 символов и, таким образом, помещается в 1264 бит. Нажмите здесь, чтобы увидеть, что это работает.

Мы говорим о «невозможной» короткой реализации, потому что, если перестановка была результатом случайного процесса (как утверждают его разработчики), то такой короткой программы не существовало бы (см. Эту страницу для более подробной информации).

Ссылочная реализация

Более читаемая версия предыдущего кода C:

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;
}

Таблица kтакова, что k[x] = L(16-x), где Lлинейно в том смысле, что L(x^y)==L(x)^L(y)и где, как в C, ^обозначает XOR. Однако нам не удалось использовать это свойство для сокращения нашей реализации. Мы не знаем ни о какой структуре, sкоторая могла бы позволить более простую реализацию - хотя ее вывод всегда находится в подполе, то есть $s[x]^{16}=s[x]$ где возведение в степень выполняется в конечном поле. Конечно, вы можете свободно использовать более простое выражение, sесли найдете его!

Цикл while соответствует оценке дискретного логарифма в конечном поле с 256 элементами. Он работает с помощью простого перебора: фиктивная переменная aзадается как генератор конечного поля и умножается на этот генератор до тех пор, пока результат не будет равен x. Когда это так, у нас lесть это дискретный журнал x. Эта функция не определена в 0, следовательно, это особый случай, соответствующий ifутверждению.

Умножение на генератор можно рассматривать как умножение на $X$ в $\mathbb{F}_2[X]$ которое затем уменьшается по модулю полинома $X^8+X^4+X^3+X^2+1$ . Роль unsigned charзаключается в том, чтобы гарантировать, что переменная aостается на 8 битах. В качестве альтернативы мы могли бы использовать a=(a<<1)^(a>>7)*(256^29), в этом случае aможет быть int(или любой другой целочисленный тип). С другой стороны, нужно начинать с того, l=1,a=2что нужно, l=255когда xравен 1.

Более подробная информация о свойствах pпредставлена ​​в нашей статье с описанием большинства наших оптимизаций для получения предыдущей краткой реализации.

правила

Предложите программу, которая реализует функцию pменее чем в 1683 битах. Чем короче программа, тем ненормальнее она для данного языка, тем короче, тем лучше. Если на вашем языке есть Kuznyechik, Streebog или pкак встроенный, вы не можете их использовать.

Метрика, которую мы используем для определения наилучшей реализации, - это длина программы в байтах. Мы используем длину в битах в нашей академической статье, но здесь для простоты мы придерживаемся байтов.

Если ваш язык не имеет четкого представления о функции, аргумента или вывода, кодирование до вас , чтобы определить, но приемы , такие как кодирующая значение , pi[x]как x, очевидно , запрещены.

Мы уже представили исследовательскую работу с нашими выводами по этой теме. Это доступно здесь . Однако, если она будет опубликована в научном центре, мы с радостью примем авторов лучших реализаций.

Кстати, спасибо xnor за помощь при составлении этого вопроса!

Сборка AMD64 (78 байтов или 624 бит машинного кода)

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,22,34,48,16,2,54,36,52,38,18,0};

    если (х) {
      для (y = z = 1; (y = (y << 1) ^ ((y >> 7) * 29))! = x; z ++);
      х = (z% 17);
      z = (z / 17);
      х = (х)? k [x] ^ s [z]: k [z];
    }
    возврат х ^ 252;
}

64-битная сборка x86

    ; 78 байтов сборки AMD64
    ; odzhan
    биты 64

    % ifndef BIN
      глобальный SubBytex
    % ENDIF

SubBytex:
    мов ал, 252
    Jecxz L2; если (х) {
    позвоните L0
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
L0:
    поп rbx
    мов ал, 1; у = 1
    CDQ; z = 0
L1:
    вкл дл; г ++
    добавить al, al; у = у + у
    JNC $ + 4; пропустить XOR, если нет переноса
    xor al, 29;
    cmp al, cl; если (y! = x) перейти к L1
    Jne L1    

    xchg eax, edx; eax = z
    CDQ; edx = 0
    мов кл, 17; al = z / 17, dl = z% 17
    div ecx

    mov cl, [rbx + rax + 17]; cl = s [z]
    xlatb; al = k [z]
    тест дл, дл; если (x == 0) перейти к L2
    JZ L2
    xchg eax, edx; al = x
    xlatb; al = k [x]
    xor al, cl; al ^ = s [z]
L2:
    RET

Разобранный 64-битный код

00000000 B0FC mov al, 0xfc
00000002 67E348 jecxz 0x4d
00000005 E820000000 вызов 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 кдк
0000002E FEC2, включая дл
00000030 00C0 добавить все, все
00000032 7302 JNC 0x36
00000034 341D xor al, 0x1d
00000036 38C8 cmp al, cl
00000038 75F4 jnz 0x2e
0000003A 92 xchg eax, edx
0000003B 99 кдк
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, cl
0000004D C3 ret

32-битная сборка x86

    ; 72 байта сборки x86
    ; odzhan
    биты 32

    % ifndef BIN
      глобальный SubBytex
      глобальный _SubBytex
    % ENDIF

SubBytex:
_SubBytex:
    мов ал, 252
    Jecxz L2; если (х) {
    позвоните L0
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
L0:
    поп прилив
    мов ал, 1; у = 1
    CDQ; z = 0
L1:
    inc edx; г ++
    добавить al, al; у = у + у
    JNC $ + 4; пропустить XOR, если нет переноса
    xor al, 29;
    cmp al, cl; если (y! = x) перейти к L1
    Jne L1    
    xchg eax, edx; al = z
    аам 17; al | x = z% 17, ах | z = z / 17
    мов кл, ах; cl = z
    cmove eax, ecx; если (x == 0) al = z, иначе al = x
    xlatb; al = k [z] или k [x]
    JZ L2; если (x == 0) перейти к L2
    xor al, [ebx + ecx + 17]; k [x] ^ = k [z]
L2:
    RET

Разобрали 32-битный код

00000000 B0FC mov al, 0xfc
00000002 E345 jecxz 0x49
00000004 E820000000 вызов 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 кдк
0000002D 42 inc edx
0000002E 00C0 добавить все, все
00000030 7302 JNC 0x34
00000032 341D xor al, 0x1d
00000034 38C8 cmp al, cl
00000036 75F5 jnz 0x2d
00000038 92 xchg eax, edx
00000039 D411 aam 0x11
0000003B 88E1 MOV CL, ах
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 байта

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

es* повторяет что-то по текущей метке времени, которая является большим числом, и это займет слишком много времени, чтобы закончить.

Фактически тестируемая версия, 64 байта:

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

Попробуйте онлайн!

Попробуйте все онлайн!

Для выполнения этого кода (на машине Linux), вам нужно добавить строку en_US.ISO-8859-1 ISO-8859-1в /etc/locale.genи запустить locale-gen. Тогда вы можете использовать:

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

Или вы можете попробовать эту эквивалентную 72-байтовую версию 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

объяснение

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.

Символы в строке:

• 221. Смотри ниже.
• 48, 36, 38, 18. Это линейное разложение k на основе характеристик L в вопросе.
• 220, значение заполнителя массива s, когда используется только массив k.
• Массив s xor 220 перевернут, за исключением последнего элемента или первого элемента перед инвертированным, которым является 221 в начале строки.

Желе 71 59 байт

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

Попробуйте онлайн!

Проверьте все возможности

Теперь переписайте его, используя переработанную версию умного ответа CJam от jimmy23013, так что не забудьте также его подтвердить! Использует только 472 бита (28,0% от наивного подхода). @ jimmy23013 также сохранил еще один байт!

объяснение

Этап 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

Этап 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

Этап 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

Оригинальный подход

Желе , 71 66 байт

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

Попробуйте онлайн!

Проверьте все возможности

Монадическая ссылка или полная программа, которая принимает один аргумент и возвращает соответствующее значение pi[x]. Это 536 бит, так что меньше трети наивного хранилища пи.

Сэкономили 3 байта, используя метод для поиска ответа CJaml от jimmy23013, так что не забудьте также его подтвердить!

объяснение

Этап 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

Этап 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

Этап 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 байт

Скромное улучшение по сравнению с примером 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;}

Попробуйте онлайн!

C (gcc) , 150 142 127 126 байтов

Это зависит от особенностей gcc, x86 и 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;}

Попробуйте онлайн!

Спасибо @XavierBonnetain за -1 и менее неопределенное поведение.

05AB1E , 101 100 98 97 95 94 байта

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

-3 байта благодаря @Grimy .

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

Отсюда порт C-функции Ксавье Боннетейна (версия на 1106 битов) с тем же улучшением, которое @ceilingcat внес в свой ответ C, чтобы сэкономить 3 байта, так что не забудьте его оповестить!

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)

Смотрите этот 05AB1E наконечник шахты (разделы Как сжать большие целые числа? И Как сжать целые списки? ) , Чтобы понять , почему •α">η≠ε∍$<Θγ\&@(Σα•это 20576992798525946719126649319401629993024; •α">η≠ε∍$<Θγ\&@(Σα•₅весть [64,96,114,70,84,68,86,98,112,80,66,118,100,116,102,82,64]; Ƶ¹есть 285; •¾#kôlb¸ù,-ó"a·ú•есть 930891775969900394811589640717060184; •¾#kôlb¸ù,-ó"a·ú•₅весть [189,97,46,243,47,37,183,248,106,107,242,96,36,182,249]; и Ƶ∞есть 188.

Stax , 65 64 62 59 58 байт

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

Запустите и отладьте его

К сожалению, эта программа использует некоторые инструкции, которые внутренне используют некоторые устаревшие инструкции stax. Я просто забыл обновить их реализацию. Это приводит к появлению ложного предупреждения, но результаты все еще верны.

Это вдохновлено отличным ответом jimmy23013 . Некоторые детали были изменены, чтобы лучше подходить для Stax.

Программы Stax, написанные на ASCII для печати, имеют альтернативное представление, которое сохраняет чуть более 1 бита на байт, поскольку существует только 95 печатаемых символов ASCII.

Вот представление ascii этой программы, отформатированное для «читабельности» с комментариями.

{                       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

Запустите этот

Модифицированная версия для запуска для всех входов 0..255

Python 3 , 151 байт

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

Попробуйте онлайн!

Функция, которая реализует перестановку. Код использует только 7-битные символы ASCII.

Кодирует kкак строку Python 3, сдвинутую ^64в диапазон для печати. Напротив, sкодируется как базовые 256 цифр числовой константы, а цифры извлекаются как [number]>>[shift]*8&255. Это было короче, чем кодирование sв строке из-за необходимого количества escape-символов, даже с оптимальным сдвигом, ^160чтобы минимизировать их.

Вычисление дискретного логарифма выполняется в обратном направлении. Обновление x=x*2^x//128*285зацикливается в циклической группе, имитируя умножение на генерирование, пока оно не достигнет идентификатора x=1. Мы начинаем дискретный лог в l=255(длина цикла) и уменьшаем его на каждой итерации. Чтобы обработать x=0случай и сделать так, чтобы он не зацикливался вечно, мы также завершаем когда l=0, что делает x=0сопоставление с l=0указанным.

Python 2 проигрывает из-за отсутствия хороших строк байтов, поэтому мы должны это сделать map(ord,...)(ArBo сохранил здесь байт). Это позволяет нам использовать, /а не //для целочисленного деления.

Python 2 , 156 байт

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

Попробуйте онлайн!

JavaScript (ES6), 139 байт

Аналогично версии Node.js, но с использованием символов за пределами диапазона 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

Попробуйте онлайн!

JavaScript (Node.js) ,  149  148 байт

Основано на реализации C Ксавье Боннетейна (которая представлена здесь ).

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

Попробуйте онлайн!

кодирование

В исходном ответе Ксавье таблицы s[]и k[]хранятся в следующей строке:

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

Первые 17 символов являются представлениями ASCII, k[i] XOR 64а следующие 15 символов являются представлениями ASCII s[i-17] XOR 173или s[i-17] XOR 64 XOR 17 XOR 252.

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

Вот что мы получаем:

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$

NB: Это просто примечание, не связанное с ответами выше.

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

Попробуйте онлайн!

C # (интерактивный компилятор Visual C #) , 141 байт

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;}

Просто порт примера решения, портированный на C #.

Попробуйте онлайн!

Python 3 , 182 байта

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]

Попробуйте онлайн!

Python не собирается выиграть первый приз здесь, но это все еще 10-байтовый гольф лучшей программы Python здесь .

Python 3 , 176 байт

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

Попробуйте онлайн!

Как лямбда, он еще на шесть байт короче. Мне больно пользоваться if... else, но я не вижу другого варианта для короткого замыкания, учитывая, что 0 является возможным ответом.

Python 3 , 173 байта

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

Попробуйте онлайн!

Еще короче в байтах (хотя я не уверен насчет битов, потому что это больше не чистый ASCII), любезно предоставлено ovs.

Ржавчина , 170 163 байта

|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]}

Попробуйте онлайн!

Это порт моего решения в C с несколько иной строкой, который не требует xor 17. Я ожидаю, что большинство решений основано на строке "@` rFTDVbpPBvdtfR @ \ xacp? \ Xe2> 4 \ xa6 \ xe9 {z \ xe3q5 \ xa7 \ xe8 "также можно улучшить (просто измените строку, удалите xor 17 и xor 173 вместо 188).

Я удалил один из поисков, добавив 17*17к нему l, как мы (более или менее), в решении с машинным кодом ARM.

У Rust есть логический тип и замыкания, но его приведения (даже для логических значений или между целыми числами) всегда явные, изменчивость должна быть отмечена, у нее нет тернарного оператора, целочисленные операции, по умолчанию, паника при переполнении и операции мутации ( l+=1) возвращает единицу. Мне не удалось получить более короткое решение с итераторами, так как замыкания + отображение все еще довольно многословны.

Это, кажется, делает Rust довольно плохим выбором для игры в гольф. Тем не менее, даже на языке, который подчеркивает удобочитаемость и безопасность, а не краткость, мы слишком коротки.

Обновление: использовалась анонимная функция, по предложению manatwork.

05AB1E , 74 байта

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

Порт первого ответа желе @NickKennedy . Я работал над портом ответа CJam @jimmy23013 напрямую , но у меня уже было 78 байт, и мне все еще приходилось исправлять ошибку, поэтому она была бы больше. Это, безусловно, все еще можно сыграть в гольф совсем немного.

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

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

Смотрите этот 05AB1E наконечник шахты (разделы Как сжать большие целые числа? И Как сжать целые списки? ) , Чтобы понять , почему Ƶfэто 142; •5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•есть 29709448685778434533295690952203992295278432248, ƵŠесть 239; и •5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•ƵŠвесть [19,48,36,38,18,238,87,24,138,206,92,197,196,86,25,139,129,93,128,207].