Algorithm Practice: Ransom Note walkthrough
If you’re starting out the exciting journey to become a software engineer, you may have heard from someone that you should start working on your algorithm skills. There is no question about it, anyone starting out who wants to make a dent in the industry will need to get their hands dirty and develop those problem solving skills.
I decided to start a series of blog posts where I can breakdown the algorithm practice I come across. These series of blog posts will be a great practice for me to review these algorithms, hone my pattern recognition and problem solving skills. I will do my best to go over each step of the problem. I will be transparent about the parts that confused me when I began coding and got me stuck (in some cases for days). I hope I can help you if you’ve been struggling with this specific problem or just want a walk-through.
I wanna be clear that I started out a while ago but my programming studies had to suffer a halt for a while, but I’m happy I was able to get back at it and attend to Flatiron School this year where I see myself being challenged and improving every day.
Sketch your logic and pseudocode
— DO NOT TYPE YET! —
If you’re itching to start typing, think twice.
It’s very important that the first thing you do before start typing any code on your screen is to think about your problem first. Think about what is being asked and write down the logic. Find a way to sketch the problem and remove the abstraction of the instructions given. It’s ok if you miss a thing or two when going over your logic. The most important thing is to lay out all the steps you think you will need to solve it and to internalize them so when you’re solving it you have a plan in your head (an image or a map) how to start.
This process is key. Maybe when syntax becomes second nature for us and we have worked with tons of algorithms we might be able to skip this step since we will be more familiar with more algorithm patterns. But for now, a pen/pencil and a paper are our best friends and what you will get you through that initial block of not knowing how to get started.
Note: It may occur to you that when you put your first strategy into code that your initial plan no longer seems the best way to solve it. So it’s fine if you need to get back a step or two and plan it out again. As beginners we’re learning the most important skill there is: problem solving. So let’s take our time for now.
- These notes above are from different algorithms I worked on. I couldn’t find the notebook I had the RansomNote one since whenever I fill my sketch notebooks I tend to throw them away.
- Sources: Check these out before moving on: The Learn Programming Channel, How to write pseudocode, Codecademy.
Problem Description:
The ransomNote algorithm will take 2 string parameters. The first parameter will be the note we want to create. The second parameter will be a random text where we will extract the words to create our note. The function will return true or false to indicate whether the note is possible or not.
Once we have mapped out our plan. We have something to get our feet wet.
Remember to work on your logic and pseudocode first.
Step 1:
// Define the function with the 2 expected parameters.function ransomNote(noteText, randomText) {// Do we have noteText?
console.log(noteText)// Do we have randomText?
console.log(randomText)}// Invoke the function and pass in the 2 arguments.
ransomNote(
"Flatiron School wont let me sleep","At Flatiron School we believe that everyone should have access to a quality education and a career they love. We do that through community, commitment, and transparency. It doesnt mean things will be easier, you will may lose some nights of sleep But let me tell you this, once you put the work there wont be anything you cant tackle in the future."
);
Let’s start out by defining our ransomNote function with the 2 parameters we need. Let’s invoke and pass in some arguments to our function at the bottom. Let’s console.log() our parameters within our function and check to see if we have them.
Step 2 :
function ransomNote(noteText, randomText) {
var noteTextArr = noteText.split(" ");
var randomTextArr = randomText.split(" "); //remember to console.log to see your new transformed data.
console.log(noteTextArr)
console.log(randomTextArr)
}
- Think about the arguments being passed into the function. We know those arguments are strings.
- We need those strings to be broken down into a simple data set so we can count how many words we have in each string. — What data type do we know that we can store each bit of information from these strings?
- Store each word in an array using the .split() built in method.
If we console.log we will see that we have:
[ 'Flatiron', 'School', 'wont', 'let', 'me', 'sleep' ]
[
'At', 'Flatiron', 'School', 'we',
'believe', 'that', 'everyone', 'should',
'have', 'access', 'to', 'a',
'quality', 'education', 'and', 'a',
'career', 'they', 'love', 'We',
'do', 'that', 'through', 'community,',
'commitment,', 'and', 'transparency', 'It',
'doesnt', 'mean', 'things', 'will',
'be', 'easier,', 'you', 'will',
'may', 'lose', 'some', 'nights',
'of', 'sleep', 'But', 'let',
'me', 'tell', 'you', 'this,',
'once', 'you', 'put', 'the',
'work', 'on', 'there', 'wont',
'be', 'anything', 'you', 'cant',
'tackle', 'in', 'the', 'future.'
]Great. We have all the words stored in an array. The first array at the top
[ ‘Flatiron’, ‘School’, ‘wont’, ‘let’, ‘me’, ‘sleep’ ]Is the string we want to create.
The second array:
[
'At', 'Flatiron', 'School', 'we',
'believe', 'that', 'everyone', 'should',
'have', 'access', 'to', 'a',
'quality', 'education', 'and', 'a',
'career', 'they', 'love', 'We',
'do', 'that', 'through', 'community,',
'commitment,', 'and', 'transparency', 'It',
'doesnt', 'mean', 'things', 'will',
'be', 'easier,', 'you', 'will',
'may', 'lose', 'some', 'nights',
'of', 'sleep', 'But', 'let',
'me', 'tell', 'you', 'this,',
'once', 'you', 'put', 'the',
'work', 'on', 'there', 'wont',
'be', 'anything', 'you', 'cant',
'tackle', 'in', 'the', 'future.'
]Is the given string where we need to find each one of the words we need to write the noteTextArr => “Flatiron School wont let me sleep”.
Step 3:
Let’s loop over each element (word) of our randomTextArr array:
function ransomNote(noteText, randomText) {
var noteTextArr = noteText.split(" ");
var randomTextArr = randomText.split(" ");
var wordCount = {}; // loop over the randomTextArr elements
randomTexArr.forEach(word => {
// console.log each element to see what we have
console.log(word)
})
}
Now let’s collect and count the number of words we have in the randomText array:
function ransomNote(noteText, randomText) {
var noteTextArr = noteText.split(" ");
var randomTextArr = randomText.split(" ");
var wordCount = {}; randomTextArr.forEach(word => {
if (!wordCount[word]) { // if we do not have that key,
// create a new key with the current word in the iteration
// and set it to 0 wordCount[word] = 0; } // increment the value of that key (word) by 1 wordCount[word]++; })
}
}
- Outside of the loop, we want to initialize an object where we will store our key/value pairs: wordCount. The keys will be each word in our randomTextArr array and the value of each key will be the many times we encounter that word in that array.
- Pay attention to our conditional statement. We want to check if that word is already a key in wordCount object. In our case, if it is NOT ( ! — bang operator — !wordCount[word]) a key we want to go inside that first block of our conditional statement where we will set that initial key to 0 (so it can be incremented on the second part of the conditional statement).
- On the second block of our conditional statement we will increment by 1 the key that has been set on the first block of the conditional statement — on step 2—
- Let’s look into our wordCount object:
console.log(wordCount) At: 1,
Flatiron: 1,
School: 1,
we: 1,
believe: 1,
that: 2,
everyone: 1,
should: 1,
have: 1,
access: 1,
to: 1,
a: 2,
quality: 1,
education: 1,
and: 2,
career: 1,
they: 1,
love: 1,
We: 1,
do: 1,
through: 1,
'community,': 1,
'commitment,': 1,
transparency: 1,
... we get the gist ...
Beautiful! We know how many of each word we have.
Now get up, stretch your legs and go get some water. If this is a little overwhelming it’s just because you’re not yet familiar with these patterns. If you can move on, go to the next step, otherwise, take a 3 minutes break. It will also help you internalize it. You’ve done great so far!
Step 4:
Let’s loop over each element (word) from our noteTextArr array.
noteTextArr.forEach(word => {
console.log(word)
})Let’s check it out…
Flatiron
School
wont
let
me
sleepGreat! We have them. The next step is to check in our wordCount object if we have enough of those words, if any, to build our ransom note.
Before putting into code let’s see what we want to happen with a concrete and simpler example:
The note we want: “I think I like you”
Random Text: “I will not tolerate this behavior mister. I do not like this. I think you should go now.”
It seems like we have all the words we need to build our note from that random text. Let’s count to make sure.
Yes! We have it all and for one of the words we have more than enough.
noteTextArr.forEach(word => {
if (wordCountObj[word]) { // if we have it, decrement that word count by one wordCountObj[word]--; } else {
// something else will happen
}
})
- The first condition will evaluate if we have that word as a key in our wordCount object.
- Inside the block of the first condition we will decrement the value of that key by 1.
- What about the rest? Let’s check what our problem says again:
…The function will return true or false to indicate whether the note is possible or not. — hmmm…
Well, since we’re optimistic people… Let’s assume our algorithm will always think we have enough.
var weHaveAllWords = true; // from this point on, unless you tell
// me otherwise. We have enough!noteTextArr.forEach(word => {
if (wordCountObj[word]) {
// if we have it, decrement that word count by one
wordCountObj[word]--; } else { // set variable to false if we can't find a word and return return weHaveAllWords = false; }
})
- weHaveAllWords variable will be a boolean set to true.
- On the second block of our conditional statement we will set weHaveAllWords to false if we cannot find one of the words and return it immediately, thus exiting that conditional statement.
But wait! What if we need more of the same word to build our note?
Step 5:
Note: I will not cover all edge cases on for this algorithm. This will be the only one I will be covering on this blog post.
var weHaveAllWords = true; // from this point on, unless you tell
// me otherwise. We have enough!noteTextArr.forEach(word => {
if (wordCountObj[word]) {
// if we have it, decrement that word count by one
wordCountObj[word]--; // before we exit this block of code.
// do we have at least 1 of this same key for another
// iteration?
if (wordCountObj[word] < 0) { // we have less than 0 for the value for our key (word)
// (not enough for another iteration)
// set variable to false and return
return weHaveAllWords = false; }} else {
// set variable to false if we can't find a word
return weHaveAllWords = false
}
})
- Decrement the value from the current key (word) in the wordCount object.
- Check to see if after decrementing the value of the current key, if we have at least 0 as a value for the current key in the wordCount object. If we do, we will skip the nested condition and continue to the next iteration. If we don’t, our nested condition will set the weHaveAllWords variable to false and return the boolean value of our ransomNote function.
— Transparency time
When I started, this edge case confused me. It’s simple now when I look at it, but I struggled for a while with that simple nested conditional statement.
Finally, we will just return our boolean variable.
return weHaveAllWords;If everything goes as planned and we exhaust our loop going over all of the elements of the noteTextArr array without any problems, we will exit our loop normally and the weHaveAllWords boolean variable declared in our function scope will be returned with the value of true.
We’re done — Thank you!
I hope I was able to help you see through this problem if you were stuck or simply gave you a better understanding of a few of the many patterns in algorithm problem solving. You’re not the only one learning, I really enjoy trying to breaking down these problems, reinforce and practice these patterns. Check out my other blog post here.
If you enjoyed this walkthrough and think someone could benefit from it, please share with a friend. Oh! since I have your attention, if you really liked it, give me a few thumbs up too.
— Thank you again :)
See full code bellow:
function ransomNote(noteText, randomText) { var noteText = noteText.split(" ");
var randomText = randomText.split(" ");
var wordCount = {}; randomText.forEach(word => { if (!wordCount[word]) {
wordCount[word] = 0;
}
wordCount[word]++;
}) var weHaveAllWords = true;
noteText.forEach(word => {
if (wordCount[word]) {
wordCount[word]--; if (wordCount[word] < 0) {
return weHaveAllWords = false;
}
} else {
return weHaveAllWords = false;
}
}) return weHaveAllWords;
}ransomNote("Flatiron School wont let me sleep","At Flatiron School we believe that everyone should have access to a quality education and a career they love We do that through community, commitment, and transparency It doesnt mean things will be easier, you will may lose some nights of sleep But let me tell you this, once you put the work on there wont be anything you cant tackle in the future.");
If you want more practice go over to freecodecamp and checkout their algorithms and data structures section.
