Debugging a Sorting Algorithm in Ruby-CodePudding

I'm learning to code and just finished writing a method that would sort strings into subsets of anagrams and return an array containing these subsets as subarrays. The original writing of the strings should be preserved.

My code passed the test provided by the bootcamp, but further testing revealed a glitch: in certain combinations a value that would shift to last position would then not be added to the respective subarray.

I've retraced the logic of my code several times but am failing to see why this is the case.

I'm looking to understand where the glitch is coming from in my method, so, if you can help me learn, please do! Thanks in advance! :)

Here's the glitch as screenshot (values: 'creams', 'SCREAM', 'scream')

And the code itself:

test = ['cars', 'for', 'POTATOES', 'racs', 'four', 'scar', 'creams', 'SCREAM', 'scream']

# separate method for sorting
def sorted(word)
  word.downcase.chars.sort.join
end

def group_anagrams(words)
  result = []
  while words.length.positive?
    # use the first word as reference
    reference = [words.shift]
    # loop through the array looking for a match
    words.each do |word|
      # if match is found, add it to reference array and delete it from words
      reference << words.delete(word) if sorted(reference[0]) == sorted(word)
    end
    # when done, add reference array to result
    result << reference
  end
  result
end

p group_anagrams(test)

CodePudding user response：

The problem is at the call to the delete function. You're iterating over the words array but inside the each block words.delete changes the length of the array. You shouldn't mutate the array while you're iterating over it.

CodePudding user response：

I think you code failed because you were deleting elements from words while simultaneously iterating through that array. Here's a slight modification of your code which works fine:

def group_anagrams(words)
  words = words.dup
  result = []
  while !words.empty?
    reference = [words.shift]
    words.each do |word|
      reference << word if sorted(reference[0]) == sorted(word)
    end
    words -= reference
    result << reference
  end
  result
end

However, please note that for a large list of words, your algorithm will be O(N²), and it is much more complicated than it needs to be, so I would not recommend using it in practice.

You can use a hash table to speed things up:

def group_anagrams2(words)
  hash = {}
  words.each do |word|
    (hash[word.downcase.chars.sort] ||= []) << word
  end
  hash.values
end

However, you don't even have to write all that code yourself. You can just replace all of the code above with this:

grouped_words = words.group_by { |w| w.downcase.chars.sort }.values