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?

• tuxtimo: Your code does not work
• tuxtimo: I think your examples don't much your algo description ...
• Hoopdady: The code does work, unless you got the earliest revision of the post. But I fixed that pretty quickly after I posted. The examples are fixed. I didn't run them through my code I just tried to give some examples to help understand the logic. Thanks for noticing though.
• Scüter: In python, functions are lowercase, capitalization is reserved for classes.

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

• tokland: I don't think that's abusing generator expressions, your second snippet is exactly how it should be done IMO (I'd just use more meaningful names).
• SylvainD: Agree! I just try to give the different steps leading to the solution and giving the name of the principle behind it. I'm glad you like it :-)

Answer 2

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

• Hoopdady: You're right, I just created examples off the top of my head, I've fixed them in the examples. But the code works. Thanks for the heads up.

Answer 3

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

• BenVlodgi: Using exception handling is generally considered bad practice. It breaks logical flow, and in some cases can slow down your program.
• BeetDemGuise: Correct @BenVlodgi. However, as some food for thought, a classic Python axium is its easier to ask for forgiveness than permission. Essentially, in some cases its bette to use try-except than many possible if-statements.