diff options
author | Jack Sangdahl <[email protected]> | 2025-02-05 14:39:55 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-02-05 14:39:55 -0700 |
commit | 39012fcdcf9a747d962a6fc7048ed13981afa127 (patch) | |
tree | 83a9b2a826ca44e20ebc21e5c1028140aa48c689 | |
parent | 5a6cba4d25e6bf80c57aa0b65778a947a0d940f1 (diff) | |
download | leetcode-39012fcdcf9a747d962a6fc7048ed13981afa127.tar.gz leetcode-39012fcdcf9a747d962a6fc7048ed13981afa127.zip |
2115. find all possible recipes from given supplies
-rw-r--r-- | possible_recipes_supplies.c | 128 | ||||
-rw-r--r-- | possible_recipes_supplies.py | 66 |
2 files changed, 194 insertions, 0 deletions
diff --git a/possible_recipes_supplies.c b/possible_recipes_supplies.c new file mode 100644 index 0000000..1761eaf --- /dev/null +++ b/possible_recipes_supplies.c @@ -0,0 +1,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); +} diff --git a/possible_recipes_supplies.py b/possible_recipes_supplies.py new file mode 100644 index 0000000..63fe5ff --- /dev/null +++ b/possible_recipes_supplies.py @@ -0,0 +1,66 @@ +# 2115. Find All Possible Recipes from Given Supplies +from collections import defaultdict, Counter + +""" +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. +""" + + +class Solution(object): + def findAllRecipes(self, recipes, ingredients, supplies): + """ + :type recipes: List[str] + :type ingredients: List[List[str]] + :type supplies: List[str] + :rtype: List[str] + """ + to_recipe, in_deg = defaultdict(set), Counter() + for i, j in zip(recipes, ingredients): + for k in j: + to_recipe[k].add(i) + in_deg[i] = len(j) + ans = [] + for i in supplies: + for j in to_recipe.pop(i, set()): + in_deg[j] -= 1 + if in_deg[j] == 0: + supplies.append(j) + ans.append(j) + return ans + + +if __name__ == "__main__": + obj = Solution() + print( + obj.findAllRecipes( + recipes=["bread"], + ingredients=[["yeast", "flour"]], + supplies=["yeast", "flour", "corn"], + ) + ) + print( + obj.findAllRecipes( + recipes=["bread", "sandwich"], + ingredients=[["yeast", "flour"], ["bread", "meat"]], + supplies=["yeast", "flour", "meat"], + ) + ) + print( + obj.findAllRecipes( + recipes=["bread", "sandwich", "burger"], + ingredients=[ + ["yeast", "flour"], + ["bread", "meat"], + ["sandwich", "meat", "bread"], + ], + supplies=["yeast", "flour", "meat"], + ) + ) |