Right Tool, Right Problem

So there is an old adage which I will paraphrase: "If the only tool you have is a hammer, every problem looks like a nail". I was reminded of this recently when going through a simple exercise of building solutions for the "Ransom Note" problem. Essentially you're just given two strings, one represents a ransom note and the other the source (such as a book or newspaper) from which the note is constructed. The problem is to determine whether or not the note can be constructed from the characters within the source material. Basically it's what you see on old movies or TV shows where the criminal cuts out letters from a newspaper and constructs a ransom note from them so as not to reveal his identity through his handwriting. In the case of Sherlock Holmes, it doesn't help a whole lot since he seems to be able to deduce the publication and the specific edition just based on the newsprint and then go on determine, based on the phrasing, the age, gender, height, weight, and place of origin of the perpetrator! But for normal humans the note remains, for all intents and purposes, anonymous.

The point being, that because the problem is couched in terms of physical texts, each letter from the source material can only be used once in the target note. From a programming standpoint, there are many ways to solve this problem and I do not mean to imply that the approach I'm about to outline is the most efficient either in time or space complexity; however, it did bring to my mind that old saying about the hammer and the nail. The idea is this, if I can construct an collection of the characters in each string, I could simply subtract the source material collection from the note collection and if the result was an empty collection, then all he netters in the note would be accounted for in the source. Then the question is, how to I represent this collection in a specific language. I tried building my solutions in two different languages: Ruby and Elixir.

Using Ruby, the first inclination is to represent the collection as an array; but this has an obvious flaw. When you subtract arrays in Ruby, every occurrence of an entry in the left-hand array side is removed if even a single occurrence of that entry appears in the right-hand array. So the frequency of occurrence is not factored into the operation. For example:

[1, 1, 2, 3, 4] - [1 ,2] => [3, 4]        

So this approach in Ruby would not solve the problem. As I said before there are a lot of other approaches to take that will solve this problem (e.g., frequency counting, iteration with modification, etc) but this specific approach will not work.

Then I came to Elixir (which I've been recently learning) and I came across this in this in the section hat outlined lists and tuples:

iex> [1, 2, 3] ++ [4, 5, 6]
[1, 2, 3, 4, 5, 6]
iex> [1, true, 2, false, 3, true] -- [true, false]
[1, 2, 3, true]        

and I saw that Lists in elixir behave differently to arrays in Ruby. The List difference algorithm in Elixir only removes each separate occurrence of the entry between the source and target. So a simple List difference calculation can be used to solve the ransom note problem:

def can_construct(ransom_note, source) do
  ransom_note_chars = String.to_charlist(ransom_note)
  source_chars = String.to_charlist(source)
  length(ransom_note_chars -- source_chars) == 0
end        

Now this is a pretty trivial example, but It reinforced in my mind the benefits of "expanding your toolbox" so that you when you are confronted with a particular problem, you may be able to pull out a tool that is more appropriate the problem. Which is another way of saying: understand the problem first as best you can, understand the tools available that can be used to solve the problem (as best you can), and then choose the tool that best meets the need.