# Substring Diffing Ruby Challenge

**URL:** <https://www.ruby-forum.com/t/substring-diffing-ruby-challenge/109791>\
**Category:** Ruby\
**Created:** [July 19, 2007, 3:06am UTC](https://www.ruby-forum.com/t/substring-diffing-ruby-challenge/109791 "2007-07-19T03:06:02Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![robertjames](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/r/e9c0ed/32.png) [@robertjames](https://www.ruby-forum.com/u/robertjames)\
**Post date:** [July 19, 2007, 3:06am UTC](https://www.ruby-forum.com/t/substring-diffing-ruby-challenge/109791/1 "2007-07-19T03:06:02Z")

</div>

first = ‘Joe went to the store and bought 2 loaves of bread’  
second = ‘Joe and I went to the market and bought 3 loaves of bread  
and butter’

assert\_equal [4…9, 21…29, 57…68], diff(first, second) # diff()  
returns a list of Ranges spanning the position of edits or insertions

Anyone know an algorithm (or code) that can make that work?

---

<div class="post-metadata">

**Author:** ![robertjames](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/r/e9c0ed/32.png) [@robertjames](https://www.ruby-forum.com/u/robertjames)\
**Post date:** [July 19, 2007, 11:21am UTC](https://www.ruby-forum.com/t/substring-diffing-ruby-challenge/109791/2 "2007-07-19T11:21:04Z")

</div>

S. Robert J. wrote:

> first = ‘Joe went to the store and bought 2 loaves of bread’  
> second = ‘Joe and I went to the market and bought 3 loaves of bread  
> and butter’
> 
> assert\_equal [4…9, 21…29, 57…68], diff(first, second) # diff()  
> returns a list of Ranges spanning the position of edits or insertions
> 
> Anyone know an algorithm (or code) that can make that work?

I extended Austin Z.'s LCS/Diff library to do just this for my  
project

LCS/Diff:  
[http://raa.ruby-lang.org/project/diff-lcs/](http://raa.ruby-lang.org/project/diff-lcs/)

Weft QDA code that does it:  
[http://viewvc.rubyforge.mmmultiworks.com/cgi/viewvc.cgi/trunk/weft-qda/lib/weft/diff.rb?root=weft-qda&view=co](http://viewvc.rubyforge.mmmultiworks.com/cgi/viewvc.cgi/trunk/weft-qda/lib/weft/diff.rb?root=weft-qda&view=co)

The ‘transform’ method accepts two strings and returns an array of  
‘Transformation’ objects, each representing a single  
insert/delete/change

hth  
alex