Decomposing a matrix as a sum of two bitstrings

Question

I chanced upon this question and came up with the following algorithm, looking for criticisms and advice on how to improve my algorithm efficiency.

You are given 3 arguments:

• A & B are integers within the range (0 to 100,000)

• M is an array of integers within the range (0 to 2)

Return an output (as a string) that describes matrix M in the following format:

• The first part of the string should contain a description of the upper row using only the 1 and 0 characters and should add up to the integer A

• The second part of the string should contain a description of the lowerrow using only the 1 and 0 characters and should add up to the integer B

• The sum of integers at K index of the output(string1, string2) should be equal to M[K] so like: string1[K] + string2[K] == M[K]

So for example,

Given A = 2, B = 2, M = [2, 0, 2, 0], your function should return a string like "1010, 1010"

Given A = 3, B = 2, M = [2, 1, 1, 0, 1], your function should return "11001, 10100"

Given A = 2, B = 3, M = [0, 0, 1, 1, 2], your function should return 0, because no matrix can be constructed that satisfies such conditions.

def convert(A, B, M):
    if (A+B) != sum(M) or max(A, B) > len(M):
        return 0

'''
logic:

set 2 arrays
if value in matrix = 2, array1 & array2 at index where 2 occurs
will be [1] and [1]

if value in matrix = 0, array1 & array2 at index where 0 occurs will
be [0] and [0]

Then, we only need to handle 1s in matrix...
same logic as above,
however,
we handle position of 1 by checking whether A > B or vice versa
'''

    array1 = [""] * len(M)
    array2 = [""] * len(M)

    # first check for 2's and 0's:
    for index, value in enumerate(M):
        if value == 2:
            array1[index] = 1
            array2[index] = 1
            A -= 1
            B -= 1
        elif value == 0:
            array1[index] = 0
            array2[index] = 0

    # then check for 1's:
        elif value == 1 and A>B:
            array1[index] = 1
            array2[index] = 0
            A -= 1
        elif value == 1 and A<=B:
            array1[index] = 0
            array2[index] = 1
            B -= 1

    array1 = ''.join(str(x) for x in array1)
    array2 = ''.join(str(x) for x in array2)   
    return array1 + ', ' + array2

Answer 1

First thing I notice is that you initialize your lists to contain strings

array1 = [""] * len(M)
array2 = [""] * len(M)

but later assign integer values to these. This is misleading, and so I would instead do

array1 = [0] * len(M)
array2 = [0] * len(M)

This has the added benefit that we get one case for free- if we want the value to be zeros (value == 0) we don't have to do anything.

Another issue I see with these variables is that they are named arrayX, but are in fact lists. In general, its best to leave out the type in the variable name, and just provide a descriptive name for its purpose. I would name these something like bitsA and bitsB, which also follows suite in A/B vs 1/2 naming.

Moving into your for loop, I would first reorder these conditionals to check value in numerical order (zero case first, then one, etc.), however as mentioned before we can now skip case zero, and so with only two cases (one or two) its not as big of a deal in my opinion. There is still one problem though. In one conditional you check A>B and then in the other you check the exact opposite. This added redundancy is unnecessary, and if you later edit one to be A<B, neither case will cover A==B. For this reason, it should be removed.

Normally I argue for reducing nested if statements, but in this case it seems like a logical separation, since the two subcases for value == 1 really mirror each other and deserve distinguishing from the value == 2 case. I would rewrite the loop as:

for index, value in enumerate(M):
    if value == 2:
        array1[index] = 1
        array2[index] = 1
        A -= 1
        B -= 1

    elif value == 1:
        if A > B:
            array1[index] = 1
            array2[index] = 0
            A -= 1
        else:
            array1[index] = 0
            array2[index] = 1
            B -= 1

However, there is one other route we could take, which would remove the remaining repeated logic.

for index, value in enumerate(M):
    if value == 2 or value == 1 and A > B:
        array1[index] = 1
        A -= 1
    if value == 2 or value == 1 and A <= B:
        array2[index] = 1
        B -= 1

Note this does break that rule I just mentioned about not including both A > B and A <= B, because our if statements are independent- both can execute. It becomes a trade off of bug resistance vs reducing redundancy.