«

I put this suggestion to James Edward Gray II as a means to an
end. I was thinking that if the quiz inspires people to tackle
manageable problems, then it might be that we can use it to help us
improve Ruby itself. We may get components for packages built up
for the cases where people find them sufficiently interesting to
write.

So, would anyone object to this strategy?

Is the problem expressed below sufficiently challenging to be of
interest to those who know they could tackle it? Does it make a
good quiz? James said I should ask, so I am.

<quote>
Date: Wed, 26 Oct 2005 18:11:12 +0100 (WEST)
From: Hugh Sasse <>
To: James Edward Gray II <>
Cc: Hugh Sasse <>
Subject: Another Ruby Quiz suggestion: generic diff/patch

I don't know if this is too big for the Ruby quiz. I'm not sure how
to tackle it (though my maximum string length code might be of some
use) but I can tell you why it would be useful. First: the
problem:

Given 2 versions of a file, which may be binary, generate the
difference in GDIFF format, detailed here:

http://www.w3.org/TR/NOTE-gdiff-19970901

For extra marks, implement the patch program that will generate the
new file from the old file and the GDIFF file.

The reason this is needed:

RFC3229 Delta encoding in HTTP

ftp://ftp.rfc-editor.org/in-notes/rfc3229.txt

may make use of this format, and it seems there are no rights to it
as there are for vcdiff referenced in the same document.

Why is this of interest to us?

Rubygems is facing the problem that as more gems are added the index
is getting far too big to handle. Implementing RFC3229 seems
feasible, given the existence of a pure ruby - and thus as portable
as rubygems - differencing library. The logic of the protocol is
fairly clear, but without some means to handle the differences it is
a non-starter.


So, is this too hard for a quiz? Would the Ruby black-belts relish
the challenge?

Hugh
</quote>

So I open this to the floor, so to speak...
Hugh

------=_Part_11314_8680035.1130466241697
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

On 10/28/05, Jacob Quinn Shenker <> wrote:
>
> This might be a really fun way to improve Ruby! Good idea. However, I
> think it should compliment the original RubyQuiz, not replace it...
> RubyQuizzes in the past have been fun quickies, and this is a
> different, more practical and involved beast...


I agree with Jacob. This particular problem might be a bit involved for
RubyQuiz. Perhaps if we could break it down into smaller problems. I really
would love a native ruby diff. Having said that, I think Hughs idea is a
good one.

Dave

------=_Part_11314_8680035.1130466241697--

------=_Part_11326_669626.1130466738955
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

On second thoughts, after a quick read of the spec, I think this would be a
perfect ruby quiz.

Dave

------=_Part_11326_669626.1130466738955--

SSB3YXMgdGFsa2luZyBhYm91dCB0aGVzZSBtb3JlIHByYWN0aW NhbCBhbmQgY29tcGxpY2F0ZWQg
c29sdXRpb25zIGluCmdlbmVyYWwsIHRoaXMgcGFydGljdWxhci BvbmUgbWlnaHQgYmUgZ29vZCBh
cyBhIFJ1YnlRdWl6ICh1aCwgSSBkaWRuJ3QKcmVhZCB0aGUgc3 BlYyB0aGUgZmlyc3QgdGltZS4u
LiA7KS4KCkphY29iCgpPbiAxMC8yNy8wNSwgRGF2aWQgQmFsbW FpbiA8ZGJhbG1haW4ubWxAZ21h
aWwuY29tPiB3cm90ZToKPiBPbiBzZWNvbmQgdGhvdWdodHMsIG FmdGVyIGEgcXVpY2sgcmVhZCBv
ZiB0aGUgc3BlYywgSSB0aGluayB0aGlzIHdvdWxkIGJlIGEKPi BwZXJmZWN0IHJ1YnkgcXVpei4K
Pgo+IERhdmUKPgo+Cg==

Well I've got to dash off early today, but here's something I've hacked
together (very rough)

I'm sure there are many better ways of doing this - indeed my algorithm
is very naive, it doesn't scan for matches in an efficient way (just
barely scans
The approach I was going for was to have a GDiffFile class, and then
create various GDiff command objects and pump them into the file.

At the moment it will spit out a semi-compliant gdiff file, but it's
horrendously bloated, and I couldn't find a nice way to quote strings as
in the example on

http://www.w3.org/TR/NOTE-gdiff-19970901

Kev

GDiff composer (just bytes, not longs etc), not in class, just hacking
at the script really

gdiff.rb
require 'lib/gdiff_copy'
require 'lib/gdiff_data'
require 'lib/gdiff_file'

diff_file = GDiff::GDiffFile.new("d:\\ruby_projects\\gdiff\\te st")
diff_file.put_header

# get data into arrays
old = IO.read("d:\\ruby_projects\\gdiff\\gdiff.rb").scan (/./)
new = IO.read("d:\\ruby_projects\\gdiff\\gdiff_new.rb"). scan(/./)

# dumb scan comparing single chars, should make it compare matching
sequences
pos =0
old.each do |oldb|
diff_file.put_cmd_and_data(GDiff::GDiffCopy.new(po s, 1)) if new[pos] == oldb
diff_file.put_cmd_and_data(GDiff::GDiffData.new(1, new[pos])) if new[pos]
!= oldb
pos +=1
end
diff_file.put_trailer
diff_file.write_diff


lib/gdiff_cmd.rb

module GDiff
class GDiffCmd
attr_accessor :cmd
attr_accessor :data
def initialize(cmd, data)
@cmd = cmd
@data = data
end
end
end

lib/gdiff_copy.rb

require 'lib/gdiff_cmd'

module GDiff
class GDiffCopy < GDiffCmd

def initialize(position, length)
@cmd = 249
@data = [0]
@data << position
@data << length
end
end
end


