4
\$\begingroup\$

Basically, this code takes a keyword and an array of strings, then sorts them based on two things: the number of characters shared with the key, and the distance between them.(As a side note, would this properly be called a sort, not a search?)

def search(key, list)
  # Format for everything pushed to out:
  # Should this be a class?    
  # { 
  #   val: the string in question, 
  #   shared_chars: [{char: shared char of key list elem, 
  #                   index: index of shared char,
  #                   kindex: index of shared char in key
  #                   distance: how close the shared chars are}]
  # }
  out = []
  key = key.downcase

  list.each { |l|
    l.downcase!
    shared_chars = []

    keyi = 0
    key.each_char { |c|
      index = /#{c}/ =~ l

      if index != nil
        shared_chars.push char: c, index: index, kindex: keyi
      end

      # Inelegant?
      keyi += 1
    }

    # Calulate total distance between shared_chars
    distance = 0
    odistance = 0

    shared_chars.each_index { |i|
      unless i == shared_chars.length-1
        distance += (shared_chars[i+1][:index] - shared_chars[i][:index]).abs
        odistance += (shared_chars[i+1][:kindex] - shared_chars[i][:kindex]).abs 
      end
    }

    distance -= odistance
    distance = distance.abs

    out.push val: l, shared_chars: shared_chars, distance: distance
  }

  out.sort_by! { |e|
    # 100 is arbitrary
    100 + e[:distance] - e[:shared_chars].length*3
  }

  out
end

Specifically I would like to know if any part of it could be made more efficient and/or elegant, but general critique is of course welcome.

\$\endgroup\$
6
\$\begingroup\$
  • Blocks longer than one line are conventionally written using doend rather than braces.
  • Code of the form

    out = []
    list.each { |l| ... out.push(something) }
    

    … would be better expressed as

    out = list.collect { |l| something }
    

    Besides being slightly more compact, there is a subtle difference in thinking: the former feels like "do this, then this, then this to build a result"; the latter says "transform each element like this", and it's easier to see that there is a one-to-one correspondence between input elements and output elements.

  • Within that block,

    out = list.collect do |l|
      # Calling l.downcase! would have the side-effect of modifying
      # strings in the original list, which is impolite.
      l = l.downcase
    
      shared_chars = []
      key.split.each_with_index do |c, keyi|
        index = l.index(c)
        # Actually, char:c is never used and could be eliminated
        shared_chars.push(char: c, index: index, kindex: keyi) if index
      end
    
      distance, kdistance = 0, 0
      shared_chars.each_cons(2) do |a, b|
        distance += (b[:index] - a[:index]).abs
        kdistance += (b[:kindex] - a[:kindex]).abs
      end
    
      { val: l, shared_chars: shared_chars, distance: (distance - odistance).abs }
    end
    
  • Furthermore,

    out.sort_by! { |e| ... }
    out
    

    could just be

    out.sort_by { |e| ... }
    

    (.sort_by is defined because an Array is an Enumerable.)

  • I think that the whole function would be better as one chained expression:

    def search(key, list)
      key = key.downcase
    
      list.collect do |l|
        ...
      end.sort_by do |e|
        # There's no point in adding 100 to each element
        e[:distance] - 3 * e[:shared_chars].length
      end
    end
    
\$\endgroup\$
  • \$\begingroup\$ Excellent answer. Note that the bad indentation only happened when I pasted to stackexchange \$\endgroup\$ – starscape Dec 23 '13 at 19:16
  • \$\begingroup\$ do ... end can make problems because of operator precedence. \$\endgroup\$ – Nakilon Dec 24 '13 at 12:05
  • \$\begingroup\$ @Nakilon As can {....}. The difference in precedence between do...end and {...} matters mostly in internal DSLs, where parentheses are, by convention, frequently omitted from method calls. As used in this answer, it's not an issue. \$\endgroup\$ – Wayne Conrad Jan 9 '14 at 9:48
2
\$\begingroup\$

Here's one way to modify your code:

def sort_list_by_key(key, list)
  key_arr = key.downcase.chars.each_with_index.to_a
  metric = list.each_with_object([]) do |l, m|
    w = l.downcase
    ndx = key_arr.each_with_object({w: [], k: []}) do |(c, i), h|
      if (j = w.index(c))
        h[:w] << j
        h[:k] << i
      end
    end     
    m << (distance(ndx[:w]) - distance(ndx[:k])).abs - 3 * ndx[:w].size
  end
  list.zip(metric).sort_by(&:last).map(&:first)
end

def distance(ndx)
  ndx.each_cons(2).to_a.reduce(0) {|d, (i,j)| d + (i-j).abs}
end

Let's look at an example:

key = "match"
list = %w[The cat had kittens] # => ["the", "cat", "had", "kittens"]

We know we will need the index of each character of key for each word in list, so we first construct key_arr:

key_arr # => [["m", 0], ["a", 1], ["t", 2], ["c", 3], ["h", 4]]  

We now ask Enumerable#each_with_object (available since Ruby 1.9) to iterate a block for each element of list, and return the results in an array, denoted by the block variable m. This array will be captured by the variable metric. each_with_object creates this (initially empty) array. Each element is the ordering metric for the corresponding member of list.

Consider the first element of list: l => "The". We use String#downcase to change "The" to "the" (not downcase!, because we don't want to change list). We again use each_with_object, this time to create a hash that will contain two arrays that are needed to calculate the ordering metric. These arrays contain indices of matching characters, for "the" (ndx[:w]) and "match" (ndx[:k]), respectively. The calculation key_arr.each... proceeds as follows:

w => "the"
   [c, i]    j=index(c)    ndx[:w]    ndx[:k]
  ['m', 0]         nil         []         [] 
  ('a', 1]         nil         []         [] 
  ['t', 2]          0         [0]        [2]
  ['c', 3]         nil        [0]        [2]
  ['h', 4]          1       [0,1]      [2,4]

A similar calculation is done for "cat", "had" and "kittens". The results are as follows:

                                   distance
  w           ndx[:w]   ndx[:k] list  key |diff| 3*size  metric 
'the'          [0,1]     [2,4]    1    2     1      6     -5
'cat'      [1, 2, 0] [1, 2, 3]    3    2     1      9     -8
'had'         [1, 0]    [1, 4]    1    3     2      6     -4
'kittens'        [2]       [2]    0    0     0      3     -3

metric # => [-5, -8, -4, -3]

These index arrays provide the information needed to calculate the ordering metric for each word, shown in the last column of this table. For w => "cat", the ordering metric is:

(distance([1,2,0]) - distance[1,2,3]).abs - 3 * [1,2,0].size

For distance([1,2,0])

[1,2,0].each_cons(2).to_a # => [[1, 2], [2, 0]]
[[1, 2], [2, 0]].reduce(0) {|d, (i,j)| d + (i-j).abs} # => 3

(Recall that reduce and inject are synonyms.)

Similarly, distance([[1, 2, 3]]) => 2 and 3 * [1,2,0].size => 9, so

(distance([1,2,0]) - distance[1,2,3]).abs - 3 * [1,2,0].size => |3 - 2| - 9 => -8

We can now construct

list.zip(metric) # => [["The", -5], ["cat", -8], ["had", -4], ["kittens", -3]]

which we sort on the second (last) value of each array to obtain:

=> [["cat", -8], ["The", -5], ["had", -4], ["kittens", -3]]

Lastly, we return the first element of each array:

 => ["cat", "The", "had", "kittens"] 

I invite corrections and suggestions for improvements.

\$\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.