0
$\begingroup$

I have two data sets of a particular structure:

User 1:
  Salad1: Tuna, Mayo, Lettuce
  ...
  Breakfast1: Egg, Avocado, Toast 

User 2:
  Salad1: Tuna, Mayo
  ...
  Breakfast1: Egg, Toast, Sausage 

There are thousands of dishes, and the goal is to ensure that all the ingredients from User 1 dish are present in the corresponding recipe of User 2 data set. We can't overwrite the recipe in User 2 data set, removing their additions - we only need to ensure that the ingredients from the corresponding User 1 dishes are present, and add them in if they are absent.

My solution:

Create a list of hashes for each recipe from each User:

Salad1|Tuna~Mayo~Lettuce
Breakfast1|Egg~Avocado~Toast

Perform a 'difference' operation on the two string arrays and end up with a list of those recipies that don't match. Break away the dish identifier from each resulting string, find the dish in the second data set and append the missing ingridient.

Benefits of my solution

As you can see, once we add the 'Lettuce' to the Salad1 recipe of User2, the relevant dish will stop coming up in the 'Difference of hashes' output, and the consequent synchronisations will take much less time.

Problems with my solution

Sadly, the Breakfast1 recipe of User2 will keep flagging up the difference even after we add the 'Toast' entry to it, because here the user has added 'Sausage' to the list. This way, if User2 chooses to add a 'special ingridient' to each recipe we will end up evaluating every single dish in his database for having ingridients of the corresponding dish in User1 data set.

Essentially: my approach reduces the amount of individual dishes that I need to evaluate (iterate over ingridients to see if the ingridients from the User1 dataset are present), but I still need to evaluate those where extra ingridients were added.

The challenge

Is there any established algorithm that would take the two datasets above, and return only 'dishes' from the second data set that need 'ingridients' added to them?

$\endgroup$
2
  • 2
    $\begingroup$ I'm struggling to understand what you are looking for. Are you looking for a data structure that will allow you to store this data, update it, and ensure the condition holds? Are you looking for an algorithm to take a bunch of data and check whether the condition holds? If you want a data structure, what are the operations you want to perform on it? If you want an algorithm, what is the input to the algorithm, and what do you want it to produce as output? What's the best approach you've found so far? I don't understand what it means to 'avoid parsing recipes'. $\endgroup$
    – D.W.
    Dec 17 '20 at 19:55
  • $\begingroup$ I can't modify the data structure. I am looking for an algorithm to take a bunch of data and see if condition holds. Please allow me to update the question $\endgroup$
    – Tony Sepia
    Dec 17 '20 at 20:51
2
$\begingroup$

I think you are asking about how to implement a set difference operation. Specifically, if user 1's recipe for salad 1 is viewed as a set of ingredients A, and user 2's recipe for salad 1 is viewed as a set of ingredients B, then the the set difference A \ B is exactly the set of ingredients that are in A but not in B.

One well-known and particularly simple algorithm goes like this:

  1. Sort each list of ingredients (let's say in ascending order).
  2. At the start, the first element of each list is the current element.
  3. Repeatedly compare the current elements of the lists. Calling the current elements of A and B by the names a and b, respectively, there are three cases:
    • a < b Ingredient a is in A and not in B, so make a note of it. Advance the current element for A, but keep the same current element in B.
    • a = b Ingredient a is in both, so nothing special need be done. Advance both current elements.
    • a > b Ingredient b is in B and not in A. We don't need to do anything special to rectify this situation. Advance the current element in B.

When you reach the end of both sorted lists, you will have a record of the ingredients that must be added to B's recipe.

There are more complicated algorithms that exploit the fact that strings support more interesting observations than just comparison, or which can take advantage of situations where there's only a small collection of possible ingredients, but I recommend you start here until you're confident that this algorithm doesn't meet your performance needs.

$\endgroup$
9
  • $\begingroup$ Thank you, Daniel. You have described an algorithm that I am referring to in the 'Problems with my solution' section, when I use the word 'evaluate' - "my approach reduces the amount of individual dishes that I need to evaluate". My problem is having two large data sets of recipies. Above I describe how I am trying to avoid performing unnecessary set difference operations in cases where ingredient lists are identical. You haven't touched upon this part of my question in your answer. But thank you anyway! $\endgroup$
    – Tony Sepia
    Dec 18 '20 at 10:59
  • $\begingroup$ @TonySepia Okay. Then I don't understand your question. You may need to make it more clear. In particular, it appears you are asking how to check if one set is a subset of another without checking if one set is a subset of another. What are the criteria you are using to decide whether a check is allowable or not? (Also, FWIW, "thousands" is not a large data set.) $\endgroup$ Dec 18 '20 at 15:08
  • $\begingroup$ I agree that my explanation must be quite poor. I give an example of how I am deciding whether a check is allowable in my question: I can exclude a lot of unnecessary checks by 'flattening' the ingredients (parts of the set) into a hash that contains both the ID of the dish and the ingredients. I then simply find an intersection between two arrays of strings (hashes from each set). If the dish has the same ingredients in both datasets, then it won't appear in the resulting set, thus eliminating the requirement to perform a set difference operation on every dish in each dataset. $\endgroup$
    – Tony Sepia
    Dec 18 '20 at 17:44
  • $\begingroup$ I have also come up with a nice way to make the order of the ingredients irrelevant by sorting the ingredients alphabetically when producing the hash. I guess what I am asking about is.. experts in computer science must have already solved this problem, so should know whether I am using the most efficient way. Perhaps I am re-inventing the wheel and there are simpler ways of achieving what I want. $\endgroup$
    – Tony Sepia
    Dec 18 '20 at 17:46
  • 1
    $\begingroup$ @TonySepia If the amount of data transferred is the metric you care about, then you may enjoy using a Bloom filter. It is a probabilistic technique, but they can be made to be arbitrarily unlikely to give a wrong answer -- say, 2^-64. $\endgroup$ Dec 18 '20 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.