Scala : forcomp assignment Scala : completed

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))
+  }
 
 }