Записки программиста, обо всем и ни о чем. Но, наверное, больше профессионального.

2016-03-23

FPP in Scala, assignments

Вот тут
я начал выкладывать материал про Scala.
Продолжу.

Задачки к курсу
Functional Programming Principles in Scala
Мартин Одерски (Martin Odersky), автор Scala.

Assignments



Week 1 assignment

Pascal's triangle
The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it.
Do this exercise by implementing the pascal function in Main.scala, which takes a column c and a row r, counting from 0
and returns the number at that spot in the triangle.
    def pascal(c: Int, r: Int): Int = {
        if (c == r || r <= 1 || c == 0) 1
        else pascal(c - 1, r - 1) + pascal(c, r - 1) }

Parentheses Balancing
Write a recursive function which verifies the balancing of parentheses in a string
    def balance(chars: List[Char]): Boolean = {
        def loop(acc: Int, chars: List[Char]): Boolean = {
            if (chars.isEmpty && acc == 0) true
            else {
                if (chars.head == '(')
                    loop(acc + 1, chars.tail)
                else {
                    if (chars.head == ')') {
                        if (acc - 1 < 0) false
                        else loop(acc - 1, chars.tail) }
                    else loop(acc, chars.tail) }
            } }
        loop(0, chars) }

Counting Change
Write a recursive function that counts how many different ways you can make change
for an amount, given a list of coin denominations.
    def countChange(money: Int, coins: List[Int]): Int = {
        def cc(money: Int, coins: List[Int]): Int = {
            if (money <= 0 || coins.isEmpty) 0
            else {
                if (money == coins.head) 1
                else
                    countChange(money - coins.head, coins) + countChange(money, coins.tail)
            } }
        cc(money, coins.sorted) }

Testing
package recfun
import org.scalatest.FunSuite
import org.scalatest.junit.JUnitRunner
import org.junit.runner.RunWith

@RunWith(classOf[JUnitRunner])
class CountChangeSuite extends FunSuite {
  import Main.countChange
  test("countChange: example given in instructions") {
    assert(countChange(4,List(1,2)) === 3) } }

Week 2 assignment: higher order functions

We will work with sets of integers
passing functions as a parameter; returning functions as a result

As an example to motivate our representation, how would you represent the set of all negative integers?
You cannot list them all… one way would be so say:
if you give me an integer, I can tell you whether it’s in the set or not: for 3, I say ‘no’; for -1, I say yes.
Mathematically, we call the function which takes an integer as argument and which returns a boolean
indicating whether the given integer belongs to a set, the characteristic function of the set.
For example, we can characterize the set of negative integers by the characteristic function
(x: Int) => x < 0
Therefore, we choose to represent a set by its characterisitc function and define a
type alias for this representation:
type Set = Int => Boolean
Using this representation, we define a function that
tests for the presence of a value in a set:
def contains(s: Set, elem: Int): Boolean = s(elem)

Implementation
  /**
   * Returns the set of the one given element.
   */
  def singletonSet(elem: Int): Set = x => x == elem
Define the functions union, intersect, and diff,
which takes two sets, and return, respectively, their union, intersection and differences.
  /**
   * Returns the union of the two given sets,
   * the sets of all elements that are in either `s` or `t`.
   */
  def union(s: Set, t: Set): Set = x => s(x) || t(x)

  /**
   * Returns the intersection of the two given sets,
   * the set of all elements that are both in `s` and `t`.
   */
  def intersect(s: Set, t: Set): Set = x => s(x) && t(x)

  /**
   * Returns the difference of the two given sets,
   * the set of all elements of `s` that are not in `t`.
   */
  def diff(s: Set, t: Set): Set = x => s(x) && !t(x)
Define the function filter which selects only the elements of a set that are accepted by a given predicate p.
  /**
   * Returns the subset of `s` for which `p` holds.
   */
  def filter(s: Set, p: Int => Boolean): Set = x => s(x) && p(x)

Queries and Transformations on Sets
In this part, we are interested in functions used to make requests on elements of a set.
The first function tests whether a given predicate is true for all elements of the set.
This forall function has the following signature:
def forall(s: Set, p: Int => Boolean): Boolean
Here, we consider that an integer x has the property -1000 <= x <= 1000 in order to limit the search space.
  /**
   * Returns whether all bounded integers within `s` satisfy `p`.
   */
  def forall(s: Set, p: Int => Boolean): Boolean = {
    def iter(a: Int): Boolean = {
      if (a > bound) true
      else if (contains(s, a) && !p(a)) false
      else iter(a + 1) }
    iter(-bound) }
Using forall, implement a function exists which tests whether a set contains
at least one element for which the given predicate is true.
  /**
   * Returns whether there exists a bounded integer within `s`
   * that satisfies `p`.
   */
  def exists(s: Set, p: Int => Boolean): Boolean = {
    def iter(a: Int): Boolean = {
      if (a > bound) false
      else if (filter(s, p)(a)) true
      else iter(a + 1) }
    // iter(-bound)
    !forall(s, x => !p(x)) }
Finally, write a function map which transforms a given set
into another one by applying to each of its elements the given function
  /**
   * Returns a set transformed by applying `f` to each element of `s`.
   */
  def map(s: Set, f: Int => Int): Set = x => exists(s, y => f(y) == x)

