A system is transmitting messages in binary, however it is not a perfect transmission, and sometimes errors will occur which result in a single bit flipping from 0 to 1, or from 1 to 0.

To resolve this, A 2-dimensional Parity Bit Code is used: https://en.wikipedia.org/wiki/Multidimensional_parity-check_code

In this system, a message is arrayed out on a M x N grid. A 24-bit message could be put on a 4x6 grid like so:


>1 0 1 0 0 1
>1 0 0 1 0 0
>0 1 1 1 0 1
>1 0 0 0 0 1

Then, Parity bits are computed for each row and for each column, equal to 1 if there is an odd number of 1s in the row of column, and 0 if it is an even number. The result for the above message looks like:


>1 0 1 0 0 1 1
>1 0 0 1 0 0 0
>0 1 1 1 0 1 0
>1 0 0 0 0 1 0
>1 1 0 0 0 1

Since the 1st row, and 1st, 2nd and 6th column each have an odd number of 1s in them, and the others all do not.

Then the whole message is sent, including the parity bits. This is arranged as:

> message + row_parities + column_parities
> 101001100100011101100001 + 1000 + 110001
> 1010011001000111011000011000110001

If an error occurs in transmission, the parity bit for a column and row will be incorrect, which can be used to identify and correct the error. If a row parity bit is incorrect, but all column bits are correct, then we can assume the row parity bit was the one flipped, and likewise if a column is wrong but all rows are correct.

 Your Task: 

Create a function correct, which takes in integers M and N, and a string of bits where the first M\*N represent the content of the message, the next M represent the parity bits for the rows, and the final N represent the parity bits for the columns. A single-bit error may or may not have appeared in the bit array.

The function should check to see if there is a single-bit error in the coded message, correct it if it exists, and return the corrected string of bits.

Difficulty: introductory

Starter code:

def correct(m, n, bits):
	

Solutions:
def correct(m, n, bits):
    l = m*n
    row = next((i for i in range(m) if f"{bits[i*n:(i+1)*n]}{bits[l+i]}".count("1") % 2), None)
    col = next((i for i in range(n) if f"{bits[i:l:n]}{bits[l+m+i]}".count("1") % 2), None)
    if row is col is None:
        return bits
    err = (l + row) if col is None else (l + m + col) if row is None else (row * n + col)
    return f"{bits[:err]}{int(bits[err])^1}{bits[err+1:]}"


from functools import reduce

def correct(m, n, bits):
        
    def getDiff(check,lines):
        return next((i for i,(c,line) in enumerate(zip(check,lines)) if int(c) != reduce(int.__xor__, list(map(int,line)))), -1)

    a = getDiff(bits[-m-n:-n], (bits[i:i+n]   for i in range(0,m*n,n)) )
    b = getDiff(bits[-n:],     (bits[i:m*n:n] for i in range(n)) )
    
    if a+b != -2:
        i    = a*n+b if a+1 and b+1 else -m-n+a if b==-1 else len(bits)-n+b
        bits = f'{ bits[:i] }{ int(bits[i])^1 }{ bits[i+1:] }'
        
    return bits


from functools import partial, reduce
from itertools import chain
from operator import xor

calc_parity = partial(reduce, xor)


def correct(m, n, bits):
    bits = list(map(int, bits))
    xs = [bits[i*n:(i+1)*n] for i in range(m)]
    row_parity = bits[m*n:-n]
    col_parity = bits[-n:]
    invalid_row = invalid_col = -1
    for i, (row, p) in enumerate(zip(xs, row_parity)):
        if calc_parity(row) != p:
            invalid_row = i
            break

    xs = [list(col) for col in zip(*xs)]
    for i, (col, p) in enumerate(zip(xs, col_parity)):
        if calc_parity(col) != p:
            invalid_col = i
            break
    xs = [list(col) for col in zip(*xs)]

    if invalid_row >= 0 <= invalid_col:
        xs[invalid_row][invalid_col] = 1 - xs[invalid_row][invalid_col]
    elif invalid_row >= 0:
        row_parity[invalid_row] = 1 - row_parity[invalid_row]
    elif invalid_col >= 0:
        col_parity[invalid_col] = 1 - col_parity[invalid_col]

    return "".join(map(str, chain(chain.from_iterable(xs), row_parity, col_parity,)))

def correct(m, n, bits):
    parities = lambda matrix: [sum(row) & 1 for row in matrix]
    wrong_index = lambda a, b: next((i for i, (x, y) in enumerate(zip(a, b)) if x ^ y), None)
    
    bits = list(map(int, bits))
    message, row_par, col_par = bits[:-m-n], bits[-m-n:-n], bits[-n:]
    rows = list(zip(* [iter(message)] * n))
    
    actual_row, actual_col = parities(rows), parities(zip(*rows))
    idx_row, idx_col = wrong_index(row_par, actual_row), wrong_index(col_par, actual_col)
    
    if idx_row is not None and idx_col is not None:
        message[idx_row * n + idx_col] = message[idx_row * n + idx_col] ^ 1
    elif idx_row is not None:
        row_par[idx_row] = row_par[idx_row] ^ 1
    elif idx_col is not None:
        col_par[idx_col] = int(col_par[idx_col]) ^ 1

    return ''.join(map(str, message + row_par + col_par))

