Robot Collisions

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;
    }
};

In the provided C++ solution, the task is to determine the remaining health of robots after a series of movements and collisions. Robots that face right (R) and left (L) collide based on their positions and health points. The solution employs sorting to track the positions of robots and simulate the collisions using conditions derived from their health points and directions.

Here's a breakdown of how the solution tackles this problem:

• Initialization: Arrays for coords (positions of the robots) and vitality (health points) are taken as input along with a movement string. Auxiliary containers, like sortingIndex for tracking sorted indices of coords, and a stack for robots facing right, are initialized.

• Sorting: Robots are sorted by their positions using a custom comparator. This ensures that processing happens from the leftmost robot to the rightmost, aiding in the simulation of movements and collisions accurately.

• Collision Simulation: Iterations take place in the order of sorted positions. If a robot faces right, its index is pushed onto the stack. When encountering a robot facing left, collisions are checked with any robot facing right (detected by examining the stack):

  • If vitality of the robot from the stack (facing right) is greater than the current left-facing robot, the right-facing robot decreases its vital by 1, and the left-facing robot's vitality drops to 0, indicating it's out.
  • If the left-facing robot has higher vital, vice versa occurs.
  • If both have equal vitality, both are set to 0.

• Determine Survivors: After processing all robots, the vector survivors is filled with the vitalities of robots that still maintain a vitality greater than 0.

This method ensures efficiency by avoiding direct O(n^2) comparisons and leverages sorting and stack operations to handle collisions in an optimal way relative to the sequence of robot positions and movements.

class Solution {

    public List<Integer> remainingRobotsHealth(
        int[] placements,
        int[] vitality,
        String movements
    ) {
        int count = placements.length;
        Integer[] sortedIndices = new Integer[count];
        List<Integer> survivors = new ArrayList<>();
        Stack<Integer> collisionStack = new Stack<>();

        for (int i = 0; i < count; ++i) {
            sortedIndices[i] = i;
        }

        Arrays.sort(
            sortedIndices,
            (left, right) -> Integer.compare(placements[left], placements[right])
        );

        for (int sortedIndex : sortedIndices) {
            if (movements.charAt(sortedIndex) == 'R') {
                collisionStack.push(sortedIndex);
            } else {
                while (!collisionStack.isEmpty() && vitality[sortedIndex] > 0) {
                    int stackTop = collisionStack.pop();

                    if (vitality[stackTop] > vitality[sortedIndex]) {
                        vitality[stackTop] -= 1;
                        vitality[sortedIndex] = 0;
                        collisionStack.push(stackTop);
                    } else if (vitality[stackTop] < vitality[sortedIndex]) {
                        vitality[sortedIndex] -= 1;
                        vitality[stackTop] = 0;
                    } else {
                        vitality[sortedIndex] = 0;
                        vitality[stackTop] = 0;
                    }
                }
            }
        }

        for (int idx = 0; idx < count; ++idx) {
            if (vitality[idx] > 0) {
                survivors.add(vitality[idx]);
            }
        }
        return survivors;
    }
}

The provided Java solution is designed to simulate a scenario where robots placed on a line and moving in specified directions can collide based on their movements. Each robot has a corresponding health level, and the output should be the remaining health of the robots that survive any collisions.

Explanation:

• Robots and their properties are represented by two arrays placements and vitality, and their movement directions are indicated by a string movements.
• Each robot is initially considered by sorting them based on their placement positions to process encounters sequentially.
• A stack (collisionStack) is utilized to manage collisions in sequence. If a robot moves right ('R'), it is pushed onto the stack. Conversely, when a robot moving left is encountered, the stack is processed:
  1. Robots popping from the stack (moving right) collide with the current left-moving robot.
  2. The collision results in the decrement of their health based on the conditions given; if the health of colliding robots is equal, both are considered destroyed (health becomes zero). If one robot's health is greater, it survives, and the weaker robot's health becomes zero.
• After processing all movements and collisions, the remaining health values are gathered for robots that have a non-zero health, indicating their survival.

Result:

• The method remainingRobotsHealth returns a list of the health values for the surviving robots after all possible collisions have been resolved based on the initial positions, health, and movements of the robots using effective data structures like arrays, stacks, and sorting mechanisms for an efficient solution.

class Solution:
    def finalRobotsHealths(
        self, positions: List[int], healths: List[int], directions: str
    ) -> List[int]:
        count = len(positions)
        robot_indices = list(range(count))
        output = []
        collision_stack = deque()

        # Sorting based on robot positions
        robot_indices.sort(key=lambda idx: positions[idx])

        for idx in robot_indices:
            # Process right-moving robots
            if directions[idx] == "R":
                collision_stack.append(idx)
            else:
                while collision_stack and healths[idx] > 0:
                    # Resolving collisions
                    last_idx = collision_stack.pop()

                    if healths[last_idx] > healths[idx]:
                        # Last index robot wins the collision
                        healths[last_idx] -= 1
                        healths[idx] = 0
                        collision_stack.append(last_idx)
                    elif healths[last_idx] < healths[idx]:
                        # Current index robot wins the collision
                        healths[idx] -= 1
                        healths[last_idx] = 0
                    else:
                        # Both robots are destroyed
                        healths[idx] = 0
                        healths[last_idx] = 0

        # Remaining robots with non-zero health
        for index in range(count):
            if healths[index] > 0:
                output.append(healths[index])

        return output

This Python program calculates the final health of robots moving on a line after potential collisions. Each robot has a position, initial health, and a direction of movement, either right ("R") or left ("L"). Here's a concise breakdown of the implementation:

• The program first retrieves the number of robots and initializes an output list and a stack to handle collisions.
• The robots are sorted by their positions to ensure they are processed in the correct order of potential collisions.
• The program uses a loop to assess each robot:
  • If a robot moves right, its index gets pushed onto the stack.
  • If a robot moves left, it triggers collision checks with any right-moving robots that were previously added to the stack.
• Collisions are resolved based on their health:
  • If the right-moving robot has higher health, the left-moving robot is annihilated, and the right-moving robot loses one health unit but remains in the stack for further collision checks.
  • If the left-moving robot has higher health, it assumes the winner's position with decreased health, and the right-moving robot is annihilated.
  • If both have equal health, both robots are annihilated.
• After processing all robots, the remaining robots' healths are compiled into the output list if their health is non-zero.

This logic ensures that only robots that survive collisions and still contain health are listed in the output, neatly capturing the dynamics of robot movements and interactions.