tests (JUnit Test)
package funsets
import org.scalatest.FunSuite
import org.junit.runner.RunWith
import org.scalatest.junit.JUnitRunner
@RunWith(classOf[JUnitRunner])
class FunSetSuite extends FunSuite {
  import FunSets._
  test("contains is implemented") { assert(contains(x => true, 100)) }

  trait TestSets {
    val s1 = singletonSet(1)
    val s2 = singletonSet(2)
    val s3 = singletonSet(3) }
    
  test("singletonSet(1) contains 1") {
    new TestSets { assert(contains(s1, 1), "Singleton") } }
    
  test("union contains all elements of each set") {
    new TestSets { val s = union(s1, s2)
      assert(contains(s, 1), "Union 1")
      assert(contains(s, 2), "Union 2")
      assert(!contains(s, 3), "Union 3") } }

  test("intersect contains only common items") {
    new TestSets { val s = intersect(s1, union(s1, s2))
      assert(contains(s, 1))
      assert(!contains(s, 2)) } }

  test("diff contains items from set a that not in set b") {
    new TestSets { val s = diff(union(s1, s2), s2)
      assert(contains(s, 1))
      assert(!contains(s, 2)) } }

  test("filter make a subset where p(i) is true") {
    new TestSets { val s = union(union(s1, s2), s3)
      val t = filter(s, x => x != 2)
      assert(contains(t, 1), "1 != 2 == true")
      assert(contains(t, 3), "3 != 2 == true")
      assert(!contains(t, 2), "2 != 2 == false") } }

  test("forall tests all set items for p(i) == true") {
    new TestSets { val s = union(union(s1, s2), s3)
      assert(forall(s, x => (x > 0 && x < 4)), "0 < 1,2,3 < 4")
      assert(!forall(s, x => x != 2), " 2 != 2 == false") } }

  test("exists tests that any set item satisfy p(i) == true") {
    new TestSets { val s = union(union(s1, s2), s3)
      assert(exists(s, x => x == 2), "2 == 2")
      assert(!exists(s, x => x > 3), " {1,2,3} > 3 == false") } }

  test("map transforms set by applying f to each item") {
    new TestSets { val s = map(union(union(s1, s2), s3), x => x * x)
      assert(exists(s, x => List(1, 4, 9) contains x), "has x in 1,4,9")
      assert(forall(s, x => List(1, 4, 9) contains x), "x is 1,4,9") } }
}

Week 3 assignment : object-oriented sets
In this assignment you will work with an object-oriented representations based on binary trees.

