Walking Robot Simulation Algorithm with Obstacles Detection

  • 时间：2020-09-17 14:26:24
  • 分类：网络文摘
  • 阅读：123 次
robot Walking Robot Simulation Algorithm with Obstacles Detection algorithms brute force c / c++ javascript python

robot

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.

Example 1:
Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: robot will go to (3, 4)

Example 2:
Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation: robot will be stuck at (1, 4) before turning left and going to (1, 8)

Note:

  • 0 <= commands.length <= 10000
  • 0 <= obstacles.length <= 10000
  • -30000 <= obstacle[i][0] <= 30000
  • -30000 <= obstacle[i][1] <= 30000

The answer is guaranteed to be less than 2 ^ 31.

Simulation Algorithm with Obstacle Detection

The obstacles are given beforehand and we can store them in a hash set for easy detection with O(1) time and O(N) space. The direction is initially facing north and we can define four directions with increment steps for X and Y axis clockwise.

When robot is turning left or right, we need to update the direction index accordingly. When the robot walks forward, we need to simulate unless its next move is obstacle – in which case we break the loop and do nothing. Otherwise, we update the position accordingly.

The simulation algorithm for the robot can be implemented just in bruteforce – naively following exactly each instructions/commands.

In C++, the list e.g. array or vector is not hash-able by default. Therefore, we convert the coordinates to string then we can remember the locations in a hash set.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        int dir[][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = 0, y = 0;
        unordered_set<string> obj;
        for (const auto &n: obstacles) {
            obj.insert(std::to_string(n[0]) + "," + std::to_string(n[1]));
        }
        int d = 0, ans = 0;
        for (const auto &n: commands) {
            switch(n) {
                case -2: d = (d + 3) % 4; break;
                case -1: d = (d + 1) % 4; break;
                default: 
                    for (int i = 0; i < n; ++ i) {
                        int nx = x + dir[d][0];
                        int ny = y + dir[d][1];
                        if (!obj.count(std::to_string(nx) + "," + std::to_string(ny))) {
                            x = nx;
                            y = ny;
                            ans = max(ans, x * x + y * y);
                        } else {
                            break;
                        }
                    }
                    break;
            }
        }
        return ans;
    }
};
class Solution {
public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        int dir[][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = 0, y = 0;
        unordered_set<string> obj;
        for (const auto &n: obstacles) {
            obj.insert(std::to_string(n[0]) + "," + std::to_string(n[1]));
        }
        int d = 0, ans = 0;
        for (const auto &n: commands) {
            switch(n) {
                case -2: d = (d + 3) % 4; break;
                case -1: d = (d + 1) % 4; break;
                default: 
                    for (int i = 0; i < n; ++ i) {
                        int nx = x + dir[d][0];
                        int ny = y + dir[d][1];
                        if (!obj.count(std::to_string(nx) + "," + std::to_string(ny))) {
                            x = nx;
                            y = ny;
                            ans = max(ans, x * x + y * y);
                        } else {
                            break;
                        }
                    }
                    break;
            }
        }
        return ans;
    }
};

Converting to Javascript, we can use the Set class available to ES6.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

/**
 * @param {number[]} commands
 * @param {number[][]} obstacles
 * @return {number}
 */
var robotSim = function(commands, obstacles) {
    const dir = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    let x = 0, y = 0;
    let obj = new Set();
    for (const n of obstacles) {
        obj.add(n[0] + "," + n[1]);
    }
    let d = 0, ans = 0;
    for (const n of commands) {
        switch(n) {
            case -2: d = (d + 3) % 4; break;
            case -1: d = (d + 1) % 4; break;
            default: 
                for (let i = 0; i < n; ++ i) {
                    const nx = x + dir[d][0];
                    const ny = y + dir[d][1];
                    if (!obj.has(nx + "," + ny)) {
                        x = nx;
                        y = ny;
                        ans = Math.max(ans, x * x + y * y);
                    } else {
                        break;
                    }
                }
                break;
        }
    }
    return ans;    
};
/**
 * @param {number[]} commands
 * @param {number[][]} obstacles
 * @return {number}
 */
var robotSim = function(commands, obstacles) {
    const dir = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    let x = 0, y = 0;
    let obj = new Set();
    for (const n of obstacles) {
        obj.add(n[0] + "," + n[1]);
    }
    let d = 0, ans = 0;
    for (const n of commands) {
        switch(n) {
            case -2: d = (d + 3) % 4; break;
            case -1: d = (d + 1) % 4; break;
            default: 
                for (let i = 0; i < n; ++ i) {
                    const nx = x + dir[d][0];
                    const ny = y + dir[d][1];
                    if (!obj.has(nx + "," + ny)) {
                        x = nx;
                        y = ny;
                        ans = Math.max(ans, x * x + y * y);
                    } else {
                        break;
                    }
                }
                break;
        }
    }
    return ans;    
};

As for Python, we can use the set and the list is unhashable.

1
2
3
4
5
6
7

>>> a = set()
>>> a.add([1,2])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>>
</module>
>>> a = set()
>>> a.add([1,2])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>>
</module>

However, we can convert it to tuple e.g. a.add(tuple([1,2])). Thus, it is handy to add a list/tuple into a Python hash table or set.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        x = 0
        y = 0
        obj = set()
        for n in obstacles:
            obj.add(tuple(n))
        d = 0
        ans = 0
        for n in commands:
            if n == -2:
                d = (d + 3) % 4
            elif n == -1:
                d = (d + 1) % 4
            else:
                for i in range(n):
                    nx = x + dir[d][0]
                    ny = y + dir[d][1]
                    if (nx, ny) in obj:
                        break
                    else:
                        x = nx
                        y = ny
                        ans = max(ans, x**2 + y**2)
        return ans                        
class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        x = 0
        y = 0
        obj = set()
        for n in obstacles:
            obj.add(tuple(n))
        d = 0
        ans = 0
        for n in commands:
            if n == -2:
                d = (d + 3) % 4
            elif n == -1:
                d = (d + 1) % 4
            else:
                for i in range(n):
                    nx = x + dir[d][0]
                    ny = y + dir[d][1]
                    if (nx, ny) in obj:
                        break
                    else:
                        x = nx
                        y = ny
                        ans = max(ans, x**2 + y**2)
        return ans

All implementations of C++, Javascript and Python run at O(N) time and require O(N) space.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
小数的意义是什么？　 井字形有几条射线　 有效数字的定义　 尾数的定义　 关于除夕的作文400字　 别样的寒假作文600字　 国庆节小学作文　 常回家看看|小学作文　 小学生作文中秋节300字　 2011国庆节作文700字　
评论列表
添加评论