comparing two arrays and getting similarity java

March 22, 2022

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.

>Solution :

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.