16
\$\begingroup\$

In this challenge, we consider an encoding from positive integers (up to a limit) to binary sequences. Some examples:

A. 1 -> 00, 2 -> 01, 3 -> 10, 4 -> 11

B. 1 -> 0, 2 -> 1, 3 -> 01

C. 1 -> (empty sequence)

A prefix code is a coding where no code is a prefix of another. B is not a prefix code because the code for 1 (0) is a prefix of that for 3 (01). Fibonacci coding and Elias omega coding are examples of prefix codes that can encode all positive integers.

It is possible to construct a prefix code where 1 encodes to a code of length \$l_1\$, 2 to \$l_2\$, ..., \$n\$ to \$l_n\$ if the sum of \$\tfrac{1}{2}\$ raised to the power of each length does not exceed 1, i.e. \$\sum_{i=1}^{n}{\tfrac{1}{2^{l_i}}} \le 1\$. Your task is to construct such a prefix code where \$l_1, \cdots, l_n\$ is the input.

The following I/O are allowed:

  • Take the list as input, and output the list or mapping of encodings for each positive integer
  • Take the list and a number to encode as input, and output the encoding for the given number

Each encoding (binary sequence) can be given as a list or a string. Outputting as a single integer is not allowed, as leading zeros are not representable. You can choose to output an encoding for \$0, \cdots, n-1\$ instead of \$1, \cdots, n\$.

Examples

[0] -> {1 -> ""}
[1, 1] -> {1 -> "0", 2 -> "1"}
[2, 3, 4, 4, 5, 5, 5] ->
  {1 -> "11"
   2 -> "011"
   3 -> "0011"
   4 -> "1011"
   5 -> "00011"
   6 -> "10011"
   7 -> "01011"}
[3, 3, 3, 1, 3] ->
  {1 -> "101"
   2 -> "111"
   3 -> "110"
   4 -> "0"
   5 -> "100"}
[5, 4, 3, 2, 5, 4, 3, 2] ->
  {1 -> "10101"
   2 -> "1011"
   3 -> "000"
   4 -> "01"
   5 -> "10100"
   6 -> "1001"
   7 -> "001"
   8 -> "11"}
\$\endgroup\$
5
  • \$\begingroup\$ Is it OK if the solution fails for lengths greater than 53 due to floating-point inaccuracies? \$\endgroup\$ Aug 30, 2023 at 4:57
  • \$\begingroup\$ @CommandMaster Yes, that's fine. \$\endgroup\$
    – Bubbler
    Aug 30, 2023 at 5:51
  • \$\begingroup\$ Since the codes may be assigned to any of those with their length may we output just the unsorted codes (e.g. from shortest to longest)? \$\endgroup\$ Aug 30, 2023 at 21:55
  • \$\begingroup\$ ...or even stronger could we assume the code lengths are provided ordered? \$\endgroup\$ Aug 30, 2023 at 22:07
  • \$\begingroup\$ @JonathanAllan No to both. I like the golf you did there though :) \$\endgroup\$
    – Bubbler
    Aug 30, 2023 at 22:58

5 Answers 5

4
\$\begingroup\$

05AB1E, 21 bytes

