8
\$\begingroup\$

I have solved the Ransom Note challenge on HackerRank using JavaScript / ECMAScript 6. The challenge goes like this:

A kidnapper wrote a ransom note but is worried it will be traced back to him. He found a magazine and wants to know if he can cut out whole words from it and use them to create an untraceable replica of his ransom note. The words in his note are case-sensitive and he must use whole words available in the magazine, meaning he cannot use substrings or concatenation to create the words he needs.

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

Input Format

The first line contains two space-separated integers describing the respective values of (the number of words in the magazine) and (the number of words in the ransom note).

The second line contains space-separated strings denoting the words present in the magazine.

The third line contains space-separated strings denoting the words present in the ransom note.

My solution uses JavaScript Map objects (as suggested by the name of the challenge) and passes all tests with no timeouts. However, the solution itself is very literal, as in, it removes out each word in the ransom note from the magazine, unless the needed word is not available.

Note that the portion of code above ignore above this line is included with all challenges on the site, I left it in for the sake of completeness, so that anyone can copy-paste the whole block into the challenge page, if they wish.

process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
    input_stdin += data;
});

process.stdin.on('end', function () {
    input_stdin_array = input_stdin.split("\n");
    main();    
});

function readLine() {
    return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////

const addValueOrIncrementCount = (value, map) => {
    let count = map.get(value)
    if (count) {
        map.set(value, ++count)
    } else {
        map.set(value, 1)
    }
    return count
}

const decrementCountIfPossible = (value, map) => {
    let count = map.get(value)
    if (!count) {
        return null
    } else {
        map.set(value, --count)
        return count
    }
}

const mapWordCounts = inputString => {
    const output = new Map()
    let occurrences
    for (let word of inputString.split(" ")) {
        addValueOrIncrementCount(word, output)
    }
    return output
}

const isRansomComposedFromMagazine = (ransom, magazine) => {
    const ransomMap = mapWordCounts(ransom)
    const magazineMap = mapWordCounts(magazine)
    let ransomWordFromMagazine
    for (let [word, count] of ransomMap.entries()) {
        while (count > 0) {
            ransomWordFromMagazine = decrementCountIfPossible(word, magazineMap)
            if (ransomWordFromMagazine === null) {
                return false
            }
            count--
        }
    }
    return true
}

const getProgramInput = () => {
    const firstLine = readLine().split(' ')
    const magazineWordCount = parseInt(firstLine[0])
    const ransomWordCount = parseInt(firstLine[1])
    const magazine = readLine()
    const ransom = readLine()
    return {
        magazineWordCount: magazineWordCount,
        ransomWordCount: ransomWordCount,
        magazine: magazine,
        ransom: ransom
    }
}

const main = () => {
    const input = getProgramInput()
    console.log(isRansomComposedFromMagazine(input.ransom, input.magazine) ? "Yes" : "No")
}
\$\endgroup\$
2
  • \$\begingroup\$ Related question \$\endgroup\$
    – Flambino
    Mar 24, 2017 at 20:01
  • \$\begingroup\$ The while (count > 0) loop seems unnecessary. Why not just add a count parameter to decrementIfPossible? I notice that you don't use semi-colons at all. Although not a requirement I would recommend that you do - there are enough cases where this will cause you problems. \$\endgroup\$ Mar 24, 2017 at 22:45

3 Answers 3

4
\$\begingroup\$

I think that generally the approach is solid, however there is certainly room for performance/memory optimization (Hint - the input variables are given to you in a specific order for a specific reason).

Some examples:

  • I would only read the first line of input and quickly compare magazine word count vs. ransom note word count. If ransom note count exceeds magazine count you can immediately return no. You could also pick up edge case of 0 0 here for immediate return of no.
  • I would then parse the magazine input into a map of similar structure to what you currently have. The only difference I might take is to conserve memory (as one might be concerned with when talking about a potentially sizable magazine) by not reading the whole line into an array first. You might instead parse the input one substring at a time along space boundaries, building your map as you chunk through the string.
  • When completed with the magazine map, you could start up with parsing through the ransom note input. Here again, rather than reading the whole thing into first an array and then a map structure, you can conserve memory by gobbling up one substring at a time and comparing against the magazine map one by one.

So for rough max memory utilization comparison (ignoring word counts which are trivial).

You current solution:

Magazine memory - 3x input string size (input string + array + map)
Note memory = 3x input string size (input string + array + map)

vs. proposed optimization:

Magazine memory - 2x input string size (input string + map)
Note memory - 1x input size (input string only)

You could, in your current solution, even shave some memory utilization, in that you could discard the input strings once you read them into arrays, meaning you could get to 2x max memory utilization for both dictionaries. Of course you still spend processor time reading the strings into arrays.

\$\endgroup\$
4
  • \$\begingroup\$ Re: reading the input one word at a time, that would essentially be an input stream, correct? \$\endgroup\$
    – Phrancis
    Mar 24, 2017 at 18:35
  • 1
    \$\begingroup\$ @Phrancis You would in essence be treating much as you would an input stream, but given the fact that you are given the readline() as the input mechanism for the challenge, you don't really get to work with the input data as you truly would a stream, so you can't really optimize out the memory utilization of storing the full input strings. \$\endgroup\$
    – Mike Brant
    Mar 24, 2017 at 18:40
  • \$\begingroup\$ Given that the magazine is likely to contain far more words than the note, if you are trying to optimize for memory consumption (or performance, since looping through a list of words is O(n) and building a map of them is slightly above that), it's probably better to do it the other way around. \$\endgroup\$
    – Tgr
    Mar 24, 2017 at 19:45
  • \$\begingroup\$ @Tgr Good point. You should consider adding as additional answer. In either solution you would need to parse the entire magazine string in worst case, through you could exit early using your suggested approach if you decremented word counters from initial input and got to a point where you had parsed through enough magazine words without making matches against the note map to where you know you can not fulfill the note. \$\endgroup\$
    – Mike Brant
    Mar 24, 2017 at 22:00
4
\$\begingroup\$

This code reads like a story, very nice, though at times a bit verbose.

The value returned from addValueOrIncrementCount is never used, so you could drop the return statement.

decrementCountIfPossible returns a count, or null if the count cannot be decremented. It would be simpler and more natural to use if it returned boolean, because the returned count is not used anyway.

In mapWordCounts the variable occurrences is declared but never used.

Note that the map of word counts for ransomMap is not really necessary. It's possible to simply loop over the words, updating the magazineMap, and return false whenever the magazineMap doesn't have the required word.

You could use the || operator to simplify addValueOrIncrementCount:

const addValueOrIncrementCount = (value, map) => {
    map.set(value, 1 + (map.get(value) || 0))
}
\$\endgroup\$
4
\$\begingroup\$

Your code is definitely easy to follow, but I do feel there's too much of it. I reviewed a similar question, and provided a pretty basic solution there, but to do yours justice, I'll stick to using Map, but I'll still pare the code way down.

Essentially, I just believe you're being overly verbose. Still, I like the care you've taken.

Here, I've chosen to model the "magazine vocabulary" as a class. I'm assuming your readLine() function is still there:

// A simple class for storing words and the their number of occurrences
class MagazineVocabulary {
  constructor() {
    this.map = new Map;
  }

  // adds a new word, or increments the number of occurrences for an existing one
  add(word) {
    this.map.set(word, this.occurrencesOf(word) + 1);
  }

  // removes a word or decrements its number of occurrences
  // returns true if the word could be removed/decremented, false otherwise
  remove(word) {
    const occurrences = this.occurrencesOf(word);

    if(!occurrences) {
      return false;
    }

    this.map.set(word, this.occurrencesOf(word) - 1);
    return true;
  }

  // get a word's occurrence count
  occurrencesOf(word) {
    return this.map.get(word) || 0;
  }
}

readLine(); // eat first line

// build vocabulary
const vocabulary = new MagazineVocabulary;
readLine().split(' ').forEach(vocabulary.add.bind(vocabulary));

// check ransom note against vocabulary
const result = readLine().split(' ').every(vocabulary.remove.bind(vocabulary));

console.log(result ? "Yes" : "No")
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I like the OOP approach, I thought of it also afterwards, very nice \$\endgroup\$
    – Phrancis
    Mar 24, 2017 at 22:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.