CODEWITHSUNDEEP
javascriptalgorithmrecursion
Londeren
Londeren

Reputation: 3341

All combinations of a nested object

I have the following string

Hello, have a {good {night|day}|wonderful {evening|morning}} and {goodbye|bye}!

And I'm trying to generate all the combinations of the strings. For example: Hello, have a good day and bye!, Hello, have a wonderful evening and goodbye! etc.

Rules: {one|two} means write one on the first time and two on the second. As you can see these conditions can be nested any number of times.

I've parsed this to the following structure

[
 "Hello, have a ",
 {
  "or": [
   [
    "good ",
    {
     "or": [
      "night",
      "day"
     ]
    }
   ],
   [
    "wonderful ",
    {
     "or": [
      "evening",
      "morning"
     ]
    }
   ]
  ]
 },
 " and ",
 {
  "or": [
   "goodbye",
   "bye"
  ]
 },
 "!"
]

And now I can't figure out how to generate all the strings from this structure.

Upvotes: 2

Views: 97

Answers (1)

maraca
maraca

Reputation: 8858

You can generate the sentences directly when parsing, basically you just have to go through all the possibilities:

function generateSentences(s) {
    const start = s.indexOf('{') + 1
    if (start == 0)
        return [s]
    for (let i = start, braces = 1;; i++)
        if (s[i] == '{')
            braces++
        else if (s[i] == '}')
            if (--braces == 0) {
                const options = generateOptions(s.substring(start, i)),
                      posts = generateSentences(s.substr(i + 1)),
                      pre = s.substring(0, start - 1)
                let sentences = []
                for (const option of options)
                    for (const post of posts)
                        sentences.push(pre + option + post)
                return sentences
            }
}
function generateOptions(options) {
    let braces = 0, start = 0, sentences = []
    for (let i = 0; i < options.length; i++)
        if (options[i] == '{')
            braces++
        else if (options[i] == '}')
            braces--
        else if (options[i] == '|' && braces == 0) {
            sentences = sentences.concat(generateSentences(options.substring(start, i)))
            start = i + 1
        }
    return sentences.concat(generateSentences(options.substring(start, options.length)))
}
console.log(generateSentences('Hello, have a {good {night|day}|wonderful {evening|morning}}!'))
console.log(generateSentences('hello, {|111|{!2!|@2@} 222|33 {@333@|444} 3333}! 555. {666|{777 {888|999}}} end...'))

Upvotes: 1

Related Questions