107
\$\begingroup\$

The aim of this challenge is to find an impossibly short implementation of the following function p, in the langage of your choosing. Here is C code implementing it (see this TIO link that also prints its outputs) and a wikipedia page containing it.

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

What is p

p is a component of two Russian cryptographic standards, namely the hash function Streebog and the block cipher Kuznyechik. In this article (and during ISO meetings), the designers of these algorithms claimed that they generated the array pi by picking random 8-bit permutations.

"Impossible" implementations

There are \$256! \approx 2^{1684}\$ permutations on 8 bits. Hence, for a given random permutation, a program that implement it shall not be expected to need fewer than 1683 bits.

However, we have found multiple abnormally small implementations (which we list here), for example the following C program:

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

which contains only 158 characters and thus fits in 1264 bits. Click here to see that it works.

We talk about an "impossibly" short implementation because, if the permutation was the output of a random process (as claimed by its designers), then a program this short would not exist (see this page for more details).

Reference implementation

A more readable version of the previous C code is:

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

The table k is such that k[x] = L(16-x), where L is linear in the sense that L(x^y)==L(x)^L(y), and where, like in C, ^ denotes the XOR. However, we did not manage to leverage this property to shorten our implementation. We are not aware of any structure in s that could allow a simpler implementation---its output is always in the subfield though, i.e. \$s[x]^{16}=s[x]\$ where the exponentiation is done in the finite field. Of course, you are absolutely free to use a simpler expression of s should you find one!

The while loop corresponds to the evaluation of a discrete logarithm in the finite field with 256 elements. It works via a simple brute-force search: the dummy variable a is set to be a generator of the finite field, and it is multiplied by this generator until the result is equal to x. When it is the case, we have that l is the discrete log of x. This function is not defined in 0, hence the special case corresponding to the if statement.

The multiplication by the generator can be seen as a multiplication by \$X\$ in \$\mathbb{F}_2[X]\$ which is then reduced modulo the polynomial \$X^8+X^4+X^3+X^2+1\$. The role of the unsigned char is to ensure that the variable a stays on 8 bits. Alternatively, we could use a=(a<<1)^(a>>7)*(256^29), in which case a could be an int (or any other integer type). On the other hand, it is necessary to start with l=1,a=2 as we need to have l=255 when x is equal to 1.

More details on the properties of p are presented in our paper, with a writeup of most of our optimizations to obtain the previous short implementation.

Rules

Propose a program that implements the function p in less than 1683 bits. As the shorter the program, the more abnormal it is, for a given language, shorter is better. If your language happens to have Kuznyechik, Streebog or p as a builtin, you cannot use them.

The metric we use to determine the best implementation is the program length in bytes. We use the bit-length in our academic paper but we stick to bytes here for the sake of simplicity.

If your language does not have a clear notion of function, argument or output, the encoding is up to you to define, but tricks like encoding the value pi[x] as x are obviously forbidden.

We have already submitted a research paper with our findings on this topic. It is available here. However, should it be published in a scientific venue, we will gladly acknowledge the authors of the best implementations.

By the way, thanks to xnor for his help when drafting this question!

\$\endgroup\$
15
  • 14
    \$\begingroup\$ I hope someone submits an answer in Seed. \$\endgroup\$ Jun 7, 2019 at 5:43
  • 8
    \$\begingroup\$ Similarily, can, for example, brainfuck code be scored at 3 bits per character if it has no nops? And is the 1683 bits at most a strict restriction [sic?] or the goal? \$\endgroup\$ Jun 7, 2019 at 10:04
  • 36
    \$\begingroup\$ "If the permutation was the output of a random process (as claimed by its designers), then a program this short would not exist" I disagree (although it doesn't matter for the challenge). If it was the output of a random process, it would be unlikely that such program existed; or it would be difficult to find \$\endgroup\$
    – Luis Mendo
    Jun 7, 2019 at 11:13
  • 8
    \$\begingroup\$ @Grimy The statement then a program this short would not exist is a conceptual one (not a programming one). Using your terms, it belongs to the pure-math world, not to the programming world \$\endgroup\$
    – Luis Mendo
    Jun 7, 2019 at 12:16
  • 7
    \$\begingroup\$ It may have been already noticed, but just in case: \$s_i \text{ XOR } s_{i-1}\$ results in only 8 distinct values: \$1,10,68,79,146,153,220,221\$ (starting with \$i=1\$ and assuming \$s_0=0\$). \$\endgroup\$
    – Arnauld
    Jun 8, 2019 at 8:43

12 Answers 12

41
\$\begingroup\$

AMD64 Assembly (78 bytes or 624 bits of machine code)

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

    if(x) {
      for(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];
    }
    return x^252;
}

