aboutsummaryrefslogtreecommitdiff
path: root/race_car.c
blob: e117bafd98b6fe26ef6f0bc65815b164bbe043cc (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
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
}