6
\$\begingroup\$

Description

Inspired by this question, write a program/function to encode a number and a program (possibly the same as the first) to decode a bitstream in variable-length encoding as follows (taken from that question's answer, slightly modified):

Represent the string x using the following encoding:

$$0, x_k, \dots, 0, x_2, 0, x_1, 1, x_0$$

where \$x_0\$ is just \$x\$, then \$x_{i+1} = \mathrm{len}(x_i)\$ is a binary representation of the length of \$x_i\$ in bits (namely, \$\mathrm{len}(x_i)=\mathrm{ceil}(\log_2 x_i)\$, for \$i \ge 1\$), and \$k\$ is the smallest \$k \ge 1\$ such that \$x_k \le 3\$.
In particular, you always encode \$x_k\$ with 2 bits, and encode \$x_i\$ with \$x_{i+1}\$ bits.

Some example encodings:

Decimal Encoded
0 00110
1 00111
2 010110
3 010111
4 0111100
8 011010011000
127 011011111111111

Note that based on this encoding, the first bit is always 0, and the next 2 bits afterwards always encode the length of the next part.

Input/Output

For the encoder, it will take as input a list of non-negative integers, which may be empty (in any list representation you like), and output the string as per the encoding above. When encoding multiple numbers, simply concatenate the encoding. If the input is an empty list, output empty string.

For the decoder, it will take as input a (possibly invalid encoding, but always consists only of 0 and 1) bit string, and output a list of integers it encodes (in the same representation as the input to your encoder). If the string is an invalid encoding, you can output anything that cannot be misconstrued as a valid list of integers. For example, you can just output "INVALID" as the whole output, or you output "X" after outputting partially decoded list of integers (e.g., when the first part of the string is valid, but the later one isn't). As long as your invalid output cannot be read as a list of integers as a whole (in the same representation you use for the encoder input), it's fine. This includes terminating with an exception or a non-zero exit code (since it's also not a valid input to the encoder).

Scoring

This is code golf, the score of an answer is the sum of the number of bytes in both programs. If your program can do both in the same program, the length of that program is the score. Lowest score wins. Standard code golf rules apply.

Test Cases

Some test cases (input, then output on the next line, separated by a blank line):

Encoder

2
010110

1 5 3
001110111101010111

0 0 1
001100011000111

8 127 512 987654321
0110100110000110111111111110110100010101100000000001101010111101111010110111100110100010110001



The last test case is an empty list as input, and empty string as output

Decoder

010110
2

001110111101010111
1 5 3

001100011000111
0 0 1

00111011110010111
Invalid (a new number starts with 1)

1
Invalid (a new number starts with 1)

0011000110001
Invalid (not complete)

001100011001101001100
Invalid (not complete)

0011000110011010
Invalid (not complete)

0110100110000110111111111110110100010101100000000001101010111101111010110111100110100010110001
8 127 512 987654321



The last test case is an empty string, outputting empty list (which is empty string in this case, but it depends on your list representation)

\$\endgroup\$
6
  • \$\begingroup\$ Can we throw an exception/terminate with a non-zero exit code when decoding finds an invalid input? \$\endgroup\$
    – corvus_192
    Commented Dec 1, 2022 at 10:40
  • \$\begingroup\$ @corvus_192, hmm. I guess so. Since the idea is that the encoder and decoder should be chainable. If the input is invalid, it should break the chain anyway. I'll include this. Also, didn't know we need the backslash for the mathjax to work. Thanks corvus. \$\endgroup\$
    – justhalf
    Commented Dec 1, 2022 at 11:10
  • 2
    \$\begingroup\$ Was there any particular reason not to encode 0-3 as 100, 101, 110 and 111? \$\endgroup\$
    – Neil
    Commented Dec 1, 2022 at 13:36
  • \$\begingroup\$ @Neil That question might be better suited to the person who came up with the encoding in the linked ComputerScience stackexchange answer. :) \$\endgroup\$ Commented Dec 1, 2022 at 13:41
  • \$\begingroup\$ @KevinCruijssen Ah, I didn't realise the link was to a different site. (And not one that I can be bothered to create an account on. I see the author explicitly said 3 wasn't encoded as 111... shame.) \$\endgroup\$
    – Neil
    Commented Dec 1, 2022 at 13:52

4 Answers 4

3
\$\begingroup\$

JavaScript (ES6), 170 bytes

Encoder, 85 bytes

a=>a.map(g=(n,_,i,b=n.toString(2))=>(i=+!!i)|n>3?g(b.length)+i+b:i+=n<2?0+b:b).join``

Try it online!

Commented

a =>                // a[] = input array
a.map(g = (         // g is a recursive callback function taking:
  n,                //   n = current integer
  _,                //   the index is ignored
  i,                //   the reference to the array is used as a flag
                    //   (either defined or undefined)
  b = n.toString(2) //   b = binary representation of n
) =>                //
  (i = +!!i) |      //   turn i into either 0 or 1
  n > 3 ?           //   if i = 1 or n is greater than 3:
    g(b.length) +   //     do a recursive call with the length of b
    i + b           //     append i, followed by b
  :                 //   else:
    i +=            //     append i, followed by:
      n < 2 ?       //       if n is less than 2:
        0 + b       //         a leading '0' and b
      :             //       else:
        b           //         just b
).join``            // end of map(); join everything

Decoder, 85 bytes

Throws an error if the input is invalid.

f=(s,n=3,S=s.slice(n))=>s?(k='0b'+s.slice(1,n))[n]?s>k?[+k,...f(S)]:f(S,-~k):_:n-3||s

Try it online!

Commented

f = (             // f is a recursive function taking:
  s,              //   s = input string
  n = 3,          //   n = length of current bit block
  S = s.slice(n)  //   S = remaining string after the current block
) =>              //
s ?               // if s is not empty:
  ( k =           //   define k as:
    '0b' +        //     the binary prefix followed by
    s.slice(1, n) //     the current bit block without the leading digit
  )[n] ?          //   if k is as long as expected:
    s > k ?       //     if the leading digit is '1':
      [ +k,       //       append k, coerced to an integer
       ...f(S) ]  //       followed by the result of a recursive call with S
    :             //     else:
      f(S, -~k)   //       do a recursive call with S and n = k + 1
  :               //   else:
    _             //     force an error (undefined variable)
:                 // else:
  n - 3 ||        //   force an error if n is not equal to 3
  []              //   otherwise, stop the recursion properly
\$\endgroup\$
2
  • \$\begingroup\$ @KevinCruijssen Thanks for the notification. Should be fixed now. \$\endgroup\$
    – Arnauld
    Commented Dec 1, 2022 at 12:31
  • 1
    \$\begingroup\$ Np. You've accidentally used the wrong TIO for the encoder (both TIO links were the decoder), so I've just fixed it. Feel free to modify it the way you want it again if necessary. \$\endgroup\$ Commented Dec 1, 2022 at 13:38
2
\$\begingroup\$

Python3, 300 bytes

Encoder, 142 bytes

def e(x,l='1'):return''.join(e(s)for s in x)if type(x)is list else '0'+f"{x>>1}{x&1}"if x<4 and l=='0'else e(len(bin(x)[2:]),'0')+l+bin(x)[2:]

Try it online!

Decoder 158 bytes

def d(s,l=2,t=0):return''if s==''and t==0else d(s[1+l:],int(s[1:1+l],2),1)if s[0]=='0'else str(int(s[1:1+l],2))+' '+d(s[1+l:],2,0)if s[0]=='1'and t==1else 1/0

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Commented Dec 2, 2022 at 16:19
  • 1
    \$\begingroup\$ you can replace bin(x)[2:] with f'{x:b}' for -2 bytes each. \$\endgroup\$
    – justhalf
    Commented Dec 6, 2022 at 4:53
1
\$\begingroup\$

Charcoal, 115 bytes

Encoder, 43 bytes

FEA⟦ι⟧«W∨⁼¹Lι‹³⌊ι⊞ιL⍘⌊ι²⪫⮌Eι⁺¬λ⁺…0∧λ‹κ²⍘κ²ω

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

FEA⟦ι⟧«

Loop over the input list, but wrap each number in its own list.

W∨⁼¹Lι‹³⌊ι

Repeat until the list has at least two elements and the smallest element is no more than 3.

⊞ιL⍘⌊ι²

Push the length in binary of the smallest element to the list.

⪫⮌Eι⁺¬λ⁺…0∧λ‹κ²⍘κ²ω

Output the elements in binary in ascending order prefixing the last one with 1 and the rest with 0 or 00 if it is less than 2.

Decoder, 72 bytes

W∧θ⁼§θ⁰0«≔²ηW∧∧‹ηLθ⁼§θ⁰0θ«≔Φκ›μηθ≔⍘…κ⊕η²η»¿‹ηLθ«⟦I⍘…Φθλη²⟧≔Φθ›ληθ»≔1θ»Lθ

Try it online! Link is to verbose version of code. Will output at least one - at some point if the string is invalid. Explanation:

W∧θ⁼§θ⁰0«

Repeat until the string has been processed.

≔²η

The first block is of length 2.

W∧∧‹ηLθ⁼§θ⁰0θ«

Repeat while there's a valid bit block starting with 0...

≔Φκ›μηθ

... cut the string after the block, and...

≔⍘…κ⊕η²η

convert the block from binary to give the length of the next block.

»¿‹ηLθ«

If there's still a valid bit block, then...

⟦I⍘…Φθλη²⟧

... output its value on its own line, and...

≔Φθ›ληθ

... cut the string after the block.

»≔1θ

Otherwise set the string to an invalid value.

»Lθ

Output at least one - if the string was invalid.

\$\endgroup\$
1
\$\begingroup\$

Python 3, 117+154 = 271 bytes

Represents a list as space-separated integers.

Each is a full program, taking input from stdin, outputting to stdout.

Encoder, 117 bytes

f=lambda n,s=1:f'{f(len(f"{n:b}"),0)if n>3or s else""}{s}{n:0{2-s}b}'
print(''.join(map(f,map(int,input().split()))))

Try it online!

Prints each encoding backward, from the number itself, then consecutively prints the length of the previous number in binary, separated by the right separator. The parameter s represent the separator to be output. Recurse when length is still more than 3, or it is the original number (s=1).

Decoder, 154 bytes

s=input()
r=[]
def f(i,l,z):
 if len(s)==i:return 1/z
 p=int(s[i]);m=int(s[i+1:i+1+l],2)//(1-z*p);p and r.append(m);f(i+1+l,[m,2][p],p)
f(0,2,1)
print(*r)

Try it online!

Interpret the length of the next binary number repetitively, until separator 1 is found, which indicates the final number. Handles invalid encoding by raising ZeroDivisionError (if first bit in a number is not 0, or bitstream ended while original number is not yet found) or ValueError (trying to interpret empty string as number).

The tricky part is handling the invalid encoding.

\$\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.