(Traversal) How to solve this question in python?

Question

• Write a function traverse() that takes in a list tb of n strings each containing n lower case characters (a-z).
• tb represents a square table with n rows and n columns. The function returns a string st generated by the procedure below that traverses the grid starting from the top left cell and ending at the bottom right cell.
• At every step, the procedure moves either horizontally to the right or vertically down, depending on which of the two cells has a \smaller" letter (i.e., a letter that appears earlier in the alphabetical order).
• The letter in the visited cell is then added to st. In case of ties, either direction can be taken.
• When the right or bottom edges of the table are reached, there is obviously only a unique next cell to move to. As an example, traverse(["veus", "oxde", "oxlx", "hwuj"]) returns "veudexj"

so the table would look like this:

v  o  o  h
e  x  x  w
u  d  l  u
s  e  x  j

I am new in python and I wrote this code ... but it only prints "veuexj" I would say the problem is in this line if new_list[a - 1][b - 1] == new_list[a - 1][-2]: which force the parameter to skip the 'd' character. #And I don't know how to solve it.

def traverse(tb_list):
    new_list = tb_list.copy()
    st = new_list[0][0]
    parameter = ''
    handler = 1
    for a in range(1, len(new_list)):
        
        for b in range(handler, len(new_list[a])):

            if new_list[a - 1][b - 1] == new_list[a - 1][-2]:
                parameter = new_list[a][b]

            elif new_list[a - 1][b - 1] > min(new_list[a - 1][b], new_list[a][b - 1]):
                parameter = min(new_list[a - 1][b], new_list[a][b - 1])

            elif new_list[a - 1][b - 1] < min(new_list[a - 1][b], new_list[a][b - 1]):
                parameter = min(new_list[a - 1][b], new_list[a][b - 1])

            st += parameter

        handler = b

    return st


print(traverse(["veus", "oxde", "oxlx", "hwuj"]))

Answer 1

You can try something like this (explanation added as comments):

def traverse(tb_list):
    lst = tb_list.copy() #Takes a copy of tb_list
    lst = list(zip(*[list(elem) for elem in lst])) #Transposes the list
    final = lst[0][0] #Sets final as the first element of the list
    index = [0,0] #Sets index to 0,0

    while True:
        x = index[0] #The x coordinate is the first element of the list
        y = index[1] #The y coordinate is the second element of the list

        if x == len(lst) - 1: #Checks if the program has reached the right most point of the table
            if y == len(list(zip(*lst))) - 1: #Checks if program has reached the bottommost point of the table
                return final #If both the conditions are True, it returns final (the final string)
            else:
                final += lst[x][y+1] #If the program has reached the right most corner, but not the bottommost, then the program moves one step down
                index = [x, y+1] #Sets the index to the new coordinates

        elif y == len(list(zip(*lst))) - 1: #Does the same thing in the previous if condition button in an opposite way (checks if program has reached bottommost corner first, rightmost corner next)
            if x == len(lst) - 1:
                return final
            else:
                final += lst[x + 1][y] #If the program has reached the bottommost corner, but not the rightmost, then the program moves one step right
                index = [x + 1, y]

        else: #If both conditions are false (rightmost and bottommost)
            if lst[x+1][y] < lst[x][y+1]: #Checks if right value is lesser than the bottom value
                final += lst[x+1][y] #If True, then it moves one step right and adds the alphabet at that index to final
                index = [x+1,y] #Sets the index to the new coords
            else: #If the previous if condition is False (bottom val > right val)
                final += lst[x][y+1] #Moves one step down and adds the alphabet at that index to final
                index = [x,y+1] #Sets the index to the new coords

lst = ["veus", "oxde", "oxlx", "hwuj"]
print(traverse(lst))

Output:

veudexj

I have added the explanation as comments, so take your time to go through it. If you are still not clear with any part of the code, feel free to ask me. Any suggestions to optimize/shorten my code are most welcome.