CODEWITHSUNDEEP
c++algorithm
user9221677
user9221677

Reputation:

Intuition behind this step?

I am trying to solve a question from the LeetCode contest held earlier today:

A robot on an infinite grid starts at point (0, 0) and faces north. The robot can receive one of three possible types of commands:

-2: turn left 90 degrees
-1: turn right 90 degrees
1 <= x <= 9: move forward x units

Some of the grid squares are obstacles. The i-th obstacle is at grid point (obstacles[i][0], obstacles[i][1]). If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.) Return the square of the maximum Euclidean distance that the robot will be from the origin.

The highly accepted solution is as follows:

typedef pair<int, int> ii;
const int d[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
class Solution {
public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        set<ii> A;
        for (auto& it : obstacles) {
            A.insert({it[0], it[1]});
        }
        int dir = 0, x = 0, y = 0;
        int ret = 0;
        for (auto& it : commands) {
            if (it == -2) {
                dir = (dir + 3) % 4;
            } else if (it == -1) {
                dir = (dir + 1) % 4;
            } else {
                for (int k = 0; k < it; ++k) {
                    int nx = x + d[dir][0];
                    int ny = y + d[dir][1];
                    if (A.count({nx, ny})) break;
                    x = nx;
                    y = ny;
                }
            }
            ret = max(ret, x * x + y * y);
        }
        return ret;
    }
};

My question is, while calculating dir, what is the intuition behind adding 3 and 1 in the formulae below:

dir=(dir+3)%4;
         ^?
dir=(dir+1)%4;
         ^?

Thanks!

Edit: If it==-2 then it means that the robot moved to the left; whereas if it==-1 then it means that it moved to the right. How does adding 3 and 1 ensure this change of direction?

Upvotes: 2

Views: 149

Answers (2)

o11c
o11c

Reputation: 16046

dir=(dir+3)%4 is conceptually dir=(dir-1)%4 - the two expressions are just implementing ++ and -- but keeping the result in [0, 4), since that's the bounds of the d array.

old new
0   3
1   0
2   1
3   2

It would've been much clearer if dir were declared as enum Dir { N, E, S, W };, and the changes to dir were made into function calls, and a valarray-like pair class was written in place of both std::pair and int[2], and ...

That code is a weird mix of C++ and pointlessly-low-level/opaque code.

Upvotes: 1

Amichai
Amichai

Reputation: 374

The directions are defined as:

      0  
      |  
 3 ------- 1
      |  
      2

Starting off you are facing north (dir = 0)

If you wish to go right (i.e. -90 deg) then you need to face "1", which is 0+1 (dir+1)
If you wish to go left (i.e. +90 deg) then you need to face "3", which is 0+3 (dir+3)

That's it! hope i was clear enough and good luck ;)

Upvotes: 3

Related Questions