Walking Robot Simulation Algorithm with Obstacles Detection

  • 时间：2020-09-17 14:26:24
  • 分类：网络文摘
  • 阅读：141 次
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) —

推荐阅读：
数学题：乘积末尾有几个0　 求解答：加工一批服装，每天加工300套，16天可以完成　 数学题－这个工厂原有男工人多少名　 开心“六一”之太阳岛之旅作文　 橘子洲作文　 关于奢侈　 爱你在心口难开（24至25章） 吴志俨　 珍惜生活的机会　 美丽的青海作文　 庆六一游园活动有感作文　
评论列表
添加评论