5
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Your code does not work \$\endgroup\$ – tuxtimo May 23 '14 at 14:37
  • \$\begingroup\$ I think your examples don't much your algo description ... \$\endgroup\$ – tuxtimo May 23 '14 at 14:49
  • \$\begingroup\$ 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. \$\endgroup\$ – Hoopdady May 23 '14 at 14:52
  • \$\begingroup\$ In python, functions are lowercase, capitalization is reserved for classes. \$\endgroup\$ – Scüter May 26 '14 at 2:47
3
\$\begingroup\$

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())
\$\endgroup\$
  • \$\begingroup\$ 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). \$\endgroup\$ – tokland May 23 '14 at 19:05
  • \$\begingroup\$ 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 :-) \$\endgroup\$ – Josay May 23 '14 at 19:15
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Hoopdady May 23 '14 at 14:50
0
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Using exception handling is generally considered bad practice. It breaks logical flow, and in some cases can slow down your program. \$\endgroup\$ – BenVlodgi May 23 '14 at 15:20
  • \$\begingroup\$ 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. \$\endgroup\$ – BeetDemGuise May 23 '14 at 15:27

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.