http://math.stackexchange.com/questions/1266263/minimum-number-of-operations-to-make-all-of-the-strings-objects-the-same

hammingeq.rb

$text = "You want to know (in a polynomial time) the minimum cost of making all of the strings the same"

def number_len(k)
  return Math::log10(k).floor + 1
end

$words = $text.upcase
  .split(/[^A-Z]/)
  .select { |w| not w.empty? }

$k = $words.map { |w| w.length }.max

$words = $words.map { |w| w.slice(0, $k).ljust($k, ".") }.uniq.sort

$n = $words.size

$kn = number_len($k)
$nn = number_len($n)

def dh(x, y)
  d = 0
  $k.times do |i|
    if x[i] != y[i]
      d += 1
    end
  end
  return d
end

def print_words
  $n.times do |i|
    printf "%#{$nn}d. '%s'\n", i+1, $words[i]
  end
end

def print_h
  c_min = $k * $n
  cn = number_len(c_min)
  i_min = 0
  $n.times do |i|
    x = $words[i]
    c = 0
    printf "%#{$nn}d: [", i+1
    $n.times do |j|
      y = $words[j]
      d = dh(x, y)
      c += d
      printf "%#{$kn}d ", d
    end
    printf "], c = %#{cn}s\n", c
    if c < c_min
      c_min = c
      i_min = i
    end
  end
  puts "c_min = #{c_min}, i_min = #{i_min+1}"
  puts "final word: '#{$words[i_min]}'"
end

print_words
puts
print_h