āø{ø`soDzηO>*<b€¦sākè

Try it online!

Uses the same idea as arithmetic coding. Fails for lengths greater than 53 due to floating-point inaccuracies.

If we can output sorted by length, we can we 12 bytes:

05AB1E, 12 bytes

{oDzηO>*<b€¦

Try it online!

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

Jelly, 18 bytes

eƤ€`Ḅ=QƑẠ
Ø.ṗŒpÇƇṪ

A monadic Link that accepts the lengths and yields a list of prefix-codes in the same order.

Try it online!

Save a byte by outputting symbols \$1\$ and \$2\$ by replacing Ø. with 2.

How?

eƤ€`Ḅ=QƑẠ - Link 1: isValid?: list of codes, Assignment
   `      - use {Assignment} as both arguments of:
  €       -   for each Code in {Assignment}:
 Ƥ        -     for each prefix of {Code}:
e         -       exists in {Assignment}?
    Ḅ     - convert {each exists-in vector} from binary
              -> PrefixFoundIds, a list of ints
                 ...a value is greater than 1 when a prefix was in Assignments
                    otherwise it equals 1 (only the full code was in Assignments)
       Ƒ  - is {Assignments} invariant under?:
      Q   -   deduplication
                -> AllDifferent = 0 if there are repeats, 1 if not
     =    - {PrefixFoundIds} equals {AllDifferent} (vectorises)
        Ạ - all?

Ø.ṗŒpÇƇṪ - Main Link: list of integers, CodeLengths
Ø.       - [0,1]
  ṗ      - Cartesian product {CodeLengths} (vectorises)
             -> all codes for each of the respective lengths
   Œp    - Cartesian product
             -> all possible Assignments of codes
      Ƈ  - filter keep those {Assignments} for which:
     Ç   -   call Link 1 as a monad - f(Assignment)
       Ṫ - tail

17 bytes (non-compliant)

Less brute force, so much faster, but outputs the prefix codes sorted by their lengths. Again Ø. could be replaced with 2 to save a byte. If the input were guaranteed to be sorted too, then 2ṗeƤẸ¥ÐḟḢṭð@ƒḟ does the job at \$14\$ bytes.

Ø.ṗeƤẸ¥ÐḟḢṭ
Ṣç@ƒḟ

Try it online!

How?

Ø.ṗeƤẸ¥ÐḟḢṭ - Link 1: integer NextCodeLength, list of codes, FoundAlready
Ø.          - [0,1]
  ṗ         - Cartesian power {NextCodeLength} -> PotentialCodes
       Ðḟ   - filter discard those for which:
      ¥     -   last two links as a dyad - f(PotentialCode, FoundAlready)
    Ƥ       -     for prefixes of {PotentialCode}
   e        -       exists in {FoundAlready}?
     Ẹ      -     any?
         Ḣ  - head -> first valid PotentialCode
          ṭ - tack to {FoundAlready}

Ṣç@ƒḟ - Main Link: list of integers, CodeLengths
Ṣ     - sort {CodeLengths}
    ḟ - {CodeLengths} filter discard {CodeLengths} -> [] (initial FoundAlready)
   ƒ  - starting with {[]} reduce {sorted CodeLengths} by:
  @   -   with swapped arguments:
 ç    -     call the dyadic helper above, Link 1 = f(NextCodeLength, FoundAlready)
\$\endgroup\$
1
\$\begingroup\$

Python, 88 bytes

lambda s,k=0,r=2:{j:bin(r:=(r<<-k+(k:=i))-1)[3:]for i,j in sorted(zip(s,range(len(s))))}

Attempt This Online!

Takes a list of integers and returns a dictionary.

How?

Sorts the prescribed lengths and then simply counts down binary numbers of that length appending zeros when the length increases.

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

JavaScript (ES6), 115 bytes

A simple but quite long algorithm.

a=>a.map((v,i)=>(h=x=>b.some(s=>c.match("^"+s)+s.match("^"+c),c=x.toString(2).padStart(v,0))?h(-~x):b[i]=c)``,b=[])

Try it online!

Method

We process all entries in the input order. For each entry, we simply start with \$x=0\$ and increment it while \$x\$ is a prefix of a previous output or a previous output is a prefix of \$x\$, in left-padded binary format.

Note

Because \$x\$ is actually initialized to [''], x.toString(2).padStart(0,0) returns an empty string rather than "0", which is the expected behavior for the edge case a = [0].

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

Charcoal, 30 bytes

→F⊕⌈θ«F⌕Aθ髧≔θκΦ⍘ⅈ²μ→»Mⅈ→»θ

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

Start with a next code number of 1, but all the codes will have their leading 1 removed again later.

F⊕⌈θ«

Loop over all possible code lengths.

Mⅈ→

Double the next code number.

F⌕Aθι«

Loop over all indices with this length.

§≔θκΦ⍘ⅈ²μ

Generate the code of this length, but remove the leading 1.

Increment the next code number.

»»θ

Output the resulting codes.

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