The three rules of Ruby Q.:
-
Please do not post any solutions or spoiler discussion for this quiz
until
48 hours have passed from the time on this message.
-
Support Ruby Q. by submitting ideas as often as you can:
http://www.rubyquiz.com/
- Enjoy!
Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby T. follow the discussion. Please reply to the original quiz
message,
if you can.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
This week’s Ruby Q. is to write a script that finds the longest
repeated
substring in a given text.
Your program will be passed some text on STDIN and is expected to print
the
longest repeated substring within that text to STDOUT.
Repeated substrings may not overlap. If more than one substring is
repeated
with the same length, you may print any of them. If there is no
repeated
substring, the result is an empty string (print nothing).
Example:
$ echo banana | ruby longest_repeated_substring.rb
an
OR
$ echo banana | ruby longest_repeated_substring.rb
na
Make sure your code runs efficiently when passed a large text.
On Jan 18, 2008, at 7:23 AM, Ruby Q. wrote:
This week’s Ruby Q. is to write a script that finds the longest
repeated
substring in a given text.
Make sure your code runs efficiently when passed a large text.
Posting the strings you find in a given text and/or timings is not a
spoiler.
James Edward G. II
On 18 Jan 2008, at 13:23, Ruby Q. wrote:
with the same length, you may print any of them. If there is no
$ echo banana | ruby longest_repeated_substring.rb
na
Make sure your code runs efficiently when passed a large text.
Should white space and punctuation be treated as part of the
substring, or are they to be ignored?
/dh
On Jan 18, 2008, at 9:49 AM, Denis H. wrote:
repeated
$ echo banana | ruby longest_repeated_substring.rb
na
Make sure your code runs efficiently when passed a large text.
Should white space and punctuation be treated as part of the
substring, or are they to be ignored?
I vote that we treat all characters equally.
James Edward G. II
On Jan 18, 2008, at 7:23 AM, Ruby Q. wrote:
Repeated substrings may not overlap. If more than one substring is
repeated
with the same length, you may print any of them. If there is no
repeated
substring, the result is an empty string (print nothing).
Must they be adjacent, or does “aaabaaa” contain the repeating
substring “aaa”?
Dave
On Jan 18, 2008, at 10:37 AM, Dave T. wrote:
On Jan 18, 2008, at 7:23 AM, Ruby Q. wrote:
Repeated substrings may not overlap. If more than one substring is
repeated
with the same length, you may print any of them. If there is no
repeated
substring, the result is an empty string (print nothing).
Must they be adjacent, or does “aaabaaa” contain the repeating
substring “aaa”?
They do not have to be adjacent. aaa would be a valid answer for
aaabaaa.
James Edward G. II
I hope I get some time to take a shot at this one. It looks like fun.
On Fri, 18 Jan 2008 08:23:40 -0500, Ruby Q. wrote:
Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone on Ruby T. follow the discussion. Please reply to the
original quiz message, if you can.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
=-=-=-=-=
Example:
$ echo banana | ruby longest_repeated_substring.rb an
OR
$ echo banana | ruby longest_repeated_substring.rb na
Make sure your code runs efficiently when passed a large text.
First testcase:
“your banana my banana” should give " banana"
–Ken
On Jan 18, 2008 10:00 PM, yermej [email protected] wrote:
On Jan 18, 2:38 pm, Ken B. [email protected] wrote:
And a second:
“aaaaaa” should give “aaa”
Right?
It should, otherwise “banana” would give “ana” rather than “an”.
My question is (I’m not familiar with RubyQuiz too much :)): episode
focus on algorithm (speed) or source code (readable)?
–
Rados³aw Bu³at
http://radarek.jogger.pl - mój blog
On Jan 18, 2:38 pm, Ken B. [email protected] wrote:
First testcase:
“your banana my banana” should give " banana"
–Ken
–
Ken (Chanoch) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.http://www.iit.edu/~kbloom1/
And a second:
“aaaaaa” should give “aaa”
Right?
It should, otherwise “banana” would give “ana” rather than “an”.
Or even better it would be the same string.
–
Rados³aw Bu³at
http://radarek.jogger.pl - mój blog
2008/1/18 Rados³aw Bu³at [email protected]:
My question is (I’m not familiar with RubyQuiz too much :)): episode
focus on algorithm (speed) or source code (readable)?
Normally this is not very important all aspects can be of interest but
please be aware that this time James has explicitly asked for
solutions that are reasonable fast for longer input.
Great to have you join in BTW. The most important thing is to
participate of course…
Cheers
Robert
http://ruby-smalltalk.blogspot.com/
Whereof one cannot speak, thereof one must be silent.
Ludwig Wittgenstein
My question is (I’m not familiar with RubyQuiz too much :)): episode
focus on algorithm (speed) or source code (readable)?
Hopefully both. 
How long input string I could expect?
–
Rados³aw Bu³at
http://radarek.jogger.pl - mój blog
On Jan 18, 2008, at 3:10 PM, Rados³aw Bu³at wrote:
My question is (I’m not familiar with RubyQuiz too much :)): episode
focus on algorithm (speed) or source code (readable)?
Hopefully both. 
James Edward G. II
On Jan 18, 3:54 pm, tho_mica_l [email protected] wrote:
") Convey the object code in, or embodied in, a physical product
(including a physical distribution medium), accompanied by "…
If somebody can verify this.
I think this really starts to make fun when running the script over
Mark Twains entire work (from Gutenberg) or something similar.
I agree on GPL3.
How much whitespace followed your GPL2 result? I ended up with
" 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n"
which is 57 characters. Maybe just a difference in the text files we
used? I used ‘ruby-1.8.6/GPL’.
First testcase:
“your banana my banana” should give " banana"
For the GNU GENERAL PUBLIC LICENSE Version 2, June 1991, I get:
"customarily used for software interchange; or, "… some more
whitespace
For the GPL3 I get:
") Convey the object code in, or embodied in, a physical product
(including a physical distribution medium), accompanied by "…
If somebody can verify this.
I think this really starts to make fun when running the script over
Mark Twains entire work (from Gutenberg) or something similar.
" 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n"
It seems there is another version of this document around (at least on
my harddisk) in which the line in the header reads " 59 Temple Place,
Suite 330, Boston, MA 02111 USA\n" instead.
Thanks for verifying.
Thomas.
On Jan 18, 2008, at 2:00 PM, yermej wrote:
And a second:
“aaaaaa” should give “aaa”
Right?
i would think that
‘aaaaaa’.longest_repeating_substring #=> ‘aaaaa’
the quiz did not say that the two strings could not overlap.
is this correct james?
a @ http://codeforpeople.com/
On 18 Jan 2008, at 23:05, ara.t.howard wrote:
is this correct james?
Actually the spec says “Repeated substrings may not overlap.” so the
correct answer for “aaaaaa” should be “aaa”.
/dh
On Jan 18, 2008, at 5:05 PM, ara.t.howard wrote:
Ken (Chanoch) Bloom. PhD candidate. Linguistic Cognition Laboratory.
the quiz did not say that the two strings could not overlap.
is this correct james?
Actually, it did. Here’s the relevant line from the quiz:
“Repeated substrings may not overlap.”
James Edward G. II