Skip to content

874. Walking Robot Simulation

Description

A robot on an infinite XY-plane starts at point (0, 0) facing north. The robot receives an array of integers commands, which represents a sequence of moves that it needs to execute. There are only three possible types of instructions the robot can receive:

  • -2: Turn left 90 degrees.
  • -1: Turn right 90 degrees.
  • 1 <= k <= 9: Move forward k units, one unit at a time.

Some of the grid squares are obstacles. The ith obstacle is at grid point obstacles[i] = (xi, yi). If the robot runs into an obstacle, it will stay in its current location (on the block adjacent to the obstacle) and move onto the next command.

Return the maximum squared Euclidean distance that the robot reaches at any point in its path (i.e. if the distance is 5, return 25).

Note:

  • There can be an obstacle at (0, 0). If this happens, the robot will ignore the obstacle until it has moved off the origin. However, it will be unable to return to (0, 0) due to the obstacle.
  • North means +Y direction.
  • East means +X direction.
  • South means -Y direction.
  • West means -X direction.

Β 

Example 1:

Input: commands = [4,-1,3], obstacles = []

Output: 25

Explanation:

The robot starts at (0, 0):

  1. Move north 4 units to (0, 4).
  2. Turn right.
  3. Move east 3 units to (3, 4).

The furthest point the robot ever gets from the origin is (3, 4), which squared is 32 + 42 = 25 units away.

Example 2:

Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]

Output: 65

Explanation:

The robot starts at (0, 0):

  1. Move north 4 units to (0, 4).
  2. Turn right.
  3. Move east 1 unit and get blocked by the obstacle at (2, 4), robot is at (1, 4).
  4. Turn left.
  5. Move north 4 units to (1, 8).

The furthest point the robot ever gets from the origin is (1, 8), which squared is 12 + 82 = 65 units away.

Example 3:

Input: commands = [6,-1,-1,6], obstacles = [[0,0]]

Output: 36

Explanation:

The robot starts at (0, 0):

  1. Move north 6 units to (0, 6).
  2. Turn right.
  3. Turn right.
  4. Move south 5 units and get blocked by the obstacle at (0,0), robot is at (0, 1).

The furthest point the robot ever gets from the origin is (0, 6), which squared is 62 = 36 units away.

Β 

Constraints:

  • 1 <= commands.length <= 104
  • commands[i] is either -2, -1, or an integer in the range [1, 9].
  • 0 <= obstacles.length <= 104
  • -3 * 104 <= xi, yi <= 3 * 104
  • The answer is guaranteed to be less than 231.

Solutions

Solution 1: Hash Table + Simulation

We define a direction array \(dirs = [0, 1, 0, -1, 0]\) of length \(5\), where each pair of adjacent elements represents a direction. That is, \((dirs[0], dirs[1])\) represents north, \((dirs[1], dirs[2])\) represents east, and so on.

We use a hash table \(s\) to store the coordinates of all obstacles, so we can determine in \(O(1)\) time whether the next step will encounter an obstacle.

Additionally, we use two variables \(x\) and \(y\) to represent the robot's current coordinates, initially \(x = y = 0\). The variable \(k\) represents the robot's current direction, and the answer variable \(ans\) represents the maximum squared Euclidean distance from the origin.

Next, we iterate over each element \(c\) in the array \(commands\):

  • If \(c = -2\), the robot turns left \(90\) degrees, i.e., \(k = (k + 3) \bmod 4\);
  • If \(c = -1\), the robot turns right \(90\) degrees, i.e., \(k = (k + 1) \bmod 4\);
  • Otherwise, the robot moves forward \(c\) units. We combine the robot's current direction \(k\) with the direction array \(dirs\) to obtain the increments along the \(x\)-axis and \(y\)-axis. We accumulate the increments step by step onto \(x\) and \(y\), and check whether each new coordinate \((nx, ny)\) is in the obstacle set. If not, we update the answer \(ans\); otherwise, we stop the simulation and proceed to the next command.

Finally, return the answer \(ans\).

The time complexity is \(O(C \times n + m)\) and the space complexity is \(O(m)\), where \(C\) is the maximum number of steps per move, and \(n\) and \(m\) are the lengths of the arrays \(commands\) and \(obstacles\), respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        dirs = (0, 1, 0, -1, 0)
        s = {(x, y) for x, y in obstacles}
        ans = k = 0
        x = y = 0
        for c in commands:
            if c == -2:
                k = (k + 3) % 4
            elif c == -1:
                k = (k + 1) % 4
            else:
                for _ in range(c):
                    nx, ny = x + dirs[k], y + dirs[k + 1]
                    if (nx, ny) in s:
                        break
                    x, y = nx, ny
                    ans = max(ans, x * x + y * y)
        return ans

 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
