Ruby creating sentences with substrings while maintaining order

Question

I am currently working on a Ruby problem in which I am essentially creating my own language. Below (nouns, verbs, articles) can be thought as words. However, in order to create a valid sentence, I must have a verb, a noun, or at least 2 articles.

Nouns: "abcd", "c", "def", "h", "ij, "cde"

Verbs: "bc", "fg", "g", "hij", "bcd"

Articles: "a", "ac", "e"

So what I am trying to do is basically write a method that takes a string and returns all possible valid sentences (while keeping characters in the same order and inserting a space between the words)

ex. input = "abcdefg" returns the list

[ "a bc def g", "a bcd e fg", "abcd e fg"]

So I tried breaking down the problem and this is what I have so far

alpha = "abcdefg"



nouns = ["abcd", "c", "def", "h", "ij", "cde"]
verbs = ["bc", "fg", "g", "hij", "bcd"]
articles = ["a", "ac", "e"]

verbArray = [];
nounArray = [];
articleArray = [];

nouns.each do |item|
  if alpha.include?(item)
    nounArray << item
  end
end

verbs.each do |item|
  if alpha.include?(item)
    verbArray << item
  end
end

articles.each do |item|
  if alpha.include?(item)
    articleArray << item
  end
end


puts nounArray.inspect => ["abcd", "c", "def", "cde"]
puts verbArray.inspect => ["bc", "fg", "g", "bcd"]
puts articleArray.inspect => ["a", "e"]

My thought process was that I first wanted to get all possible combinations for each of the words (nouns, verb, article). I am not sure if this is the most efficient way to approach this problem but beyond this step I was trying without much success to form ordered sentences.

I've been searching stacks and other websites for types of combinations/sorting techniques plus I am trying to avoid using regex at the moment. I would honestly appreciate any direction/feedback as how to continue my journey to solving this problem.Thank you for your time!

Also, I must have a verb, a noun, or at least 2 articles. is ambiguous. — Eric Duminil
– Eric Duminil, Commented Feb 28, 2017 at 18:59
The example values look quite cryptic. Is there a good reason not to use actual (or maybe fake but pronounceable) nouns, verbs, and articles? — Stefan
– Stefan, Commented Feb 28, 2017 at 19:08
There is no restriction on order for a verb, noun, or article as long as the original order remains the same — joshh45
– joshh45, Commented Feb 28, 2017 at 20:29

Eric Duminil · Accepted Answer · 2017-02-28 19:24:50Z

1

It is possible without Regex, but you'll have a hard time writing anything without recursion :

grammar = {
  noun: ["abcd", "c", "def", "h", "ij", "cde"],
  verb: ["bc", "fg", "g", "hij", "bcd"],
  article:  ["a", "ac", "e"]}

def find_sentences(text, grammar, head = [], structure = [])
  if text.empty?
    if structure.include?(:verb) || structure.include?(:noun) || structure.count(:article) > 2
      puts "Sentence found : "
      puts head.join(' ')
      puts structure.join(' ')
      puts
    end
  else
    grammar.each do |type, words|
      words.each do |word|
        if text.start_with?(word)
          find_sentences(text.slice(word.size..-1), grammar, head + [word], structure + [type])
        end
      end
    end
  end
end

find_sentences("abcdefg", grammar)

It outputs :

Sentence found :
abcd e fg
noun article verb

Sentence found :
a bc def g
article verb noun verb

Sentence found :
a bcd e fg
article verb article verb

edited Feb 28, 2017 at 19:24

answered Feb 28, 2017 at 19:17

Eric Duminil

54.6k10 gold badges80 silver badges134 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Cary Swoveland Over a year ago

Good solution, Eric. You might want to pare down grammar as an optimization before doing anything else:

str = "abcdefg"; gram = grammar.each_with_object({}) { |(k,v),h| h[k] = v.select { |s| str.include?(s) } } #=> {:noun=>["abcd", "c", "def", "cde"], :verb=>["bc", "fg", "g", "bcd"], :article=>["a", "e"]}

.

Eric Duminil Over a year ago

Thanks, good idea. Given the OP code, I didn't want to invest too much time either.

Cary Swoveland Over a year ago

I wrote another recursive solution, but it's nowhere near as nice as yours. Your solution will have some take-aways for me.

Cary Swoveland · Accepted Answer · 2017-03-01 07:34:31Z

1

