Comparing some recursive and array product implementations

gistfile1.txt

Taking 4 implementations (code below)

```
✗ ls -l *.rb
-rw-r--r--  1 peter_v  staff   825 Oct 25 22:16 roland_spec.rb
-rw-r--r--  1 peter_v  staff   807 Oct 25 22:17 michael_spec.rb
-rw-r--r--  1 peter_v  staff  1515 Oct 25 22:17 peter_spec.rb
-rw-r--r--  1 peter_v  staff   825 Oct 25 22:18 tom_spec.rb
```

3 out of produce the expected results (variation allowed in example 2):

```
➜  spec git:(master) ✗ rspec roland_spec.rb 
.....

Finished in 0.00101 seconds
5 examples, 0 failures
➜  spec git:(master) ✗ rspec michael_spec.rb 
..FFF

Failures:

  1) letters example 3
     Failure/Error: letters(a, "el").should == [[1,2], [1,3], [1,9]]
       expected: [[1, 2], [1, 3], [1, 9]]
            got: [[1], [2, 3, 9]] (using ==)
     # ./michael_spec.rb:32:in `block (2 levels) in <top (required)>'

  2) letters example 4
     Failure/Error: letters(a, "lo").should == [[2,4], [2,7], [3,4], [3,7]]
       expected: [[2, 4], [2, 7], [3, 4], [3, 7]]
            got: [[2, 3, 9], [4, 7]] (using ==)
     # ./michael_spec.rb:36:in `block (2 levels) in <top (required)>'

  3) letters example 5
     Failure/Error: letters(a, "lod").should == [ [2,4,10], [2,7,10], [3,4,10], [3,7,10] ]
       expected: [[2, 4, 10], [2, 7, 10], [3, 4, 10], [3, 7, 10]]
            got: [[2, 3, 9], [4, 7], [10]] (using ==)
     # ./michael_spec.rb:40:in `block (2 levels) in <top (required)>'

Finished in 0.00111 seconds
5 examples, 3 failures

Failed examples:

rspec ./michael_spec.rb:31 # letters example 3
rspec ./michael_spec.rb:35 # letters example 4
rspec ./michael_spec.rb:39 # letters example 5
➜  spec git:(master) ✗ rspec peter_spec.rb 
.....

Finished in 0.00101 seconds
5 examples, 0 failures
➜  spec git:(master) ✗ rspec tom_spec.rb 
.....

Finished in 0.00118 seconds
5 examples, 0 failures
```

As an _extremely_ naive speed test, changing the
test string to ("hello world" * 100) and running
rspec again on all 4 yields:

```
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
```


```
➜  spec git:(master) ✗ cat roland_spec.rb
```
```ruby
require 'rspec/autorun'

##
# find letter combinations recursively

def letters(a, b)
  indexes = b.each_char.map do |letter|
    a.each_char.each_with_index.select {|l, _| l == letter }.map {|_, i| i }
  end

  start = indexes.shift

  if indexes.empty?
    [start]
  else
    start.product(*indexes).select {|x| x == x.sort }
  end
end

describe "letters" do
  let(:a) { "hello world" * 100 }

  specify "example 1" do
    letters(a, "e").should == [[1]]
  end

  specify "example 2" do
    letters(a, "l").should == [[2, 3, 9]]
  end

  specify "example 3" do
    letters(a, "el").should == [[1,2], [1,3], [1,9]]
  end

  specify "example 4" do
    letters(a, "lo").should == [[2,4], [2,7], [3,4], [3,7]]
  end

  specify "example 5" do
    letters(a, "lod").should == [ [2,4,10], [2,7,10], [3,4,10], [3,7,10] ]
  end
end
```

```
➜  spec git:(master) ✗ cat michael_spec.rb 
```
```ruby
require 'rspec/autorun'

##
# find letter combinations recursively

def get_indexes(needle, haystack)
  (0...haystack.length).find_all { |i| haystack[i,1] == needle }
end

def map_indexes(needle, haystack)
  needle.split('').map do |nee|
    get_indexes nee, haystack
  end
end

def letters(a, b)
 map_indexes(b, a)
end

describe "letters" do
  let(:a) { "hello world" * 100 }

  specify "example 1" do
    letters(a, "e").should == [[1]]
  end

  specify "example 2" do
    letters(a, "l").should == [[2, 3, 9]]
  end

  specify "example 3" do
    letters(a, "el").should == [[1,2], [1,3], [1,9]]
  end

  specify "example 4" do
    letters(a, "lo").should == [[2,4], [2,7], [3,4], [3,7]]
  end

  specify "example 5" do
    letters(a, "lod").should == [ [2,4,10], [2,7,10], [3,4,10], [3,7,10] ]
  end
end
```

```
➜  spec git:(master) ✗ cat peter_spec.rb 
```
```ruby
require 'rspec/autorun'

##
# find letter combinations recursively
def letters(text, pattern)
  start = 0
  result = find_all_from_pattern(text, start, pattern)
end

def find_all_from_pattern(text, from, pattern)
  letter = pattern[0]
  remainder = pattern[1..-1]
  r = find_all_from_letter(text, from, letter)
  if remainder.size > 0
    r.each_with_object([]) do |previous, results|
      one_deeper = find_all_from_pattern(text, (previous+1), remainder)
      one_deeper.each do |deeper|
        results  << ([previous] + deeper)
      end
    end
  else # leaf node, end of iteration
    r
  end.map{ |e| Array(e) }
end

def find_all_from_letter(text, from, letter)
  [].tap do |result|
    while(match = find_one_from_letter(text, from, letter))
      result << match
      from = match + 1
    end
  end
end

def find_one_from_letter(text, from, letter)
  return nil unless letter
  index = text[from..-1].index(letter)
  index && (index + from)
end

describe "letters" do
  let(:a) { "hello world" * 100 }

#  specify "example 0" do
#    letters(a, "z").should == []
#  end

  specify "example 1" do
    letters(a, "e").should == [[1]]
  end

  specify "example 2" do
    letters(a, "l").should == [[2], [3], [9]]
  end

  specify "example 3" do
    letters(a, "el").should == [[1,2], [1,3], [1,9]]
  end

  specify "example 4" do
    letters(a, "lo").should == [[2,4], [2,7], [3,4], [3,7]]
  end

  specify "example 5" do
    letters(a, "lod").should == [ [2,4,10], [2,7,10], [3,4,10], [3,7,10] ]
  end
end
```

```
➜  spec git:(master) ✗ cat tom_spec.rb 
```
```ruby
require 'rspec/autorun'

def letters(a, b, starting_at = 0)
  if b.empty?
    [[]]
  else
    a.each_char.with_index.drop(starting_at).
      select { |c, _| c == b[0] }.map(&:last).
      flat_map { |i| letters(a, b[1..-1], i.succ).map(&[i].method(:+)) }
  end
end

describe "letters" do
  let(:a) { "hello world" * 100 }

#  specify "example 0" do
#    letters(a, "z").should == []
#  end

  specify "example 1" do
    letters(a, "e").should == [[1]]
  end

  specify "example 2" do
    letters(a, "l").should == [[2], [3], [9]]
  end

  specify "example 3" do
    letters(a, "el").should == [[1,2], [1,3], [1,9]]
  end

  specify "example 4" do
    letters(a, "lo").should == [[2,4], [2,7], [3,4], [3,7]]
  end

  specify "example 5" do
    letters(a, "lod").should == [ [2,4,10], [2,7,10], [3,4,10], [3,7,10] ]
  end
end
```