Ruby programing Quiz

Question

Please help me in solving ruby program

Let us Suppose you have three strings say s1, s2 and s3.Now coding F(s1, s2, s3) should be shortest continuous subsequence of s1 such that it has all the chars of s2 and none of s3. s2 has uniq chars

For example: s1 = "peeeeloisagood", s2 = "le", s3 = "z". Ans = el

Answer 1

This should do it. (Don't be fooled by the fact that I posted before @AFaderDarkly, who has a similar answer. My original answer had a flaw. When I noticed it, I deleted my answer and set about the repair. Darkly posted before I completed the fix, but I didn't know that until I undeleted my amended answer.)

Code

def find_it(s1,s2,s3)
  arr = s1.chars
  good = s2.chars
  bad = s3.chars    
  (good.size..arr.size).each { |n| arr.each_cons(n) { |c|
    return c.join if (good-c).empty? && (c-bad) == c } }
  nil
end

Examples

find_it("peeeeloisagood", "le", "z") #=> "el"
find_it("abcdezfherdzn", "def", "z") #=> "fherd"

Explanation

Let s1, s2 and s3 be as in the second example above:

s1 = "abcdezfherdzn"
s2 = "def"
s3 = "z"

We will first look at substrings of s1 of length 2 (the size of s2). If we find one that contains all the letters of s2, we are finished (as it could not contain any letters of s3). If we do not find a match we look at substrings of s1 of length 3. We are finished if we find a substring that contains all the letters of s2 and none of s3, and so on. If no substring of s1 of any length contains all the letters of s2 and none of the letters of s3, nil is returned.

arr = s1.chars
  #=> ["a", "b", "c", "d", "e", "z", "f", "h", "e", "r", "d", "z", "n"]
good = s2.chars
  #=> ["d", "e", "f"]
bad = s3.chars    
  #=> ["z"]

enum1 = (good.size..arr.size).each
  #=>   (3..13).each
  #=>   #<Enumerator: 3..13:each>

We can convert an enumerator to an array to what it will be passing into its block:

enum1.to_a
  #=> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]

This enumerator first passes 3 into its block and assigns it to the block variable:

n = 3

enum2 = arr.each_cons(n)
  #=>   #<Enumerator: ["a", "b", "c", "d", "e", "z", "f", "h",
  #                    "e", "r", "d", "z", "n"]:each_cons(3)> 
enum2.to_a
  #=> [["a", "b", "c"], ["b", "c", "d"], ["c", "d", "e"], ["d", "e", "z"],
  #    ["e", "z", "f"], ["z", "f", "h"], ["f", "h", "e"], ["h", "e", "r"],
  #    ["e", "r", "d"], ["r", "d", "z"], ["d", "z", "n"]]

It first passes ["a", "b", "c"] into the block and assigns it to the block variable:

c = ["a", "b", "c"]

and executes

return c.join if (good-c).empty? && (c-bad) == c 
  #=> return "abc" if (["d", "e", "f"]-["a", "b", "c"]).empty? &&
  #                   (["a", "b", "c"] - ["z"]) == ["a", "b", "c"]
  #=> return "abc" if (["d", "e", "f"]).empty? && 
                      (["a", "b", "c"]) == ["a", "b", "c"]
  #=> return "abc" if false and true
  #=> false

This continues until the array ["d", "e", "z", "f"] comes up, at which point we obtain:

return c.join if (good-c).empty? && (c-bad) == c 
  #=> return "dezf" if (["d", "e", "f"]-["d", "e", "z", "f"]).empty? &&
                       (["d", "e", "z", "f"]-["z"]) == ["d", "e", "z", "f"]
  #=> return "dezf" if [].empty? && ["d", "e", "f"] == ["d", "e", "z", "f"]
  #=> return "dezf" if true && false
  #=> false

so we reject that substring as well, this time because of the presence of z.

When we get to

c = ["f", "h", "e", "r", "d"]

we obtain:

 return c.join if (good-c).empty? && (c-bad) == c 
   #=> return "fherd" if (["d", "e", "f"]-["f", "h", "e", "r", "d"]).empty? &&
                (["f", "h", "e", "r", "d"]-["z"]) == ["f", "h", "e", "r", "d"]
   #=> return "fherd" if [].empty? &&
                 ["f", "h", "e", "r", "d"] == ["f", "h", "e", "r", "d"]
   #=>return "fherd" if true && true

and therefore return "fherd".

Answer 2

search_string = s1.gsub(/^[^#{s2}]+|[^#{s2}]+$/, '')

The shortest string containing all of s2 will always start and end with a character from s2, so this reduces the search space.

included = s2.chars.to_a.uniq
excluded = s3.chars.to_a.uniq
input = search_string.chars.to_a

This just makes things easier to deal with - all are converted to arrays. We run uniq over the included and excluded arrays to catch edge cases and optimise the algorithm.

Now we can scan through the string, brute-force style:

(included.length..search_string.length).each do |l|

The shortest string can only be as short as the set of included characters, so we set up a search window moving through the string, starting at this length and moving up to the full length of the string. l is the window length.

    input.each_cons(l) do |s|

Move the window through the input array.

      if (included - s).length == 0 && excluded == excluded - s

Check if the string matches by subtracting arrays.

      puts s.join

This will show all matches, shortest first.

    end
  end
end

Putting it all together:

def find_string(s1, s2, s3)
  search_string = s1.gsub(/^[^#{s2}]+|[^#{s2}]+$/, '')
  included = s2.chars.to_a.uniq
  excluded = s3.chars.to_a.uniq
  input = search_string.chars.to_a

  (included.length..search_string.length).each do |l|
    input.each_cons(l) do |s|
      if (included - s).length == 0 && excluded == excluded - s
        return s.join
      end
    end
  end
  ""
end   

find_string  "pleeeesoisalzesgood", "les", "z"
# => "leeees"

find_string  "pleeeesoisalesgood", "les", "z"
# => "les"

find_string  "pleeeesoisalesgood", "lees", "z" # Without the .uniq on included this would return 'sale'
# => "les" 

find_string  "peeeeloisagood", "le", "z"
# => "el"