#!/usr/bin/ruby

class Table
  def initialize(m, n)
    @t = Array.new(m) { Array.new(n) { nil } }
  end

  def to_s
    @t.map{|row| row.join(" ") }.join("\n")
  end

  def [](i, j)      
    @t[i][j]
  end

  def []=(i, j, v)
    @t[i][j] = v
  end
end

def edit_distance_ij(a, b, i, j, table)
  return j, "e" * j if i == 0
  return i, "l" * i if j == 0
  return table[i-1, j-1] if table[i-1, j-1]
  if a[i-1] == b[j-1]
    cij = 0
    c = ' '
  else
    cij = 1
    c = 'c'        
  end
  d1, a1 = edit_distance_ij(a, b, i-1, j,   table)
  d2, a2 = edit_distance_ij(a, b, i,   j-1, table)
  d3, a3 = edit_distance_ij(a, b, i-1, j-1, table)
  table[i-1, j-1] = [[d1 + 1, a1 + "d"], [d2 + 1, a2 + "i"], [d3 + cij, a3+c]].min
end

def edit_distance(a_string, b_string)
  m = a_string.length
  n = b_string.length
  edit_distance_ij(a_string, b_string, m, n, Table.new(m,n))
end

if ARGV.length != 2
  puts "Usage: editierdistanz WORT_1 WORT_2"
else
  puts edit_distance(ARGV[0], ARGV[1])
end