Implement filtering on tweet sets.
Complete the stubs for the methods filter  and filterAcc.
abstract class TweetSet {
     // This method takes a predicate and returns a subset of all the elements
     // in the original set for which the predicate is true.
    def filter(p: Tweet => Boolean): TweetSet =
        filterAcc(p, new Empty)
     // This is a helper method for `filter` that propagates the accumulated tweets.
    def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet
class Empty extends TweetSet {
    def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = acc
class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet {
    def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = {
        if (p(elem)) (left.filterAcc(p, acc) union right.filterAcc(p, acc)).incl(elem)
        else left.filterAcc(p, acc) union right.filterAcc(p, acc)

The method union takes another set that, and computes a new set which is the union of this and that,
i.e. a set that contains exactly the elements that are either in this or in that, or in both.
abstract class TweetSet {
     // Returns a new `TweetSet` that is the union of `TweetSet`s `this` and `that`.
    def union(that: TweetSet): TweetSet
class Empty extends TweetSet {
    def union(that: TweetSet): TweetSet = that
class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet {
    def union(that: TweetSet): TweetSet = 
        left union (right union (that incl elem))

The goal of this part of the exercise is to add a method descendingByRetweet to TweetSet 
which should produce a linear sequence of tweets (as an instance of class TweetList), ordered by their number of retweets
abstract class TweetSet {
     // Returns the tweet from this set which has the greatest retweet count.
    def mostRetweeted: Tweet
     // Returns a list containing all tweets of this set, sorted by retweet count
     // in descending order. In other words, the head of the resulting list should
     // have the highest retweet count.
    def descendingByRetweet: TweetList
class Empty extends TweetSet {
    def descendingByRetweet: TweetList = Nil
    def mostRetweeted: Tweet = null
class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet {
    def descendingByRetweet: TweetList = {
        val mr = mostRetweeted
        val ts = remove(mr)
        new Cons(mr, ts.descendingByRetweet) }
    def mostRetweeted: Tweet = {
        def max(x: Tweet, y: Tweet): Tweet = {
            if (x == null) y
            else if (y == null) x
            else if (x.retweets > y.retweets) x
            else y }
        max(elem, max(left.mostRetweeted, right.mostRetweeted)) }

We are providing you with a TweetSet containing several hundred tweets from popular tech news sites in the past few days,
located in the TweetReader object (file “TweetReader.scala”).
TweetReader.allTweets returns an instance of TweetSet containing a set of all available tweets.
Furthermore, you are given two lists of keywords.
The first list corresponds to keywords associated with Google and Android smartphones,
while the second list corresponds to keywords associated with Apple and iOS devices.
Your objective is to detect which platform has generated more interest or activity in the past few days.
object GoogleVsApple {
    val google = List("android", "Android", "galaxy", "Galaxy", "nexus", "Nexus")
    val apple = List("ios", "iOS", "iphone", "iPhone", "ipad", "iPad")
    def tweetInList(tw: Tweet, strs: List[String]): Boolean = {
        if (strs.isEmpty) false
        else if (tw.text.contains(strs.head)) true
        else tweetInList(tw, strs.tail) }
    lazy val googleTweets: TweetSet =
        TweetReader.allTweets.filter { tw => tweetInList(tw, google) }
    lazy val appleTweets: TweetSet =
        TweetReader.allTweets.filter { tw => tweetInList(tw, apple) }
     // A list of all tweets mentioning a keyword from either apple or google,
     // sorted by the number of retweets.
    lazy val trending: TweetList =
        (googleTweets union appleTweets).descendingByRetweet }

Week 4 assignment, types & pattern matching (Huffman coding)

Huffman coding is a compression algorithm that can be used to compress lists of characters.
In a normal, uncompressed text, each character is represented by the same number of bits (usually eight).
In Huffman coding, each character can have a bit representation of a different length, depending on how common a character is:
the characters that appear often in a text are represented by a shorter bit sequence than those being used more rarely.
Every huffman code defines the specific bit sequences used to represent each character.
A Huffman code can be represented by a binary tree whose leaves represent the characters that should be encoded.
The leaf nodes have associated with them a weight which denotes the frequency of appearance of that character.
Every branching node of the code tree can be thought of as a set containing the characters present in the leaves below it.
The weight of a branching node is the total weight of the leaves below it.
Encoding : For a given Huffman tree, one can obtain the encoded representation of a character by
traversing from the root of the tree to the leaf containing the character.
Along the way, when a left branch is chosen, a 0 is added to the representation,
and when a right branch is chosen, 1 is added to the representation.

To begin, implement the following two (hint: very simple) functions using pattern matches on the code tree:
abstract class CodeTree {
    def weight: Int }
case class Fork(left: CodeTree, right: CodeTree, chars: List[Char], weight: Int) extends CodeTree
case class Leaf(char: Char, weight: Int) extends CodeTree
def weight(tree: CodeTree): Int = tree match {
    case a: Leaf => a.weight
    case b: Fork => b.weight }
def chars(tree: CodeTree): List[Char] = tree match {
    case Leaf(char, weight)               => List(char)
    case Fork(left, right, chars, weight) => chars }
def makeCodeTree(left: CodeTree, right: CodeTree): CodeTree =
    Fork(left, right, chars(left) ::: chars(right), weight(left) + weight(right))

a function times which calculates the frequency of each character in the text
def times(chars: List[Char]): List[(Char, Int)] = {
    def howMany(ch: Char, chars: List[Char]): Int = chars match {
        case Nil => 0
        case x :: xs => {
            if (x == ch) 1 + howMany(ch, xs)
            else howMany(ch, xs) } }
    def getDistinct(chars: List[Char]): List[Char] = {
        val acc = Nil
        def collect(chars: List[Char], acc: List[Char]): List[Char] = chars match {
            case Nil => acc
            case x :: xs => {
                if (acc.contains(x)) collect(xs, acc)
                else collect(xs, x :: acc) } }
        collect(chars, acc) }
    val uniqChars = getDistinct(chars).reverse
    uniqChars map (ch => (ch, howMany(ch, chars))) }

write a function makeLeafList which generates a list containing all the leaves of the Huffman tree to be constructed
def makeOrderedLeafList(freqs: List[(Char, Int)]): List[CodeTree] = {
    val leafs = freqs map (pair => new Leaf(pair._1, pair._2))
    def sortLeafs(leafs: List[CodeTree]): List[CodeTree] = leafs match {
        case Nil => leafs
        case x :: xs =>
            val sorted = sortLeafs(xs)
            insert(x, sorted) }
    sortLeafs(leafs) }
def insert(leaf: CodeTree, leafs: List[CodeTree]): List[CodeTree] = leafs match {
    case Nil => List(leaf)
    case y :: ys => {
        if (leaf.weight <= y.weight) leaf :: leafs
        else y :: insert(leaf, ys) }}

Write a simple function singleton which checks whether a list of code trees contains only one single tree
def singleton(trees: List[CodeTree]): Boolean = trees match {
    case Nil => true
    case x :: xs => xs match {
        case Nil     => true
        case y :: ys => false }}

Write a function combine which
(1) removes the two trees with the lowest weight from the list constructed in the previous step, and
(2) merges them by creating a new node of type Fork.
Add this new tree to the list - which is now one element shorter - while preserving the order (by weight)
def combine(trees: List[CodeTree]): List[CodeTree] = trees match {
    case Nil => trees
    case x :: xs => xs match {
        case Nil => trees
        case y :: ys => {
            val fork = makeCodeTree(x, y)
            insert(fork, ys) }}}

Write a function until which calls the two functions defined above until
this list contains only a single tree. This tree is the optimal coding tree.
The function until can be used in the following way:
until(singleton, combine)(trees)
def until(
    check: List[CodeTree] => Boolean,
    fold: List[CodeTree] => List[CodeTree])(
        trees: List[CodeTree]): List[CodeTree] = {
    if (check(trees)) trees
    else until(check, fold)(fold(trees)) }

use the functions defined above to implement the function createCodeTree
def createCodeTree(chars: List[Char]): CodeTree = {
    val freqs = times(chars)
    val leafs = makeOrderedLeafList(freqs)
    until(singleton, combine)(leafs).head }

Define the function decode
type Bit = Int
def decode(tree: CodeTree, bits: List[Bit]): List[Char] = {
    def collect(left: CodeTree, right: CodeTree, bits: List[Bit]): List[Char] = {
        bits match {
            case Nil => Nil
            case code :: bitstail => {
                code match {
                    case 0 => left match {
                        case Leaf(char, _)    => char :: decode(tree, bitstail)
                        case Fork(l, r, _, _) => collect(l, r, bitstail) }
                    case 1 => right match {
                        case Leaf(char, _)    => char :: decode(tree, bitstail)
                        case Fork(l, r, _, _) => collect(l, r, bitstail)
                    } }}}}
    tree match {
        case Leaf(_, _)                       => Nil
        case Fork(left, right, chars, weight) => collect(left, right, bits) }}

Define the function encode which encodes a list of characters using Huffman coding, given a code tree
def encode(tree: CodeTree)(text: List[Char]): List[Bit] = {
    def contains(char: Char, node: CodeTree): Boolean = {
        node match {
            case Fork(left, right, chars, _) =>
                if (chars.contains(char)) true
                else false
            case Leaf(ch, _) =>
                if (ch == char) true
                else false }}
    def charBits(tree: CodeTree, char: Char): List[Bit] = {
        tree match {
            case Fork(left, right, chars, _) => {
                if (contains(char, left))   0 :: charBits(left, char)
                else                        1 :: charBits(right, char) }
            case Leaf(char, _) => Nil }}
    text match {
        case Nil              => Nil
        case char :: texttail => charBits(tree, char) ++ (encode(tree)(texttail)) }}

The previous function is simple, but very inefficient.
You goal is now to define quickEncode which encodes an equivalent representation, but more efficiently
Your implementation will build a coding table once
which, for each possible character, gives the list of bits of its code.
The encoding must then be done by accessing the table, via a function codeBits.
The creation of the table is defined by convert which traverses the coding tree and constructs the character table.
Implement the function convert by using the function mergeCodeTables
type CodeTable = List[(Char, List[Bit])]
def quickEncode(tree: CodeTree)(text: List[Char]): List[Bit] = {
    val table = convert(tree)
    def enc(txt: List[Char]): List[Bit] = {
        txt match {
            case Nil              => Nil
            case char :: texttail => codeBits(table)(char) ++ enc(texttail) }}
    enc(text) }
def codeBits(table: CodeTable)(char: Char): List[Bit] = {
    table match {
        case Nil => Nil
        case pair :: tabtail => {
            if (pair._1 == char) pair._2
            else codeBits(tabtail)(char) }}}
def convert(tree: CodeTree): CodeTable = {
    def toTable(tree: CodeTree, bits: List[Bit]): CodeTable = {
        tree match {
            case Leaf(char, _) => (char, bits) :: Nil
            case Fork(left, right, _, _) =>
                mergeCodeTables(
                    toTable(left, bits ++ List(0)),
                    toTable(right, bits ++ List(1))) }}
    toTable(tree, Nil) }
def mergeCodeTables(a: CodeTable, b: CodeTable): CodeTable = a ++ b

tests
import org.scalatest.FunSuite
import org.junit.runner.RunWith
import org.scalatest.junit.JUnitRunner
@RunWith(classOf[JUnitRunner])
class HuffmanSuite extends FunSuite {
    trait TestTrees {
        val t1 = Fork(Leaf('a', 2), Leaf('b', 3), List('a', 'b'), 5)
        val t2 = Fork(Fork(Leaf('a', 2), Leaf('b', 3), List('a', 'b'), 5), Leaf('d', 4), List('a', 'b', 'd'), 9)}
    test("weight of a larger tree") {
        new TestTrees {
            assert(weight(t1) === 5)
            assert(weight(t2) === 9)}}
    test("chars of a larger tree") {
        new TestTrees {
            assert(chars(t2) === List('a', 'b', 'd'))
            assert(chars(t1) === List('a', 'b')) }}
    test("string2chars(\"hello, world\")") {
        assert(string2Chars("hello, world") === List('h', 'e', 'l', 'l', 'o', ',', ' ', 'w', 'o', 'r', 'l', 'd')) }
    test("number of times char occurs") {
        assert(times(List('a', 'b', 'a')) === List(('a', 2), ('b', 1))) }
    test("makeOrderedLeafList for some frequency table") {
        assert(makeOrderedLeafList(List(('t', 2), ('e', 1), ('x', 3))) === List(Leaf('e', 1), Leaf('t', 2), Leaf('x', 3))) }
    test("single tree or not") {
        new TestTrees {
            assert(singleton(List(t1)) === true)
            assert(singleton(List(t1, t2)) === false) }}
    test("combine of some leaf list") {
        val leaflist = List(Leaf('e', 1), Leaf('t', 2), Leaf('x', 4))
        assert(combine(leaflist) === List(Fork(Leaf('e', 1), Leaf('t', 2), List('e', 't'), 3), Leaf('x', 4))) }
    test("until singleton") {
        new TestTrees {
            val t3 = List(t1, t2)
            val t4 = until(singleton, combine)(t3)
            assert(singleton(t4) === true) }}
    test("create code tree") {
        val chars = "oops".toList
        val ct = createCodeTree(chars)
        val tst = Fork(Fork(Leaf('p', 1), Leaf('s', 1), List('p', 's'), 2), Leaf('o', 2), List('p', 's', 'o'), 4)
        assert(ct === tst) }
    test("decode bits to chars") {
        val tree = Fork(
            Fork(Leaf('p', 1), Leaf('s', 1), List('p', 's'), 2),
            Leaf('o', 2), List('p', 's', 'o'), 4)
        val bits = List(1, 1, 0, 0, 0, 1)
        val tst = List('o', 'o', 'p', 's')
        assert(decode(tree, bits) === tst)
        assert(decodedSecret === List('h', 'u', 'f', 'f', 'm', 'a', 'n', 'e', 's', 't', 'c', 'o', 'o', 'l')) }
    test("decode and encode a very short text should be identity") {
        new TestTrees {
            assert(decode(t1, encode(t1)("ab".toList)) === "ab".toList)
            assert(decode(t2, encode(t2)("abbda".toList)) === "abbda".toList) }}
    test("code table bits for char") {
        val tab = List(('a', List(1)), ('b', List(0)), ('h', List(1, 0)), ('n', List(0, 1)))
        assert(codeBits(tab)('h') === List(1, 0)) }
    test("convert tree to table") {
        val tree = Fork(
            Fork(Leaf('p', 1), Leaf('s', 1),List('p', 's'), 2),
            Leaf('o', 2), List('p', 's', 'o'), 4)
        assert(convert(tree) === List(('p', List(0, 0)), ('s', List(0, 1)), ('o', List(1)))) }
    test("decode and quickEncode") {
        new TestTrees {
            assert(decode(t1, quickEncode(t1)("ab".toList)) === "ab".toList)
            assert(decode(t2, quickEncode(t2)("abbda".toList)) === "abbda".toList) }} }

Week 6 assignment, anagrams
combinatorial problem of finding all the anagrams of a sentence using the Scala Collections API
and for-comprehensions.

An anagram of a word is a rearrangement of its letters such that a word with a different meaning is formed.
For example, if we rearrange the letters of the word
Elvis we can obtain the word
lives, which is one of its anagrams.
In a similar way, an anagram of a sentence is a rearrangement of all the characters in the sentence such that a new sentence is formed.
The new sentence consists of meaningful words, the number of which may or may not correspond to the number of words in the original sentence.
For example, the sentence:
I love you
is an anagram of the sentence:
You olive
In this exercise, we will consider permutations of words anagrams of the sentence. In the above example:
You I love
is considered a separate anagram.

Here is the general idea.
We will transform the characters of the sentence into a list saying how often each character appears.
We will call this list the occurrence list.
To find anagrams of a word we will find all the words from the dictionary which have the same occurrence list.
Finding an anagram of a sentence is slightly more difficult.
We will transform the sentence into its occurrence list, then try to extract any subset of characters from it to see if we can form any meaningful words.
From the remaining characters we will solve the problem recursively and then combine all the meaningful words we have found with the recursive solution.

def wordOccurrences(w: Word): Occurrences = {
    val word = w.toLowerCase()
    val mapLetters = word groupBy (x => x)
    val mapOcc = mapLetters map {
        case (char, str) => (char, str.length()) }
    mapOcc.toList.sortWith({
        case ((achar, _), (bchar, _)) => achar < bchar }) }

def sentenceOccurrences(s: Sentence): Occurrences = {
    val chars = s mkString ""
    wordOccurrences(chars) }

// we use the simple observation that all the anagrams of a word have the same occurrence list
lazy val dictionaryByOccurrences: Map[Occurrences, List[Word]] = {
    dictionary.groupBy(x => wordOccurrences(x)) }

def wordAnagrams(word: Word): List[Word] = {
    val ind = wordOccurrences(word)
    val anagrams = dictionaryByOccurrences.get(ind)
    anagrams match {
        case None    => List()
        case Some(x) => x } }
To compute all the anagrams of a sentence, we will need a helper method
which, given an occurrence list, produces all the subsets of that occurrence 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))
def combinations(occurrences: Occurrences): List[Occurrences] = {
    def powerset(chars: String): List[Occurrences] = {
        var lst = for {
            len <- 0 to chars.length
            comb <- chars.combinations(len)
        } yield wordOccurrences(comb)
        lst.toList }
    val letters = expand(occurrences)
    powerset(letters)
}
def expand(chars: Occurrences): String = {
    val lst = for {
        (char, cnt) <- chars
        n <- 1 to cnt
    } yield char
    lst mkString "" }
// todo: study powerset, combinations, permutations 
* Subtracts occurrence list `y` from occurrence list `x`
def subtract(x: Occurrences, y: Occurrences): Occurrences = {
    def sub(xchar: Char, xcnt: Int): Int = {
        y.foldLeft(xcnt)((cnt, occ) => {
            if (xchar == occ._1) cnt - occ._2
            else cnt }) }
    val lst = for {
        (xChar, xCnt) <- x; newCnt = sub(xChar, xCnt)
        if (newCnt > 0)
    } yield (xChar, newCnt)
    lst.toList }
* Returns a list of all anagram sentences of the given sentence
def sentenceAnagrams(sentence: Sentence): List[Sentence] = {
    val soccur = sentenceOccurrences(sentence)
    def wordAnagrams(word: Occurrences): List[Word] = Anagrams.wordAnagrams(expand(word))
    def ang(occur: Occurrences): List[Sentence] = {
        if (occur.isEmpty) List(Nil)
        else
            for {
                comb <- combinations(occur);
                other = subtract(occur, comb)
                word <- wordAnagrams(comb)
                rest <- ang(other)
            } yield word :: rest }
    ang(soccur) }
combinatorics design template
def innerFunc(argument) {
... 
for { 
  branchingChoice <- enumerateBranchingChoices(argument)
  subSolution <- innerFunc(reducedArgument(argument, branchingChoice))
  if isValid(subSolution, branchingChoice)
} yield someComposition(subSolution, branchingChoice)
}
Tests
test("sentenceOccurrences: abcd e") {
    assert(sentenceOccurrences(List("abcd", "e")) === List(('a', 1), ('b', 1), ('c', 1), ('d', 1), ('e', 1)))
    assert(sentenceOccurrences(List("oopse", "e")) === List(('e', 2), ('o', 2), ('p', 1), ('s', 1))) }
test("dictionaryByOccurrences.get: eat") {
    assert(dictionaryByOccurrences.get(List(('a', 1), ('e', 1), ('t', 1))).map(_.toSet) === 
        Some(Set("ate", "eat", "tea"))) }
test("combinations: abba") {
    val abba = List(('a', 2), ('b', 2))
    val abbacomb = 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)))
    assert(combinations(abba).toSet === abbacomb.toSet) }
test("subtract: with two y elements and a non-zero remainder") {
    val lardd = List(('a', 1), ('d', 2), ('l', 1), ('r', 1))
    val dr = List(('d', 1), ('r', 1))
    val lad = List(('a', 1), ('d', 1), ('l', 1))
    assert(subtract(lardd, dr) === lad) }
test("sentence anagrams: Linux rulez") {
    val sentence = List("Linux", "rulez")
    val anas = List(
        List("Rex", "Lin", "Zulu"),
        List("nil", "Zulu", "Rex"),
        List("Rex", "nil", "Zulu"),
        List("Zulu", "Rex", "Lin"),
        List("null", "Uzi", "Rex"),
        List("Rex", "Zulu", "Lin"),
        List("Uzi", "null", "Rex"),
        List("Rex", "null", "Uzi"),
        List("null", "Rex", "Uzi"),
        List("Lin", "Rex", "Zulu"),
        List("nil", "Rex", "Zulu"),
        List("Rex", "Uzi", "null"),
        List("Rex", "Zulu", "nil"),
        List("Zulu", "Rex", "nil"),
        List("Zulu", "Lin", "Rex"),
        List("Lin", "Zulu", "Rex"),
        List("Uzi", "Rex", "null"),
        List("Zulu", "nil", "Rex"),
        List("rulez", "Linux"),
        List("Linux", "rulez"))
    assert(sentenceAnagrams(sentence).toSet === anas.toSet) }

Week 7 assignment, Bloxorz
In this assignment you will implement a solver for a simplified version of a Flash game named “Bloxorz” using streams and lazy evaluation

The objective of Bloxorz is simple;
you must navigate your rectangular block to the hole at the end of the board, by rolling it,
in the fewest number of moves possible.
A block can be moved in 4 possible directions, left, right, up, down, using the appropriate keys on the keyboard.

The goal of your program, given a terrain configuration with a start position and a goal position, is to
return the exact sequence of keys to type in order to reach the goal position
We start at some initial state S, and we are trying to reach an end state T.
From every state, there are possible transitions to other states, some of which are out of bounds.
We explore the states, starting from S. by exploring its neighbors and following the chain, until we reach T.

A block is a 2 x 1 x 1 cuboid. We represent it as a case class which contains two fields, the 2d position of both the cubes which make up the block.
// coords
  0 1 2 3   <- y axis
0 o o o o
1 o o o o
2 o # o o    # is at position Pos(2, 1)
3 o o o o
^
|
x axis

  case class Pos(x: Int, y: Int) {
    def dx(d: Int) = copy(x = x + d)
    def dy(d: Int) = copy(y = y + d) }

//The function returns true for every position that is inside the terrain.
  type Terrain = Pos => Boolean

  /**
   * This method returns terrain function that represents the terrain
   * in `levelVector`. The vector contains parsed version of the `level`
   * string. For example, the following level
   *   val level =
   *     """ST
   *       |oo
   *       |oo""".stripMargin
   * is represented as
   *   Vector(Vector('S', 'T'), Vector('o', 'o'), Vector('o', 'o'))
   * The resulting function should return `true` if the position `pos` is
   * a valid position (not a '-' character) inside the terrain described
   * by `levelVector`.
   */
  def terrainFunction(levelVector: Vector[Vector[Char]]): Pos => Boolean = {
    (p: Pos) =>
      p match {
        case Pos(x, y) =>
          try
            levelVector(x)(y) != '-'
          catch { case ex: IndexOutOfBoundsException => false } } }

/**
* This function should return the position of character `c` in the
* terrain described by `levelVector`. You can assume that the `c`
* appears exactly once in the terrain.
*/
  def findChar(c: Char, levelVector: Vector[Vector[Char]]): Pos = {
    val x = levelVector.indexWhere(row => row.contains(c))
    val y = levelVector(x).indexOf(c)
    new Pos(x, y) }

  def startBlock: Block = new Block(startPos, startPos)
  sealed abstract class Move
  case object Left extends Move
  case object Right extends Move
  case object Up extends Move
  case object Down extends Move

  case class Block(b1: Pos, b2: Pos) {
    require(b1.x <= b2.x && b1.y <= b2.y, "Invalid block position: b1=" + b1 + ", b2=" + b2)
    def isStanding: Boolean = { b1.x == b2.x && b1.y == b2.y }
    def isLegal: Boolean = { terrain(b1) && terrain(b2) }
    def neighbors: List[(Block, Move)] = List(
      (this.right, Right),
      (this.left, Left),
      (this.up, Up),
      (this.down, Down))
    def legalNeighbors: List[(Block, Move)] =
      this.neighbors filter (pair => pair._1.isLegal) ... }

    def done(b: Block): Boolean = b == Block(goal, goal)

/**
* This function takes two arguments: the current block `b` and
* a list of moves `history` that was required to reach the
* position of `b`.
*
* The `head` element of the `history` list is the latest move
* that was executed, i.e. the last move that was performed for
* the block to end up at position `b`.
*
* The function returns a stream of pairs: the first element of
* the each pair is a neighboring block, and the second element
* is the augmented history of moves required to reach this block.
*
* It should only return valid neighbors, i.e. block positions
* that are inside the terrain.
*/
    def neighborsWithHistory(b: Block, history: List[Move]): Stream[(Block, List[Move])] = {
        if (done(b)) Stream.Empty
        else {
            val neighbors = for {
                (block, move) <- b.legalNeighbors
            } yield (block, move :: history)
            neighbors.toStream } }

/**
* This function returns the list of neighbors without the block
* positions that have already been explored. We will use it to
* make sure that we don't explore circular paths.
*/
    def newNeighborsOnly(neighbors: Stream[(Block, List[Move])],
                         explored: Set[Block]): Stream[(Block, List[Move])] = {
        neighbors.filter {
            case (block, _) => !(explored.contains(block)) } }

/**
* The function `from` returns the stream of all possible paths
* that can be followed, starting at the `head` of the `initial`
* stream.
*
* The blocks in the stream `initial` are sorted by ascending path
* length: the block positions with the shortest paths (length of
* move list) are at the head of the stream.
*
* The parameter `explored` is a set of block positions that have
* been visited before, on the path to any of the blocks in the
* stream `initial`. When search reaches a block that has already
* been explored before, that position should not be included a
* second time to avoid cycles.
*
* The resulting stream should be sorted by ascending path length,
* i.e. the block positions that can be reached with the fewest
* amount of moves should appear first in the stream.
*
* Note: the solution should not look at or compare the lengths
* of different paths - the implementation should naturally
* construct the correctly sorted stream.
*/
    def from(initial: Stream[(Block, List[Move])],
             explored: Set[Block]): Stream[(Block, List[Move])] = {
        def f3(initial: Stream[(Block, List[Move])],
               explored: Set[Block]): Stream[(Block, List[Move])] = {
            if (initial.isEmpty) Stream.Empty
            else {
                val neighbors = for {
                    (block, moves) <- initial
                    nbr <- newNeighborsOnly(neighborsWithHistory(block, moves), explored)
                } yield nbr
                def updExplored = explored ++ neighbors.map { case (block, _) => block }
                initial #::: from(neighbors, updExplored) } }
        f3(initial, explored) }

/**
* The stream of all paths that begin at the starting block.
*/
    lazy val pathsFromStart: Stream[(Block, List[Move])] = from(
        neighborsWithHistory(startBlock, List()),
        Set(startBlock))

/**
* Returns a stream of all possible pairs of the goal block along
* with the history how it was reached.
*/
    lazy val pathsToGoal: Stream[(Block, List[Move])] = {
        def v2 = { pathsFromStart.filter {
            case (block, _) => done(block) } }
        v2 }

/**
* The (or one of the) shortest sequence(s) of moves to reach the
* goal. If the goal cannot be reached, the empty list is returned.
*
* Note: the `head` element of the returned list should represent
* the first move that the player should perform from the starting
* position.
*/
    lazy val solution: List[Move] = {
        if (pathsToGoal.isEmpty) Nil
        else pathsToGoal.head._2.reverse }

Tests
    trait SolutionChecker extends GameDef with Solver with StringParserTerrain {
        def solve(ls: List[Move]): Block =
            ls.foldLeft(startBlock) {
                case (block, move) => move match {
                    case Left  => block.left
                    case Right => block.right
                    case Up    => block.up
                    case Down  => block.down } } }
    trait Level1 extends SolutionChecker {
        val level =
            """ooo-------
              |oSoooo----
              |ooooooooo-
              |-ooooooooo
              |-----ooToo
              |------ooo-""".stripMargin
        val optsolution = List(Right, Right, Down, Right, Right, Right, Down) }
    test("neighborsWitHistory 1") {
        new Level1 {
            val nwh = neighborsWithHistory(Block(Pos(1, 1), Pos(1, 1)), List(Left, Up))
            val ans = Set(
                (Block(Pos(1, 2), Pos(1, 3)), List(Right, Left, Up)),
                (Block(Pos(2, 1), Pos(3, 1)), List(Down, Left, Up)))
            assert(nwh.toSet === ans) } }
    test("new neighborsWitHistory 1") {
        new Level1 {
            val nwh = newNeighborsOnly(
                Set(
                    (Block(Pos(1, 2), Pos(1, 3)), List(Right, Left, Up)),
                    (Block(Pos(2, 1), Pos(3, 1)), List(Down, Left, Up))).toStream,
                Set(Block(Pos(1, 2), Pos(1, 3)), Block(Pos(1, 1), Pos(1, 1))))
            val ans = Set(
                (Block(Pos(2, 1), Pos(3, 1)), List(Down, Left, Up)))
            assert(nwh === ans.toStream) } }
    test("optimal solution for level 1") {
        new Level1 {
            assert(solve(solution) == Block(goal, goal)) } }
    test("optimal solution for level 2") {
        new Level2 {
            assert(solve(solution) == Block(goal, goal)) } }


Martin Odersky is the inventor of the Scala language,
a professor at EPFL in Lausanne, Switzerland, and Chairman and Chief Architect of Typesafe.

Lightbend: formerly Typesafe


https://mitpress.mit.edu/sicp/ Structure and Interpretation of Computer Programs
http://www.artima.com/pins1ed/ Programming in Scala, First Edition by Martin Odersky, Lex Spoon, and Bill Venners December 10, 2008






original post http://vasnake.blogspot.com/2016/03/fpp-in-scala-assignments.html

Комментариев нет:

Отправить комментарий

Архив блога

Ярлыки

linux (241) python (191) citation (185) web-develop (170) gov.ru (156) video (123) бытовуха (111) sysadm (100) GIS (97) Zope(Plone) (88) Book (81) programming (81) бурчалки (80) грабли (77) development (73) Fun (72) windsurfing (72) Microsoft (64) hiload (62) opensource (58) internet provider (57) security (57) опыт (55) movie (52) Wisdom (51) ML (47) language (45) hardware (44) JS (41) curse (40) money (40) driving (39) DBMS (38) bigdata (38) ArcGIS (34) history (31) PDA (30) howto (30) holyday (29) Google (27) Oracle (27) virtbox (27) health (26) vacation (24) AI (23) Autodesk (23) SQL (23) Java (22) humor (22) knowledge (22) translate (20) CSS (19) cheatsheet (19) hack (19) tourism (18) Apache (16) Manager (15) web-browser (15) Никонов (15) happiness (14) music (14) todo (14) PHP (13) weapon (13) HTTP. Apache (12) SSH (12) course (12) frameworks (12) functional programming (12) hero (12) im (12) settings (12) HTML (11) SciTE (11) crypto (11) game (11) map (11) scala (10) HTTPD (9) ODF (9) купи/продай (9) benchmark (8) documentation (8) 3D (7) CS (7) DNS (7) NoSQL (7) Photo (7) cloud (7) django (7) gun (7) matroska (7) telephony (7) Microsoft Office (6) VCS (6) bluetooth (6) pidgin (6) proxy (6) Donald Knuth (5) ETL (5) NVIDIA (5) REST (5) bash (5) flash (5) keyboard (5) price (5) samba (5) CGI (4) LISP (4) RoR (4) cache (4) display (4) holywar (4) nginx (4) pistol (4) xml (4) Лебедев (4) IDE (3) IE8 (3) J2EE (3) NTFS (3) RDP (3) USA (3) mount (3) spark (3) Гоблин (3) кухня (3) урюк (3) AMQP (2) ERP (2) IE7 (2) NAS (2) Naudoc (2) PDF (2) address (2) air (2) british (2) coffee (2) font (2) ftp (2) holiday (2) messaging (2) notify (2) sharepoint (2) ssl/tls (2) stardict (2) tests (2) tunnel (2) udev (2) APT (1) CRUD (1) Canyonlands (1) Cyprus (1) DVDShrink (1) Jabber (1) K9Copy (1) Matlab (1) Palanga (1) Portugal (1) VBA (1) WD My Book (1) autoit (1) bike (1) cannabis (1) chat (1) concurrent (1) dbf (1) ext4 (1) idioten (1) krusader (1) license (1) mindmap (1) pneumatic weapon (1) quiz (1) regexp (1) robot (1) science (1) serialization (1) tie (1) vim (1) Науру (1) крысы (1) налоги (1) пианино (1)

Google+ Followers