def correct(R,C,Q) :
    Q = list(map(int,Q))
    r = next((F for F,V in enumerate(Q[-R - C:-C]) if 1 & sum(Q[F * C:-~F * C]) ^ int(V)),-1)
    c = next((F for F,V in enumerate(Q[-C:]) if 1 & sum(Q[F:R * C:C]) ^ int(V)),-1)
    if 0 <= r or 0 <= c : Q[r - R - C if c < 0 else c + (-C if r < 0 else r * C)] ^= 1
    return ''.join(map(str,Q))

def correct(m, n, bits):
    def invert(n):
        if n == 1:
            return 0
        if n == 0:
            return 1
        else:
            return None
    
    matrix = []
    wrong_row = None
    wrong_col = None
    
    n_list = [int(x) for x in bits[m * n + m:]]
    m_list = [int(x) for x in bits[m * n:m * n + m]]
    
    for i in range(m):
        row = [int(x) for x in bits[n * i: n * i + n]]
        if sum(row) % 2 != m_list[i]:
            wrong_row = i
        matrix.append(row)
    
    col = []
    for j in range(n):
        for i in range(m):
            col.append(matrix[i][j])
        if sum(col) % 2 != n_list[j]:
            wrong_col = j
        col = []
    
    if wrong_col == None and wrong_row != None:
        m_list[wrong_row] = invert(m_list[wrong_row])
    elif wrong_col != None and wrong_row == None:
        n_list[wrong_col] = invert(n_list[wrong_col])
    elif wrong_col != None and wrong_row != None:
        matrix[wrong_row][wrong_col] = invert(matrix[wrong_row][wrong_col])
    
    res = ''
    for matrix_row in matrix:
        res += ''.join([str(x) for x in matrix_row])
    
    res += ''.join([str(x) for x in m_list])
    res += ''.join([str(x) for x in n_list])
    return res


def correct(m, n, bits):
    res=[]
    for i in range(0, n*m, n):
        res.append(bits[i:i+n])
    start=n*m
    check=[]
    check.append(next((i for i in range(m) if digit_sum(res[i])%2!=int(bits[start+i])), None))
    for j in range(n):
        string=""
        for i in range(m):
            string+=res[i][j]
        if digit_sum(string)%2!=int(bits[start+m+j]):
            check.append(j)
            break
    if len(check)==1:
        check.append(None)
    if check[0]==None and check[1]==None:
        return bits
    elif check[1]==None:
        temp="0" if bits[start+check[0]]=="1" else "1"
        return bits[:start+check[0]]+temp+bits[start+check[0]+1:]
    elif check[0]==None:
        temp="0" if bits[start+m+check[1]]=="1" else "1"
        return bits[:start+m+check[1]]+temp+bits[start+m+check[1]+1:]
    else:
        temp="0" if res[check[0]][check[1]]=="1" else "1"
        return bits[:check[0]*n+check[1]]+temp+bits[check[0]*n+check[1]+1:]
def digit_sum(s):
    return sum(int(i) for i in s)

import pandas as pd

def correct(m,n,s):
    s,r,c = s[:m*n], s[m*n:m*n+m], s[-n:]
    arr = pd.np.array(list(s)).reshape(m,n)
    df = pd.DataFrame(arr)
    row = ''.join(df.eq('1').sum(1).mod(2).astype(str))
    col = ''.join(df.eq('1').sum(0).mod(2).astype(str))
    if r != row and c != col:
        for idx, (i,j) in enumerate(zip(row,r)):
            if i != j:
                x = idx
        for idx, (i,j) in enumerate(zip(col,c)):
            if i!= j:
                y = idx

        df = df.astype(int)
        df.loc[x,y] ^= 1
        return ''.join(df.astype(str).values.ravel()) + r + c
        
    else:   
        return ''.join(df.values.ravel()) + row + col

def correct(m, n, bits):
    failed_row, failed_col = -1, -1
    for row in range(m):
        if sum(int(c) for c in bits[row*n:(row+1)*n]) % 2 != int(bits[m*n+row]):
            failed_row = row
            break
    for col in range(n):
        if sum(int(bits[j]) for j in range(col,len(bits)-n-m,n)) % 2 != int(bits[m*n+m+col]):
            failed_col = col
            break
    if (failed_row, failed_col) == (-1, -1):
        return bits
    elif failed_row != -1 and failed_col != -1:
        index = n*failed_row+failed_col
    elif failed_row != -1:
        index = m*n+failed_row
    else:
        index = m*n+m+failed_col
    return bits[:index] + str(1-int(bits[index]))+bits[index+1:]
        


def correct(m, n, bits):
    
    msg = [bits[i*n : (i+1)*n] for i in range(m)]
    msgt = [''.join([bits[i] for i in range(j, m*n, n)]) for j in range(n)]

    msg_row_parity = ''.join([str(x.count('1')%2) for x in msg])
    msg_col_parity = ''.join([str(x.count('1')%2) for x in msgt])

    bits_row_parity = bits[-m-n:-n]
    bits_col_parity = bits[-n:]

    if msg_row_parity == bits_row_parity and msg_col_parity == bits_col_parity: return bits
    if msg_row_parity == bits_row_parity: return bits[:-n] + msg_col_parity
    if msg_col_parity == bits_col_parity: return bits[:-m-n] + msg_row_parity + bits[-n:]
    
    err_row = [i for i in range(m) if bits_row_parity[i] != msg_row_parity[i]][0]
    err_col = [i for i in range(n) if bits_col_parity[i] != msg_col_parity[i]][0]
    
    err_bit_msg = msg[err_row][err_col]
    cor_bit = str(abs(int(err_bit_msg) - 1))
    msg_pos = err_row*n + err_col
    return bits[:msg_pos] + cor_bit + bits[msg_pos+1:]