Robot Collisions

Problem Statement

In this problem, we are dealing with a simulation where multiple robots, each uniquely placed on a straight line with individual properties of position, health, and direction of movement, start to move simultaneously. The robots can only move left ('L') or right ('R'). Throughout their movement, if any two robots occupy the same position at the same time, a collision occurs. The outcome of each collision is dependent on the health of the participating robots:

• If one robot has higher health than the other, the weaker robot is removed from the line and the health of the stronger one decreases by 1.
• If both robots have equal health, both are removed from the scene.

The goal is to compute the health values of any robots that survive after all possible collisions have been resolved. The results should be presented in the order of the original input list of robots. Moreover, if no robots survive, an empty array should be returned.

Examples

Example 1

Input:

positions = [5,4,3,2,1], healths = [2,17,9,15,10], directions = "RRRRR"

Output:

[2,17,9,15,10]

Explanation:

No collision occurs in this example, since all robots are moving in the same direction. So, the health of the robots in order from the first robot is returned, [2, 17, 9, 15, 10].

Example 2

Input:

positions = [3,5,2,6], healths = [10,10,15,12], directions = "RLRL"

Output:

[14]

Explanation:

There are 2 collisions in this example. Firstly, robot 1 and robot 2 will collide, and since both have the same health, they will be removed from the line. Next, robot 3 and robot 4 will collide and since robot 4's health is smaller, it gets removed, and robot 3's health becomes 15 - 1 = 14. Only robot 3 remains, so we return [14].

Example 3

Input:

positions = [1,2,5,6], healths = [10,10,11,11], directions = "RLRL"

Output:

[]

Explanation:

Robot 1 and robot 2 will collide and since both have the same health, they are both removed. Robot 3 and 4 will collide and since both have the same health, they are both removed. So, we return an empty array, [].

Constraints

• 1 <= positions.length == healths.length == directions.length == n <= 105
• 1 <= positions[i], healths[i] <= 109
• directions[i] == 'L' or directions[i] == 'R'
• All values in positions are distinct

Approach and Intuition

Given the complexity of the robot interactions, here's a clarifying approach that breaks down how collisions can be resolved efficiently.

• Sorting Robots by Position: To simplify the processing of movements and collisions, we first sort the robots based on their positions. This aids in determining which robots will meet and potentially collide as they move.

• Processing Movements and Collisions: Essentially, we only need to be concerned about pairs of robots where one is moving towards the other. This is particularly relevant for pairs where one robot has 'R' in the directions and the adjacent one has 'L'. Other configurations either don't result in a collision, or they always pass through without meeting (both moving in the same direction). From the examples:

  • In Example 1, all robots move to the right, making it impossible for any collisions to occur.
  • Example 2 and Example 3 highlight situations where we have alternating directions, leading to potential or actual collisions.

• Handling Collisions: For each encounter between two robots moving towards each other:

  • Calculate the meeting point and check the health to decide the outcome (robot survives, both robots get removed, etc.).
  • Update the health and, if necessary, remove the affected robots from further consideration.

• Edge Cases: Handle scenarios with an uneven distribution of movement directions or where all robots move in a single direction, as these either limit or completely negate the possibility of a collision.

By organizing the robots based on positions and then scrutinizing potential collisions based on direction and health, it becomes manageable to simulate the entire process efficiently, adhering to the given constraints.

Solutions

class Solution {
public:
    vector<int> remainingRobotsHealth(vector<int>& coords, vector<int>& vitality, string movement) {
        int total = coords.size();
        vector<int> sortingIndex(total), survivors;
        stack<int> robots;
    
        for (int i = 0; i < total; ++i) {
            sortingIndex[i] = i;
        }
    
        sort(sortingIndex.begin(), sortingIndex.end(),
             [&](int left, int right) { return coords[left] < coords[right]; });
    
        for (int sortedIdx : sortingIndex) {
            if (movement[sortedIdx] == 'R') {
                robots.push(sortedIdx);
            } else {
                while (!robots.empty() && vitality[sortedIdx] > 0) {
                    int encounterIdx = robots.top();
                    robots.pop();
                        
                    if (vitality[encounterIdx] > vitality[sortedIdx]) {
                        vitality[encounterIdx] -= 1;
                        vitality[sortedIdx] = 0;
                        robots.push(encounterIdx);
                    } else if (vitality[encounterIdx] < vitality[sortedIdx]) {
                        vitality[sortedIdx] -= 1;
                        vitality[encounterIdx] = 0;
                    } else {
                        vitality[sortedIdx] = 0;
                        vitality[encounterIdx] = 0;
                    }
                }
            }
        }
    
        // Gather robots that are still in good condition
        for (int idx = 0; idx < total; ++idx) {
            if (vitality[idx] > 0) {
                survivors.push_back(vitality[idx]);
            }
        }
        return survivors;
    }
};