Longest Repeated Substring

[quadz]

Greetings,

This week's Ruby Quiz (announced today) seems like one of those sort of problems that would be fun in any language.  Here are the details:

http://www.rubyquiz.com/quiz153.html

Here are some additional observations (culled from posts on the ruby-talk mailing list)...

---

First testcase:
"your banana my banana" should give " banana"

(notice the leading space is part of the repetition!)

---

"Repeated substrings may not overlap."

> > "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)?
>
> Hopefully both. 

...


Anyway... this seems like a fun problem in any language... it's pretty simple to write a correct but slow version (I think) ... but making it faster probably requires some cleverness.


Enjoy,

[kren.Z]

it'd be interesting to see some of those sources. I'd probably use a recursive function.



what's the difference between ruby and ruby on rails?...i keep hearing all this that ruby is like the greatest, i can't really say anything because i've never really used it. How do you guys like it?

[quadz]

it'd be interesting to see some of those sources. I'd probably use a recursive function.

The quiz was only released today... the sources will begin to appear after the 48-hour deadline... (I'd like to see them, too.... )

In the meantime, we can try our own ideas...

what's the difference between ruby and ruby on rails?...i keep hearing all this that ruby is like the greatest, i can't really say anything because i've never really used it. How do you guys like it?

Ruby is a general purpose programming language, albeit with different goals than, say, C or C++.

http://en.wikipedia.org/wiki/Ruby_(programming_language)

Ruby has been around since 1993.


Rails is a web framework written in ruby:

http://en.wikipedia.org/wiki/Ruby_On_Rails

..which was released in July, 2004.


I've been using Ruby since 1999 or 2000 or so... so to me, Rails is just another program written in Ruby.


You can try ruby in your browser here: http://tryruby.hobix.com/

Or, try ruby in more detail on your desktop here: http://code.whytheluckystiff.net/hacketyhack/


Regards,

 

[kren.Z]

fanx quadz,



i wike to program tomputers

[[BTF]Defiant!]

If I get my work done, I'll post prolog (clear but slow) for oddity sake.

[quadz]

If I get my work done, I'll post prolog (clear but slow) for oddity sake.

Cool, I'd like to see that... I've read about Prolog but never programmed in it.


Looks like most of the fastest solutions submitted so far are using variations on suffix arrays.

Here's one solution accompanied by a detailed explanation:

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/288086


Another fun one was implemented as a ruby one-liner:

2008/1/20, Raf Coremans <rrafje at gmail.com>:
>
> 2008/1/18, James Gray <james at grayproductions.net>:
> >
> > On Jan 18, 2008, at 3:10 PM, Radosław Bułat wrote:
> >
> > > On Jan 18, 2008 10:00 PM, yermej <yermej at gmail.com> 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 Gray II
> >

My solution offers speed nor readability; I went for a one-liner (if you
discount the require):

$ cat rq153.rb
#!/usr/bin/ruby -w

require 'enumerator'

p(
  ARGV.
  join( ' ').
  reverse.
  to_enum( :each_byte).
  inject( []){ |a, b| a << (a.last || "") + b.chr}.
  map{ |a| a.reverse}.
  inject( []){ |a, b| a << b.match( /^(.+).*\1/).to_a.pop }.
  flatten.
  compact.
  sort_by{ |a| a.size}.
  last
)

$ ./rq153.rb banana
"an"
$ ./rq153.rb aaabaaa
"aaa"
$ ./rq153.rb aaaaaa
"aaa"
$ ./rq153.rb ambidextrous
nil

Don't even think of running it on a reasonably-sized text, lest you want
your PC to grind to a halt.
Morale: ruby code *can* be ugly if you put your mind to it.


Regards,
Raf

He has splayed out his one-liner across several lines; but note that each line ends with a "." ... It's really a single statement.  In one line it looks like:

Code: [Select]

p(ARGV.join(' ').reverse.to_enum(:each_byte).inject([]){|a, b| a << (a.last || "") + b.chr}.map{|a| a.reverse}.inject([]){|a, b| a << b.match(/^(.+).*\1/).to_a.pop}.flatten.compact.sort_by{|a| a.size}.last)



Regards,

quadz

[reaper]

that guy has come along way from "hello world" programming

I know C, and Bash some.  So I figure I should learn a good scripting language that has more features than bash, that's also easy to do cool stuff like bash.

So i'm looking at: Ruby, Python, or Perl.

what do you think I should pick.  I'm leaning toward Python, because I'm used to C, and I like that style of programming, and hear Python is like that.  But I read that thing on Ruby, where the maker said he taylored it to the programmer, not the computer, and I like that phisophy.  Perl is probably cool, but it looks to different to me, and i don't like different so much

[quadz]

So i'm looking at: Ruby, Python, or Perl.

what do you think I should pick.  I'm leaning toward Python, because I'm used to C, and I like that style of programming, and hear Python is like that.  But I read that thing on Ruby, where the maker said he taylored it to the programmer, not the computer, and I like that phisophy.  Perl is probably cool, but it looks to different to me, and i don't like different so much

It will really come down to personal preference.  Each of the three languages is roughly "as powerful" as the other.

I've written production code in all three languages, and my personal preference is Ruby... A few months ago someone asked me why, and this was my reply:

>>   Can you give a little more insight
>> into how you came to be using ruby as your programming language of
>> choice instead of any of the other languages you mentioned.  I know why
>> you might choose ruby over C/C++ or Java, but what lead you to choose
>> ruby over python, which as far as I can tell is ruby's closest neighbor.

Wow, I wish there were some sort of universal wisdom involved, but
I'm pretty sure it was a combination of pragmatism and a personal
bias toward a particular sort of elegance and aesthetics in language
design that appeals to my own sensibilities.  (In other words, matz kicks
ass at language design!)

Of course, some languages were easier to loathe than others. <grin>
This article pretty well summarizes the sort of horror I felt when
dealing with VB6: http://www.ddj.com/windows/184403996

As for Python, i tended to find the experience more frustrating and
less fun than writing comparable code in Ruby.  Learning Ruby, for me,
involved a lot of "oh, wow, cool I can do that!"  Whereas learning Python
I noticed a lot more, "oh... I'm not allowed to do that."

I last used Python about six years ago, and I understand some things
have evolved or improved since then (don't they have something more
akin to Ruby blocks now?  And list comprehensions?)

But anyway, a few examples of things that rubbed me the wrong way
about Python.  (Note, these may be things that Python people
absolutely love about the language!)

I found the distinction between expressions and statements, and the
restrictions on where one or the other could occur in the syntax, to be
very rigid and unhelpful.

For example, the syntax is:

  if expression:
    statement
  elif expression:
    statement
  else:
    statement

And assignments are not allowed in expressions.

Thus, code that I wanted to write in Python like this, is illegal:

  while match = tagOrTextRegexp.search(html, pos):
      pos = match.end()
      gd = match.groupdict()
      if (val = gd.get('startTag')):
          attrs = parseAttrs(gd['allAttrs'])
          self.handleStartTag(val.lower(), attrs)
      elif (val = gd.get('endTag')):
          self.handleEndTag(val.lower())
      elif (val = gd.get('text')):
          self.handleNonTagText(val)
      elif (val = gd.get('comment')):
          pass  # ARTHUR (to KNIGHTS)  Walk away.  Just ignore them.
      else:
          assert 0, "unexpected match in regexp - supposed to be impossible"

...ended up being written like this:

  while True:
      match = tagOrTextRegexp.search(html, pos)
      if match is None:
          break
      pos = match.end()
      gd = match.groupdict()
      # no assignment-in-conditional sux, Guido
      val = gd.get('startTag')
      if val is not None:
          attrs = parseAttrs(gd['allAttrs'])
          self.handleStartTag(val.lower(), attrs)
      else:
          val = gd.get('endTag')
          if val is not None:
              self.handleEndTag(val.lower())
          else:
              val = gd.get('text')
              if val is not None:
                  self.handleNonTagText(val)
              else:
                  val = gd.get('comment')
                  if val is not None:
                      pass  # ARTHUR (to KNIGHTS)  Walk away.  Just ignore them.
                  else:
                      assert 0, "unexpected match in regexp - supposed to be impossible"

I found this sort of thing very annoying, as can be seen from the note
I left in the code for Guido (von Rossum, Creator of Python.)  <grin>


Another example would be class methods.  (As opposed to instance methods.)

I remember how hacky and inelegant it seemed to me that every instance
method in Python needed to explicitly list the 'self' parameter:

  class Foo:
    def bar(self):
      print "bar!"

  f = Foo()
  f.bar

But when I was learning Python, I had an insight and thought, well, at least
I know how to define class methods!  Just leave off the self parameter!

  class Foo:
    def a_class_method(x,y)
      return x+y

Then I should be able to call it directly on the class, with no instance passed
in:

  Foo.a_class_method(1,2)

Nope.  Just doesn't work.  No way to define class methods.  (Dunno if this
has changed in the past six years or not.)


