Вот тут
я начал
выкладывать материал про 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
Комментариев нет:
Отправить комментарий