The challenge

A Noun Phrase is a phrase that can be replaced by a pronoun [he/she/it].

For example, in the sentence:

a girl ate the cookie

“A girl” is a Noun Phrase, so we can say “she ate the cookie.” “The cookie” is also a Noun Phrase, so we can even say “she ate it.”

Both of these Noun Phrases are made up of an auxialliary (aux) [the/a] followed by a Noun (N) [girl/cookie].

More complicated Noun Phrases can also include an arbitrary number of adjectives (adj). For example:

a big tall scary girl ate the cookie

where “big”, “tall”, and “scary” are all adjectives.

For our simplified model, we will define a Noun Phrase as an auxiliary, followed by 0 or more adjectives, followed by a Noun.

Write a function that takes a sentence (as a string of words separated by spaces), a list of pronouns, and a dictionary (maping words to the grammatical categories aux, adj, and N). Return the sentcnce with all Noun Phrases replaced by pronouns, in the order given.

Assume:

  • sentences will contain only lower-case letters and spaces (no puctuation)
  • any words not inlcuded in the dictionary are not auxilliaries, adjectives, or nouns
  • the number of pronouns provided will be equal to the number of Noun Phrases in the sentence

The solution in Golang

Option 1:

package solution
import "strings"
func ReplaceNounPhrases(str string, pro []string, dict map[string]string) string{
  words, phrase := strings.Fields(str), ""
  state, noun := 0, 0
  if len(pro) < 1 {return str}
  for _, word := range words {
    if _, ok := dict[word]; !ok {state = 0; continue}
    if state == 0 && dict[word] != "aux" {continue}
    if state == 1 {
      if dict[word] == "adj" {phrase += " " + word}
      if dict[word] == "N" {
        phrase += " " + word
        str = strings.Replace(str, phrase, pro[noun], 1)
        if noun < len(pro) - 1 {noun++}
        state = 0
      }
    }
    if dict[word] == "aux" {state, phrase = 1, word}
  }
  return str
}

Option 2:

package solution
import "strings"
func ReplaceNounPhrases(sentence string, pronouns []string, dictionary map[string]string) string {
  words, grams, res := strings.Split(sentence, " "), []string{}, []string{}  
  for _, word := range words { grams = append(grams, dictionary[word]) }
  n, i, j, k := len(words), 0, 0, 0
  for i<n {
    word:=words[i]
    if i<n-1 && grams[i]=="aux" {
      j = i+1
      for j<n && grams[j]=="adj" { j++ }
      if j<n && grams[j]=="N" { word = pronouns[k]; k++; i = j+1 } else { i++ }  
    } else { i++ }
    res = append(res, word)
  }
  return strings.Join(res, " ")
}

Option 3:

package solution
import "strings"
func ReplaceNounPhrases(sentence string, pronouns []string, dictionary map[string]string) string {
  words := strings.Split(sentence, " ")
  aux := -1
  var pronoun int
  for i := 0; i < len(words); i++ {
    if _, ok := dictionary[words[i]]; !ok {
      aux = -1
    } else if dictionary[words[i]] == "aux" {
      aux = i
    } else if dictionary[words[i]] == "N" && aux != -1 {
      left := append(words[:aux], pronouns[pronoun])
      right := words[aux+i-aux+1:]
      words = append(left, right...)
      pronoun++
      aux = -1
      i = aux
    }
  }
  return strings.Join(words, " ")
}

Test cases to validate our solution

package solution_test
import (
  . "github.com/onsi/ginkgo"
  . "github.com/onsi/gomega"
)

var dictionary = map[string]string{
  "a": "aux",
  "the": "aux",
  "girl" : "N",
  "cookie" : "N",
  "big" : "adj",
  "tall" : "adj",
  "scary" : "adj",
}

var _ = Describe("Test Example", func() {
  It("#1", func() {
    Expect(ReplaceNounPhrases("a girl", []string{"she"}, dictionary)).To(Equal("she"))
  })
  
   It("#2", func() {
    Expect(ReplaceNounPhrases("a girl ate the cookie", []string{"she", "it"}, dictionary)).To(Equal("she ate it"))
  })
  
  It("#3", func() {
    Expect(ReplaceNounPhrases("a a a big big a cookie", []string{"it"}, dictionary)).To(Equal("a a a big big it"))
  })
  
  It("#4", func() {
    Expect(ReplaceNounPhrases("a scary girl", []string{"she"}, dictionary)).To(Equal("she"))
  })
  
  It("#5", func() {
    Expect(ReplaceNounPhrases("a big tall scary girl ate the big cookie", []string{"she", "it"}, dictionary)).To(Equal("she ate it"))
  })
  
})