Ransom Note and algorithms

A friend of mine called me and asked if I was able to solve a little algorithm challenge involving vanilla javascript.

There is a long time that didn't a javascript challenge, the last one was for a job technical test. With that I thought, why not?

He showed me the issue, we got a message by a paragraph written by a random person. Using all characters available on that message, we will check if is possible to create a ransom note.
​

Mussum's paragraph:

​

"""Mussum Ipsum, cacilds vidis litro abertis. Admodum accumsan disputationi eu sit. Vide electram sadipscing et per. Per aumento de cachacis, eu reclamis. Paisis, filhis, espiritis santis. Cevadis im ampola pa arma uma pindureta."""

Ransom note:

​

"Mussum Ipsum, cacilds vidis litro abertis. Mauris nec dolor in eros tempor."

Algorithm brainstorm and bench test

At the first moment, I misunderstood what the challenge asks for us to do. I thought that we had to check if in the paragraph there are all characters that we need to create the ransom note.

So for the first part to solve this I decide to create a set array for both messages.

const paragraph = "Mussum Ipsum, cacilds vidis litro abertis. Admodum accumsan disputationi eu sit. Vide electram sadipscing et per. Per aumento de cachacis, eu reclamis. Paisis, filhis, espiritis santis. Cevadis im ampola pa arma uma pindureta."

const ransomNote = "Mussum Ipsum, cacilds vidis litro abertis. Mauris nec dolor in eros tempor."

const paragraphSetArray = new Set([...paragraph])
const ransomNoteSetArray = new Set([...ransomNote])

const isCompile = [...ransomNoteSetArray].every(
  (character) => [...paragraphSetArray].includes(character)
);

console.log(isCompile) // True

Array.prototype.every() - Javascript

However, when I showed my solution to my friend, he said: Joao, unfortunately, you misunderstood the problem. In this case, we would like to check if is possible to compile this message, you forgot to look at the quantity of the characters.

Solving the first mistake and make others

With that, I noticed my mistake and I ask him if I could try again. He said yes. So let's go to try again.

Having this new information in mind, I thought to throw away the set arrays and try to convert the paragraph and ransom note messages from a string/characters array to an object. The character is the object key and the quantity is the character value.

// e.g.:
const message = 'a, a';
/*
{
 a: 2,
 "/s": 1,
 ",": 2,
}
*/

The first thought was to apply a reduce HOF on both strings to get the object that represents each character and their quantities.

const paragraphObject = [...paragraph].reduce((acc, cur) => {
 if (acc[cur]) {
   acc[cur] = acc[cur] + 1
 } else {
   acc[cur] = 1
 }
 return acc
}, {})

const ransomNoteObject = [...ransomNote].reduce((acc, cur) => {
 if (acc[cur]) {
   acc[cur] = acc[cur] + 1
 } else {
   acc[cur] = 1
 }
 return acc
}, {})

As a first development code, I wrote a not so pretty code - with some duplication - just to visualize how the algorithm on these two strings has the same action. After that, I did a test bench with two short strings to reproduce each step of the reduce function.

In order to be cleaner and unit-testable. I converted the reduce code to a function.

const convertArrayToObject = (array) => {
 return array.reduce((acc, cur) => {
  if (acc[cur]) {
    acc[cur] = acc[cur] + 1
  } else {
    acc[cur] = 1
  }
  return acc
 }, {})
}

The code so far is

const paragraph = "Mussum Ipsum, cacilds vidis litro abertis. Admodum accumsan disputationi eu sit. Vide electram sadipscing et per. Per aumento de cachacis, eu reclamis. Paisis, filhis, espiritis santis. Cevadis im ampola pa arma uma pindureta."

const ransomNote = "Mussum Ipsum, cacilds vidis litro abertis. mauris nec dolor in eros tempor."

const convertArrayToObject = (array) => {
 return array.reduce((acc, cur) => {
  if (acc[cur]) {
    acc[cur] = acc[cur] + 1
  } else {
    acc[cur] = 1
  }
  return acc
 }, {})
}

const paragraphObject = convertArrayToObject([...paragraph])

const ransomNoteObject = convertArrayToObject([...ransomNote])

What is missing is the validations that are possible to compile the ransom note. For that, I thought to work again with every to check on the ransomNoteObject entities if there is a corresponding element on paragraphObject and if both quantities are the same - second mistake.

const isCompiled = Object.entries(ransomNoteObject).every(([key, value]) => paragraphObject[key] === value)

return isCompiled; // False

In this case, always will return false because I'm checking only with the quantity are the same, not if the paragraphObject has that key with a value greater or equal than ransomNoteObject key value.

So, a few moments later, I realized what was wrong with my friend and I corrected that part on the code.

const isCompiled = Object.entries(ransomNoteObject).every(([key, value]) => paragraphObject[key] >= value)

return isCompiled // Possible to be True

With that last lines of code, I was confident that I covered all the parts of this test. So I presented the code to my friend, and he with just one question broke my application: if my paragraph has fewer characters than the ransom note we need to run all of these lines of code?

Sometimes we only look at how to solve the big problem and run to the code to test what we are thinking but we don't ask the real question or see the premises of the problem.

A little bit of shame, I came back to my code and add the condition.

if (Object.keys(ransomNoteObject) > Object.keys(paragraphObject)) {
  return false
}

Final Solution

Thus, the code prettier could be something like this:

const paragraph = "Mussum Ipsum, cacilds vidis litro abertis. Admodum accumsan disputationi eu sit. Vide electram sadipscing et per. Per aumento de cachacis, eu reclamis. Paisis, filhis, espiritis santis. Cevadis im ampola pa arma uma pindureta."

const ransomNote = "Mussum Ipsum, cacilds vidis litro abertis. mauris nec dolor in eros tempor."

const convertArrayToObject = (array) => {
 return array.reduce((acc, cur) => {
  if (acc[cur]) {
    acc[cur] = acc[cur] + 1
  } else {
    acc[cur] = 1
  }
  return acc
 }, {})
}

const paragraphObject = convertArrayToObject([...paragraph])

const ransomNoteObject = convertArrayToObject([...ransomNote])

const checkRansomNoteCompiled = () => {
  if (Object.keys(ransomNoteObject).lenght > Object.keys(paragraphObject).lenght){
   return false
  }
  return Object.entries(ransomNoteObject).every(([key, value]) => paragraphObject[key] >= value)
}

checkRansomNoteCompiled()

I hope that you enjoyed my code adventure!

If you liked, please write down on the comments below another algorithm that's you think is nice to try to study :D