aboutsummaryrefslogtreecommitdiff
path: root/possible_recipes_supplies.c
blob: 1761eaf2b5bcd78e5dff262508e8df911c916e26 (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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
// 2115. Find All Possible Recipes from Given Supplies
#include "leetcode.h"

/*
 * you have information about 'n' different recipes. you are given a string
 * array 'recipes' and a 2d string array 'ingredients'. the i'th recipe has the
 * name 'recipes[i]', and you can create it is you have all the needed
 * ingredients from 'ingredients[i]'. ingredients to a recipe may need to be
 * created from other recipes, ie. 'ingredients[i]' may contain a string that is
 * in 'recipes'. you are also given a string array 'supplies' containing all the
 * ingredients that you initially have, and you have an infinite supply of all
 * of them. return a list of all the recipes that you can create. you may return
 * the answer in any order.
 */

struct item {
  struct item *next[26];
  bool end;
};

struct item trie;

void trie_init(void) { memset((void *)&trie, 0, sizeof(trie)); }

void trie_push(char *s) {
  struct item *header = ≜
  for (int i = 0; s[i]; i++) {
    if (!header->next[s[i] - 'a'])
      header->next[s[i] - 'a'] = (struct item *)calloc(1, sizeof(struct item));
    header = header->next[s[i] - 'a'];
  }
  header->end = true;
}

bool trie_find(char *s) {
  struct item *header = ≜
  for (int i = 0; s[i]; i++) {
    if (!header->next[s[i] - 'a'])
      return false;
    header = header->next[s[i] - 'a'];
  }
  return header->end;
}

void trie_free_single(struct item *trie) {
  if (trie) {
    for (int i = 0; i < 26; i++)
      trie_free_single(trie->next[i]);
    free(trie);
  }
}

void trie_free(void) {
  for (int i = 0; i < 26; i++)
    trie_free_single(trie.next[i]);
}

char **findAllRecipes(char **recipes, int recipesSize, char ***ingredients,
                      int ingredientsSize, int *ingredientsColSize,
                      char **supplies, int suppliesSize, int *returnSize) {
  char **ans = (char **)malloc(recipesSize * sizeof(char *));
  trie_init();
  for (int i = 0; i < suppliesSize; i++)
    trie_push(supplies[i]);
  *returnSize = 0;
  bool progress = true;
  while (progress) {
    progress = false;
    for (int i = 0; i < recipesSize; i++) {
      if (trie_find(recipes[i]))
        continue;
      bool create = true;
      for (int j = 0; j < ingredientsColSize[i]; j++)
        if (!trie_find(ingredients[i][j])) {
          create = false;
          break;
        }
      if (create) {
        progress = true;
        trie_push(recipes[i]);
        ans[*returnSize] =
            (char *)malloc((strlen(recipes[i]) + 1) * sizeof(char));
        strcpy(ans[*returnSize], recipes[i]);
        (*returnSize)++;
      }
    }
  }
  trie_free();
  return ans;
}

int main() {
  char *r1[] = {"bread"};
  char *i11[] = {"yeast", "flour"};
  char **i1 = {i11};
  char *s1[] = {"yeast", "flour", "corn"};
  char *r2[] = {"bread", "sandwich"};
  char *i21[] = {"yeast", "flour"}, *i22[] = {"bread", "meat"};
  char **i2[] = {i21, i22};
  char *s2[] = {"yeast", "flour", "meat"};
  char *r3[] = {"bread", "sandwich", "burger"};
  char *i31[] = {"yeast", "flour"}, *i32[] = {"bread", "meat"},
       *i33[] = {"sandwich", "meat", "bread"};
  char **i3[] = {i31, i32, i33};
  char *s3[] = {"yeast", "flour", "meat"};
  int rs1, rs2, rs3;
  char **far1 =
      findAllRecipes(r1, ARRAY_SIZE(r1), (char ***)i1, ARRAY_SIZE(i11),
                     (int *)ARRAY_SIZE(i11), s1, ARRAY_SIZE(s1), &rs1);
  char **far2 =
      findAllRecipes(r2, ARRAY_SIZE(r2), (char ***)i2, ARRAY_SIZE(i21),
                     (int *)ARRAY_SIZE(i21), s2, ARRAY_SIZE(s2), &rs2);
  char **far3 =
      findAllRecipes(r3, ARRAY_SIZE(r3), (char ***)i3, ARRAY_SIZE(i31),
                     (int *)ARRAY_SIZE(i31), s3, ARRAY_SIZE(s3), &rs3);
  for (int i = 0; i < rs1; i++)
    printf("%s ", far1[i]); // expect: ["bread"]
  printf("\n");
  for (int i = 0; i < rs2; i++)
    printf("%s ", far2[i]); // expect: ["bread","sandwich"]
  printf("\n");
  for (int i = 0; i < rs3; i++)
    printf("%s ", far3[i]); // expect: ["bread","sandwich","burger"]
  printf("\n");
  free(far1);
  free(far2);
  free(far3);
}