1

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?

6
  • 1
    You are more likely to find help for this type of question at code review
    – Farmer Joe
    May 23, 2014 at 13:38
  • 1
    Oh neat. Didn't even know about that.
    – Hoopdady
    May 23, 2014 at 13:39
  • 1
    Shouldn't aabbb <-> bbbaa be 5?
    – sloth
    May 23, 2014 at 13:55
  • You are correct. All the letters start to blend together after awhile ;-)
    – Hoopdady
    May 23, 2014 at 13:56
  • 1
    According to my tests, the counter approach becomes a lot faster than your solution for long input string. For a 1000 letter string, it is 5 times faster on my computer. Your solution is O(n²) while the counter solution is O(n).
    – Samy Arous
    May 23, 2014 at 14:14

6 Answers 6

2

You could gain a ~10%* speed up by simply using the remove() method of list instead of the lookup with index().

Also, you don't need to copy guess into a list.

def Score(guess, solution):
    solution = list(solution)
    c = 0
    for g in guess:
        if g in solution:
            c += 1
            solution.remove(g)

    return c

*at least that's what I measured on my machine

2

You can do it in vectorized form using NumPy!

import numpy as np

counts1 = np.bincount(np.array('aaadez', 'c').view(np.uint8), minlength=128)
counts2 = np.bincount(np.array('eeeedddddaa', 'c').view(np.uint8), minlength=128)
np.min((counts1, counts2), axis=0).sum()

counts1 looks like this:

array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 3, 0, 0, 1, 1, 0...])

This is an array indexed by ASCII codes. The nonzero elements are at positions 97, 100, and 101, which are ASCII 'a', 'd', and 'e'. Then we do a pairwise min(), followed by sum to get the score (in this example, 4).

Something neat about this solution is that you can apply it to as many strings as you want with no decrease in efficiency, and even very long strings will be quite fast because there are no loops in Python itself--only in compiled NumPy code.

Before editing I had a similar but slower and more complex solution using Pandas and SciPy. Here it is:

import scipy.stats
import numpy as np
import pandas

x1 = scipy.stats.itemfreq(np.array('aaade', 'c').view(np.uint8))
x2 = scipy.stats.itemfreq(np.array('bbacadde', 'c').view(np.uint8))
merged = pandas.merge(pandas.DataFrame(x1), pandas.DataFrame(x2), on=0)
np.sum(np.min(merged.values[:,1:], axis=1))

That gives 4.0. The first two lines convert the strings to arrays of integers and runs itemfreq() to count how many times each character occurs. In this example, x1 is:

arrray([[  97.,    3.],
        [ 100.,    1.],
        [ 101.,    1.]])

Then we join the two tables by the 0th column, dropping any characters that do not exist in the other one:

     0  1_x  1_y
0   97    3    2
1  100    1    2
2  101    1    1

Then we just do a min and sum to get the final score (2+1+1 in this case).

0

Here is ;

list_a = list("aabbb")
list_b = list("bbbaa")

list_c = set(list_b)

counter = 0

for i in list_c:
    if i in list_b:
        counter = list_a.count(i)
        print "counter : %s  element : %s" %(counter,i )

I just wanna show how to count the common elements, you can change the code as summing the counter result.

1
  • I was using the Counter module to count them for me, it just slowed it way down.
    – Hoopdady
    May 23, 2014 at 14:01
0

here's a pretty simple solution using Counter:

def proc(vals):
    for s1, s2 in vals:
        c1, c2 = Counter(s1), Counter(s2)
        same = set(s1) & set(s2)
        print s1, s2, sum(min(c1[c], c2[c]) for c in same)

where vals looks like

vals = [('aaaaa', 'bbbbb'), ...]
3
  • I said that in the post. I tried it. Its way less efficient.
    – Hoopdady
    May 23, 2014 at 14:18
  • how big is your input?
    – acushner
    May 23, 2014 at 14:19
  • also, i read that you tried counter, but you said you also used guess and solution, and this is different from that. it could be that the guess and solution part is slow...
    – acushner
    May 23, 2014 at 14:21
0

Try this:

a, b = 'aaabb', 'ccaaa'

dict_a, dict_b = {}, {}

for key in list(a):
    dict_a[key] = dict_a.setdefault(key, 0) + 1

for key in list(b):
    dict_b[key] = dict_b.setdefault(key, 0) + 1

count = 0
for key, a_val in dict_a.items():
    try:
        b_val = dict_b[key]
        count += min(b_val, a_val)
    except KeyError:
        None

print count
0

Same concept as @sloth, but using try instead of if

def Score(guess, solution):
    solution = list(solution)
    c = 0
    for g in guess:
        try:
            solution.remove(g)
            c += 1
        except ValueError:
            pass

    return c        

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.