[LRUG] Recursion diversion

[Peter Vandenabeele]

I compared the 5 implementations for correctness and
(naively) for speed.

4 out of 5 where correct (variation in example 2 tolerated)

roland_spec.rb => correct
michael_spec.rb => not correct
peter_spec.rb => correct
tom_spec.rb => correct
dominic_spec.rb => correct

Time to run rspec for a haystack of ("hello world" * 100)
(of course the tests "failed", the results where quite
massive for the last test with three letters in the pattern).

roland_spec.rb => 9.14 s
michael_spec.rb => 0.0087 s (incorrect result)
peter_spec.rb => 5.91 s
tom_spec.rb => 20.05 s
dominic_spec.rb => DNF (with the 100 multiplier)

(dominic's version showed an interesting growth curve of
consumed time with the multipler for the haystack).

The long version of the tests:

  https://gist.github.com/petervandenabeele/7161464

Peter

PS. Yes, I know I should use Benchmark and warm-up, but hey,
it's weekend ...

On Fri, Oct 25, 2013 at 10:19 PM, Dominic Baggott <dominic.baggott at gmail.com
> wrote:

> Here's a recursive version, using Roland's tests (with an amended example
> 2): https://gist.github.com/evilstreak/7161191
>
> Dom
>
>
> On Friday, 25 October 2013 at 14:21, Andrew Stewart wrote:
>
> > Hello El Rug,
> >
> > Given two strings a and b, I would like to find all the occasions where
> the letters of b appear in the same order in a. The result should be an
> array of arrays where each inner array contains the indices of b's matches
> in a.
> >
> > a: 'hello world'
> > b: 'e'
> > result: [ [1] ]
> >
> > a: 'hello world'
> > b: 'l'
> > result: [ [2,3,9] ]
> >
> > a: 'hello world'
> > b: 'el'
> > result: [ [1,2], [1,3], [1,9] ]
> >
> > a: 'hello world'
> > b: 'lo'
> > result: [ [2,4], [2,7], [3,4], [3,7] ]
> >
> > a: 'hello world'
> > b: 'lod'
> > result: [ [2,4,10], [2,7,10], [3,4,10], [3,7,10] ]
> >
> > Hope that makes sense ;)
> >
> > I've been trying this for ages, with iteration and recursion, and I keep
> getting close...but not quite there.
> >
> > Any takers?
> >
> > Cheers,
> > Andy Stewart
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.lrug.org/pipermail/chat-lrug.org/attachments/20131025/9c4140ae/attachment-0003.html>