Skip to content

Instantly share code, notes, and snippets.

@tansengming
Created October 31, 2016 00:51
Show Gist options
  • Save tansengming/4259201bef75727f0d08d1229ef74f1c to your computer and use it in GitHub Desktop.
Save tansengming/4259201bef75727f0d08d1229ef74f1c to your computer and use it in GitHub Desktop.
# TODO: Fix this to work with addition and deletion distances
def edit_distance(word_1, word_2)
# transforms 'str' to ['s', 't', 'r']
to_array = -> (word) { word.each_char.map{|c| c} }
# xor(['s', 't', 'r'], ['s', 't', 'r']) = 0
# xor(['s', 't', 'r'], ['a', 't', 'r']) = 1
# xor(['s', 't', 'r'], ['a', 'b', 'c']) = 3
substitution_distance = -> (top, bottom) { top.zip(bottom).map{|top_node, bottom_node| top_node == bottom_node ? 0 : 1 }.inject(:+) }
word_1_array = to_array[word_1]
word_2_array = to_array[word_2]
substitution_distance[word_1_array, word_2_array]
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment