From a2c0ad269f3bb3740e86da29562affd7dbf7873e Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jeremy@asynk.ch>
Date: Fri, 17 May 2013 16:16:10 +0200
Subject: Scala : forcomp assignment Scala : completed
---
.../forcomp/src/main/scala/forcomp/Anagrams.scala | 52 +++++++++++++++++++---
1 file 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))
+ }
}
--
cgit v1.1-2-g2b99