diff options
Diffstat (limited to 'Scala/forcomp/src/main/scala')
| -rw-r--r-- | Scala/forcomp/src/main/scala/common/package.scala | 40 | ||||
| -rw-r--r-- | Scala/forcomp/src/main/scala/forcomp/Anagrams.scala | 139 | ||||
| -rw-r--r-- | Scala/forcomp/src/main/scala/forcomp/package.scala | 24 |
3 files changed, 203 insertions, 0 deletions
diff --git a/Scala/forcomp/src/main/scala/common/package.scala b/Scala/forcomp/src/main/scala/common/package.scala new file mode 100644 index 0000000..f1c74c3 --- /dev/null +++ b/Scala/forcomp/src/main/scala/common/package.scala @@ -0,0 +1,40 @@ +import java.io.File + +package object common { + + /** An alias for the `Nothing` type. + * Denotes that the type should be filled in. + */ + type ??? = Nothing + + /** An alias for the `Any` type. + * Denotes that the type should be filled in. + */ + type *** = Any + + + /** + * Get a child of a file. For example, + * + * subFile(homeDir, "b", "c") + * + * corresponds to ~/b/c + */ + def subFile(file: File, children: String*) = { + children.foldLeft(file)((file, child) => new File(file, child)) + } + + /** + * Get a resource from the `src/main/resources` directory. Eclipse does not copy + * resources to the output directory, then the class loader cannot find them. + */ + def resourceAsStreamFromSrc(resourcePath: List[String]): Option[java.io.InputStream] = { + val classesDir = new File(getClass.getResource(".").toURI) + val projectDir = classesDir.getParentFile.getParentFile.getParentFile.getParentFile + val resourceFile = subFile(projectDir, ("src" :: "main" :: "resources" :: resourcePath): _*) + if (resourceFile.exists) + Some(new java.io.FileInputStream(resourceFile)) + else + None + } +} diff --git a/Scala/forcomp/src/main/scala/forcomp/Anagrams.scala b/Scala/forcomp/src/main/scala/forcomp/Anagrams.scala new file mode 100644 index 0000000..33852d7 --- /dev/null +++ b/Scala/forcomp/src/main/scala/forcomp/Anagrams.scala @@ -0,0 +1,139 @@ +package forcomp + +import common._ + +object Anagrams { + + /** A word is simply a `String`. */ + type Word = String + + /** A sentence is a `List` of words. */ + type Sentence = List[Word] + + /** `Occurrences` is a `List` of pairs of characters and positive integers saying + * how often the character appears. + * This list is sorted alphabetically w.r.t. to the character in each pair. + * All characters in the occurrence list are lowercase. + * + * Any list of pairs of lowercase characters and their frequency which is not sorted + * is **not** an occurrence list. + * + * Note: If the frequency of some character is zero, then that character should not be + * in the list. + */ + type Occurrences = List[(Char, Int)] + + /** The dictionary is simply a sequence of words. + * It is predefined and obtained as a sequence using the utility method `loadDictionary`. + */ + val dictionary: List[Word] = loadDictionary + + /** Converts the word into its character occurence list. + * + * 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 = ??? + + /** Converts a sentence into its character occurrence list. */ + def sentenceOccurrences(s: Sentence): Occurrences = ??? + + /** The `dictionaryByOccurrences` is a `Map` from different occurrences to a sequence of all + * the words that have that occurrence count. + * This map serves as an easy way to obtain all the anagrams of a word given its occurrence list. + * + * For example, the word "eat" has the following character occurrence list: + * + * `List(('a', 1), ('e', 1), ('t', 1))` + * + * Incidentally, so do the words "ate" and "tea". + * + * This means that the `dictionaryByOccurrences` map will contain an entry: + * + * List(('a', 1), ('e', 1), ('t', 1)) -> Seq("ate", "eat", "tea") + * + */ + lazy val dictionaryByOccurrences: Map[Occurrences, List[Word]] = ??? + + /** Returns all the anagrams of a given word. */ + def wordAnagrams(word: Word): List[Word] = ??? + + /** Returns the list of all subsets of the occurrence list. + * This includes the occurrence itself, i.e. `List(('k', 1), ('o', 1))` + * is a subset of `List(('k', 1), ('o', 1))`. + * It also include the empty subset `List()`. + * + * Example: the subsets of the occurrence list `List(('a', 2), ('b', 2))` are: + * + * List( + * List(), + * List(('a', 1)), + * List(('a', 2)), + * List(('b', 1)), + * List(('a', 1), ('b', 1)), + * List(('a', 2), ('b', 1)), + * List(('b', 2)), + * List(('a', 1), ('b', 2)), + * List(('a', 2), ('b', 2)) + * ) + * + * 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] = ??? + + /** Subtracts occurrence list `y` from occurrence list `x`. + * + * The precondition is that the occurrence list `y` is a subset of + * the occurrence list `x` -- any character appearing in `y` must + * appear in `x`, and its frequency in `y` must be smaller or equal + * than its frequency in `x`. + * + * Note: the resulting value is an occurrence - meaning it is sorted + * and has no zero-entries. + */ + def subtract(x: Occurrences, y: Occurrences): Occurrences = ??? + + /** Returns a list of all anagram sentences of the given sentence. + * + * An anagram of a sentence is formed by taking the occurrences of all the characters of + * all the words in the sentence, and producing all possible combinations of words with those characters, + * such that the words have to be from the dictionary. + * + * The number of words in the sentence and its anagrams does not have to correspond. + * For example, the sentence `List("I", "love", "you")` is an anagram of the sentence `List("You", "olive")`. + * + * Also, two sentences with the same words but in a different order are considered two different anagrams. + * For example, sentences `List("You", "olive")` and `List("olive", "you")` are different anagrams of + * `List("I", "love", "you")`. + * + * Here is a full example of a sentence `List("Yes", "man")` and its anagrams for our dictionary: + * + * List( + * List(en, as, my), + * List(en, my, as), + * List(man, yes), + * List(men, say), + * List(as, en, my), + * List(as, my, en), + * List(sane, my), + * List(Sean, my), + * List(my, en, as), + * List(my, as, en), + * List(my, sane), + * List(my, Sean), + * List(say, men), + * List(yes, man) + * ) + * + * The different sentences do not have to be output in the order shown above - any order is fine as long as + * all the anagrams are there. Every returned word has to exist in the dictionary. + * + * Note: in case that the words of the sentence are in the dictionary, then the sentence is the anagram of itself, + * so it has to be returned in this list. + * + * Note: There is only one anagram of an empty sentence. + */ + def sentenceAnagrams(sentence: Sentence): List[Sentence] = ??? + +} diff --git a/Scala/forcomp/src/main/scala/forcomp/package.scala b/Scala/forcomp/src/main/scala/forcomp/package.scala new file mode 100644 index 0000000..ef08c3f --- /dev/null +++ b/Scala/forcomp/src/main/scala/forcomp/package.scala @@ -0,0 +1,24 @@ +package object forcomp { + val dictionaryPath = List("forcomp", "linuxwords.txt") + + def loadDictionary = { + val wordstream = Option { + getClass.getClassLoader.getResourceAsStream(dictionaryPath.mkString("/")) + } orElse { + common.resourceAsStreamFromSrc(dictionaryPath) + } getOrElse { + sys.error("Could not load word list, dictionary file not found") + } + try { + val s = io.Source.fromInputStream(wordstream) + s.getLines.toList + } catch { + case e: Exception => + println("Could not load word list: " + e) + throw e + } finally { + wordstream.close() + } + } + +} |