7
\$\begingroup\$

I am doing Kickstart's problem Wiggle Walk. I have tried to code with matrix, dictionary and nested dictionary but the time exceeds the limit in each submition. Can anyone help me optimize it better or is there any algorithm which I may have overlooked. The problem statement is

Problem Banny has just bought a new programmable robot. Eager to test his coding skills, he has placed the robot in a grid of squares with R rows (numbered 1 to R from north to south) and C columns (numbered 1 to C from west to east). The square in row r and column c is denoted (r, c).

Initially the robot starts in the square (SR, SC). Banny will give the robot N instructions. Each instruction is one of N, S, E or W, instructing the robot to move one square north, south, east or west respectively.

If the robot moves into a square that it has been in before, the robot will continue moving in the same direction until it reaches a square that it has not been in before. Banny will never give the robot an instruction that will cause it to move out of the grid. Input The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing the five integers N, R, C, SR and SC, the number of instructions, the number of rows, the number of columns, the robot's starting row and starting column, respectively.

Then, another line follows containing a single string of N characters; the i-th of these characters is the i-th instruction Banny gives the robot (one of N, S, E or W, as described above).

My code is as follows:

for j in range(int(input())):
instructions,rows,cols,startRow,startCol = map(int,input().split())
a=input()
dict={}
startRow-=1
startCol-=1
dict[startRow]={startCol:1}
i=0
while i <len(a):
    if a[i]=="N":
        if startRow-1 not in dict:
            dict[startRow-1]={startCol:1}
            i+=1
        elif startCol not in dict[startRow-1]:
            dict[startRow-1][startCol]=1
            i+=1
        startRow-=1

    elif a[i]=="S":
        if startRow+1 not in dict:
            dict[startRow+1]={startCol:1}
            i+=1
        elif startCol not in dict[startRow+1]:
            dict[startRow+1][startCol]=1
            i+=1
        startRow+=1

    elif a[i]=="W":
        if startRow not in dict:
            dict[startRow]={startCol-1:1}
            i+=1
        elif startCol-1 not in dict[startRow]:
            dict[startRow][startCol-1]=1
            i+=1
        startCol-=1
    elif a[i]=="E":
        if startRow not in dict:
            dict[startRow]={startCol+1:1}
            i+=1
        elif startCol+1 not in dict[startRow]:
            dict[startRow][startCol+1]=1
            i+=1
        startCol+=1

print("Case #{0}: {1} {2}".format(j+1,startRow+1,startCol+1))
\$\endgroup\$
  • \$\begingroup\$ What have you tried yourself so far? Any time complexity analysis? What are example inputs when it's too slow? \$\endgroup\$ – domen May 30 at 12:52
  • \$\begingroup\$ I have tried implementing it using 2d arrays, dictionaries. Inputs are not available as this is the question of competition. \$\endgroup\$ – Dhruv Nunia May 30 at 13:06
  • \$\begingroup\$ And what are time complexities for those approaches? Can you construct input for which your code is too slow? If you don't have answers to these two questions, you're just shooting in the dark. \$\endgroup\$ – domen May 30 at 13:08
5
\$\begingroup\$

At first glance, you code appears to have a lot of complicated and repetitive sections. That's a bad smell, and often a hint that you should either split the repetitive parts off into a function or otherwise reorganize your code to get rid of the repetition. (Sometimes, one option can be to just simplify the code until the repetitive parts become trivial.)

