aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--race_car.c112
-rw-r--r--race_car.py38
2 files changed, 150 insertions, 0 deletions
diff --git a/race_car.c b/race_car.c
new file mode 100644
index 0000000..e117baf
--- /dev/null
+++ b/race_car.c
@@ -0,0 +1,112 @@
+// 818. Race Car
+#include "leetcode.h"
+
+/*
+ * your car starts at position 0 and speed +1 on an infinite number line. your
+ * car can go into negative positions. your car drives automatically according
+ * to a sequence of instructions 'A' (accelerate), and 'R' (reverse). given a
+ * target position 'target', return the length of the shortest sequence of
+ * instructions to get there.
+ */
+
+#define MAX_POW_2 20
+
+struct args {
+ int position;
+ int speed;
+};
+
+struct queue {
+ struct args *a;
+ int prev;
+ int curr;
+ size_t len;
+};
+
+int *get_pow_2(void) {
+ int *res = (int *)malloc(2 * MAX_POW_2 * sizeof(int));
+ res[0] = 1;
+ for (int i = 1; i < MAX_POW_2; ++i)
+ res[i] = res[i - 1] * 2;
+ res[MAX_POW_2] = -1;
+ for (int i = MAX_POW_2 + 1; i < MAX_POW_2 * 2; ++i)
+ res[i] = res[i - 1] * 2;
+ return res;
+}
+
+void queue_init(struct queue *q) {
+ q->a = (struct args *)malloc(128 * sizeof(struct args *));
+ q->len = 128;
+ q->prev = -1;
+ q->curr = 0;
+}
+
+void queue_push(struct queue *q, struct args a) {
+ q->prev++;
+ if (q->prev >= q->len) {
+ q->a = (struct args *)realloc(q->a, 2 * q->len * sizeof(struct args));
+ q->len *= 2;
+ }
+ q->a[q->prev] = a;
+}
+
+struct args queue_pop(struct queue *q) {
+ struct args res = q->a[q->curr];
+ q->curr++;
+ return res;
+}
+
+bool queue_empty(struct queue *q) { return q->curr > q->prev || q->prev == -1; }
+
+void queue_free(struct queue *q) { free(q->a); }
+
+int racecar(int target) {
+ int *pow = get_pow_2();
+ int row_size = 2 * target + 1;
+ int col_size = 2 * MAX_POW_2;
+ int *vis[row_size];
+ for (int i = 0; i < row_size; ++i) {
+ vis[i] = (int *)malloc(col_size * sizeof(int));
+ memset(vis[i], -1, col_size * sizeof(int));
+ }
+ struct queue q;
+ queue_init(&q);
+ struct args initial;
+ initial.position = 0;
+ initial.speed = 0;
+ vis[initial.position][initial.speed] = 0;
+ queue_push(&q, initial);
+ while (!queue_empty(&q)) {
+ struct args curr = queue_pop(&q);
+ if (curr.position + pow[curr.speed] < row_size &&
+ curr.position + pow[curr.speed] >= 0 &&
+ vis[curr.position + pow[curr.speed]][1 + curr.speed] == -1) {
+ vis[curr.position + pow[curr.speed]][1 + curr.speed] =
+ vis[curr.position][curr.speed] + 1;
+ if (curr.position + pow[curr.speed] == target)
+ return vis[curr.position + pow[curr.speed]][1 + curr.speed];
+ struct args next;
+ next.position = curr.position + pow[curr.speed];
+ next.speed = curr.speed + 1;
+ queue_push(&q, next);
+ }
+ int change = curr.speed < MAX_POW_2 ? MAX_POW_2 : 0;
+ if (vis[curr.position][change] == -1) {
+ vis[curr.position][change] = vis[curr.position][curr.speed] + 1;
+ struct args next;
+ next.position = curr.position;
+ next.speed = change;
+ queue_push(&q, next);
+ }
+ }
+ for (int i = 0; i < row_size; i++)
+ free(vis[i]);
+ free(pow);
+ queue_free(&q);
+ return -1;
+}
+
+int main() {
+ printf("%d\n", racecar(3)); // expect: 2
+ printf("%d\n", racecar(6)); // expect: 5
+}
diff --git a/race_car.py b/race_car.py
new file mode 100644
index 0000000..5352fbe
--- /dev/null
+++ b/race_car.py
@@ -0,0 +1,38 @@
+# 818. Race Car
+
+"""
+your car starts at position 0 and speed +1 on an infinite number line. your
+car can go into negative positions. your car drives automatically according
+to a sequence of instructions 'A' (accelerate), and 'R' (reverse). given a
+target position 'target', return the length of the shortest sequence of
+instructions to get there.
+"""
+
+
+class Solution(object):
+ dp = {0: 0}
+
+ def racecar(self, target):
+ """
+ :type target: int
+ :rtype: int
+ """
+ if target in self.dp:
+ return self.dp[target]
+ n = target.bit_length()
+ if 2**n - 1 == target:
+ self.dp[target] = n
+ else:
+ self.dp[target] = self.racecar(2**n - 1 - target) + n + 1
+ for m in range(n - 1):
+ self.dp[target] = min(
+ self.dp[target],
+ self.racecar(target - 2 ** (n - 1) + 2**m) + n + m + 1,
+ )
+ return self.dp[target]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.racecar(3))
+ print(obj.racecar(6))