diff options
| -rw-r--r-- | Scala/forcomp/src/main/scala/forcomp/Anagrams.scala | 52 |
1 files changed, 45 insertions, 7 deletions
diff --git a/Scala/forcomp/src/main/scala/forcomp/Anagrams.scala b/Scala/forcomp/src/main/scala/forcomp/Anagrams.scala index 33852d7..cd08b47 100644 --- a/Scala/forcomp/src/main/scala/forcomp/Anagrams.scala +++ b/Scala/forcomp/src/main/scala/forcomp/Anagrams.scala @@ -33,10 +33,13 @@ object Anagrams { * Note: the uppercase and lowercase version of the character are treated as the * same character, and are represented as a lowercase character in the occurrence list. */ - def wordOccurrences(w: Word): Occurrences = ??? + def wordOccurrences(w: Word): Occurrences = + w.toLowerCase.groupBy((element: Char) => element).toList.sortWith(_._1 < _._1).map( x => (x._1, x._2.length)) + // .sorted .map{ case (x,y) => (x, y.length) } /** Converts a sentence into its character occurrence list. */ - def sentenceOccurrences(s: Sentence): Occurrences = ??? + def sentenceOccurrences(s: Sentence): Occurrences = wordOccurrences(s.mkString) + // s.foldLeft("")(_.concat(_)) /** The `dictionaryByOccurrences` is a `Map` from different occurrences to a sequence of all * the words that have that occurrence count. @@ -53,10 +56,10 @@ object Anagrams { * List(('a', 1), ('e', 1), ('t', 1)) -> Seq("ate", "eat", "tea") * */ - lazy val dictionaryByOccurrences: Map[Occurrences, List[Word]] = ??? + lazy val dictionaryByOccurrences: Map[Occurrences, List[Word]] = dictionary groupBy((element: Word) => wordOccurrences(element)) /** Returns all the anagrams of a given word. */ - def wordAnagrams(word: Word): List[Word] = ??? + def wordAnagrams(word: Word): List[Word] = dictionaryByOccurrences(wordOccurrences(word)) /** Returns the list of all subsets of the occurrence list. * This includes the occurrence itself, i.e. `List(('k', 1), ('o', 1))` @@ -80,7 +83,17 @@ object Anagrams { * Note that the order of the occurrence list subsets does not matter -- the subsets * in the example above could have been displayed in some other order. */ - def combinations(occurrences: Occurrences): List[Occurrences] = ??? + def combinations(occurrences: Occurrences): List[Occurrences] = occurrences match { + case Nil => List(List()) + case head :: tail => { + val combs = combinations(tail) + /* keep previous combination untouched */ + combs ::: ( for { + comb <- combs + i <- 1 to head._2 + } yield (head._1, i) :: comb) // combine each Pair with each element cons in comb + } + } /** Subtracts occurrence list `y` from occurrence list `x`. * @@ -92,7 +105,14 @@ object Anagrams { * Note: the resulting value is an occurrence - meaning it is sorted * and has no zero-entries. */ - def subtract(x: Occurrences, y: Occurrences): Occurrences = ??? + def subtract(x: Occurrences, y: Occurrences): Occurrences = { + (y.toMap.foldLeft(x.toMap) ((map, tuple) => { + val newFreq = map(tuple._1) - tuple._2 // freq diff with the corresponding Occurence in map + if (newFreq <= 0) map - tuple._1 // remove Occurence + else map.updated(tuple._1, newFreq) // reduce Occurence count + }) + ).toList.sorted + } /** Returns a list of all anagram sentences of the given sentence. * @@ -134,6 +154,24 @@ object Anagrams { * * Note: There is only one anagram of an empty sentence. */ - def sentenceAnagrams(sentence: Sentence): List[Sentence] = ??? + def sentenceAnagrams(sentence: Sentence): List[Sentence] = { + def iter(occurrences: Occurrences): List[Sentence] = { + if (occurrences.isEmpty) List(List()) + else + for { + // for each combination of the occurences + comb <- combinations(occurrences) + // for each word that exists in the dictionary + word <- dictionaryByOccurrences.getOrElse(comb, List()) + // take all the sentences that come from subtracting from the occurrences + // the occurrence list of the word + sentence <- iter(subtract(occurrences, wordOccurrences(word))) + if !comb.isEmpty + // and yield the concatenation of the word with the sentence + // preserving the invariant of the occurrence list + } yield word :: sentence + } + iter(sentenceOccurrences(sentence)) + } } |