874. Walking Robot Simulation

/**
 * Problem: LeetCode 874 - Walking Robot Simulation
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        Set<Long> obstacleSet = new HashSet<>(obstacles.length);
        for (int[] obs : obstacles) {
            long key = (((long) obs[0]) << 32) | (obs[1] & 0xFFFFFFFFL);
            obstacleSet.add(key);
        }

        // Direction vectors: 0: North, 1: East, 2: South, 3: West
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        int d = 0;

        int x = 0;
        int y = 0;
        int maxDistSq = 0;

        for (int cmd : commands) {
            if (cmd == -1) {
                // Turn right 90 degrees
                d = (d + 1) % 4;
            } else if (cmd == -2) {
                // Turn left 90 degrees
                d = (d + 3) % 4;
            } else {
                // Move forward cmd units
                for (int step = 0; step < cmd; step++) {
                    int nx = x + dx[d];
                    int ny = y + dy[d];
                    long nextKey = (((long) nx) << 32) | (ny & 0xFFFFFFFFL);
                    if (obstacleSet.contains(nextKey)) {
                        break;
                    }
                    x = nx;
                    y = ny;
                    maxDistSq = Math.max(maxDistSq, x * x + y * y);
                }
            }
        }

        return maxDistSq;
    }
}

"""
Problem: LeetCode 874 - Walking Robot Simulation
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import List

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        """
        Simulates the walking robot on an infinite 2D plane with obstacles.
        
        Time Complexity: O(C * K + M)
        Space Complexity: O(M)
        """
        obstacle_set = {(ox, oy) for ox, oy in obstacles}

        # 0: North, 1: East, 2: South, 3: West
        dx = [0, 1, 0, -1]
        dy = [1, 0, -1, 0]
        d = 0

        x = 0
        y = 0
        max_dist_sq = 0

        for cmd in commands:
            if cmd == -1:
                d = (d + 1) % 4
            elif cmd == -2:
                d = (d + 3) % 4
            else:
                for _ in range(cmd):
                    nx = x + dx[d]
                    ny = y + dy[d]
                    if (nx, ny) in obstacle_set:
                        break
                    x = nx
                    y = ny
                    max_dist_sq = max(max_dist_sq, x * x + y * y)

        return max_dist_sq

/**
 * Problem: LeetCode 874 - Walking Robot Simulation
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

class Solution {
public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        unordered_set<long long> obstacleSet;
        obstacleSet.reserve(obstacles.size());
        for (const auto& obs : obstacles) {
            long long key = (((long long)obs[0]) << 32) | ((unsigned int)obs[1]);
            obstacleSet.insert(key);
        }

        // 0: North, 1: East, 2: South, 3: West
        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {1, 0, -1, 0};
        int d = 0;

        int x = 0;
        int y = 0;
        int maxDistSq = 0;

        for (int cmd : commands) {
            if (cmd == -1) {
                d = (d + 1) % 4;
            } else if (cmd == -2) {
                d = (d + 3) % 4;
            } else {
                for (int step = 0; step < cmd; step++) {
                    int nx = x + dx[d];
                    int ny = y + dy[d];
                    long long nextKey = (((long long)nx) << 32) | ((unsigned int)ny);
                    if (obstacleSet.count(nextKey)) {
                        break;
                    }
                    x = nx;
                    y = ny;
                    maxDistSq = max(maxDistSq, x * x + y * y);
                }
            }
        }

        return maxDistSq;
    }
};

/**
 * Problem: LeetCode 874 - Walking Robot Simulation
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
var robotSim = function(commands, obstacles) {
    const obstacleSet = new Set();
    for (let i = 0; i < obstacles.length; i++) {
        obstacleSet.add(`${obstacles[i][0]},${obstacles[i][1]}`);
    }

    // 0: North, 1: East, 2: South, 3: West
    const dx = [0, 1, 0, -1];
    const dy = [1, 0, -1, 0];
    let d = 0;

    let x = 0;
    let y = 0;
    let maxDistSq = 0;

    for (let i = 0; i < commands.length; i++) {
        const cmd = commands[i];
        if (cmd === -1) {
            d = (d + 1) % 4;
        } else if (cmd === -2) {
            d = (d + 3) % 4;
        } else {
            for (let step = 0; step < cmd; step++) {
                const nx = x + dx[d];
                const ny = y + dy[d];
                if (obstacleSet.has(`${nx},${ny}`)) {
                    break;
                }
                x = nx;
                y = ny;
                maxDistSq = Math.max(maxDistSq, x * x + y * y);
            }
        }
    }

    return maxDistSq;
};