Encode - Shuffle - Decode

Question

Challenge

Your task is to encode an integer as a string of ASCII characters, then successfully decode it after said string has been randomly shuffled.

You will write two programs/functions, which will be referred to as Encoder and Decoder.

Encoder

• Input: an integer \$n\$ in the range \$[0,2^{31}-1]\$.
• Output: a string \$s\$ of ASCII characters (not necessarily printable).

Decoder

• Input: a random permutation \$s'\$ of the string \$s\$.
• Output: the integer \$n\$.

Scoring

Let \$A\$ be the maximum length of \$s\$ across all possible values of \$n\$. If the Encoder acts non-deterministically (which is allowed, see below), then the \$A\$ will be the maximum length of \$s\$ that may occur (possibly \$\infty\$).

Let \$L_E\$ be the length of the Encoder in bytes and \$L_D\$ the length of the Decoder in bytes.

Then your score is \$A\cdot(L_E+L_D)\$.

Victory is awarded to the submission the lowest score.

Time limit

There is a somewhat arbitrary time limit of 1 minute on the execution time of both the Encoder and the Decoder for a single testcase (i.e. a single value of \$n\$).

The goal is to avoid solution that find that brute-force the encoding by enumerating all sequences with certain properties. If your solution does something more clever than that, it will most likely fit the time constraint and will be considered valid. Likewise, if it works on TIO for some randomly selected values of \$n\$ it will be considered valid. Otherwise I will test it on my machine, but note that if your solution is pure brute-force it will almost certainly fail.

Rules

• The Encoder and the Decoder must be written in the same language.
• The Decoder must output the correct integer \$n\$ for every possible permutation \$s'\$ of the string \$s\$ returned by the Encoder.
• The Encoder and the Decoder are not allowed to share information in any way (e.g. by means of global variables or files).
• The output of the Encoder need not be deterministic (that is, the same input \$n\$ may produce different output strings if the Encoder is run multiple times), but the Decoder must always guess the correct integer \$n\$.
• The Encoder and the Decoder may take and return the integer \$n\$ in any convenient way (e.g. if \$n=14\$ it is fine for the input to be 14, "14" or [1,4]).
• The Encoder may output the string \$s\$ either by printing it on stdout or by returning a string, a list/array of characters or a list/array of integers in the range \$[0,127]\$; note that the Decoder will receive as input a permutation of \$s\$ as returned by the Encoder, so it should accept the string \$s'\$ in the same format as \$s\$.
• Standard loopholes are forbidden.
• If possible, explain how your code works and why the score you claim is correct.

Example

Assume \$n=14\$.

• The Encoder receives 14 as input. It may output "qwerty".
• The Decoder receives a permutation of "qwerty" as input, for instance "tweyqr". It must output 14 (in any convenient format).

The Encoder could have returned [113,119,101,114,116,121] as well, in which case the Decoder would have received (for instance) [116,119,101,121,113,114].

Note that the string returned by the Encoder may also include non-printable ASCII characters (but always in the range [0x00, ..., 0x7F]).

Answer 1

Jelly, (17 bytes + 18 bytes) × length 6 = 210 points

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

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

Try it online! (or with extra debug info)

Having had a go at solving this challenge aiming at the stated victory condition, I thought it'd be interesting to go for a hypothetical alternative victory condition: code-golf given a minimum possible maximum length for the output.

Explanation

Encoding

The first step in the encoding is to represent the input as base 36 (b36). 36⁶ = 2176782336 > 2147483647, so there will be at most 6 digits in the result, each of which is in the range 0–35.

Next, we transform this into a representation that contains 6 different digits. There are multiple possible algorithms for this, but the one used here is to add 1 to the smallest digit, 2 to the second-smallest, 3 to the third-smallest, and so on. This means that if two digits were the same, one of them will be arbitrarily considered smaller, and thus they'll become different; and obviously, this algorithm can't cause two different digits to become the same. In order to represent this in Jelly, we use Ụ ("sort indexes by values") to get a list of the indexes in sorted order; Ụ again to invert that, effectively mapping each element of the original to its position in sorted order; and µ…+ to add the original to the new list. The result is a representation of the input number as six different digits in the 1–41 range (minimum 0+1, maximum 35+6).

We then split this into yet another form: a sorted list of digits in the 1–41 range, alongside a number from 1 to 720 that represents which of the 720 possible permutations the digits were in. (The Œ¿ and Ṣ extract the permutation number and sorted list respectively.)

