Robot Collisions
Problem
Robots stand on a line, each with a position, a health value, and a direction ('L' for left or 'R' for right). All robots move at the same speed and start moving at once. When a right-moving robot reaches a left-moving robot they collide: the one with smaller health is removed and the survivor loses 1 health; if their healths are equal, both are removed. Two robots heading the same way never collide. Return the healths of the surviving robots in the order their indices appear in the original input.
positions = [3, 5, 2, 6], healths = [10, 10, 15, 12], directions = "RLRL"[14]def survived_robots_healths(positions, healths, directions):
order = sorted(range(len(positions)), key=lambda i: positions[i])
stack = []
for i in order:
if directions[i] == 'R':
stack.append(i)
continue
while stack and healths[i] > 0:
top = stack[-1]
if healths[top] < healths[i]:
healths[top] = 0
healths[i] -= 1
stack.pop()
elif healths[top] > healths[i]:
healths[i] = 0
healths[top] -= 1
else:
healths[i] = 0
healths[top] = 0
stack.pop()
return [h for h in healths if h > 0]function survivedRobotsHealths(positions, healths, directions) {
const order = [...positions.keys()].sort((a, b) => positions[a] - positions[b]);
const stack = [];
for (const i of order) {
if (directions[i] === 'R') {
stack.push(i);
continue;
}
while (stack.length && healths[i] > 0) {
const top = stack[stack.length - 1];
if (healths[top] < healths[i]) {
healths[top] = 0;
healths[i] -= 1;
stack.pop();
} else if (healths[top] > healths[i]) {
healths[i] = 0;
healths[top] -= 1;
} else {
healths[i] = 0;
healths[top] = 0;
stack.pop();
}
}
}
return healths.filter(h => h > 0);
}class Solution {
public List<Integer> survivedRobotsHealths(int[] positions, int[] healths, String directions) {
Integer[] order = new Integer[positions.length];
for (int i = 0; i < order.length; i++) order[i] = i;
Arrays.sort(order, (a, b) -> positions[a] - positions[b]);
Deque<Integer> stack = new ArrayDeque<>();
for (int i : order) {
if (directions.charAt(i) == 'R') {
stack.push(i);
continue;
}
while (!stack.isEmpty() && healths[i] > 0) {
int top = stack.peek();
if (healths[top] < healths[i]) {
healths[top] = 0;
healths[i] -= 1;
stack.pop();
} else if (healths[top] > healths[i]) {
healths[i] = 0;
healths[top] -= 1;
} else {
healths[i] = 0;
healths[top] = 0;
stack.pop();
}
}
}
List<Integer> res = new ArrayList<>();
for (int h : healths) if (h > 0) res.add(h);
return res;
}
}vector<int> survivedRobotsHealths(vector<int>& positions, vector<int>& healths, string directions) {
int n = positions.size();
vector<int> order(n);
for (int i = 0; i < n; i++) order[i] = i;
sort(order.begin(), order.end(), [&](int a, int b) { return positions[a] < positions[b]; });
vector<int> stack;
for (int i : order) {
if (directions[i] == 'R') {
stack.push_back(i);
continue;
}
while (!stack.empty() && healths[i] > 0) {
int top = stack.back();
if (healths[top] < healths[i]) {
healths[top] = 0;
healths[i] -= 1;
stack.pop_back();
} else if (healths[top] > healths[i]) {
healths[i] = 0;
healths[top] -= 1;
} else {
healths[i] = 0;
healths[top] = 0;
stack.pop_back();
}
}
}
vector<int> res;
for (int h : healths) if (h > 0) res.push_back(h);
return res;
}Explanation
Positions are scrambled in the input, but a collision can only happen between robots that are actually next to each other on the line. So the first move is to sort the robot indices by position and walk through them left to right.
A collision only ever happens when a right-moving robot is sitting to the left of a left-moving robot that comes after it. That is exactly the shape a stack captures: every time we see an 'R' robot we push its index, because it is now the closest right-mover that any future left-mover would smash into first.
When we hit an 'L' robot, it charges left into the stack of pending 'R' robots, nearest one first. We keep resolving collisions while the stack is non-empty and our 'L' robot is still alive (health > 0):
If the top 'R' robot has less health, it is destroyed (set its health to 0 and pop it) and our 'L' robot survives but loses 1 health, then continues to the next robot on the stack. If the top 'R' robot has more health, our 'L' robot is destroyed (health set to 0) and the 'R' robot loses 1 health and stays on the stack. If healths are equal, both are destroyed and we pop the top. An 'L' robot that empties the stack (or never met an 'R') simply keeps moving left and survives untouched.
Example: sorted by position the order is robot 2 (R, 15), robot 0 (R, 10), robot 1 (L, 10), robot 3 (L, 12). Push 2, push 0. Robot 1 meets robot 0: equal health, both die, pop. Robot 3 meets robot 2: 12 < 15, so robot 3 dies and robot 2 drops to 14. At the end we read every robot whose health is still positive in original index order, giving [14].