Walking Robot Simulation

class Solution {
private:
    static const long long HASH_FACTOR = 60013; // Hash factor coefficient
    
    // Encodes (x, y) tuple into a unique long long hash
    long long hashPosition(long long x, long long y) {
        return x + HASH_FACTOR * y;
    }
    
public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        unordered_set<long long> obsSet; // set to hold the obstacles hashes
        for (const auto& obs : obstacles) {
            obsSet.insert(hashPosition(obs[0], obs[1]));
        }
    
        vector<vector<int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // directional vectors
    
        vector<int> pos = {0, 0}; // start at origin
        int maxDist2 = 0; // initialize max distance squared
        int dirIndex = 0; // starting direction index
    
        for (int cmd : commands) {
            if (cmd == -1) {
                dirIndex = (dirIndex + 1) % 4; // turn right
                continue;
            }
            if (cmd == -2) {
                dirIndex = (dirIndex + 3) % 4; // turn left
                continue;
            }
    
            vector<int> dir = dirs[dirIndex]; // get current direction
            for (int steps = 0; steps < cmd; steps++) {
                int newX = pos[0] + dir[0];
                int newY = pos[1] + dir[1];
                if (obsSet.find(hashPosition(newX, newY)) != obsSet.end()) {
                    break; // obstacle encountered
                }
                pos[0] = newX;
                pos[1] = newY; // update position
            }
    
            maxDist2 = max(maxDist2, pos[0] * pos[0] + pos[1] * pos[1]); // update max distance squared
        }
    
        return maxDist2;
    }
};

The provided C++ solution for the "Walking Robot Simulation" problem implements a robot's movement on a grid where obstacles can block its path. The goal is to calculate the robot's maximum Euclidean distance squared from the origin (0, 0), considering commands for movements and turns.

The solution involves these key components:

• Hashing Positions:

  • A private method hashPosition creates a unique hash for each (x, y) position using a predetermined hash factor. This hash is used to efficiently check for obstacles during simulation.

• Tracking Obstacles:

  • Obstacles are given as a list of positions and are stored in a unordered_set called obsSet after hashing with hashPosition. This allows quick lookup to check if a new position has an obstacle.

• Processing Commands:

  • The robot can turn left, turn right, or move forward. The simulation handles these commands as follows:
    • -1 turns the robot right by shifting the direction clockwise.
    • -2 turns the robot left by shifting the direction counter-clockwise.
    • Positive numbers move the robot forward in the current direction for the number of units specified by the command.

• Calculating Movement:

  • Movements are determined by directional vectors stored in dirs. For each move command, the robot attempts to move step by step in the current direction. If it encounters an obstacle, the move is halted prematurely.

• Tracking Maximum Distance:

  • After each command, the robot's distance squared from the origin is recalculated. The program retains the maximum value encountered during the entire sequence of commands.

The algorithm concludes by returning the maximum distance squared that the robot has been from the starting point.

This approach allows for efficient simulation of the robot's movements using directional vectors and hashed positions of obstacles, optimizing the check for obstacles and updating the position and direction of the robot effectively.

class Solution {
    
    private static final long HASH_BASE = 60013;
    
    public int robotSimulation(int[] movements, int[][] blocks) {
        Set<Long> blockSet = new HashSet<>();
        for (int[] block : blocks) {
            blockSet.add(encodePosition(block[0], block[1]));
        }
    
        int[][] navigation = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
            
        int[] pos = {0, 0};
        int greatestDistanceSquared = 0;
        int dir = 0; 
    
        for (int move : movements) {
            if (move == -1) {
                dir = (dir + 1) % 4;
                continue;
            }
            if (move == -2) {
                dir = (dir + 3) % 4;
                continue;
            }
    
            int[] vector = navigation[dir];
            for (int step = 0; step < move; step++) {
                int nextX = pos[0] + vector[0];
                int nextY = pos[1] + vector[1];
                if (blockSet.contains(encodePosition(nextX, nextY))) {
                    break;
                }
                pos[0] = nextX;
                pos[1] = nextY;
            }
    
            greatestDistanceSquared = Math.max(
                greatestDistanceSquared,
                pos[0] * pos[0] + pos[1] * pos[1]
            );
        }
    
        return greatestDistanceSquared;
    }
    
