1 Replies - 9192 Views - Last Post: 28 May 2016 - 06:11 AM

#1 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1739
  • View blog
  • Posts: 5,895
  • Joined: 03-August 09

Challenge: Make a diff tool

Post icon  Posted 27 May 2016 - 10:39 PM

Recently I came across the following article : http://languagengine...-edit-distance/

I'd encourage you to read the whole article but the purpose of this challenge just worry about the first part before regexs are discussed. The article shows a way to think about how string edit distance works. Namely by arranging suffixs of two strings in a grid and following a certain rule for when you can jump from one point in the grid to another you can reduce string edit distance to shortest path finding! More over the particular path you take corresponds to a diff of the two strings! This is the most intuitive straight forward of making a diff tool that I have seen and I was inspired to try making one and thought you guys could make one with me! In the article it is done character by character but I think it is more practical to do this line by line.

Your challenge is to make a diff tool. You don't have to do it this way. Just write your own diff function/tool!

My design is going to go like this.

1. Don't construct an explicit graph
2. Use depth first search to find a shortest path using a table to keep track of visited nodes
3. convert that path to a diff file. + prefixes a line if the patch tool should add that line of text to the file. - followed by a number means to delete the next so many lines. a number by it self means to leave in that many lines and advance the current line by that many.
4. If I'm feeling productive I'm going to write the corresponding patch tool

Have fun and feel free to ask questions!

This post has been edited by ishkabible: 27 May 2016 - 10:45 PM


Is This A Good Question/Topic? 2
  • +

Replies To: Challenge: Make a diff tool

#2 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 5828
  • View blog
  • Posts: 19,868
  • Joined: 05-May 12

Re: Challenge: Make a diff tool

Posted 28 May 2016 - 06:11 AM

Having implemented the Myers algorithm in the past, I'm thinking of trying my hand at the Patience Diff algorithm. Admittedly, the latter produces less efficient diffs, but supposedly it creates prettier diffs that we programmers would rather see.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1