Asteroid field
Asteroids fly in a row, some left and some right; when two meet, the smaller one explodes, so decide which survive using a stack of right-moving ones. About 18 minutes.
Only some meetings are collisions
Each number is an asteroid: its size is the absolute value, and its sign is the direction, positive for right and negative for left. They all move at the same speed. Two asteroids meet only when a right-mover has a left-mover coming from its right.
Keep a stack of the asteroids that survive so far. A new right-mover is just pushed. A new left-mover may hit the top of the stack if that top is moving right.
a, b = 5, -3 meets = a > 0 and b < 0 # right-mover then left-mover
6 moves right. Push it. Stack: 6.
The fight
When a left-mover meets a right-mover on top, compare sizes. If the one on top is smaller, it explodes: pop it, and the left-mover keeps going to meet the next one. If the sizes are equal, both explode. If the one on top is bigger, the left-mover explodes.
If the left-mover meets no more right-movers, because the stack is empty or its top moves left, it survives and joins the stack.
if abs(a) > abs(b):
print("a survives")
elif abs(a) == abs(b):
print("both explode")
else:
print("b survives")A right-mover of size 5 meets a left-mover of size 5. What happens?
- ABoth explode
- BOnly the left-mover explodes
- COnly the right-mover explodes
Show the answer
Both explode. Equal sizes destroy each other.
Asteroid collision
You are given an array asteroids of non-zero integers in a row. The absolute value is an asteroid's size, and the sign is its direction (positive moves right, negative moves left). All asteroids move at the same speed. When two asteroids meet, the smaller one explodes; if they are the same size, both explode. Asteroids moving in the same direction never meet. Return the asteroids that remain after all collisions, in their original order.
asteroids = [4, 7, -3, -9, 2] → [-9, 2]
1 ≤ length of asteroids ≤ 100,000 · -1,000 ≤ asteroids[i] ≤ 1,000 · asteroids[i] is not 0