Source code in the crystal programming language

require "levenshtein"
puts Levenshtein.distance("kitten", "sitting")
puts Levenshtein.distance("rosettacode", "raisethysword")


module Levenshtein
 
  def self.distance(a, b)
    a, b = a.downcase, b.downcase
    costs = (0..b.size).to_a
    (1..a.size).each do |i|
      costs[0], nw = i, i - 1  # j == 0; nw is lev(i-1, j)
      (1..b.size).each do |j|
        costs[j], nw = [costs[j] + 1, costs[j-1] + 1, a[i-1] == b[j-1] ? nw : nw + 1].min, costs[j]
      end
    end
    costs[b.size]
  end
 
  def self.test
    %w{kitten sitting saturday sunday rosettacode raisethysword}.each_slice(2) do |(a, b)| #or do |pair| a, b = pair
      puts "distance(#{a}, #{b}) = #{distance(a, b)}"
    end
  end
 
end
 
Levenshtein.test


def levenshtein_distance(str1, str2)
  n, m = str1.size, str2.size
  max = n / 2
  
  return 0 if n == 0 || m == 0
  return n if (n - m).abs > max
 
  d = (0..m).to_a
  x = 0
 
  str1.each_char_with_index do |char1, i|
    e = i + 1
 
    str2.each_char_with_index do |char2, j|
      cost = (char1 == char2) ? 0 : 1
      x = [ d[j+1] + 1, # insertion
            e + 1,      # deletion
            d[j] + cost # substitution
          ].min
      d[j] = e
      e = x
    end
 
    d[m] = x
  end
  x
end

%w{kitten sitting saturday sunday rosettacode raisethysword}.each_slice(2) do |(a, b)| #or do |pair| a, b = pair
  puts "distance(#{a}, #{b}) = #{levenshtein_distance(a, b)}"
end