13
\$\begingroup\$

Background

Here on CGCC, a commonly seen subgenre is – writing a program that works even if one character is deleted. A similar problem is studied in the field of coding theory: finding an encoding that can be decoded even if one symbol is deleted from the encoded string. In this challenge, we're looking at the "binary" variant of the problem: the codes are strings of bits, and the deletions that we're trying to harden against happen at the bit level.

Although the problem of finding the optimal code for handling a single deletion from a string of bits is still not entirely solved, one commonly used code for the purpose is the Varshamov–Tenengolts code (typically called the "VT code" for short); this code has the property that for every encoded codeword, the sum of the 1-based indexes of the 1 bits is divisible by the length of the codeword plus 1. The full version of this code is conjectured to be an optimal solution to the problem (and is known to at least be close to optimal).

This challenge is about implementing an encoder for a variant of the VT code, known as the "systematic VT code". The systematic variant occasionally wastes a bit in order to make the encoding and decoding algorithms more efficient (and is used here because I think it makes for a more interesting golfing challenge than the original version of the code).

The task

Given a string of bits as input, output a string of bits that represents the input string encoded with the systematic binary VT code.

The following algorithm is one possible definition of the code in question: following the algorithm will let you know the systematic VT encoding of any string of bits. The task is to implement something that produces the same results as this algorithm would; your solution doesn't necessarily need to use this algorithm itself, but it does have to produce the same results.

  1. Imagine an infinite array of positions into which bits can be placed. Mark those positions whose 1-based indexes are powers of 2:

    _* _* _ _* _ _ _ _* _ _ _ _ _ _ _ _* _ _ …

  2. Fill the input bits into the unmarked positions of the array, in order from left to right, until no input bits are left. For example, suppose we were encoding the string 01101001100:

    _* _* 0 _* 1 1 0 _* 1 0 0 1 1 0 0 _* _ _ …

  3. Cut off the array after the last filled bit: anything beyond that point is deleted, whether marked or unmarked:

    _* _* 0 _* 1 1 0 _* 1 0 0 1 1 0 0

  4. Add together the 1-based indexes of all the 1 bits in the array so far.

    1  2  3 4  5 6 7 8  9 10 11 12 13 14 15