Finally, we convert the number from 1 to 720 into base 3 (b3), reverse it (U), and encode the six base 3 digits and six 1–41 digits via packing them each into a single ASCII character using reverse divmod (the value of the character mod 3 is the base 3 digit, the value divided by 3 is the 1–41 digit). The possible range of results is (1×3)+0=3 at minimum, and (41×3)+2=125 at maximum, fitting within our ASCII range. The packing is done via ×3 and +, together with an additional µ to make sure that every command operates on the right bit of data. (There's a bit of a golfing trick here, in that we do the multiplication by 3 before extracting the permutation; that saves the need to spend a byte on a grouping character.)

Incidentally, the reason to reverse the base 3 number is because it may have fewer digits than the 1–41 number. (It can't have more; the smallest number for which n! > 3ⁿ is slightly above 6.) Jelly effectively inserts trailing zeros when adding together two numbers of different lengths, in order to make them match up; trailing zeroes would affect the interpretation of the number, but leading zeroes wouldn't, so the reverse is used to ensure that the extra zeroes end up somewhere that won't mess up our answer.

Decoding

The first step in decoding is to extract the two numbers (the base 3 number and the 1–41 number). We can get their digits easily enough with division (:3) and modulo (%3) respectively, but how to know which order they were in? Well, the 1–41 number had its digits in sorted order, and digits in corresponding positions of the two numbers were stored in the same characters; thus, we can work out which order the 1–41 number's digits were shuffled into (by looking at their relative values) and know that the base-3 number's digits must have been shuffled the same way. In fact, because characters of our ASCII encoding sort the same way as the 1–41 number's digits (these were all distinct and they're more significant than the base 3 number's), we can simply put the characters of the encoding back into order with a sort Ṣ. So both extractions start with Ṣ, followed by %3 or :3 as appropriate.

While the 1–41 number's digits are still in sorted order, we have a very convenient/terse way to go back to the 0–35 digits of base 36; just subtract 1 from the first, 2 from the second, 3 from the third, and so on. In Jelly, we can do that with _J ("subtract index").

Meanwhile, in the other branch of the decode, we reverse the base 3 number's digits back into order (U), and convert it from base 3 back into a permutation index with ḅ3.

We can then combine the two branches with œ?Ç; œ? means "permute given this permutation index", and Ç means "the result of applying the line above", i.e. it's what tells Jelly to run both lines separately on the same input.

What we have now is the digits of the original number, in base 36 (due to the _J), and in the original order (due to the œ?), so we can simply do a ḅ36 to convert back from base 36 into a single integer.

Commentary

The TIO! link above uses 312699167 as the number to encode. This number in base 36 is [5, 6, 6, 8, 7, 35], and thus shows off all aspects of the encoding: the 35 tests the limit of the 0–127 range we have; the duplicate 6s test the resolution of identical digits in the original base 36; and the fact that the digits are almost (but not quite) sorted means that the permutation number is very small, giving it many fewer digits than the base 36 number, and thus showing the need to reverse it before adding it to the original.

It's really convenient how all the constants here fit together. 36⁶ is only just high enough to fit 2³¹, 3⁶ is only just high enough to fit 6!, and (36+6)×3 is only just high enough to fit within the 128 possibilities we have. (The last constraint here is the least tight, because we could use 0-indexing rather than 1-indexing to make use of characters in the 0-2 range. Still, that'd only give enough room to use 37 as the base rather than 36.)

Answer 2

Jelly, (4 3 bytes + 6 5 bytes) × length 8 = 80 64 points

b⁴Ä

ṢŻIḅ⁴

Try it online!

Jelly, (2 1 byte + 4 3 bytes) × length 10 = 60 40 points

Ä

ṢŻI

Try it online!

Explanation

Solution 1

This is using a different algorithm from most of the other answers. We start by encoding the value in hexadecimal (b⁴), as with the other answers, then take a cumulative sum (Ä). Each input will clearly give a different output (as both these operations are reversible), and given that the hexadecimal encoding will contain at most 8 digits whose maximums are 7 (for the 8th-last digit) and 15 (for the last to 7th-last digits), the maximum number in the output list will be 7+(7×15) = 112, less than the 127 required by the question. Additionally, the output will necessarily be in sorted order, allowing us to reverse the shuffle.

For the decoder, we first reverse the shuffle with a sort (Ṣ); then reverse the cumulative sum, by prepending a zero (Ż) and taking the difference of consecutive pairs (I); then convert back from hexadecimal (ḅ⁴).

Solution 2

The question actually allows us to take the input as a list of (presumably decimal) digits, so we can "cheat" by simply removing the base conversion; the maximum number used in the output will then be 2 + (9×9) = 83 (actually 82 because 2999999999 is out of range, so the worst possible input is 1999999999). The resulting encoding is pretty terrible as encodings for this problem go, but it has the advantage of being very terse to generate, which outweighs the verbosity of the encoding.

This answer feels so much like cheating that it's not my primary solution for this problem, but it seems like it's worth adding because it technically complies with the rules and produces a better score.

Commentary

I have some algorithms in mind for getting below length 8, but it seems unlikely you could implement a length-7 algorithm in ≤9 bytes (non-cheating) or ≤5 bytes (cheating), so by the scoring in the question, this is likely the best way to do it. (I might have a go at a solution for the alternative "minimize the length of the encoding" challenge anyway, though, just for fun.)

Unlike some of the solutions, the use of 16 as the base here isn't critical; there are plenty of other numbers that would work for a length 8 solution (e.g. 18). I picked 16 for the first solution simply because Jelly has a 1-byte way to represent that, and other viable bases would need to use up multiple bytes from the program. Of course, the second solution needs to use 10 as the base in order to exploit the loophole.

Thanks to @Dennis for pointing out some newer Jelly commands that made this algorithm even terser to write.

Answer 3

Shakespeare Programming Language, 10 * (264 + 494) = 8650 7910 7580

Encoder: 264 bytes

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

Try it online!

Decoder: 494

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

Try it online!

This was a thing.

The encoder encodes each digit as the digit plus the index of the digit times twelve. The decoder stores all the input in the Ford's memory and then loops over a counter, outputting then deleting each digit lower than the counter*12 + 10.

Explanation:

Encoder

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

Decoder

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

Answer 4

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

Encoder (69 52 bytes):

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

Decoder (41 37 bytes):

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

Stores the all the non-zero bits in the input number as ascii values. The value of the ascii character stores the position of the set bit. For example the value 'a' would mean that the 97th bit is set.

A few improvements, thanks to @Delfad0r

Try it online!

Answer 5

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

Encoder (45 bytes):

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

Decoder (38 bytes):

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

Try it online!

Answer 6

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

Encoder, 10 bytes

Ç·MÉJ'♀τ│½

Run and debug it

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

The encoder outputs the string in an increasing order.

Decoder, 9 bytes

üL∟n╫k∞‼9

Run and debug it

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

Answer 7

05AB1E, 8 maximum length * (8 + 7) bytes = 120

Encoder (8)

hεHN16*+

Try it online!

Decoder (7)

{16%hJH

Try it online!

Uses the same technique as wastl and Jonathan.

Answer 8

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

The encoder outputs an array of \$0\$ to \$8\$ integers. The decoder takes the same format as input.

Encoder (40 bytes)

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

Decoder (32 bytes)

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

Demo

Try it online!

How?

The input is divided into 8 blocks of 4 bits and each block is encoded with 1 among 16 possible characters. The most significant bit of the last block is never set.

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

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

Answer 9

Jelly, (8 + 9) bytes * 8 max-length = 136

b⁴+J’Ɗ⁴¡

Encoder (footer formats the list as Python would for clarity)

Ṣ_J‘Ɗ⁴¡ḅ⁴

Decoder

It's theoretically possible to have a max-length of six, can that be done in 22 bytes or fewer?

It's impossible with a max-length of five since \$\sum_{i=0}^{i=5}\binom{127+i}{127}=321402081< 2^{31}-1\$

How?

Since \$2^{31}-1\$ is encodable as 8 hexadecimal digits (7fffffff or [7,15,15,15,15,15,15,15]) we may then add the zero-based index of each hex-digit multiplied by 16 to ensure such a conversion is always in sorted order while keeping even the rightmost value in-bounds (i.e. [7,15,15,15,15,15,15,15] + [0,16,32,48,64,80,96,112] = [7,31,47,63,79,95,111,127]). Decoding is then reversing this same process.

Encoder:

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

Decoder:

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

Answer 10

Shakespeare Programming Language, 31 * (472 + 383 379 344) = 26505 26381 25296

Previous score: 16909322 * (246 + 217) = 7829016086

This is still very high, but it's the lowest I can think of right about now.

Encoder:

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

Try it online!

Decoder:

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

Try it online!

Basically, if the string contains a character with the ASCII code (n+1), the nth binary digit is set.

Answer 11

Charcoal, score 10 * (10 + 15) = 250.

Uses decimal; previous base 16-based solution scored 328 296 264.

May output nonprintable characters. In particular, character 10 is tricky to input to Charcoal.

Encoder, 10 bytes:

⭆⮌Ｓ℅⁺Ｉι×χκ

Try it online! Link is to verbose version of code.

Decoder, 15 bytes:

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

Try it online! Link is to verbose version of code.

Version using a list of integers scores 360 296 (base 16; decimal would score 310):

Encoder, 19 bytes:

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

Try it online! Link is to verbose version of code.

Decoder, 18 bytes:

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

Try it online! Link is to verbose version of code.

Version using printable characters scores 360 (was 416 384 368 in base 16):

Encoder, 19 bytes:

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

Try it online! Link is to verbose version of code.

Decoder, 17 bytes:

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

Try it online! Link is to verbose version of code.

Answer 12

Python 3, (208 bytes + 200 bytes) * 6 length = 2448

Try it online! (contains both, the extra byte is the newline between them).

-4 bytes (-24 score) by utilizing the empty list (which allowed more things to start at 0)

Encoder (208 bytes)

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

Decoder (200 bytes)

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

Observations:

• Shuffling can be losslessly reversed for strictly non-increasing (i.e. sorted) lists.

• Strictly non-increasing numerical lists of the same length can be totally ordered (as they are in Python).

• We can define that lists are ordered by length first to form a total order of all sorted lists.

• We can form an indexable sequence of these lists if we define that the only valid values in a list are integers from 0 to 127 inclusive (i.e. there exist a finite number of valid lists with length L).

Strategy:

• Encoder: Given a number N, find the Nth valid strictly non-increasing list.

• Decoder: Given a (shuffled) valid list, sort it and return its index in the sequence of valid lists.

Common code explanation:

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

• Compute the nth d-simplex number

  • For d=0, always 1

  • For d=1, n (the number of dots in a line of dots with length n)

  • For d=2, \$\sum_{i=1}^{n} i\$, (the number of dots in a triangle of dots with side length n)

  • For d=3, \$\sum_{j=1}^n \sum_{i=1}^{j} i\$, (the number of dots in a tetrahedron of dots with side length n)

Encoder explanation:

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

• n is the input number, h is the "high value" (i.e. the highest number allowed + 1), d is the length the output will be, s is the output, l is the "low value" (starting at 0, explained more later)

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

• There are T(h,d) valid length-d lists, and our calculation is easier if n is an index relative to the list [0]*d (at index 0) instead of an actual index, so decrement n accordingly. This also adjusts d (the length) to be correct for the given n.

• for i in range(d):

• Effectively: "for the i+1th number in the list"

  • This is where I will explain l, the "low value"

  • After a number has been put into the list, no number less than it can be put in the list (to keep it sorted), so l is the last number that was added to the list.

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

  • If n is too big to be encoded with an l at this "digit", then adjust n accordingly and increment l

  • s+=[l]

  • Encode n with an l at this "digit".

  • At first, we have h options for what "digit" to put in next, but once we put in a "digit" (which is assigned to l), we are limited to h-l options for the next "digit".

  • At first there were T(h,d) valid lists, but we have added a "digit" l, decreasing the number of "digits" left to d-1 and the number of valid next "digits" to h-l, so the number of valid lists after this is T(h-l,d-1)

Decoder explanation:

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

• s is the (shuffled) input list, so s.sort() it; l is the "low value" (h the "high value" is just literal 128s in the code to save bytes), n is the output number, d is the length.

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

• Adjust n to the point in the sequence of [0]*length

• for i in s:

• For each digit:

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

  • Adjust n to the point in the sequence of [...prevdigits, thisdigit, 0...]

    • l=i: Set the "low value" to the most recent digit

    • d-=1: Decrement the length since we used a digit

• return n: After n has been adjusted for all of the digits, it is the right number; return it.

Sorry if this isn't clear, but here's my original nongolfed debug version Try it online!, which doesn't use the empty list, so is 1 off from all numbers used in this version

Answer 13

Ruby, (36+29 bytes)*8, score 520

Encode:

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

Try it online!

Decode:

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

Try it online!

How it works:

The number is encoded using 4-bit chunks and a 3-bit index.

Decoder takes the input array and puts every nibble into its place again.

Answer 14

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

Encoder Try it online!, 14 bytes:

I8FfPSD8*L+o|;

Decoder Try it online!, 13 bytes:

iEh8SD4*2$X*+

Since this can output unprintable ascii characters, thus messing with the decoder, there is now a version using numbers in the output / input:

Encoder Try it online!, 14 bytes:

I8FfPSD8*L+N|;

Decoder Try it online!, 13 bytes:

IEh8SD4*2$X*+

Encoding:

The encoding works by breaking the given number into 8 x 4bit chunks. These chunks are then shifted right by 3 bit and the original location of the chunk is appended on the end as a number between 0 and 7. Thus the encoding looks like this:

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

Answer 15

Brachylog, 17+18 bytes * 8 length = 280

Encoder:

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

Decoder:

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

A p can be added to the end of the encoder with no effect. The decoder is run by putting the (shuffled) result as the output and getting the original number in the input.

If there would be a (properly implemented) cumulative sum predicate the score could drop down to 20

Try it online!

Answer 16

05AB1E, score: (2 + 2 bytes) * 11 maximum length = 44

Encoder (2 bytes):

.¥

Try it online.

Decoder (2 bytes):

{¥

Try it online.

Input of the encoder and output of the decoder are a list of digits.

Port of @ais523's 2nd Jelly answer.

Explanation:

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

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

Because .¥ prepends a zero to the output, the length of the output is the length of the input + 1. Since \$2^{31}-1\$ has a length of 10 digits, the maximum length of the output is 11.

Answer 17

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

Encoder:

{^@_ Z~@_}

Decoder:

{.sort X%10}

Try it online!

The encoder function zips each digit with the 0-index of the number. Then the encoder sorts the list of numbers and gets the modulo by 10, in other words the second digit of the number.

The total is 10, since that's the maximum length of 2³¹-1.

Answer 18

Haskell, 10*(23+51) = 740

Here's a program that encodes, shuffles, decodes and validates values: Try it online!

Encoder, 23 bytes

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

Try it online!

Decoder, 51 bytes

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

Try it online!

Explanation

Since we're allowed to use input as decimal digits, we'll use that.. The encoder maps each digit that occurs to 10*index + digit, note that all digits will be in [0..9] so we can reverse the above by using divMod. After restoring the indices and the digits it's only a matter of sorting by the indices and getting rid of them.

The solution is expected to work for values up to \$2^{31} - 1 = 2147483647\$ which is 10 digits long, so the maximum code-point we get will be \$9 \cdot 9 = 81 < 128\$. Also each digit will be converted to a "character", so we'll end up with a maximal length of 10.

Answer 19

Husk, 10*(7+8) = 150

Straight port of my Haskell solution only with the observation that \$10 \cdot 9 = 90 < 128\$ (Husk's N is 1-based):

Encoder, 7 bytes

zo+*10N

Try it online!

Decoder, 8 bytes

m→Ö←m‰10

Try it online!

Answer 20

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

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

Try it online! (contains 5 extra bytes for the assignments and the newline).

Uses ⎕IO←0

How:

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

---

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

Answer 21

PHP, 8*(44+53) = 776

encoder, 44 bytes:

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

prints space separated list of integers. Run as pipe with -nR.

maximum 8 bytes with 4 data bits (lower nibble) and 3 weight bits (upper nibble).

Simply put:
Put each hex digit in an own character and use the upper half of the byte to store the digit´s position.

example:

1457893891 (0x56e5b203) will turn into
0x03, 0x10, 0x22, 0x3b, 0x45, 0x5e, 0x66, 0x75
→ 3 16 34 59 69 94 102 117

decoder, 53 bytes:

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

or

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

or

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

take integers from command line arguments. Run with -nr.

---

Try them online.

Answer 22

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

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

Try it online!

EDIT: Thanks to Jo King for the pointers - not sure why I was offsetting by 32, in retrospect.

Encodes the position and value of each place as a single character, starting with [space] (position 0, value 0) the NUL byte 0x0.

Decodes by:

• sorting the string (Python will sort characters by their ordinal value)
• converts each character into its ordinal value
• takes the last digit of each ordinal integer
• joins the integers into a string
• converts the joined string back into an int

Answer 23

C (gcc), 10*112 = 1120

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

Try it online!

I have global variables, but they are not actually passing any info between two functions. Variable declaration for c is used in both functions saving me 2 bytes in code length.

A version that uses printable ASCII only for a 3 5 byte penalty is here:

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

Thanks @ceilingcat for 70 points improvements.