Replace 0 with 01 and 1 with 10 in a List[int]

Question

I am taking efforts to solve problem K-th Symbol in Grammar - LeetCode

On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.

Explanation:
row 1: 0
row 2: 01
row 3: 0110
row 4: 01101001

I wrote such a replace function

        def replace(row: "List[int]") -> "List[int]":
            """
            rtype: row 
            """
            for i in range(len(row)):
                if row[i] == 0: #0 -> 01
                    row.insert(i+1, 1)
                elif row[i] == 1: #1 -> 10
                    row.insert(i+1, 0)
            return row 

However, it does not work properly.

In [3]: r2 = replace([0])                                                                                                     
In [4]: r2                                                                                                                    
Out[4]: [0, 1] 
In [5]: r3 = replace(r2); print(r3)                                                                                           
[0, 1, 0, 1] # correct is [0, 1, 1, 0]
In [6]: r4 = replace(r3); print(r4)                                                                                           
[0, 1, 0, 1, 0, 1, 0, 1] #correct is  ['0', '1', '1', '0', '1', '0', '0', '1']

Use a new list does not work either.

    def replace(row: "List[int]") -> "List[int]":
        """
        rtype: row 
        """
        copy = list(row)
        for i in range(len(copy)):
            if copy[i] == 0: #0 -> 01
                row.insert(i+1, 1)
            elif copy[i] == 1: #1 -> 10
                row.insert(i+1, 0)
        return row 

What's the problem?

Answer 1

Use str.join with dict:

a = '0'
d = {'0': '01', '1': '10'}
# Now run below line only
a = ''.join(d[s] for s in a)
a

Output:

01
0110
01101001
...

Answer 2

the problem with your code is that you are inserting elements in a list in a loop without taking into account the elongation of the list.

This can be solved by adding a simple "index shifter":

def replace(row: "List[int]") -> "List[int]":
    for en, i in enumerate(range(len(row))):
        if row[i] == 0: #0 -> 01
            row.insert(i+1 + en, 1)
        elif row[i] == 1: #1 -> 10
            row.insert(i+1 + en, 0)
    return row 

replace([0, 1, 1, 0])

>>> [0, 1, 1, 0, 1, 0, 0, 1]

Some explanation:

I gave this answer because you asked what was wrong with your code, and I supposed you wanted to, or you were asked to, solve this task with this approach.

I have to say I'd definitely go with other approaches, as many have proposed, anyway:

• if you really want to understand why it works print row and row[i] in the for loop
• you'll probably find out that this approach works only for this specific task of the "k-th symbol" (try for example replace([0, 0])), and this is quite mind blowing
• p.s. if you were wondering about the en variable, here it is used just for "didactic" purposes, as in this case it's always en == i >>> True

Update:

I had a look at the link you provided, and the task you were asked for was:

Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed).

with:

row 1: 0
row 2: 01
row 3: 0110
row 4: 01101001
# etc.

and the following constraints:

N will be an integer in the range [1, 30]

K will be an integer in the range [1, 2^(N-1)]

so, I think none of the proposed solutions is going to work with a list of 2^29 elements.
In order to solve the quiz, we have to go a bit deeper.

Basically, what we are doing by replacing 0 and 1 with 01, 10, starting from 0, at an n-th iteration, is extending list from n-1-th with the the same inverted list, in fact:

def replace(row):
    return row + list(map(lambda x: int(not x), row))

replace([0, 1, 1, 0])

>>> [0, 1, 1, 0, 1, 0, 0, 1]

produces the correct output, and that's why your corrected algorithm works.

But still this wouldn't allow you to deal with a N = 2^30 constraint. As hinted in the link, a recursive approach is the best.
Here I give a possible solution with no explanation, just as a curiosity:

def solution(n, k):
    if n == 1:
        return 0
    if k <= 2**(n-1)/2:
        return solution(n-1, k)
    else:
        return 1 - solution(n-1, k-2**(n-1)/2)

`