commit 738535d11be07f7840c63e3b822995e2062dd565
parent d17da29c5340ec5d1e336b48ebf633dfbf6ad98c
Author: Jack Sangdahl <jack@pngu.org>
Date: Tue, 31 Mar 2026 20:52:41 -0600
2751. robot collisions
Diffstat:
2 files changed, 98 insertions(+), 82 deletions(-)
diff --git a/robot_collisions.c b/robot_collisions.c
@@ -13,86 +13,98 @@
* further collisions can occur
*/
-int cmp(const void *a, const void *b) {
- int *aa = *(int **)a, *bb = *(int **)b;
- return aa[0] - bb[0];
+struct robot {
+ int position;
+ int health;
+ int index;
+ char direction;
+};
+
+int cmp_pos(const void *a, const void *b) {
+ return ((struct robot *)a)->position - ((struct robot *)b)->position;
+}
+
+int cmp_idx(const void *a, const void *b) {
+ return ((struct robot *)a)->index - ((struct robot *)b)->index;
}
int *survivedRobotsHealths(int *positions, int positionsSize, int *healths,
int healthsSize, char *directions, int *returnSize) {
- int **record = (int **)malloc(sizeof(int *) * positionsSize);
- int *stack = (int *)malloc(sizeof(int) * positionsSize), idx = -1;
- int *ans = (int *)malloc(sizeof(int) * positionsSize);
- *returnSize = 0;
- for (int i = 0; i < positionsSize; i++) {
- record[i] = (int *)malloc(sizeof(int) * 2);
- record[i][0] = positions[i];
- record[i][1] = i;
- if (directions[i] == 'L')
- healths[i] *= 1;
+ int n = positionsSize, m = 0;
+ struct robot *robots = (struct robot *)malloc(n * sizeof(struct robot));
+ struct robot *stack = (struct robot *)malloc(n * sizeof(struct robot));
+ for (int i = 0; i < n; ++i) {
+ robots[i].position = positions[i];
+ robots[i].health = healths[i];
+ robots[i].direction = directions[i];
+ robots[i].index = i;
}
- qsort(record, positionsSize, sizeof(int *), cmp);
- for (int i = 0; i < positionsSize; i++) {
- if (idx == -1) {
- stack[++idx] = record[i][1];
- } else if (healths[record[i][1]] < 0 && healths[stack[idx]] > 0) {
- if (healths[stack[idx]] == -1 * healths[record[i][1]]) {
- healths[stack[idx]] = 0;
- healths[record[i][1]] = 0;
- idx--;
- } else if (healths[stack[idx]] > -1 * healths[record[i][1]]) {
- healths[record[i][1]] = 0;
- healths[stack[idx]] -= 1;
- } else {
- while (idx != -1 && healths[stack[idx]] > 0 &&
- healths[stack[idx]] < -1 * healths[record[i][1]]) {
- healths[stack[idx]] = 0;
- idx--;
- healths[record[i][1]] += 1;
- }
- if (idx == -1 || healths[stack[idx]] < 0) {
- stack[++idx] = record[i][1];
- } else if (-1 * healths[record[i][1]] == healths[stack[idx]]) {
- healths[stack[idx]] = 0;
- healths[record[i][1]] = 0;
- idx--;
+ qsort(robots, n, sizeof(struct robot), cmp_pos);
+ for (int i = 0; i < n; ++i) {
+ struct robot curr = robots[i];
+ if (curr.direction == 'R' || !m || stack[m - 1].direction == 'L') {
+ stack[m++] = curr;
+ continue;
+ }
+ if (curr.direction == 'L') {
+ bool add = true;
+ while (m > 0 && stack[m - 1].direction == 'R' && add) {
+ int prev_health = stack[m - 1].health;
+ if (curr.health > prev_health) {
+ m--;
+ curr.health--;
+ } else if (curr.health < prev_health) {
+ stack[m - 1].health--;
+ add = false;
} else {
- healths[record[i][1]] = 0;
- healths[stack[idx]] -= 1;
+ m--;
+ add = false;
}
}
- } else {
- stack[++idx] = record[i][1];
+ if (add)
+ stack[m++] = curr;
}
}
- for (int i = 0; i < positionsSize; i++)
- free(record[i]);
- free(record), free(stack);
- for (int i = 0; i < positionsSize; i++)
- if (healths[i])
- ans[(*returnSize)++] = abs(healths[i]);
+ qsort(stack, m, sizeof(struct robot), cmp_idx);
+ int *ans = (int *)malloc(m * sizeof(int));
+ *returnSize = m;
+ for (int i = 0; i < m; ++i)
+ ans[i] = stack[i].health;
+ free(robots);
+ free(stack);
return ans;
}
int main() {
- int p1[] = {5, 4, 3, 2, 1}, h1[] = {2, 17, 9, 15, 10}, rs1;
- int p2[] = {3, 5, 2, 6}, h2[] = {10, 10, 15, 12}, rs2;
- int p3[] = {1, 2, 5, 6}, h3[] = {10, 10, 11, 11}, rs3;
- char s1[] = "RRRRR", s2[] = "RLRL", s3[] = "RLRL";
+ int p1[] = {5, 4, 3, 2, 1}, h1[] = {2, 17, 9, 15, 10};
+ int r1[] = {2, 17, 9, 15, 10}, rs1;
+ int p2[] = {3, 5, 2, 6}, h2[] = {10, 10, 15, 12};
+ int r2[] = {14}, rs2;
+ int p3[] = {1, 2, 5, 6}, h3[] = {10, 10, 11, 11};
+ int r3[] = {}, rs3;
+ char *s1 = "RRRRR", *s2 = "RLRL", *s3 = "RLRL";
int *sbh1 =
survivedRobotsHealths(p1, ARRAY_SIZE(p1), h1, ARRAY_SIZE(h1), s1, &rs1);
int *sbh2 =
survivedRobotsHealths(p2, ARRAY_SIZE(p2), h2, ARRAY_SIZE(h2), s2, &rs2);
int *sbh3 =
survivedRobotsHealths(p3, ARRAY_SIZE(p3), h3, ARRAY_SIZE(h3), s3, &rs3);
- for (int i = 0; i < rs1; i++)
- printf("%d ", sbh1[i]); // expect: 2,17,9,15,10
+ for (int i = 0; i < rs1; i++) {
+ printf("%d ", sbh1[i]);
+ assert(r1[i] == sbh1[i]);
+ }
printf("\n");
- for (int i = 0; i < rs2; i++)
- printf("%d ", sbh2[i]); // expect: 14
+ for (int i = 0; i < rs2; i++) {
+ printf("%d ", sbh2[i]);
+ assert(r2[i] == sbh2[i]);
+ }
printf("\n");
- for (int i = 0; i < rs3; i++)
- printf("%d ", sbh3[i]); // expect: null
+ for (int i = 0; i < rs3; i++) {
+ printf("%d ", sbh3[i]);
+ assert(r3[i] == sbh3[i]);
+ }
printf("\n");
- free(sbh1), free(sbh2), free(sbh3);
+ free(sbh1);
+ free(sbh2);
+ free(sbh3);
}
diff --git a/robot_collisions.py b/robot_collisions.py
@@ -1,4 +1,5 @@
# 2751. Robot Collisions
+from typing import List
"""
there are 'n' 1 idxexed robots, each having a position on a line, health, and
@@ -13,32 +14,35 @@ further collisions can occur
"""
-class Solution(object):
- def survivedRobotsHealths(self, positions, healths, directions):
- """
- :type positions: List[int]
- :type healths: List[int]
- :type directions: str
- :rtype: List[int]
- """
+class Solution:
+ def survivedRobotsHealths(
+ self, positions: List[int], healths: List[int], directions: str
+ ) -> List[int]:
n = len(positions)
- idx = sorted(range(n), key=positions.__getitem__)
+ robots = [[positions[i], healths[i], directions[i], i] for i in range(n)]
+ robots.sort()
stack = []
- for i in idx:
- if directions[i] == "R":
- stack.append(i)
+ for robot in robots:
+ if robot[2] == "R" or not stack or stack[-1][2] == "L":
+ stack.append(robot)
continue
- while stack and healths[i] > 0:
- if healths[stack[-1]] < healths[i]:
- healths[stack.pop()] = 0
- healths[i] -= 1
- elif healths[stack[-1]] > healths[i]:
- healths[stack[-1]] -= 1
- healths[i] = 0
- else:
- healths[stack.pop()] = 0
- healths[i] = 0
- return [v for v in healths if v > 0]
+ if robot[2] == "L":
+ add = True
+ while stack and stack[-1][2] == "R" and add:
+ last_health = stack[-1][1]
+ if robot[1] > last_health:
+ stack.pop()
+ robot[1] -= 1
+ elif robot[1] < last_health:
+ stack[-1][1] -= 1
+ add = False
+ else:
+ stack.pop()
+ add = False
+ if add:
+ stack.append(robot)
+
+ return [robot[1] for robot in sorted(stack, key=lambda robot: robot[3])]
if __name__ == "__main__":