lib/gdiff_data.rb

require 'lib/gdiff_cmd'

module GDiff

class GDiffData < GDiffCmd
def initialize(cmd, data)
#if cmd < 1 or cmd > 248
# raise DataError
#end
@cmd = cmd
@data = data
end
end

end

lib/gdiff_file.rb

module GDiff

class GDiffFile < File
@@magic = 0xd1ffd1ff
@@version = 0x04
@@EOF = 0

def initialize(filename)
@filename = filename
@filedata = []
end

def put_header
put_data(@@magic)
put_data(@@version)
end

def put_trailer
put_data(@@EOF)
end

def copy_byte(start)
write_diff()
end

def put_data(data)
if data.respond_to?(length) then
if data.length==1 then
@filedata << data
else
data.each_byte do |b|
@filedata << data + ","
end
else
@filedata << data
end
end

def put_cmd(cmd)
@filedata << cmd.cmd << ","
end

def put_cmd_and_data(cmd)
put_cmd(cmd)
put_data(cmd.data)
end

def write_diff
p @filedata
File.open(@filename, "w") { |f|
f << @filedata.flatten
}
end
end
end

On Fri, 28 Oct 2005, Kev Jackson wrote:

> Well I've got to dash off early today, but here's something I've hacked
> together (very rough)
>

Well, I was asking if it would be acceptable as a quiz. I wasn't
expecting any attempts at a solution yet! Thank you. I'll let
James decide how he'd like to fit this into the quizzes, be that in
parallel with the normal ones or otherwise.

Thank you again
Hugh

> [snip quiz request]

Hello Hugh,

I now you did not ask for an implementation right now, but with the
help of Zed Shaws wonderfull suffix-tree implementation I whipped up a
gdiff / gpatch release.

It can be found at
http://ruby.brian-schroeder.de/gdiff/

If there is interest in continuing this project I will register a
rubyforge project for it and pack it also as a gem. ATM the release is
packaged with setup.rb

The suffix tree seems to be licensed under gpl, I don't know if zed
would accept a ruby-licence release too. I will write him an email.

best regards,

Brian


--
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/

------=_Part_1958_6270784.1130514113481
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Funny the number of people implementing this. Well, since we're showing our
code;

http://blog.davebalmain.com/pages/rdiff

Enjoy,
Dave

On 10/29/05, Brian Schr=F6der <> wrote:
>
> > [snip quiz request]
>
> Hello Hugh,
>
> I now you did not ask for an implementation right now, but with the
> help of Zed Shaws wonderfull suffix-tree implementation I whipped up a
> gdiff / gpatch release.
>
> It can be found at
> http://ruby.brian-schroeder.de/gdiff/
>
> If there is interest in continuing this project I will register a
> rubyforge project for it and pack it also as a gem. ATM the release is
> packaged with setup.rb
>
> The suffix tree seems to be licensed under gpl, I don't know if zed
> would accept a ruby-licence release too. I will write him an email.
>
> best regards,
>
> Brian
>
>
> --
> http://ruby.brian-schroeder.de/
>
> Stringed instrument chords: http://chordlist.brian-schroeder.de/
>
>

------=_Part_1958_6270784.1130514113481--

---559023410-959030623-1130514039=:7489
Content-Type: MULTIPART/MIXED; BOUNDARY="-559023410-959030623-1130514039=:7489"

This message is in MIME format. The first part should be readable text,
while the remaining parts are likely unreadable without MIME-aware tools.

---559023410-959030623-1130514039=:7489
Content-Type: TEXT/PLAIN; charset=X-UNKNOWN
Content-Transfer-Encoding: QUOTED-PRINTABLE

On Sat, 29 Oct 2005, Brian Schr=F6der wrote:

> > [snip quiz request]
>=20
> Hello Hugh,
>=20
> I now you did not ask for an implementation right now, but with the
> help of Zed Shaws wonderfull suffix-tree implementation I whipped up a
> gdiff / gpatch release.
>=20
> It can be found at
> http://ruby.brian-schroeder.de/gdiff/

This sort of response is just amazing. I'll explore that. Thank
you. I'll let you know how I get on.
>=20
> If there is interest in continuing this project I will register a
> rubyforge project for it and pack it also as a gem. ATM the release is
> packaged with setup.rb

Thank you.
>=20
> The suffix tree seems to be licensed under gpl, I don't know if zed
> would accept a ruby-licence release too. I will write him an email.

Might be an idea to document the interface and see if soneone wants
to meet that challenge
>=20
> best regards,
>=20
> Brian
>=20
Thank you
Hugh
---559023410-959030623-1130514039=:7489--
---559023410-959030623-1130514039=:7489--

On 10/27/05, Hugh Sasse <> wrote:
> I put this suggestion to James Edward Gray II as a means to an
> end. I was thinking that if the quiz inspires people to tackle
> manageable problems, then it might be that we can use it to help us
> improve Ruby itself. We may get components for packages built up
> for the cases where people find them sufficiently interesting to
> write.
>
> So, would anyone object to this strategy?

I think it's a good idea. Quizzes are great for fun and learning, but
that doesn't mean the results have to be thrown away.

The only thing to worry about is licensing. As long as the intentions
of the quiz are clear, and the participants agree to including the
code under a Ruby license (or whatever), we should be fine.

> Is the problem expressed below sufficiently challenging to be of
> interest to those who know they could tackle it? Does it make a
> good quiz? James said I should ask, so I am.

The day before you posted, I was thinking about starting a diff
library for Ruby, as the ones I found were pure ports and/or out of
date and undocumented (in English). I just started thinking about it,
so don't commit me to anything.

I think the quiz would be on par with the other quizzes, and should be
considered for inclusion in the regular cycle. I would participate,
time allowing.

--
Rob