Given a list of recipes a list of owned ingredients, which algorithm is best to determine "Whic-CodePudding

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

CodePudding user response：

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

CodePudding user response：

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.)

CodePudding user response：

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