Walking Robot Simulation Algorithm with Obstacles Detection

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

推荐阅读：
食药监总局提醒注意保健食品五大陷阱　 对儿童健康成长有益的六大食物　 健康养生：七种常见的黑色滋补食物　 竹炭食品排毒就是一个忽悠人的概念　 中华人民共和国食品安全法(全文)　 山东启动打击非法保健食品专项行动　 盘点那些不科学不健康的饮食习惯　 养生推荐：几种最牛的常见抗衰老食物　 营养健康食品系列：休闲干果开心果　 营养健康食品：向日葵的种子葵花籽　
评论列表
添加评论