CODEWITHSUNDEEP
pythonpython-3.x
luka'0
luka'0

Reputation: 19

Given two lists of strings, how do I match them up so that as many as possible are identical?

I'm trying to solve this Kattis problem Judging Troubles, in Python. The problem boils down to counting how many times I can match up two items, one from each list, so that they are identical.

Sample Input:

list_1 = ['correct', 'wronganswer', 'correct', 'correct', 'timelimit']
list_2 = ['wronganswer', 'correct', 'timelimit', 'correct', 'timelimit'],

Sample Output:

4

I tried solving it in these two ways, but they both exceeded the time limit.

result = 0
for el in list_1:
    if el in list_2:
        result += 1
        list_2.remove(el)
print(result)

result = 0
for el in set(list_1):
    result += min(list_1.count(el), list_2.count(el))
print(result)

Any suggestions on how to shorten the processing time?

Upvotes: 0

Views: 119

Answers (4)

Axe319
Axe319

Reputation: 4365

There are plenty of good answers already but here's my twist on it, using a defaultdict.

from collections import defaultdict

data = [5,
        'correct',
        'wronganswer',
        'correct',
        'correct',
        'timelimit',
        'wronganswer',
        'correct',
        'timelimit',
        'correct',
        'timelimit']

instances = data[0]
dom = defaultdict(int)

for entry in data[instances + 1:]:
    dom[entry] += 1

pairs = 0
for entry in data[1:instances + 1]:
    if dom[entry]:
        dom[entry] -= 1
        pairs += 1

print(pairs)

Upvotes: 1

Shubham Shaswat
Shubham Shaswat

Reputation: 1310

Try this:

based on dictionary and the keys is compared again with next n inputs and values is decremented if the keys is found and added to the result output s

n = int(input())

d={}
for _ in range(n):
   x = input()
   try:
       d[x] +=1
   except KeyError:
       d[x] = 1

s=0   
for _ in range(n):

    x=input()

    try:
        if d[x] != 0:
            s+=1
            d[x] -= 1

    except KeyError:
        pass
print(s)

Upvotes: 2

smassey
smassey

Reputation: 5931

@Alain beat me to it, but indeed, Counter was my solution as well:

import sys
from collections import Counter

count = 0
counter_a = Counter()
counter_b = Counter()
for i, line in enumerate(sys.stdin):
    line = line.strip()
    if not i:
        count = int(line)
        continue
    if i > count:
        counter_b[line] += 1
    else:
        counter_a[line] += 1

result = 0
for line, counter_a_count in counter_a.items():
    if line in counter_b:
        result += min(counter_a_count, counter_b[line])

print(result)

I believe his would be faster too, but this was "fast enough" :)

Upvotes: 0

Alain T.
Alain T.

Reputation: 42143

You can solve this easily with the Counter class from collections. Create a Counter object for each of the result set. The maximum number of matches for each result value is the minimum count between the two. Add those up to get the total maximum:

data = """5
correct
wronganswer
correct
correct
timelimit
wronganswer
correct
timelimit
correct
timelimit"""

lines         = data.split("\n")
count         = int(lines[0])
DOMResults    = lines[1:count+1]
KattisResults = lines[count+1:]

from collections import Counter
DOMCounts    = Counter(DOMResults)
KattisCounts = Counter(KattisResults)
matches = sum(min(KattisCounts[r],c) for r,c in DOMCounts.items())
print("matches:",matches)

# matches: 4

Upvotes: 2

Related Questions