A lot of the complexity in the repetitive parts of your code seems to come from your decision to store the grid as a dictionary of dictionaries. There's a couple of ways to simplify that:

  • In Python, dictionary keys can be tuples. So you can just do:

    visited = {}
    # ...
    if (row, col) not in visited:
        # do something
        visited[row, col] = True
    else:
        # do something else
    

    (Also, you shouldn't name your dictionary dict, both because it's the name of the dictionary type in Python and also because it's an uninformative name that doesn't explain what you're using the dictionary for. Call its something meaningful like visited_cells or just visited instead.)

  • Also, since you're really only using the dictionary as a set, why not make it one? The code can look exactly the same as above, except that you'll start with visited = set() instead of visited = {}, and mark cells as visited with visited.add((row, col)).

  • Alternatively, instead of using a dictionary or a set, you could just use a two-dimensional array (implemented e.g. as a list of lists) of booleans, initialized to all False, something like this:

    visited = [[False] * cols for row in range(rows)]
    # ...
    if not visited[row][col]:
        # do something
        visited[row][col] = True
    else:
        # do something else
    

    I suspect this is what the exercise is actually expecting you to do. However, I do rather like your idea of using a dictionary (or a set) instead, and I'm only mentioning this alternative for the sake of completeness.

One advantage of using a dictionary or a set to store the visited cells is that it means you don't actually need to care about the boundaries of the grid, since the dictionary can accommodate arbitrary large or small coordinates. In particular, you don't actually need to adjust the input coordinates from one-based to zero-based indexing (and back again for output), so you can just eliminate those parts of your code.


Another way to reduce the repetitiveness of your code is to observe that all the sections for handling movement in different directions look basically the same, except for the index (row or column) being changed and the step size (+1 or -1) it's being changed by. If you defined a dictionary that mapped the N/S/E/W direction letters to the corresponding coordinate offsets, something like this:

directions = {
    'N': (-1, 0),
    'S': (+1, 0),
    'W': (0, -1),
    'E': (0, +1),
}

then you could combine all those sections into a single one, something like this:

row = start_row
col = start_col
visited = {(row, col)}  # loop below assumes current square is always marked as visited

for compass_heading in instructions:
    row_step, col_step = directions[compass_heading]

    while (row, col) in visited:
        row += row_step
        col += col_step

    visited.add((row, col))

(Note that I renamed a few of your variables here. You should not use variables named startRow and startCol to store the current row and column, since that's just plain misleading, and in any case variable names in Python should be written in snake_case instead of camelCase. And a is just an awful variable name, so I renamed it to instructions. You already have a variable named that, but it's completely unnecessary and unused. You could just use the dummy variable _ in the list assignment instead.)


As for making the code faster, I see no obvious trivial opportunities there. Using a single set instead of a dictionary of dictionaries is probably somewhat faster, perhaps even twice as fast if your running time is dominated by dictionary lookups, but not orders of magnitude faster. A list of lists of booleans might be even faster for small grids, but the time to initialize it scales with the size of the grid, whereas the time to set up a single-element set (or dictionary) is basically constant. Anyway, I'd suggest first focusing on cleaning up your code, and only worrying about optimization if it's still too slow after that.

If it is, a good starting point is to focus on worst-case performance, i.e. to think about how a sneaky test case designed might make your code run as slowly as possible, and try to find ways to counter that.

In particular, the worst case input for your algorithm (with or without the improvements I suggested above) is something like NSNSNSNSNSNSNSNSNSNSNSNSNS..., which forces the robot to move back and forth over an increasingly long stretch of visited cells, leading to an O(n²) execution time.

One way to avoid that would be to store a dictionary of "signposts" recording, for each move we make, where we ended up on the grid after that move. That way, the next time the robot finds itself in the same square and moving in the same direction, it can skip all the cells in between. Also, since the movement rules are symmetric, we can also leave behind "backwards" signposts recording where the robot came from as it entered each cell, allowing us to skip the intervening cells in the opposite direction as well.

A quick sketch of how to implement that might look something like this:

# look-up table of (row_step, col_step, opposite_heading) for each compass heading
directions = {
    'N': (-1, 0, 'S'),
    'S': (+1, 0, 'N'),
    'W': (0, -1, 'E'),
    'E': (0, +1, 'W'),
}

row = start_row
col = start_col
visited = {(row, col)}  # loop below assumes current square is always marked as visited
signposts = {}

for compass_heading in instructions:
    last_row = row
    last_col = col
    row_step, col_step, opposite_heading = directions[compass_heading]

    while (row, col) in visited:
        if (row, col, compass_heading) in signposts:
            # we've been this way before!
            row, col = signposts[row, col, compass_heading]
        row += row_step
        col += col_step

    visited.add((row, col))

    signposts[last_row, last_col, compass_heading] = (row, col)
    signposts[row, col, opposite_heading] = (last_row, last_col)

Note that, as written, the signposts dictionary always grows linearly with the size of the input. You may obtain some additional speed and memory savings by removing old signposts as they become unnecessary.

In particular, we can safely remove any signposts we encounter as soon as we've used them, since they will either become useless or get overwritten anyway. We can also safely remove any backwards signposts that we pass, since those also become useless. With those changes, the optimized inner loop would look something like this:

    while (row, col) in visited:
        if (row, col, compass_heading) in signposts:
            # follow and remove signposts; any that are still valid will be restored below
            row, col = signposts.pop((row, col, compass_heading))
            del signposts[row, col, opposite_heading]
        row += row_step
        col += col_step

However, note that the set of visited cells will still grow linearly, and that meandering paths like, say, NESWNESWNESWNESWNESW... can still leave behind a linearly growing number of signposts, so the worst-case memory consumption is still linear even with this optimization.

Ps. Here's a simple online demo of the signpost-optimized algorithm I describe above, with some debug print statements added. Feel free to play around with it to see how it works.

\$\endgroup\$
  • \$\begingroup\$ I had tried using 2-d arrays, it saves time but takes a lot of memory. I liked the idea of using sets. I actually have never tried it before. Thanks a lot. \$\endgroup\$ – Dhruv Nunia May 31 at 14:18

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.