Given a list of recipes a list of owned ingredients, which algorithm is best to determine "Which ingredient could I add to access the most recipes?"

user_5636773 0
Viewed 156

I hope the long title does a decent job of explaining the question. This feels like a nominal question so I suspect there is a known algorithm for this, or maybe it maps to NP.

Given a cookbook in the form of

cookbook = {
    recipe1: [ingredient1, ingredient2, ingredient35],
    recipe2: [ingredient1, ingredient8, ingredient12], 
    recipe3: [ingredient10, ingredient22, ingredient35],
    ...
}

And a list of ingredients in the form

ingredients = {
    ingredient1: true, //owned
    ingredient2: false, //unowned
    ingredient3: true,
    ...
}

Which algorithm would efficiently answer "Which ingredient can you add to complete the most recipes?"

Assume

  • There are a large number of recipes & ingredients
  • A given recipe will not have more than 10 ingredients
  • You can transform/manipulate the data however you see fit
  • The grading criteria is how efficient can you make an algorithm which can answer "Which ingredient should I add to make the most recipes, given the ingredient's I already own"
  • A person could add/remove ingredients at random, and must be able to answer the "Which ingredient?" question efficiently
  • Space complexity can be ignored for now
  • Then intent is design a data structure + algorithm, however computationally complex that might be, which allows for rapid queries. The 'grading' is how fast those future queries are
coding-efficiency graph-theory algorithm performance
3 Answers

Pseudo code

bestIngredient = 0
bestCount = 0
Loop I  over owned ingredients
   count = 0
   Loop R over recipes
       If I completes R
          increment count
   if count > bestCount
      bestCount = count
      bestIngredient = I

When an ingredient I is added:

Loop R over recipies
    If R needs I 
    Add I to R
user_165820

Create a trie from the recipes. For each query, recurse on subsequences of the query and one allowed wildcard, walking the trie. (Both recipes and query should sort ingredients in the same way.)

user_20347870 
score = empty hashmap
for each R in recipes
  missing = empty list
  for each I in R
    if ingredients[i] = false
      missing += I
  if size(missing) = 1
    I = missing[0]
    score[I]++
result = choose key I in score with maximum value
user_8214970
Related