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!

Answer 1

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"]

Answer 2

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").

Answer 3

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