1
\$\begingroup\$

I'm working on a project to find anagrams of words. My goal is to figure out the longest anagrams out there. I took a look at my code and it works but is woefully inefficient.

I have two arrays, each containing a length of long words:

words_one = ["sarcocarcinomata", "dactylopteridae", "autoradiographic", "pterylographical",
"nonconversational", "pathophysiological"]

words_two = ["carcinosarcomata", "pterodactylidae", "radioautographic", "pterylographical", "nonconservational", "physiopathological"]

Most of these words have to do with science, so they're relatively long.

For what I'm working on, I would like to find if all of the word pairs are anagrams of each other. In my example above, they are.

def anagrams(words_one, words_two)
  x = 0
  while x < words_one.count
    if words_one[x].chars.to_a.permutation.include?(words_two[x].chars.to_a)
      puts 1
      x += 1
    else
      puts 0
      x += 1
    end
  end
end

There are several potential problems I see here:

  1. Permutation Method: This sorts through all permutations of a given string. Each letter can be one of 26 different characters. This adds up real quickly.
  2. While Loop: I'm not sure this is the most effective method.
  3. Duplicate Code: I put x+=1 in both sections of my if-else block.

I'd like to learn some new techniques to optimize Ruby code.

Which type of algorithm is my code and which type of algorithm do I need?

\$\endgroup\$
2
\$\begingroup\$

While the formulation Does any permutation of word A's letters match word B? is technically correct, it's also terribly impractical when implemented. As you yourself point out, there are a lot of permutations, and we're looking for just one.

A simpler formulation would be

Are the letters in word A the same as in word B?

Or, in code

word_a.chars.sort == word_b.chars.sort

That'll be a lot quicker.

Also, since you've got 2 arrays, and want to match one word from each at a time, you could use Array#zip to produce a single array of pairs, and loop that instead. You rarely need to deal with plain C-style loops or actual array indexes in Ruby, because you have all the methods from Enumerable. It's not that these are necessarily more efficient than old-school loops, it's that they are more expressive and much more idiomatic.

One of those Enumerable methods, by the way, is all? which simply checks if a block evaluates to non-false/non-nil for all items.

So for instance, you could do this:

def all_anagrams?(words_one, words_two)
  words_one.zip(words_two).all? do |word_a, word_b|
    word_a.chars.sort == word_b.chars.sort
  end
end

Basically: pair up the words from each array, and check if the words in each and every pair are anagrams of each other.

And yes, it returns true for the two arrays in your question.

Of course, it doesn't say much about what words (if any) aren't anagrams. If you want more feedback, you could look into using #detect to find the first pair that isn't anagrammatic (if no such pair is found, well, they are all anagrams). Or you could use #partition to divide the list of pairs into two lists: Those that are anagrammatic, and those that are not.

In any case, I'd recommend against printing anything in a method, unless it's stated purpose is indeed to print stuff. Much better to have more methods and combine their functionality, than have a few methods do many things.

Speaking of methods, the current name of your method, anagrams, doesn't quite say what it does. Does it return some random anagrams? Does it produce them based on input? Does it verify them? Typically, when a method just returns a boolean value, its name is suffixed with a ? in Ruby. Makes it nice and obvious that you can expect a yes/no answer.
I've tried for a slightly more descriptive name above with the all_anagrams? name (it isn't perfect either, though).

Oh, and yes, the duplication of x += 1 is problematic. You can just move it to appear after the if..else. It's doubly wise to do so here, since you'll have an infinite loop if x doesn't get incremented as expected. So it's better to at least have the increment happen in only 1 place, than to hope it happens in several, branching code paths.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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