_* _* 0 _* 1 1 0 _* 1  0  0  1  1  0  0
           5+6     +9      +12+13       = 45

  5. Calculate minus this sum, wrapping-modulo the length of the array plus 1. In this case, we're calculating \$-45\mod (15+1)\$, which is \$3\$ (because \$-45=(16\times-3)+3\$, i.e. \$-45\$ has remainder \$3\$ upon dividing by \$16\$).

  6. Express the resulting value as a sum of distinct powers of 2; in this case, we have \$3=2^1+2^0=2+1\$. (In other words, we're writing the sum in binary, and then looking at the place-value of the resulting 1s.)

  7. Fill in the marked positions of the array, placing a 1 into those positions whose indexes were part of the sum in the previous step, and a 0 into those positions that weren't:

    1  2    4        8
1* 1* 0 0* 1 1 0 0* 1 0 0 1 1 0 0

The result of the process is the bit string we want to create as output, e.g. for our input string 01101001100, the output is 110011001001100.

Clarifications

  • As usual, your submission can either be a full program or a function, and can take input and produce output via any of the usually permitted I/O methods.
  • The algorithm is defined in terms of 1-based indexes, because this is necessary for the resulting code to be able to handle deletions in every position. Even if your language uses 0-based indexes, you still have to produce the same result as the algorithm above does using its 1-based indexes (e.g. the first bit of the input string has to appear as the third bit of the output string, not the first or fourth).
  • You can represent the "string of bits" in the input or output as a string/list of Booleans (i.e. using the truthiness or falsiness of each element); a string/list of numbers that are each 0 or 1 (or, in output, other values that are numerically 0 or 1); or a string/list of characters that are each "0" or "1" or each have a codepoint of 0 or 1. You can't represent it as the digits of a binary or decimal number, because that would cause leading zeroes to be lost.
  • In I/O, you must use the same representation consistently, e.g. if "1" has a codepoint of 0 in some encoding, you can't output a string of "1"s and say that the 0s are being output by codepoint and the 1s as characters; but you may use different encodings for the input and the output if you wish.
  • Although an empty input is meaningful (and, in theory, should encode to itself), your solution doesn't need to be able to handle this particular case.

Test cases

0 -> 000
1 -> 101
10 -> 11100
01 -> 10001
111 -> 001011
1101 -> 1010101
1010 -> 1111010
01101001100 -> 110011001001100

Victory condition

This is a challenge: as usual for code golf, the fewer bytes there are in your answer, the better. Your submission should contain a header listing the language in which the answer is written, and the number of bytes it contains.

Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ Is 111111' a valid encoding of 111? If not, why not? \$\endgroup\$
    – Neil
    Aug 3, 2022 at 1:20
  • \$\begingroup\$ @Neil: In the full version of the code, 111111 and 001011 are both valid code words but encode different strings. (The number of possible strings of a given bit length is often not a power of 2, and calculating it can be slow.) The systematic encoding sacrifices some of the code words to keep a round number of possibilities, meaning that you end up with some non-canonical representations like 111111 for 111; these generally go unused in the VT code literature, and thus probably aren't part of the systematic VT code even though it's obvious what they'd decode to. So it's invalid. \$\endgroup\$
    – ais523 - high effort answers
    Aug 3, 2022 at 2:21

7 Answers 7

Reset to default
3
\$\begingroup\$

05AB1E, 29 27 26 bytes

gÝo<£õÜD»SÐƶ«þO(sgÌ%bRs0ζS

Try it online, or try all test cases.

I'm quite sure this can be golfed

Explanation

g             push the input's length
Ý             push the range [0,...,length]
o             take 2^<each value>
<             remove 1 from each value

£             split the input string into subsequences of those sizes
              (e.g. ["", "0", "110", "1001100", "", "", "", "", "", "", "", ""])
õ             push the empty string
Ü             remove all of its occurrences at the end of the list
              (e.g. ["", "0", "110", "1001100"])
D             duplicate the result
»             join it by newlines
S             convert it to a list of characters
              (e.g. ["\n", "0", "\n", "1", "1", "0", "\n", "1", "0", "0", "1", "1", "0", "0"])
Ð             triplicate that list, pushing 2 new copies
ƶ             lift the first copy, multiplying each number by its 1-based index
              (and not changing the newlines)
              (e.g. ["\n", 0, "\n", 4, 5, 0, "\n", 8, 0, 0, 11, 12, 0, 0])
«             merge it with the second copy
þ             keep only the numbers from that list
O             take the sum
(             negate it

s             swap that with the third copy
g             find that list's length (e.g. 14)
Ì             add 2 to it (e.g. 16)
%             calculate (-sum) % (length+2) (e.g. 3)

b             convert it to binary (e.g. "11")
R             reverse it (e.g. "11")
s             swap, to make the copy without newlines on top
              (e.g. ["", "0", "110", "1001100"])
0ζ            zip it with the reversed binary string, using 0 as a filler
              (e.g. [["1", ""], ["1", "0"], ["0", "110"], ["0", "1001100"]])
S             convert it to a list of characters
              (e.g. ["1", "1", "0", "0", "1", "1", "0", "0", "1", "0", "0", "1", "1", "0", "0"])
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6),  89  83 bytes

A rather literal implementation of the algorithm described in the challenge.

s=>(g=(q,i=j=t=0)=>s[i]?(j&++j?s[t+=j*s[i],i++]:(q/=2)*2&1)+g(q,i):"")(g()&&j*t%~j)

Try it online!

Commented

s => (                   // main function taking the input string
  g = (                  // g is a recursive function taking:
    q,                   //   q = result of the 5th step of the algorithm
                         //       as described in the challenge,
                         //       or undefined during the first pass
    i =                  //   i = pointer in s[]
                         // and also using:
    j =                  //   j = pointer in the output string
    t = 0                //   t = sum of the indices of 1 bits
  ) =>                   //
  s[i] ?                 // if s[i] is defined:
    (                    //
      j & ++j ?          //   increment j; if j is not a power of 2:
        s[               //
          t += j * s[i], //     add j to t if s[i] is "1"
          i++            //     yield s[i] and increment i afterwards
        ]                //
      :                  //   else:
        (q /= 2) * 2 & 1 //     yield the least significant bit of q
                         //     and divide q by 2
    ) + g(q, i)          //   append the result of a recursive call
  :                      // else:
    ""                   //   stop the recursion
)(                       //
  g() &&                 // do a first call to g so that j and t are set
  j * t % ~j             // then compute the correct value of q and use
)                        // it for the second call
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

R, 126 bytes

\(x){v=!(l=seq(3*sum(x|1)))
v[p<--2^l/2]=seq(!x)
v=v[l<-1:(m=which.max(v))]
v[p]=x
v[-l[p]]=-sum(which(v>0))%%(m+1)%/%-p%%2
v}

Attempt This Online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 40 bytes

ＦＳ«Ｗ¬＆Ｌυ⊖Ｌυ⊞υω⊞υι»⭆υ⎇ιι⎇κ﹪÷﹪±↨⌕Ａυ1¹Ｌυκ²ω

Try it online! Link is to verbose version of code. I/O is as digit strings. Explanation:

ＦＳ«

Loop over the input bits.

Ｗ¬＆Ｌυ⊖Ｌυ⊞υω

Skip over powers of 2. (0 also gets skipped over, which adjusts for 0-indexing.)

⊞υι

Push the next bit in the position where it is to be output.

»⭆υ⎇ιι⎇κ﹪÷﹪±↨⌕Ａυ1¹Ｌυκ²ω

Fill in the skipped bits with the base 2 of the shortfall.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

MATL, 27 26 bytes

0i"NB?0]@]vtfs_ynQ\BfqW1w(

Try it online! Or verify all test cases.

How it works

0       % Push 0 (first "marked" position)
i       % Push input: numerical vector
"       % For each digit in the input
  N     %   Push current number of elements in the stack
  B?    %   Does its binary expansion contain only ones? If so,
    0   %     Push a 0 ("marked position")
  ]     %   End
  @     %   Push current input digit
]       % End
v       % Concatenate all digits into a column vector
tf      % Duplicate, find: push 1-based positions of non-zeros
s_      % Sum, negate
y       % Duplicate from below: pushes copy of column vector
nQ      % Length plus 1
\       % Modulo
Bf      % 1-based indices of binary expansion
qW      % Subtract 1, then compute 2 raised to that, element-wise
1w(     % Write 1 at those positions. Implicitly display
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Husk, 29 bytes

ΣSżż+öm;↔ḋ§%o→Lȯ_ΣWIΣmΘCΘm←İ2

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Desmos, 250 bytes

g(a)=2^a2-a-2
L=l.length
C=ceil(log_2L)-1
c=\{L<3:L,g(C)<L:C+1,C\}
K=2^c+L-g(c-1)
B=[1...K]
A=-0^{mod(log_2B,1)}
D=\{A=0:l[B+\sum_{n=1}^BA[n]],A\}
E=2^{[0...c]}
F=(i-mod(floor(mod(-B[D=1].total,K+1)/E),2)E)^2.min
f(l)=[\{D[i]>=0:D[i],F=0,0\}\for i=B]

The function \$f(l)\$ takes in a list of bits and returns the encoded list of bits. Pretty much follows the exact algorithm specified in the challenge.

Holy crap it's long. 100% can be golfable, but I'm too lazy to do that.

Try It On Desmos!

Try It On Desmos! - Prettified

Improve this answer
\$\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.