Skip to content

Instantly share code, notes, and snippets.

@evilstreak
Last active December 26, 2015 13:49
Show Gist options
  • Save evilstreak/7161191 to your computer and use it in GitHub Desktop.
Save evilstreak/7161191 to your computer and use it in GitHub Desktop.
require 'rspec/autorun'
module DominicRecursion
def self.letters(haystack, needles, index = 0)
# base case: if the letters to match are empty, we've succeeded
return [[]] if needles.empty?
# base case: if the word to match in is empty, we've failed
return [] if haystack.empty?
result = []
if needles[0] == haystack[0]
tail = letters(haystack[1..-1], needles[1..-1], index + 1)
result += tail.map { |t| [index] + t }
end
result + letters(haystack[1..-1], needles, index + 1)
end
end
module DominicLists
def self.letters(haystack, needles)
indices = Hash[haystack.each_char.with_index.group_by { |(char, _)| char }.map { |(char, values)| [char, values.map { |(_, index)| index }] }]
results = indices[needles[0]].map { |i| [i] }
needles[1..-1].each_char do |char|
results = results.flat_map do |r|
indices[char].drop_while { |i| i < r.last }.map { |i| r + [i] }
end
end
results
end
end
[DominicRecursion, DominicLists].each do |c|
describe "#{c.name}: letters" do
let(:a) { "hello world" }
specify "example 1" do
c.letters(a, "e").should == [[1]]
end
specify "example 2" do
c.letters(a, "l").should == [[2],[3],[9]]
end
specify "example 3" do
c.letters(a, "el").should == [[1,2], [1,3], [1,9]]
end
specify "example 4" do
c.letters(a, "lo").should == [[2,4], [2,7], [3,4], [3,7]]
end
specify "example 5" do
c.letters(a, "lod").should == [ [2,4,10], [2,7,10], [3,4,10], [3,7,10] ]
end
end
end
@evilstreak
Copy link
Author

Using the benchmarking code from https://gist.github.com/textgoeshere/02fd396e56ca8a8d2efe

Desktop$ ruby letters-benchmarking.rb
Running each test once. Test will take about 2 minutes.
DominicLists is similar to Dave
Dave is faster than Jason by 2x ± 1.0
Jason is similar to Peter
Peter is faster than DominicRecursion by 4x ± 1.0
DominicRecursion is similar to Tom
Tom is faster than Roland by 3x ± 1.0
Roland is faster than DominicOriginal by 2x ± 1.0

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment