Ruby Quiz for building up Ruby?

[Hugh Sasse]

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

 

[David Balmain]

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

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--

 

[David Balmain]

------=_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--

 

[Jacob Quinn Shenker]

SSB3YXMgdGFsa2luZyBhYm91dCB0aGVzZSBtb3JlIHByYWN0aWNhbCBhbmQgY29tcGxpY2F0ZWQg
c29sdXRpb25zIGluCmdlbmVyYWwsIHRoaXMgcGFydGljdWxhciBvbmUgbWlnaHQgYmUgZ29vZCBh
cyBhIFJ1YnlRdWl6ICh1aCwgSSBkaWRuJ3QKcmVhZCB0aGUgc3BlYyB0aGUgZmlyc3QgdGltZS4u
LiA7KS4KCkphY29iCgpPbiAxMC8yNy8wNSwgRGF2aWQgQmFsbWFpbiA8ZGJhbG1haW4ubWxAZ21h
aWwuY29tPiB3cm90ZToKPiBPbiBzZWNvbmQgdGhvdWdodHMsIGFmdGVyIGEgcXVpY2sgcmVhZCBv
ZiB0aGUgc3BlYywgSSB0aGluayB0aGlzIHdvdWxkIGJlIGEKPiBwZXJmZWN0IHJ1YnkgcXVpei4K
Pgo+IERhdmUKPgo+Cg==

 

[Kev Jackson]

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\\test")
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(pos, 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

 

[Hugh Sasse]

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

 

[Brian Schröder]

[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

 

[David Balmain]

------=_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

[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

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

 

[Hugh Sasse]

---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

[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--

 

[Rob Rypka]

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.

 

[James Edward Gray II]

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.

I'm all for quizzes that help build Ruby technologies. I strongly
encourage library authors to farm some work out to us. Just try to
get it down to a small enough piece and announce that you intend to
steal any posted solutions for whatever purposes. I'll run them.

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.

This is all my fault. I told Hugh I was concerned you guys wouldn't
work this problem. Clearly I was wrong.

What the opinion now that we've seen solutions? Go ahead and make it
official or consider it a lesson learned and hope James is more
intuitive next time?

James Edward Gray II

 

[Rob Rypka]

What the opinion now that we've seen solutions? Go ahead and make it
official or consider it a lesson learned and hope James is more
intuitive next time?

It pretty much already was a quiz, without the waiting period. If
Hugh already has what he needs, I'd say skip it. C'est la vie...

I just printed off Zed's paper and McIlroy's "An algorithm for
differential file comparison" for some fun weekend reading.

 

[Brian Schröder]

I'm all for quizzes that help build Ruby technologies. I strongly
encourage library authors to farm some work out to us. Just try to
get it down to a small enough piece and announce that you intend to
steal any posted solutions for whatever purposes. I'll run them.


This is all my fault. I told Hugh I was concerned you guys wouldn't
work this problem. Clearly I was wrong.

What the opinion now that we've seen solutions? Go ahead and make it
official or consider it a lesson learned and hope James is more
intuitive next time?

James Edward Gray II

I think it is a good idea to use quizzes to advance certain libraries.
But I would like it also if someone could put up a website with these
kind of requests, and people like the gem people would write up small
"wished" projects or subprojects. Or maybe just use the rubyforge
"help wanted" feature for this. I do not have the capacities to join a
big project, but submitting something once in a while is a great
thing.

best regards,

Brian

 

[swille]

I think it is a good idea to use quizzes to advance certain libraries.
But I would like it also if someone could put up a website with these
kind of requests, and people like the gem people would write up small
"wished" projects or subprojects. Or maybe just use the rubyforge
"help wanted" feature for this. I do not have the capacities to join a
big project, but submitting something once in a while is a great
thing.

best regards,

Brian

I agree with this. I think it would be a great idea to often and
openly ping the community, and if it fits a quiz, that's a great way
to do it. This [the quizes and the application of projects to the
quiz] sort of seems like a whole new take on open source software too
-- go to the community rather having them come to the project. I like
it!