Walking Robot Simulation Algorithm with Obstacles Detection

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

推荐阅读：
维生素C的主要作用及人体推荐摄入量　 补充维生素C的药品维生素C片服用禁忌　 维生素C缺乏症的主要表现及其治疗　 素食有哪些误区素食者需要注意的问题　 素食的分类及适当素食具有的保健作用　 冬季咳嗽吃什么自制美味止咳小零食　 冬季进补鸡汤要注意 几类人不宜喝鸡汤　 芦荟的保健价值、食用禁忌及食用方法　 冬季食疗养生：吃南瓜可有效治疗哮喘　 食疗：有效增强男人性能力的八款药膳　
评论列表
添加评论