Here's another way of writing a recursive method.

def all_sentences(str, grammar)
  gram = grammar.each_with_object({}) { |(k,v),h|
    v.select { |s| str.include?(s) }.each { |s| h[s] = k } }
  recurse(str, gram.keys, gram, '')
end

def recurse(str, parts, gram, partial)
  p = partial.delete(' ')
  parts.each_with_object([]) do |part, arr|
    combine = p + part
    next unless str.start_with?(combine)
    s = (partial + ' ' + part).lstrip
    if combine.size == str.size
      arr << s if valid?(s, gram)
    else
      arr.concat(recurse(str, parts, gram, s))
    end
  end
end

def valid?(candidate, gram)
  arr = candidate.split
  arr.any? { |s| [:noun, :verb].include?(gram[s]) } ||
    arr.count { |s| gram[s] == :article } > 1
end

Example

grammar = {
  noun: ["abcd", "c", "def", "h", "ij", "cde"],
  verb: ["bc", "fg", "g", "hij", "bcd"],
  article:  ["a", "ac", "e"]
}

str = "abcdefg"

all_sentences(str, grammar)
  #=> ["abcd e fg", "a bc def g", "a bcd e fg"]

Note

For the example, the hash gram is computed as follows.

gram = grammar.each_with_object({}) { |(k,v),h|
  v.select { |s| str.include?(s) }.each { |s| h[s] = k } }
  #=> {"abcd"=>:noun, "c"=>:noun, "def"=>:noun, "cde"=>:noun,
  #    "bc"=>:verb, "fg"=>:verb, "g"=>:verb, "bcd"=>:verb,
  #    "a"=>:article, "e"=>:article}

Notice that as well as mapping words into parts of speech, I have removed a few "words" that cannot be part of the "sentence" str.

It strikes me that

words_to_pos = grammar.each_with_object({}) { |(k,v),h| v.each { |s| h[s] = k } }
  #=> {"abcd"=>:noun, "c"=>:noun, "def"=>:noun, "h"=>:noun, "ij"=>:noun,
  #    "cde"=>:noun, "bc"=>:verb, "fg"=>:verb, "g"=>:verb, "hij"=>:verb,
  #    "bcd"=>:verb, "a"=>:article, "ac"=>:article, "e"=>:article}

would have been a more convenient data structure than the original grammar ("pos" for "part of speech").

edited Mar 1, 2017 at 7:34

answered Mar 1, 2017 at 7:11

Cary Swoveland

111k6 gold badges69 silver badges105 bronze badges

2 Comments

Eric Duminil Over a year ago

"set" is a noun and a verb, so your structure might not work.

Cary Swoveland Over a year ago

Eric, joshh45's language is called "Bishna". One of it's characteristics (as in the example) is that every word is exactly one part of speech (similar to Umzergi). If the language were changed to permit a word to be more than one part of speech we could deal with that by merely modifying grammar: remove all but one instance of each word, with preference for the one remaining being noun or verb, then article.

aqfaridi · Accepted Answer · 2017-04-29 20:02:43Z

solved using recursion and lambda in ruby :

@nouns = ["abcd", "c", "def", "h", "ij", "cde"]
@verbs = ["bc", "fg", "g", "hij", "bcd"]
@articles = ["a", "ac", "e"]
@return_arr = []
def solve(idx, hash, ans = [])
    # base case
    if (idx >= $str.length) and  ( hash['vs'] >= 1) and (hash['ns'] >= 1 or hash['as'] >= 2)
        @return_arr << ans.join(" ")
        return
    end
    # define lamda to do common operation
    execute = lambda do |var, i|
        hash[var] += 1
        ans << $str[idx..i]
        solve(i+1, hash, ans)
        ans.pop
        hash[var] -= 1
    end
    #check for nouns, verbs, articles
    $str.each_char.with_index do |c,i|
        next if i < idx
        execute.call('ns', i) if @nouns.include? $str[idx..i]
        execute.call('vs', i) if @verbs.include? $str[idx..i]
        execute.call('as', i)if @articles.include? $str[idx..i]
    end
end

$str = gets.strip
hash = Hash.new(0)
solve(0, hash)
p @return_arr

Input : abcdefg

Output : ["a bc def g", "a bcd e fg", "abcd e fg"]

Collectives™ on Stack Overflow

Ruby creating sentences with substrings while maintaining order

3 Answers 3

3 Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related