aboutsummaryrefslogtreecommitdiff
path: root/alphabet_board_path.c
blob: 16fa77f65b58f986d53f9302a18560a7791f4470 (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
// 1138. Alphabet Board Path
#include <stdio.h>
#include <stdlib.h>

/*
 * on an alphabet board, we start position [0,0], corresponding to character
 * 'board[0][0]'. here, 'board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy",
 * "z"]' as show in the diagram (see page). return a sequence of moves that
 * makes our answer equal to 'target' in the minimum numbe of moves. (in any
 * order/path)
 */

char *alphabetBoardPath(char *target) {
  char map[26][2] = {0};
  int i;
  for (i = 0; i < 26; i++) {
    map[i][0] = i % 5;
    map[i][1] = i / 5;
  }
  char *curr, *prev;
  curr = "a";
  prev = target;
  char *ans = (char *)malloc(100 * sizeof(char));
  int ans_size = 100;
  i = 0;
  while (*prev) {
    if (ans_size - i < 11) {
      ans_size += 11;
      char *new_ans = (char *)realloc(ans, ans_size * sizeof(char));
      if (new_ans)
        ans = new_ans;
    }
    int j = (int)(*prev) - (int)('a');
    int k = (int)(*curr) - (int)('a');
    int dx = map[j][0] - map[k][0];
    int dy = map[j][1] - map[k][1];
    if (dx < 0)
      while (dx) {
        ans[i++] = 'L';
        dx++;
      }
    if (dy > 0)
      while (dy) {
        ans[i++] = 'D';
        dy--;
      }
    if (dy < 0)
      while (dy) {
        ans[i++] = 'U';
        dy++;
      }
    if (dx > 0)
      while (dx) {
        ans[i++] = 'R';
        dx--;
      }
    ans[i++] = '!';
    curr = prev;
    prev++;
  }
  ans[i] = '\0';
  return ans;
}

int main() {
  char *t1 = "leet";
  char *t2 = "code";
  printf("%s\n", alphabetBoardPath(t1)); // expect: DDR!UURRR!!DDD!
  printf("%s\n", alphabetBoardPath(t2)); // expect: RR!DDRR!UUL!R!
}