Background
Here on CGCC, a commonly seen subgenre is radiation-hardening – 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.
Imagine an infinite array of positions into which bits can be placed. Mark those positions whose 1-based indexes are powers of 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 _* _ _ …
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
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
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\$).
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.)
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 code-golf 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.
111111'
a valid encoding of111
? If not, why not? \$\endgroup\$111111
and001011
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 like111111
for111
; 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\$