<div dir="ltr"><div><div><div>I compared the 5 implementations for correctness and<br>(naively) for speed.<br><br></div><div>4 out of 5 where correct (variation in example 2 tolerated)<br><pre><span style="font-family:courier new,monospace"><code>roland_spec.rb => correct<br>
michael_spec.rb => not correct<br>peter_spec.rb => correct<br>tom_spec.rb => correct<br>dominic_spec.rb => correct</code></span><br></pre></div>Time to run rspec for a haystack of ("hello world" * 100)<br>
</div><div>(of course the tests "failed", the results where quite<br>massive for the last test with three letters in the pattern).<br></div><div><pre><span style="font-family:courier new,monospace"><code>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)</code></span></pre>(dominic's version showed an interesting growth curve of<br></div><div>consumed time with the multipler for the haystack).<br><br></div>The long version of the tests:<br>
<br>  <a href="https://gist.github.com/petervandenabeele/7161464">https://gist.github.com/petervandenabeele/7161464</a><br><br></div>Peter<br><div class="gmail_extra"><br></div><div class="gmail_extra">PS. Yes, I know I should use Benchmark and warm-up, but hey,<br>
it's weekend ...<br><br></div><div class="gmail_extra"><div class="gmail_quote">On Fri, Oct 25, 2013 at 10:19 PM, Dominic Baggott <span dir="ltr"><<a href="mailto:dominic.baggott@gmail.com" target="_blank">dominic.baggott@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Here's a recursive version, using Roland's tests (with an amended example 2): <a href="https://gist.github.com/evilstreak/7161191" target="_blank">https://gist.github.com/evilstreak/7161191</a><br>

<br>
Dom<br>
<div><div class="h5"><br>
<br>
On Friday, 25 October 2013 at 14:21, Andrew Stewart wrote:<br>
<br>
> Hello El Rug,<br>
><br>
> 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.<br>

><br>
> a: 'hello world'<br>
> b: 'e'<br>
> result: [ [1] ]<br>
><br>
> a: 'hello world'<br>
> b: 'l'<br>
> result: [ [2,3,9] ]<br>
><br>
> a: 'hello world'<br>
> b: 'el'<br>
> result: [ [1,2], [1,3], [1,9] ]<br>
><br>
> a: 'hello world'<br>
> b: 'lo'<br>
> result: [ [2,4], [2,7], [3,4], [3,7] ]<br>
><br>
> a: 'hello world'<br>
> b: 'lod'<br>
> result: [ [2,4,10], [2,7,10], [3,4,10], [3,7,10] ]<br>
><br>
> Hope that makes sense ;)<br>
><br>
> I've been trying this for ages, with iteration and recursion, and I keep getting close...but not quite there.<br>
><br>
> Any takers?<br>
><br>
> Cheers,<br>
> Andy Stewart</div></div></blockquote></div></div></div>