Encode - Shuffle - Decode 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]).
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). 366 = 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! > 3n 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. 366 is only just high enough to fit 231, 36 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.)