Image courtesy of Sheila Sund from Salem, United States, CC BY 2.0, via Wikimedia Commons.
This Python programming challenge is adapted from a challenge on HackerRank called Ransom Note, which is part of a collection involving hash tables. If you are unfamiliar with HackerRank, you can read about it here: Introduction to HackerRank for Python Programmers.
The problem descriptions on HackerRank are sometimes a bit obscure, and one of the skills you need to develop to solve the challenges is the ability to work out exactly what is being asked. Sometimes it’s easier to go straight for the input/output required to get a feel for what is required, and then read the description to see how it leads to the problem specification.
The basic idea with the Ransom Note challenge is that you have two lists of values, and you need to determine if one list can be formed from elements in the other list.
For example thinking of sentences as lists of words,
give me one grand today night contains give one grand today, so the answer is Yes
whereas for two times three is not four containing two times two is four, the answer is No, as although all the words are present in the second list, there are not enough instances of the word two.
Make sense?
Have a go for yourself now. At this stage, don’t worry about the efficiency of your solution – instead just go for a brute force approach to get a feel for the problem.
Here’s a stub and some tests to get you started. The goal is to complete the checkMagazine() function to get the tests to pass. With assert tests, you will know they have passed if you run your code and get no AssertionError – i.e. nothing happens. This is good.
Note that in the problem on HackerRank, the answer is printed as Yes or No rather than returned as a Boolean.
def checkMagazine(magazine, note):
pass
magazine = "give me one grand today night".split()
note = "give one grand today".split()
assert checkMagazine(magazine, note) is True
magazine = "two times three is not four".split()
note = "two times two is four".split()
assert checkMagazine(magazine, note) is False
Brute Force Solution to Ransom Note Python Challenge
Here’s my original attempt. Can you see what my thinking was? I tried to remove each item in note from message, but if this raised an exception, I set the return value to False.
def checkMagazine(magazine, note):
for word in note:
try:
del magazine[magazine.index(word)]
except Exception as e:
return False
return True
magazine = "give me one grand today night".split()
note = "give one grand today".split()
assert checkMagazine(magazine, note) is True
magazine = "two times three is not four".split()
note = "two times two is four".split()
assert checkMagazine(magazine, note) is False
Python Counters
The solution above, and likely many other brute force solutions, passes most of the tests on HackerRank, but there are a few where it times out. We need to do better.
There is a big hint in the fact that this challenge occurs in a collection abut hash tables. In Python this means we are probably going to use a dictionary. However, since this dictionary will contain counts of the various words in our lists, it makes sense to use the specialised dictionary type available in Python called Counter.
You can see a Python Counter in action in the following example:
from collections import Counter
note = "give one grand today".split()
note_counter = Counter(note)
print(note_counter)
If for any reason using a specialised tool such as collections.Counter if forbidden (e.g. you are studying a syllabus which doesn’t encourage “that kind of thing”), you can create a counter dictionary manually by doing something like this:
magazine = "give me one grand today night".split()
freq = {}
for word in magazine:
if word in freq:
freq[word] += 1
else:
freq[word] = 1
print(freq)
Solution to Ransom Note Challenge in Python
One final piece you might find helpful in writing an efficient solution to the Ransom Note challenge is the intersection operator as in Counter(a) & Counter(b). This returns the minimum of corresponding counts.
With all that at your disposal, have a good attempt at the problem for yourself not, either using the stub and tests from above, or on the HackerRank site. Good luck.
My solution is below for reference when you are ready.
In this post we have looked at the Ransom Note challenge from HackerRank, and how to solve it with Python. I hope you found it interesting and helpful.
Happy computing!