64-bit x86 assembly


    ; 78 bytes of AMD64 assembly
    ; odzhan
    bits   64

    %ifndef BIN
      global SubBytex
    %endif

SubBytex:
    mov    al, 252
    jecxz  L2                ; if(x) {
    call   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               ; skip XOR if no carry
    xor    al, 29            ;
    cmp    al, cl            ; if(y != x) goto 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            ; if(x == 0) goto L2
    jz     L2
    xchg   eax, edx          ; al = x
    xlatb                    ; al = k[x]
    xor    al, cl            ; al ^= s[z]
L2:
    ret

Disassembled 64-bit code

00000000  B0FC              mov al,0xfc
00000002  67E348            jecxz 0x4d
00000005  E820000000        call 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,cl
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,cl
0000004D  C3                ret

32-bit x86 assembly


    ; 72 bytes of x86 assembly
    ; odzhan
    bits   32

    %ifndef BIN
      global SubBytex
      global _SubBytex
    %endif

SubBytex:
_SubBytex:
    mov    al, 252
    jecxz  L2                ; if(x) {
    call   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               ; skip XOR if no carry
    xor    al, 29            ;
    cmp    al, cl            ; if(y != x) goto 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] or k[x]
    jz     L2                ; if(x == 0) goto L2
    xor    al, [ebx+ecx+17]  ; k[x] ^= k[z]
L2:
    ret

Disassembled 32-bit code

00000000  B0FC              mov al,0xfc
00000002  E345              jecxz 0x49
00000004  E820000000        call 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,cl
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
\$\endgroup\$
12
  • 1
    \$\begingroup\$ Nice answer! Since the OP was looking for bit count, this (85 bytes) comes out to 680 bits, using 8 bits per byte, or 595 bits using 7 bits per byte (possible since all the characters are ASCII). You could probably go shorter if you compressed to an even more restrictive character set. \$\endgroup\$
    – Cullub
    Jun 7, 2019 at 16:41
  • 1
    \$\begingroup\$ Welcome to PPCG; nice first solution. \$\endgroup\$
    – Shaggy
    Jun 7, 2019 at 17:27
  • 9
    \$\begingroup\$ @Cullub My point was, the code in this answer is just C/Assembler that gets compiled, so the byte count isn't that of the given code, but of the compiled code. And that's not ASCII. \$\endgroup\$
    – ArBo
    Jun 7, 2019 at 17:58
  • 7
    \$\begingroup\$ Just for clarification, the 84 bytes is the size of the machine code after this has been assembled? If so the title should be updated to reflect that this is a machine code answer rather than an assembly answer. \$\endgroup\$
    – Potato44
    Jun 7, 2019 at 23:06
  • 1
    \$\begingroup\$ And BTW, you don't have to use a standard calling convention; you can use a custom convention where RBX is call-clobbered, saving 2 bytes for push/pop. (And where uint8_t args are zero-extended to 64-bit for JRCXZ). Also, if you write position-dependent code you can put the table address into a register with a 5-byte mov ebx, imm32 instead of a 6-byte call/pop. Or use it as a disp32 in mov al, [table + rax], but that might lose since you have two xlatb and a mov already. The call+pop shellcode trick does win vs. 7-byte RIP-relative LEA with the data after the ret, though. \$\endgroup\$ Jun 8, 2019 at 19:45
29
\$\begingroup\$

CJam, 72 67 66 63 bytes

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

es* repeats something by the current timestamp, which is a big number, and it would take too long to finish.

Actually testable version, 64 bytes:

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

Try it online!

Try all online!

To run this code (on a Linux machine), you need to add the line en_US.ISO-8859-1 ISO-8859-1 into /etc/locale.gen and run locale-gen. Then you could use:

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

Or you could try this equivalent 72 byte UTF-8 version:

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

Explanation

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.

The characters in the string are:

  • 221. See below.
  • 48, 36, 38, 18. It's the linear decomposition of k based on the characteristics of L in the question.
  • 220, the filler value of array s when only array k is used.
  • Array s xor 220 reversed, except for the last element, or the first element before reversed, which is the 221 at the beginning of the string.
\$\endgroup\$
5
  • \$\begingroup\$ What would you do with power set? PS I'm probably going to steal that trick of doing the finite field operation in reverse. Very neat. \$\endgroup\$ Jun 9, 2019 at 8:00
  • \$\begingroup\$ @PeterTaylor You could get array k using the power set of [48 36 38 18] (or its reverse) with the most straightforward ordering, and reduce each by xor. But in the golfing languages used in this question so far, only 05AB1E had the right ordering. Jelly and Stax apparently had a different idea about what I thought should be straightforward. \$\endgroup\$
    – jimmy23013
    Jun 9, 2019 at 8:16
  • \$\begingroup\$ I'm currently in the process of golfing your answer to 05AB1E. What are the integer values for your string "Ý0$&Ü™ÖD�’\n˜×EO“N"? \$\endgroup\$ Jun 13, 2019 at 10:21
  • \$\begingroup\$ @KevinCruijssen Are you asking about what they meant, or their numeric values (which you could see from the hex dump)? \$\endgroup\$
    – jimmy23013
    Jun 13, 2019 at 11:12
  • \$\begingroup\$ @jimmy23013 Ah, of course.. Forgot about the hex-dump.. \$\endgroup\$ Jun 13, 2019 at 11:21
25
\$\begingroup\$

Jelly 71 59 bytes

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

Try it online!

Verify all possibilities

Now rewritten using a reworked version of jimmy23013’s clever CJam answer so be sure to upvote that one too! Uses only 472 bits (28.0% of the naive approach). @jimmy23013 has also saved another byte!

Explanation

Stage 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

Stage 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

Stage 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

Original approach

Jelly, 71 66 bytes

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

Try it online!

Verify all possibilities

A monadic link or full program that takes a single argument and returns the relevant value of pi[x]. This is 536 bits, so under a third of the naive storage of pi.

Saved 3 bytes by using the method for finding l from jimmy23013’s CJam answer so be sure to upvote that one too!

Explanation

Stage 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

Stage 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

Stage 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
\$\endgroup\$
1
18
\$\begingroup\$

C (gcc), 157 148 140 139 bytes

Modest improvement over the C example.

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

Try it online!

C (gcc), 150 142 127 126 bytes

This one depends on gcc and x86 and UTF-8 quirks.

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

Try it online!

Thanks to @XavierBonnetain for -1 and less undefined behaviour.

\$\endgroup\$
15
\$\begingroup\$

Stax, 65 64 62 59 58 bytes

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

Run and debug it

Unfortunately, this program uses some instructions that internally use some deprecated stax instructions. I just forgot to update their implementation. This causes some spurious warning to appear, but the results are still correct.

This is inspired by jimmy23013's excellent answer. Some parts have been changed to suit stax better.

Stax programs written in printable ASCII have an alternative representation that saves slightly more than 1 bit per byte, since there are only 95 printable ASCII characters.

Here's the ascii representation of this program formatted for "readability" with comments.

{                       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

Run this one

Modified version to run for all inputs 0..255

\$\endgroup\$
2
  • \$\begingroup\$ Stax has S for power set. You could get the power set of [18 38 36 48], index and reduce by xor. (I don't know Stax and I'm not sure it would be shorter though.) \$\endgroup\$
    – jimmy23013
    Jun 8, 2019 at 5:10
  • \$\begingroup\$ I think stax's ordering for subsets produced by the S operator aren't in the right order for that to work. e.g. "abc"SJ (powerset of "abc" joined with spaces) produces "a ab abc ac b bc c". \$\endgroup\$
    – recursive
    Jun 8, 2019 at 5:23
10
\$\begingroup\$

05AB1E, 101 100 98 97 95 94 bytes

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

-3 bytes thanks to @Grimy.

Try it online or verify all test cases.

Explanation:

Port of Xavier Bonnetain's C function (1106 bits version) from here, with the same improvement @ceilingcat made in his C answer to save 3 bytes, so make sure to upvote him!

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)

See this 05AB1E tip of mine (sections How to compress large integers? and How to compress integer lists?) to understand why •α">η≠ε∍$<Θγ\&@(Σα• is 20576992798525946719126649319401629993024; •α">η≠ε∍$<Θγ\&@(Σα•₅в is [64,96,114,70,84,68,86,98,112,80,66,118,100,116,102,82,64]; Ƶ¹ is 285; •¾#kôlb¸ù,-ó"a·ú• is 930891775969900394811589640717060184; •¾#kôlb¸ù,-ó"a·ú•₅в is [189,97,46,243,47,37,183,248,106,107,242,96,36,182,249]; and Ƶ∞ is 188.

\$\endgroup\$
3
  • \$\begingroup\$ @Grimy Thanks, I always forgot that kind of golf with the compressed integer lists.. (PS: You can surround code containing ` in the comments with two of them at both sides. I.e. with ' instead of `: ''code'code''.) \$\endgroup\$ Jun 7, 2019 at 12:50
  • \$\begingroup\$ Whoops, sorry about the messed up formatting. I know about doubling backticks, but I didn't realize the compressed list had a backtick in it. Also: s^ => ^ (XOR is commutative). Actually, isn't s^_ just the same as Q? \$\endgroup\$
    – Grimmy
    Jun 7, 2019 at 13:20
  • \$\begingroup\$ @Grimy Thanks! You're indeed right. We basically check if one of the following three things is truthy to exit the loop: i==0 || X==0 || X==1. \$\endgroup\$ Jun 7, 2019 at 13:54
9
\$\begingroup\$

Python 3, 151 bytes

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

Try it online!

A function that implements the permutation. The code uses only 7-bit ASCII chars.

Encodes k as a Python 3 bytestring, shifted ^64 into the printable range. In contrast, s is encoded as the base-256 digits of a numerical constant, and the digits are extracted as [number]>>[shift]*8&255. This was shorter than encoding s in a string due to the number of escape characters this required, even with an optimal shift ^160 to minimize those.

The discrete-log computation is done backwards. The update x=x*2^x//128*285 loops forward in the cyclic group by simulating multiplying by the generate, until it reaches the identity x=1. We start the discrete log at l=255 (the cycle length), and decrement it each iteration. To handle the x=0 case and make it not loop forever, we also terminate when l=0, which makes x=0 map to l=0 as specified.


Python 2 loses out on not having nice bytestrings, so we need to do map(ord,...) (ArBo saved a byte here). It lets us use / rather than // for integer division.

Python 2, 156 bytes

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

Try it online!

\$\endgroup\$
0
8
\$\begingroup\$

JavaScript (ES6), 139 bytes

Similar to the Node.js version, but using characters beyond the ASCII range.

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

Try it online!


JavaScript (Node.js),  149  148 bytes

Based on Xavier Bonnetain's C implementation (which is presented here).

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

Try it online!

Encoding

In Xavier's original answer, the tables s[] and k[] are stored in the following string:

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

The first 17 characters are the ASCII representations of k[i] XOR 64 and the next 15 characters are the ASCII representations of s[i-17] XOR 173, or s[i-17] XOR 64 XOR 17 XOR 252.

All the ASCII codes for k[i] XOR 64 are matching printable characters, but 7 ASCII codes for s[i-17] XOR 173 are beyond \$126\$ and need to be escaped. We force them into the printable range by subtracting \$128\$.

Here is what we get:

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"

By reversing the bitmask formed by the 2nd row in the above table, we get 110010011001001 in binary, or \$25801\$ in decimal.

This bitmask is multiplied by \$128\$, so that we can directly perform a bitwise OR with the extracted bit. Hence the formula:

| 3302528 >> i - b & 128

Building \$s\$

NB: This is just a side note, unrelated to the above answers.

This code demonstrates how \$s\$ can be built by XOR'ing only 4 distinct values together.

In this example, we are using all 15 non-empty subsets of \$\{1, 11, 79, 146\}\$, but other values can be chosen.

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

Try it online!

\$\endgroup\$
4
\$\begingroup\$

C# (Visual C# Interactive Compiler), 141 bytes

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

Just a port of the example solution, ported to C#.

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Python 3, 182 bytes

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]

Try it online!

Python isn't going to win first prize here, but this is still a 10-byte golf of the best Python program here.

Python 3, 176 bytes

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

Try it online!

As a lambda, it's six bytes shorter still. It pains me to have to use if... else, but I don't see another option for short-circuiting, given how 0 is a possible answer.

Python 3, 173 bytes

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

Try it online!

Even shorter in bytes (though I'm not sure about bits, because this isn't pure ASCII anymore), courtesy of ovs.

\$\endgroup\$
3
  • \$\begingroup\$ 3 bytes shorter by using the literal chars instead of \x.. escapes \$\endgroup\$
    – ovs
    Jun 7, 2019 at 15:11
  • \$\begingroup\$ slightly different method, same byte count \$\endgroup\$
    – ovs
    Jun 7, 2019 at 15:17
  • \$\begingroup\$ @ovs Thanks! Probably increases the bit count somewhat (not sure which is most important to the OP), so I'll keep my old answer too. \$\endgroup\$
    – ArBo
    Jun 7, 2019 at 15:24
4
\$\begingroup\$

Rust, 170 163 bytes

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

Try it online!

This is a port of my solution in C, with a slightly different string, that do not require to xor 17. I expect that most of the solutions based the string "@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8" can be improved as well (just change the string, remove the xor 17, and xor 173 instead of 188).

I removed one of the lookups by conditionally adding 17*17 to l, as we (more or less) did in the ARM machine code solution.

Rust has type inference and closures, but its casts (even for booleans or between integers) are always explicit, mutability has to be marked, it does not have a ternary operator, integer operations, by default, panic on overflow, and mutating operations (l+=1) returns unit. I did not manage to obtain a shorter solution with iterators, as closures+mapping is still fairly verbose.

This seems to make Rust a pretty bad choice for golfing. Nevertheless, even in a language that stresses readability and safety over conciseness, we're far too short.

Update: used an anonymous function, from manatwork's suggestion.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Except when called recursively, anonymous functions/lambdas are acceptable, so you can move let p= to Header and not count it. Unsure about the ;, as for anonymous call is not needed: Try it online!. \$\endgroup\$
    – manatwork
    Jun 17, 2019 at 11:27
2
\$\begingroup\$

05AB1E, 74 bytes

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

Port of @NickKennedy's first Jelly answer. I was working on a port of @jimmy23013's CJam answer directly, but I was already at 78 bytes and still had to fix a bug, so it would have been larger. This can definitely still be golfed quite a bit, though.

Try it online or verify all test cases.

Explanation:

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

See this 05AB1E tip of mine (sections How to compress large integers? and How to compress integer lists?) to understand why Ƶf is 142; •5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ• is 29709448685778434533295690952203992295278432248, ƵŠ is 239; and •5›@¾ÂÌLìÁŒ©.ðǝš«YWǝŠ•ƵŠв is [19,48,36,38,18,238,87,24,138,206,92,197,196,86,25,139,129,93,128,207].

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.