0
\$\begingroup\$

This is a website Question on Hackrrank called Hash Tables: Ransom Note:

Given the words in the magazine and the words in the ransom note, print "Yes" if we can replicate the ransom note exactly using whole words from the magazine; otherwise, print "No".

Here is an example input:

6 4
give me one grand today night
give one grand today

Output: Yes

And another:

6 5
two times three is not four
two times two is four

Output: No


def checkMagazine(magazine, note):

    #Creating 2 Empty Dictionaries for the "Magazine" and the "Note" then filling them up
    UniqueWordsMag = set(magazine)
    UniqueCountMag = [0]*len(UniqueWordsMag)
    UniqueWordDictMag = dict(zip(UniqueWordsMag, UniqueCountMag))

    UniqueWordsNote= set(note)
    UniqueCountNote = [0]*len(UniqueWordsNote)
    UniqueWordDictNote = dict(zip(UniqueWordsNote, UniqueCountNote))

    for i in magazine:
        if i in list(UniqueWordDictMag.keys()):
            UniqueWordDictMag[i] += 1

    for i in note:
        if i in list(UniqueWordDictNote.keys()):
            UniqueWordDictNote[i] += 1


    #Checking for existance in the magazine then checking for the correct count, print no if it does not fulfil conditions
    Success = False
    DesiredCount = len(note)
    Count = 0

    for index,i in enumerate(UniqueWordsNote):
        if i in list(UniqueWordDictMag.keys()):
            if UniqueWordDictNote[i] <= UniqueWordDictMag[i]:
                Count += UniqueWordDictNote[i]
            else:
                break
        else:
            break

    if Count == DesiredCount:
        Success = True
        print("Yes")
    else:
        print("No")

It's called from this main program, that's provided by the challenge:

def main():
    mn = input().split()

    m = int(mn[0])

    n = int(mn[1])

    magazine = input().rstrip().split()

    note = input().rstrip().split()

    checkMagazine(magazine, note)

if __name__ == "__main__":
    main()

My code is currently taking too long on some lists (e.g. lists of size 30,000 or more). Are there any optimisations I can make to make this a bit more legible and faster?

\$\endgroup\$
2
  • \$\begingroup\$ Please link to the problem. \$\endgroup\$
    – Manuel
    Mar 12 '21 at 19:44
  • \$\begingroup\$ Check out PEP 8, the Python style guide, especially the suggestion to use snake_case instead of camelCase. \$\endgroup\$ Mar 13 '21 at 10:29
4
\$\begingroup\$

You're making it enormously complicated. This is a job for Counter:

from collections import Counter

def checkMagazine(magazine, note):
    print('No' if Counter(note) - Counter(magazine) else 'Yes')
\$\endgroup\$
3
  • \$\begingroup\$ I can't find where collections.Counter is documented to evaluate false if any element is negative. Please could you enlighten me? It does seem a very useful property. \$\endgroup\$ Mar 13 '21 at 8:56
  • 1
    \$\begingroup\$ @TobySpeight That's not really what happens. As the doc says about the - operation: "the output will exclude results with counts of zero or less". So my difference Counter doesn't have negatives. I think a Counter is false for the standard reason: being empty. What I really check is whether there are any positives. That is, whether any words needed for the note remain unaccounted for after discounting by the magazine words. \$\endgroup\$
    – Manuel
    Mar 13 '21 at 9:46
  • \$\begingroup\$ Thanks for the explanation; I understand it better now. I'm not so fluent in Python, so didn't recognise the idiom! \$\endgroup\$ Mar 13 '21 at 10:13
2
\$\begingroup\$

You should use Counter, but even for not using Counter you made it very complicated. Doing it with dict and keeping your structure, you could do this:

def checkMagazine(magazine, note):
    
    mag_ctr = dict.fromkeys(magazine, 0)
    note_ctr = dict.fromkeys(note, 0)
    
    for word in magazine:
        mag_ctr[word] += 1
    
    for word in note:
        note_ctr[word] += 1
    
    for word in note_ctr:
        if note_ctr[word] > mag_ctr.get(word, 0):
            print('No')
            break
    else:
        print('Yes')

Just for fun, while I'm here... this trivial solution also got accepted despite being slow:

def checkMagazine(magazine, note):
    try:
        for word in note:
            magazine.remove(word)
        print('Yes')
    except:
        print('No')

I like it because it's simple. We can do a similar but fast one by using a Counter for the magazine (none needed for the note, saving memory compared to two Counters):

