comparing two arrays and getting similarity java-CodePudding

I have two arrays on my own custom objects. I need to find the amount of similarity to score it. The user will submit a recipe that they cooked and the program should score how accurate it was to the original recipe. Here is what I tried:

int increase = 100 / userRecipe.size();
for(int i = 0; i < userRecipe.size(); i  ) {
    if(userRecipe.get(i).equals(bookRecipe.get(i))) {
         percent  = increase;
    }
}

However the major flaw with this solution is that in theory, these two recipes below are scored 0% accuracy when it should be 75%.

Item[] userRecipe = {milk, sugar, eggs, flour};
Item[] bookRecipe = {sugar, eggs, flour};

However it doesn't work because the two lists are different lengths so it doesn't work. If anyone knows how I should approach this, I'd appreciate it. Here are the problems

The userRecipe list may be larger or smaller than the bookRecipe
The offset makes scoring inaccurate

I am a relative beginner to java, so if anyone wouldn't mind giving me a good solution, I'd appreciate it! Thank you.

CodePudding user response：

Here is my take on this.

use a set to hold the recipe ingredients.
then simply stream each submission and get the count of correct ingredients.
then compute the percentage based on the larger of the submitted ingredient count and the recipe count (to penalize for over specifying)

This works regardless of the order of the ingredients and works in linear time for each user due to the use of a set to hold the recipe.

Set<String> bookRecipe = Set.of("sugar", "eggs", "flour");
double ingredientCount = bookRecipe.size();

List<List<String>> entries = List.of(List.of("milk", "sugar"),
        List.of("milk", "sugar", "eggs", "flour"),
        List.of("milk", "sugar", "eggs", "flour", "beer"),
        List.of("milk", "sugar", "whiskey", "paint"),
        List.of("milk", "sugar", "eggs", "beer", "hay"),
        List.of("milk", "beer", "hay"),
        List.of("milk", "sugar", "eggs", "beer", "hay",
                "orange juice"));

System.out.println("Recipe: "   bookRecipe   "\n");
for (List<String> submission : entries) {
    long correct = submission.stream()
            .filter(ingredient -> bookRecipe.contains(ingredient))
            .count();
    
    double percentage = correct
            / Math.max(ingredientCount, submission.size());
    
    System.out.printf("=%% - %s%n",
            (int) (percentage * 100), submission);
}

prints

Recipe: [eggs, flour, sugar]

 33% - [milk, sugar]
 33% - [eggs]
  0% - [milk]
 75% - [milk, sugar, eggs, flour]
 60% - [milk, sugar, eggs, flour, beer]
 25% - [milk, sugar, whiskey, paint]
 40% - [milk, sugar, eggs, beer, hay]
  0% - [milk, beer, hay]
  0% - [beer, chips, salsa]
 33% - [milk, sugar, eggs, beer, hay, orange juice]

CodePudding user response：

Assuming the lists are in sorted order, to solve this problem optimally (without running in O(n^2) time), this is a classic manipulate two pointers problem.

int increase = 100 / userRecipe.size();
int userIndex = 0;
int bookIndex = 0;
while (bookIndex < boockRecipe.size() && userIndex < userRecipe.size()) {
    if (userRecipe.get(userIndex).equals(bookRecipe.get(bookIndex))) {
        percentage  = increase;
        bookIndex  ;
    }
    userIndex  ;
}

This will only loop through each list once.