Skip to content

Instantly share code, notes, and snippets.

@mattsears
Created August 21, 2011 20:01
Show Gist options
  • Save mattsears/1161076 to your computer and use it in GitHub Desktop.
Save mattsears/1161076 to your computer and use it in GitHub Desktop.
Diff.rb: CodeBrawl's "Ruby diffs" entry (http://codebrawl.com/contests/ruby-diffs)

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.
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment