Repair a Hamming Code

A space probe sends its data protected by a Hamming code, which lets the receiver fix a single flipped bit in each block. Write hamming_repair(bits, r) that repairs and unpacks a received message.

The blocks. bits is a string of '0' and '1' characters whose length is a multiple of n = 2^r - 1. Each run of n characters is one block, and inside a block the positions are numbered 1 to n from the left.

• The positions that are powers of two (1, 2, 4, 8 and so on) hold parity bits; all the other positions hold data bits.
• The parity bit at position 2^k is set so that, among all the positions whose number has bit k switched on (position 2^k itself included), the number of 1s is even.

For r = 3, a block has 7 bits, laid out as p1 p2 d1 p4 d2 d3 d4: p1 covers positions 1, 3, 5 and 7, p2 covers 2, 3, 6 and 7, and p4 covers 4, 5, 6 and 7. The data 1011 is sent as 0110011.

The damage. On the way, at most one bit of each block may have flipped, a parity bit or a data bit. The code is built so that the damaged bit, if there is one, can always be found.

Return a tuple (data, fixed): data is the repaired data bits of all the blocks in order (inside a block, from the lowest position to the highest), as a string, and fixed is how many blocks had a bit flipped back.

Examples

hamming_repair("0110011", 3)          # returns ('1011', 0)
hamming_repair("0110001", 3)          # returns ('1011', 1)
hamming_repair("11010011111100", 3)   # returns ('00011100', 1)
hamming_repair("010", 2)              # returns ('0', 1)

In the second example position 6 flipped: the groups of p2 and p4 now have an odd number of 1s, while p1's group is still fine. With r = 2 a block has 3 bits and one data bit (at position 3), so each block is the data bit sent three times.

Constraints

• 2 <= r <= 12, so a block has 3 to 4,095 bits.
• bits has up to 300,000 characters.