Anyway, I don't recall many other examples anymore, but I vividly remember
feeling frustrated in this manner often enough while learning Python that I
would actually exclaim, "Guido!!!!" out loud at my desk when it would
happen.  (But I should point out that I was still having fun.  After all, I enjoyed
programming in Python _a lot_ more than Java.)


Finally, I suppose this is a bit silly, but my very first few minutes with
Python gave me a tangible feeling of trepidation when the following
happened:

I fired up Python (whatever the version was back then), and I got an
interactive interpreter.  I was like, yay! cool!

  Python 2.4.1 (#1, May 27 2005, 18:02:40)
  Type "help", "copyright", "credits" or "license" for more information.

Then I tried to quit:

  >>> exit
  'Use Ctrl-D (i.e. EOF) to exit.'
  >>> quit
  'Use Ctrl-D (i.e. EOF) to exit.'
  >>>

And I thought... Oh no.  Somebody actually knew exactly what I
wanted the computer to do - and actually went through the trouble
to program a message to tell me I was doing it wrong.


But again, while these are aspects of Python that rubbed me the
wrong way, I realize that others may and do feel completely
differently.  If Ruby didn't exist, I'd have probably have used
Python for quite a while (maybe moving on to OCaml or Erlang
by now, I dunno.)

Anyway... so those are my own opinions...

Another example of the philosophy behind Ruby's design is portrayed by the "ruby trusts you with sharp knives" comment by Ruby's creator, matz.  (Yukihiro Matsumoto)

The discussion was about open classes in ruby.  Ruby's classes are open, which means in practice one can add new methods to a class elsewhere in the program.

Here's an example of the openness of classes, using the interactive ruby interpreter (irb).

>> class String
>>   def reverse_words
>>     self.split(/\s+/).reverse.join(' ')
>>   end
>> end
=> nil
>> "the quick brown fox jumps over the lazy dawg, yo".reverse_words
=> "yo dawg, lazy the over jumps fox brown quick the"

String is a built-in class in ruby, for dealing with character strings.  Above, we've re-opened the built in class String and added a new method to the class called reverse_words.  After that we can take a normal "string literal" and show that we can now call our new reverse_words method on it.

It is not possible to add new methods to built-in classes in Python.  Python folk have defended Python's closed classes on the grounds that having open classes like ruby does is a very dangerous feature.  One can imagine trying to use multiple different libraries together and each one trying to modify the core classes in incompatible ways, and the mayhem that could result!  And they're right... it is a dangerous feature.. but it's also really really really nice when you need it.  And so I liked what matz had to say about it:

| "open class" is so strong (often too strong), we can break things
| easily. In other word, Ruby trust you to give you sharp knives, where
| Python don't. From the Python point of view, it's wrong, I guess.



Indeed.  Ruby trusts you to give you sharp knives, and Python doesn't.  Again, a matter of personal preference, but something I really like about ruby's design.

If you'd like to give Ruby a try, there's a nifty interactive tutorial program here:

http://hacketyhack.net/


Regards,

quadz