aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--readme.md2
-rw-r--r--robot_collisions.c98
-rw-r--r--robot_collisions.py60
3 files changed, 159 insertions, 1 deletions
diff --git a/readme.md b/readme.md
index 5a802df..de35a23 100644
--- a/readme.md
+++ b/readme.md
@@ -1,7 +1,7 @@
## leetcode
this repository contains my leetcode solutions for [user 0x6A73](https://leetcode.com/u/0x6A73).
the daily challenge is solved in both c and python, but there are also
-some problems soved in c++ and rust.
+some problems solved in c++ and rust.
### notes
[`leetcode.h`](leetcode.h) contains various includes, standard leetcode
diff --git a/robot_collisions.c b/robot_collisions.c
new file mode 100644
index 0000000..8903992
--- /dev/null
+++ b/robot_collisions.c
@@ -0,0 +1,98 @@
+// 2751. Robot Collisions
+#include "leetcode.h"
+
+/*
+ * there are 'n' 1 indexed robots, each having a position on a line, health, and
+ * movement directions. all robots start moving on the line simultaneously at
+ * the same speed in their given directions. if two robots ever share the same
+ * position while moving, they will collide. if two robots collide, the robot
+ * with lower health is removed from the line and the health of the other robot
+ * decreases by 1. the surviving robot continues in the same direction it was
+ * going. if both robots have the same health they are both removed from the
+ * line. return an array containing the health of the remaining robots after no
+ * further collisions can occur
+ */
+
+int cmp(const void *a, const void *b) {
+ int *aa = *(int **)a, *bb = *(int **)b;
+ return aa[0] - bb[0];
+}
+
+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;
+ }
+ 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--;
+ } else {
+ healths[record[i][1]] = 0;
+ healths[stack[idx]] -= 1;
+ }
+ }
+ } else {
+ stack[++idx] = record[i][1];
+ }
+ }
+ 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]);
+ 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 *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
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", sbh2[i]); // expect: 14
+ printf("\n");
+ for (int i = 0; i < rs3; i++)
+ printf("%d ", sbh3[i]); // expect: null
+ printf("\n");
+ free(sbh1), free(sbh2), free(sbh3);
+}
diff --git a/robot_collisions.py b/robot_collisions.py
new file mode 100644
index 0000000..a62896b
--- /dev/null
+++ b/robot_collisions.py
@@ -0,0 +1,60 @@
+# 2751. Robot Collisions
+
+"""
+there are 'n' 1 idxexed robots, each having a position on a line, health, and
+movement directions. all robots start moving on the line simultaneously at
+the same speed in their given directions. if two robots ever share the same
+position while moving, they will collide. if two robots collide, the robot
+with lower health is removed from the line and the health of the other robot
+decreases by 1. the surviving robot continues in the same direction it was
+going. if both robots have the same health they are both removed from the
+line. return an array containing the health of the remaining robots after no
+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]
+ """
+ n = len(positions)
+ idx = sorted(range(n), key=positions.__getitem__)
+ stack = []
+ for i in idx:
+ if directions[i] == "R":
+ stack.append(i)
+ 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 __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.survivedRobotsHealths(
+ positions=[5, 4, 3, 2, 1], healths=[2, 17, 9, 15, 10], directions="RRRRR"
+ )
+ )
+ print(
+ obj.survivedRobotsHealths(
+ positions=[3, 5, 2, 6], healths=[10, 10, 15, 12], directions="RLRL"
+ )
+ )
+ print(
+ obj.survivedRobotsHealths(
+ positions=[1, 2, 5, 6], healths=[10, 10, 11, 11], directions="RLRL"
+ )
+ )