class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        int[] dirs = {0, 1, 0, -1, 0};
        Set<Integer> s = new HashSet<>(obstacles.length);
        for (var e : obstacles) {
            s.add(f(e[0], e[1]));
        }
        int ans = 0, k = 0;
        int x = 0, y = 0;
        for (int c : commands) {
            if (c == -2) {
                k = (k + 3) % 4;
            } else if (c == -1) {
                k = (k + 1) % 4;
            } else {
                while (c-- > 0) {
                    int nx = x + dirs[k], ny = y + dirs[k + 1];
                    if (s.contains(f(nx, ny))) {
                        break;
                    }
                    x = nx;
                    y = ny;
                    ans = Math.max(ans, x * x + y * y);
                }
            }
        }
        return ans;
    }

    private int f(int x, int y) {
        return x * 60010 + y;
    }
}

 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
class Solution {
public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        int dirs[5] = {0, 1, 0, -1, 0};
        auto f = [](int x, int y) {
            return x * 60010 + y;
        };
        unordered_set<int> s;
        for (auto& e : obstacles) {
            s.insert(f(e[0], e[1]));
        }
        int ans = 0, k = 0;
        int x = 0, y = 0;
        for (int c : commands) {
            if (c == -2) {
                k = (k + 3) % 4;
            } else if (c == -1) {
                k = (k + 1) % 4;
            } else {
                while (c--) {
                    int nx = x + dirs[k], ny = y + dirs[k + 1];
                    if (s.count(f(nx, ny))) {
                        break;
                    }
                    x = nx;
                    y = ny;
                    ans = max(ans, x * x + y * y);
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func robotSim(commands []int, obstacles [][]int) (ans int) {
    dirs := [5]int{0, 1, 0, -1, 0}
    type pair struct{ x, y int }
    s := map[pair]bool{}
    for _, e := range obstacles {
        s[pair{e[0], e[1]}] = true
    }
    var x, y, k int
    for _, c := range commands {
        if c == -2 {
            k = (k + 3) % 4
        } else if c == -1 {
            k = (k + 1) % 4
        } else {
            for ; c > 0 && !s[pair{x + dirs[k], y + dirs[k+1]}]; c-- {
                x += dirs[k]
                y += dirs[k+1]
                ans = max(ans, x*x+y*y)
            }
        }
    }
    return
}

 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
function robotSim(commands: number[], obstacles: number[][]): number {
    const dirs = [0, 1, 0, -1, 0];
    const s: Set<number> = new Set();
    const f = (x: number, y: number) => x * 60010 + y;
    for (const [x, y] of obstacles) {
        s.add(f(x, y));
    }
    let [ans, x, y, k] = [0, 0, 0, 0];
    for (let c of commands) {
        if (c === -2) {
            k = (k + 3) % 4;
        } else if (c === -1) {
            k = (k + 1) % 4;
        } else {
            while (c-- > 0) {
                const [nx, ny] = [x + dirs[k], y + dirs[k + 1]];
                if (s.has(f(nx, ny))) {
                    break;
                }
                [x, y] = [nx, ny];
                ans = Math.max(ans, x * x + y * y);
            }
        }
    }
    return ans;
}

 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
35
36
37
38
39
40
use std::collections::HashSet;

impl Solution {
    pub fn robot_sim(commands: Vec<i32>, obstacles: Vec<Vec<i32>>) -> i32 {
        let dirs: [i32; 5] = [0, 1, 0, -1, 0];
        let mut s: HashSet<(i32, i32)> = HashSet::new();

        for o in obstacles {
            s.insert((o[0], o[1]));
        }

        let mut ans: i32 = 0;
        let mut k: i32 = 0;
        let mut x: i32 = 0;
        let mut y: i32 = 0;

        for c in commands {
            if c == -2 {
                k = (k + 3) % 4;
            } else if c == -1 {
                k = (k + 1) % 4;
            } else {
                for _ in 0..c {
                    let nx: i32 = x + dirs[k as usize];
                    let ny: i32 = y + dirs[k as usize + 1];

                    if s.contains(&(nx, ny)) {
                        break;
                    }

                    x = nx;
                    y = ny;
                    ans = ans.max(x * x + y * y);
                }
            }
        }

        ans
    }
}

Comments