10
\$\begingroup\$

Suppose we want to encode a large integer \$x\$ as a list of words in such a way that the decoder can recover \$x\$ regardless of the order in which the words are received. Using lists of length \$k\$ and a dictionary of \$n\$ words, there are \$\binom{n+k-1}k\$ different multisets possible (why?), so we should be able to represent values of \$x\$ from \$1\$ through \$\binom{n+k-1}k\$.

This is a code golf challenge to implement such an encoder and decoder (as separate programs or functions); your golf score is the total code length. Any sensible/conventional input & output formats are allowed.

Encode: Given positive integers \$n,k,x\$ with \$x\le\binom{n+k-1}k\$, encode \$x\$ as a list of \$k\$ integers between \$1\$ and \$n\$ (inclusive).

Decode: Given \$n\$ and a list of \$k\$ integers between \$1\$ and \$n\$, output the decoded message \$x\$.

Correctness requirement: If encode(n,k,x) outputs \$L\$ and \$\operatorname{sort}(L)=\operatorname{sort}(M)\$, then decode(n,M) outputs \$x\$.

Runtime requirement: Both operations must run in polynomial time with respect to the length of \$x\$ in bits. This is meant to rule out impractical brute-force solutions that just enumerate all the multisets.

\$\endgroup\$
4
  • 3
    \$\begingroup\$ Your restricted complexity requirement is perfectly legitimate, but impractical brute-force solutions and code-golf are actually good ol' friends. :-) \$\endgroup\$
    – Arnauld
    Commented May 18, 2023 at 10:40
  • 1
    \$\begingroup\$ I admit I'm less interested in the byte-level golf and more interested in seeing simple practical algorithms for this problem! Should I change the post in some way to reflect this? \$\endgroup\$
    – Karl
    Commented May 18, 2023 at 16:22
  • \$\begingroup\$ @Karl codegolf and simple/practical are pretty much mutually exclusive. If you are interested in the latter I suggest you drop the codegolf tag. Or rather I would suggest it if there weren't already an answer. \$\endgroup\$
    – loopy walt
    Commented May 19, 2023 at 10:09
  • 3
    \$\begingroup\$ Is there a reason that you expect this to be possible within the complexity constraint of polynomial in the bit-length of \$x\$? I think the most efficient algorithm will be much like those on en.wikipedia.org/wiki/… with tweaks to cater for repeats, which I don't think will be. \$\endgroup\$ Commented May 19, 2023 at 16:40

3 Answers 3

3
\$\begingroup\$

Python, 258 bytes

from numpy import*
P=cumprod;p=prod
def e(x,k):r=r_[:k]+1;f=p(r);X=x*f-f;i=int(X**(1/k));Q=P([1,*i+r]);Q[-2::-1]*=P(i+1-r);j=sum(Q<=X);x-=Q[j-1]//f;k-=1;return*(1//k*[x]or e(x,k)),j+i-k
d=lambda L,j=1:1+sum([p(s-1+r_[:j])//p(r_[1:(j:=j+1)])for s in sort(L)])

Attempt This Online!

Two functions e and d for encoding and decoding: We do not use or accept parameter n since it is not needed (because using the "natural" encoding different n will give the same result provided they are large enough).

Multisets are represented as sorted sequences; the decoder also accepts unsorted input.

With n eliminated it actually makes sense to talk about complexity in x because now x can grow without bound.

I'll assume fixed k and that all basic operations including taking the kth root are polynomial in the bit length of their operands. As k is fixed this will also hold for all factorials and binomial coefficients the functions use.

How?

Decoding is easy since it amounts to summing a couple of binomial coefficients.

Encoding is a bit more tricky as we need to invert binomial coefficients (in n, k is fixed) to make this constant in terms of basic operations we use the simple inequality

\$n^\underline k \le n^k \le n^\overline k\$

where the underline and overline denote falling and rising factorials.

To find the largest n such that

\$\begin{pmatrix}n+k-1 \\ k \end{pmatrix}\le x\$

we take the kth root of k!x and then brute force check all rising factorials whose terms "pass" through the value obtained, k in total.

\$\endgroup\$
2
  • \$\begingroup\$ Apologies for my mistake and the previous comments and thank you for taking the time to respond to them! \$\endgroup\$
    – Hunaphu
    Commented May 20, 2023 at 14:36
  • 1
    \$\begingroup\$ @Hunaphu no worries. Good to see you figured it out in the end. \$\endgroup\$
    – loopy walt
    Commented May 20, 2023 at 19:44
1
\$\begingroup\$

Charcoal, 80 + 31 = 111 bytes

Encoder, 80 bytes

NθNη≔⁰ζ≔⁰ε≔¹δW¬›δη«≔δε≦⊕ζ≔÷×δ⁺ζθζδ»F⮌…⁰θ«W›εη«≦⊖ζ≔÷×εζ⁺ζ⊕ιε»⟦Iζ⟧≧⁻εη¿ι≔÷×ε⊕ι⁺ζιε

Try it online! Link is to verbose version of code. 0-indexed. Takes k and x as inputs. Explanation: Port of the sord function from this Math.SE answer, but outputs the values in reverse order since it's golfier.

Decoder, 31 bytes

W⁻θυF№θ⌊ι⊞υ⌊ιIΣEυ÷Π…·ι⁺ικΠ…·¹⊕κ

Try it online! Link is to verbose version of code. 0-indexed. Takes a list of k integers as input. Explanation:

W⁻θυF№θ⌊ι⊞υ⌊ι

Sort the integers.

IΣEυ÷Π…·ι⁺ικΠ…·¹⊕κ

Apply the ords algorithm from this Math.SE answer.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Isn't the sord function O(x^{1/k}) which is not polynomial in the bit length of x? I can't read charcoal, so I looked at the math SE code instead. (I was curious because efficient inversion of the binomial coefficient was what I got stuck at at my own attempts.) \$\endgroup\$
    – loopy walt
    Commented May 19, 2023 at 5:50
  • 1
    \$\begingroup\$ @loopywalt The Math.SE question asks for the most efficient algorithm. I just assumed that it would be good enough for this question... \$\endgroup\$
    – Neil
    Commented May 19, 2023 at 7:22
0
\$\begingroup\$

Haskell, 283 bytes

import Data.List
i=fromIntegral
p=product
m=map
s=succ
t=pred
f n=p[1..n]
a k n=p[n..n+k-1]`div`f k
b k x=t$until((>x).a k)s$floor((i$x*f k)**(1/i k))
d _ _[]=0
d k n(e:f)=a k e+d(k-1)e f
e 1 n x=[x]
e k n x|let m=b k x=m:e(k-1)m(x-a k m)
c k n=(m s.e k n.t,s.d k n.m t.reverse.sort)

Try it online!

\$\endgroup\$

Your Answer

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

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