Walking Robot Simulation Algorithm with Obstacles Detection

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

推荐阅读：
牛吃草问题——牛顿问题　 利用中国剩余定理的思想解题　 数图形教学视频　 平面图形的面积　 数的进位制　 最大公约数和最小公倍数　 富兰克林的遗嘱　 听出言外之意——一道三年级的数学题　 中国剩余定理经典题目——韩信点兵　 《孙子算经》中的剩余定理题　
评论列表
添加评论