3

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?

  • provide expected output – AkshayNevrekar Apr 18 at 8:26
  • You use slice locations from the list while adding objects. That doesn't work. – Stef van der Zon Apr 18 at 8:30
  • you are iterating over your list at the same time you are modifying it. Use another list to write the result in replace – pLOPeGG Apr 18 at 8:31
  • Use another list does not help, Lante provide a index shifter solution below. @pLOPeGG – Jon Apr 18 at 8:43
  • @Jon see my answer, you did not use properly the other list. – pLOPeGG Apr 18 at 8:50
3

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)

`

6

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
...
2

Just as an explanation of how to use another list to write a result while iterating over a list:

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

You shouldn't modify a iterable while iterating over unless you want to take into account length changes. Most of the time it is easier to create anothe list and fill it little by little. And the result is:

replace([0,1,1,0])
>>> [0, 1, 1, 0, 1, 0, 0, 1]
0
def replace(row: "List[int]") -> "List[int]":
    """
    rtype: row 
    """
    outList = []
    for val in row:
        if val == 0: #0 -> 01
            outList.append(0)
            outList.append(1)
        elif val == 1: #1 -> 10
            outList.append(1)
            outList.append(0)
    return outList 

Your version modified the list as it read it. Its range was only the length of the original array. It only looked at two values, but it inserted a 1 after the first 0. It then saw the 1, causing it to insert another 0.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.