Number Of Matching Elements In Two Lists

Question

I have many sets of 2 strings. I'm trying to determine the number of matching elements in these 2 strings. The rules are if the strings share a common letter, that's a point, order does matter, but each letter in the first string can only match one of the letters in the second string. So in the strings 'aaaab', 'acccc', only 1 point is awarded because there is only one 'a' to match in the second string. Here are a few examples:

aaabb  bbaaa  5
aabbb  bbbaa  5
aaabb  aabbb  4
aaabb  ccaaa  3
aaaaa  bbbbb  0
ababa  babab  4
aabcc  babaf  3
abcde  abfgh  2
bacde  abdgh  3

Hopefully that gets across how it works.

Here is the most efficient code I've been able to come up with, but its horribly convoluted. I hoping someone could think of something better.

def Score(guess, solution):
    guess = list(guess)
    solution = list(solution)
    c = 0
    for g in guess:
        if g in solution and g != "_":
            c += 1
            solution[solution.index(g)] = "_"
    return c

Surely this isn't the best way to do this, but I haven't been able to figure anything else out. I tried creating an algorithm with Counter and doing guess&solution, which worked, but ended up being way slower. Anyone have any ideas?

Answer 1

As you have updated your examples, you can write some code to ensure the code we are about to write works properly :

def main():
    """Main function"""
    assert Score('aaabb', 'bbaaa') == 5
    assert Score('aabbb', 'bbbaa') == 5
    assert Score('aaabb', 'aabbb') == 4
    assert Score('aaabb', 'ccaaa') == 3
    assert Score('aaaaa', 'bbbbb') == 0
    assert Score('ababa', 'babab') == 4
    assert Score('aabcc', 'babaf') == 3
    assert Score('abcde', 'abfgh') == 2
    assert Score('bacde', 'abdgh') == 3

Now, the main issue in your code is that we are performing complicated (dirty?) string logic and checking many times if some letter is in a list. The real solution is to count letters in both string. Each letter will count for n points where n is the minimum between the number of times it appears in string 1 and the number of times it appears in string 2.

Using Counter, you can write this :

from collections import Counter

def Score(guess, solution):
    g = Counter(guess)
    s = Counter(solution)
    n = 0
    for l,c in g.iteritems():
        n+=min(c, s[l])
    return n

Abusing generator expressions, you can also write this :

def Score(s1, s2):
    c = Counter(s2)
    return sum(min(n, c[l]) for l,n in Counter(s1).iteritems())

Answer 2

You can use defaultdict you easily get the counts of each character in the strings:

from collections import defaultdict

def get_count(string):
    counts = defaultdict(int)
    for char in string;
        counts[char] += 1

    return count

Find the counts for each string and pass the defaultdicts to your score function. Then its as simple as taking the minimum value for each key in the defaultdicts:

def get_score(dict_one, dict_two):
    score = 0
    for key in dict_one:
        score += min(dict_one[key], dict_two[key])

    return score

Here are some examples:

>>>get_score(get_count('aaabb'), get_count('bbaaa'))
5
>>>get_score(get_count('ababa'), get_count('babab'))
4

Answer 3

Not quite an answer but too big for a comment and it seems important to let you know that your examples do not work - at least not on my config.

Here's what I have (string1, string2, actual result, expected result)

aaabb bbaaa
5 5
aabbb bbbaa
5 4
aaabb aabbb
4 4
aaabb ccaaa
3 3
aaaaa bbbbb
0 0
ababa babab
4 4
aabcc babaf
3 3
abcde abfgh
2 2
bacde abdgh
3 2

Answer 4

Consider doing the following code

def count_score(guess, solution):
    score = 0
    solution = list(solution)
    for g in guess:
        try:
            solution.pop(solution.index(g))
            score += 1
        except ValueError:
            continue
    return score

If the current char from guess (g) is not found by index an ValueError Exception is thrown.