def checkMagazine(magazine, note):
    available = Counter(magazine)
    for word in note:
        if not available[word]:
            print('No')
            break
        available[word] -= 1
    else:
        print('Yes')
\$\endgroup\$
1
\$\begingroup\$

Counting the number of occurrences of an item already exists in the list.count(item) function. To continue with the approach of jumping out of code as soon as possible with your break out of a for loop, we can use a generator inside an any evaluation like so:

def check_magazine(magazine, note):
    print("No" if any(note.count(word) > magazine.count(word) for word in set(note)) else "Yes")
\$\endgroup\$
0
\$\begingroup\$

Instead of:

for i in magazine:
        if i in list(UniqueWordDictMag.keys()):
            UniqueWordDictMag[i] += 1

    for i in note:
        if i in list(UniqueWordDictNote.keys()):
            UniqueWordDictNote[i] += 1

Avoid creating a list and just iterate over the keys

for i in magazine:
        if i in UniqueWordDictMag.keys():
            UniqueWordDictMag[i] += 1

    for i in note:
        if i in UniqueWordDictNote.keys():
            UniqueWordDictNote[i] += 1
\$\endgroup\$
2
  • \$\begingroup\$ No need for .keys(), either. \$\endgroup\$
    – Manuel
    Mar 12 '21 at 19:59
  • 1
    \$\begingroup\$ Actually the entire condition is unneeded. You know that i is in there. \$\endgroup\$
    – Manuel
    Mar 12 '21 at 20:15
0
\$\begingroup\$

General (non-performance) review:

There are several variables assigned but never used. For example:

    mn = input().split()
    m = int(mn[0])
    n = int(mn[1])

We never use m or n, so this can just be replaced by

    input()

(I later discovered that main() was provided by the challenge, so you're not to blame for this. OTOH, there's nothing to stop you improving the boilerplate you were given!)

Similarly:

    Success = True
    print("Yes")

Success is never used; just remove it.

As noted elsewhere,

#Creating 2 Empty Dictionaries for the "Magazine" and the "Note" then filling them up
UniqueWordsMag = set(magazine)
UniqueCountMag = [0]*len(UniqueWordsMag)
UniqueWordDictMag = dict(zip(UniqueWordsMag, UniqueCountMag))

UniqueWordsNote= set(note)
UniqueCountNote = [0]*len(UniqueWordsNote)
UniqueWordDictNote = dict(zip(UniqueWordsNote, UniqueCountNote))

for i in magazine:
    if i in list(UniqueWordDictMag.keys()):
        UniqueWordDictMag[i] += 1

for i in note:
    if i in list(UniqueWordDictNote.keys()):
        UniqueWordDictNote[i] += 1

is much simpler using a Counter:

import collections
magazine_words = collections.Counter(magazine)
note_words = collections.Counter(note)

And the test

#Checking for existance in the magazine then checking for the correct count, print no if it does not fulfil conditions
Success = False
DesiredCount = len(note)
Count = 0

for index,i in enumerate(UniqueWordsNote):
    if i in list(UniqueWordDictMag.keys()):
        if UniqueWordDictNote[i] <= UniqueWordDictMag[i]:
            Count += UniqueWordDictNote[i]
        else:
            break
    else:
        break

if Count == DesiredCount:

reduces to just

if magazine_words & note_words == note_words:
\$\endgroup\$
4
  • \$\begingroup\$ That m/n part is kinda not their fault, you're reviewing the site's code there, not the OP's. \$\endgroup\$
    – Manuel
    Mar 12 '21 at 20:35
  • \$\begingroup\$ Ah, that wasn't clear in the question (and I don't follow links to read specs, as questions should be self-contained). And I was going to praise the correct use of a main guard, too! Is everything from def main: onwards not OP code then? \$\endgroup\$ Mar 13 '21 at 8:22
  • \$\begingroup\$ Ha, that praise would've been funny. Yes, only the body of the checkMagazine function is the OP's (the def-line is provided by the site, too). \$\endgroup\$
    – Manuel
    Mar 13 '21 at 8:26
  • \$\begingroup\$ Oops actually I might be slightly wrong there. At least at the URL I found (you can close the login dialog by clicking the X or pressing escape), the given code is not in a main function but just inside a guard. I wish the people would just link to the sources, sigh. Anyway, I think your edit is alright. \$\endgroup\$
    – Manuel
    Mar 13 '21 at 9:19

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.