[LRUG] Recursion diversion

[Jason Lee]

Hey Peter,

here's my late night effort,  https://gist.github.com/jlsync/7162908


thanks.
Jason.



On Fri, Oct 25, 2013 at 10:12 PM, Peter Vandenabeele <peter at vandenabeele.com
> wrote:

> 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
>>
>
> _______________________________________________
> Chat mailing list
> Chat at lists.lrug.org
> http://lists.lrug.org/listinfo.cgi/chat-lrug.org
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.lrug.org/pipermail/chat-lrug.org/attachments/20131025/bc47e3ae/attachment-0003.html>