Diff.rb: CodeBrawl's "Ruby diffs" entry (http://codebrawl.com/contests/ruby-diffs)

README.md

Diff.rb

A simple diff utility written in Ruby. It works with single or multi-line strings and returns an array of hashes that indicates the line number affected and change: added, deleted, or same.

Example:

old = "This line of document stays the same.
The dokument should be spelled correctly.
This line should be deleted."

new = "The new document has a line break!

This line of document stays the same.
The document should be spelled correctly.
Finally, a brand new line."

Diff.diffs(old, new).each do |diff|
  puts diff
end

# Produces:

# {:line => 1, :change => :add,    :string => "The new document has a line break!"}
# {:line => 2, :change => :add,    :string => ""}
# {:line => 1, :change => :same,   :string => "This line of document stays the same."}
# {:line => 2, :change => :delete, :string => "The dokument should be spelled correctly."}
# {:line => 3, :change => :delete, :string => "This line should be deleted."}
# {:line => 4, :change => :add,    :string => "The document should be spelled correctly."}
# {:line => 5, :change => :add,    :string => "Finally, a brand new line."}

# With a little formatting, we can produce something very similar to Unix's diff (unified format):

SYMBOLS = {:add => '+', :delete => '-', :same => ' '}

Diff.diffs(old, new).each do |diff|
  puts SYMBOLS[diff[:change]] + diff[:string]
end

# Produces: 

# +The new document has a line break!
# +
#  This line of document stays the same.
# -The dokument should be spelled correctly.
# -This line should be deleted.
# +The document should be spelled correctly.
# +Finally, a brand new line.

diff.rb

# A simple utility that returns the differences between two strings
# Note: the focus here is brevity and NOT readability!
#
module Diff
  attr_accessor :diffs, :sequences

  def self.diffs(old, new)
    new, old, @diffs = new.lines.to_a, old.lines.to_a, []
    build_sequences(old, new)
    find_diffs(old, new, old.size, new.size)
  end

  private

  def self.find_diffs(old, new, row, col)
    if row > 0 && col > 0 && old[row-1] == new[col-1]
      find_diffs(old, new, row-1, col-1)
      @diffs << { :line => row, :change => :same, :string => old[row-1].strip }
    elsif col > 0 && (row == 0 || @sequences[row][col-1] >= @sequences[row-1][col])
      find_diffs(old, new, row, col-1)
      @diffs << { :line => col, :change => :add, :string => new[col-1].strip }
    elsif row > 0 && (col == 0 || @sequences[row][col-1] < @sequences[row-1][col])
      find_diffs(old, new, row-1, col)
      @diffs << { :line => row, :change => :delete, :string => old[row-1].strip }
    end
  end

  def self.build_sequences(old, new)
    rows, cols = old.size+1, new.size+1
    @sequences = rows.times.map{|x|[0]*(x+1)}
    rows.times.each do |row|
      cols.times.each do |col|
        @sequences[row][col] = if old[row-1] == new[col-1]
          @sequences[row-1][col-1] + 1
        else
          [@sequences[row][col-1].to_i, @sequences[row-1][col].to_i].max
        end
      end
    end
  end

end