    private long encodePosition(long x, long y) {
        return x + HASH_BASE * y;
    }
}

The provided Java solution involves simulating the movement of a robot on a grid where certain positions are blocked, and computes the highest distance squared that the robot reaches from the origin. The movements are represented by an array of integers, and the blocks are given as coordinates in a 2D array. Specifically:

• Initialize a HashSet to keep track of blocked positions, using a custom hashing function to encode 2D coordinates into a single long integer.
• Define directions for movement based on compass bearings: north, east, south, and west.
• Navigate based on the robot's movements. Direction changes are handled with modulo operations to cycle between the four possible directions.
• Check for blocks before moving. If the next position is blocked, the robot does not move to that position.
• Calculate the squared distance from the origin after each valid move. The solution outputs the maximum of these squared distances.

Use the algorithm efficiently apply direction changes, handle blocked paths, and track the furthest distance reached, yielding a solution to the problem of simulating a walking robot's movements on a potentially obstructed grid.

class Solution:
    def __init__(self):
        self.PRIME_MULTIPLIER = 60013  # A prime larger than 2x maximum coordinate
    
    def simulateRobot(self, instructions: List[int], blocks: List[List[int]]) -> int:
        # Convert obstacles to a set for quick access
        obstacle_set = {self._hash_position(i, j) for i, j in blocks}
    
        # Direction vectors corresponding to North, East, South, and West
        direction_vectors = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
        x0, y0 = 0, 0
        furthest_distance_squared = 0
        facing_direction = 0
    
        for inst in instructions:
            if inst == -1:  # Turn 90 deg right
                facing_direction = (facing_direction + 1) % 4
                continue
    
            if inst == -2:  # Turn 90 deg left
                facing_direction = (facing_direction + 3) % 4
                continue
    
            # Execute forward motion
            step_x, step_y = direction_vectors[facing_direction]
            for _ in range(inst):
                new_x, new_y = x0 + step_x, y0 + step_y
                if self._hash_position(new_x, new_y) in obstacle_set:
                    break
                x0, y0 = new_x, new_y
    
            furthest_distance_squared = max(furthest_distance_squared, x0**2 + y0**2)
    
        return furthest_distance_squared
    
    # Utility to hash (x, y) as a unique number
    def _hash_position(self, ix: int, iy: int) -> int:
        return ix + self.PRIME_MULTIPLIER * iy

This Python solution involves simulating a walking robot’s movement given a set of instructions and obstacles. A Solution class is defined, containing methods to process these instructions and handle the simulation mechanics. Here’s an overview of how this solution works:

• Initialization:

  • PRIME_MULTIPLIER is set to a large prime number which is used in hashing obstacle coordinates for efficient look-up.

• Simulate Robot Process:

  1. Obstacles are converted into a set using a hashing function for quick access.
  2. Direction vectors are established for North, East, South, and West to guide the robot's movement.
  3. The robot starts at the coordinate (0, 0). furthest_distance_squared keeps track of the furthest distance the robot reaches from the start (squared, to avoid unnecessary computation of square root).
  4. It iterates over each instruction:
     • -1 rotates the facing direction to the right.
     • -2 rotates the facing direction to the left.
     • Positive numbers move the robot forward in the current facing direction, checking for obstacles. If an obstacle is encountered, the movement in that direction stops.
  5. After moving, the robot calculates the squared distance from the origin and updates furthest_distance_squared if this is the maximum distance encountered.

• Auxiliary Function:

  • _hash_position hashes coordinates for efficient tracking and checking of obstacle locations.

• Output:

  • The function simulateRobot returns the square of the maximum distance from the starting position, solely based on provided valid movements and detected obstacles.

This implementation uses several efficient programming techniques like hashing and modular arithmetic for rotation handling, making it highly suitable for scenarios with complexities such as a grid full of obstacles and a long list of mixed movement and rotation instructions. The solution ensures efficient computation and clarity, implementing direct operations based on the current state without needing to backtrack or recompute previous states.