-
Notifications
You must be signed in to change notification settings - Fork 1
shinyhappy
Nicholas Martin edited this page Oct 8, 2013
·
15 revisions
;; https://class.coursera.org/progfun-003/assignment/view?assignment_id=4
(ns scala-class.one)
;; Exercise 1 - Pascal's triangle
(defn pascal [row col]
(if (or (= col 0) (= col row)) 1
(+ (pascal (- row 1) col) (pascal (- row 1) (- col 1)))))
;; Exercise 2 - Parentheses balancing
(defn paren-acc [c]
(cond (= c \() 1
(= c \)) -1
:else 0))
(defn _balance [acc [head & tail]]
(cond (< acc 0) false
(nil? head) (= acc 0)
:else (_balance (+ acc (paren-acc head)) tail)))
(defn balance [string]
(_balance 0 string))
;; Exercise 3 - Counting change
(defn sum [coll] (reduce + coll))
(defn _count-change [acc money denominations]
(letfn [(count-with-pay [denom]
(_count-change acc (- money denom) (filter #(<= % denom) denominations)))]
(cond (< money 0) acc
(= money 0) (+ 1 acc)
:else (sum (map count-with-pay denominations)))))
(defn count-change [money denominations]
(_count-change 0 money denominations))
;; Video exercise - Tail-recursive factorial
(defn factorial [n]
(loop [target n value 1]
(if (zero? target) value (recur (- target 1) (* target value)))))
(defn r-factorial [n]
(reduce * (range 1 (+ n 1)))) /**
* Exercise 1
*/
def pascal(c: Int, r: Int): Int =
if (c == 0 || c == r) 1
else if (c < 0 || r < 0) 0
else pascal(c - 1, r - 1) + pascal(c, r - 1)
/**
* Exercise 2
*/
def balance(chars: List[Char]): Boolean = {
def balanceIter(openParens: Int, chars: List[Char]): Boolean = {
if (chars.isEmpty && openParens == 0) true
else if (chars.isEmpty && openParens > 0) false
else if (openParens < 0) false
else {
if (chars.head == '(') balanceIter(openParens + 1, chars.tail)
else if (chars.head == ')') balanceIter(openParens - 1, chars.tail)
else balanceIter(openParens, chars.tail)
}
}
balanceIter(0, chars)
}
/**
* Exercise 3
*/
def countChange(money: Int, coins: List[Int]): Int = {
if (money == 0) 1
else if (money < 0) 0
else if (coins.isEmpty) 0
else countChange(money - coins.head, coins) + countChange(money, coins.tail)
};; https://class.coursera.org/progfun-003/assignment/view?assignment_id=3
;; A note on terminology - in order to avoid all sorts of dumb confusion with
;; the built in set function, I'm going to use 'cset' to refer to
;; 'characteristic sets' used in this assignment.
(ns scala-class.two)
;; 2.0 Representation
(defn cset-contains [cset elem]
(cset elem))
;; 2.1 Basic Functions on Sets
(defn cset-singleton [elem]
#(= elem %))
(defn cset-union [cset-s cset-t]
#(or (cset-s %) (cset-t %)))
(defn cset-intersect [cset-s cset-t]
#(and (cset-s %) (cset-t %)))
(defn cset-diff [cset-s cset-t]
#(and (cset-s %) (not (cset-t %))))
(def cset-filter cset-intersect)
;; 2.2 Queries and Transformations on Sets
(defn cset-forall [cset pred]
(loop [x -1000]
(cond ((cset-diff cset pred) x) false
(> x 1000) true
:else (recur (+ x 1)))))
(defn cset-exists [cset pred]
(not (cset-forall cset #(not (pred %)))))
(defn cset-map [cset fun]
(fn [elem] (cset-exists cset #(= elem (fun %)))))
;; Bonus - https://class.coursera.org/progfun-003/forum/thread?thread_id=554
(defn csubset? [cset-s cset-t]
(cset-forall cset-s cset-t))
(defn cset-equal? [cset-s cset-t]
(and (cset-forall cset-s cset-t) (cset-forall cset-t cset-s)))
(defn cset-cartesian [cset-s cset-t]
#(and (cset-s %1) (cset-t %2)))object FunSets {
/**
* We represent a set by its characteristic function, i.e.
* its `contains` predicate.
*/
type Set = Int => Boolean
/**
* Indicates whether a set contains a given element.
*/
def contains(s: Set, elem: Int): Boolean = s(elem)
/**
* Returns the set of the one given element.
*/
def singletonSet(elem: Int): Set = (value: Int) => elem == value
/**
* 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 = (value: Int) => contains(s, value) || contains(t, value)
/**
* 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 = (value: Int) => contains(s, value) && contains(t, value)
/**
* 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 = (value: Int) => contains(s, value) && !contains(t, value)
/**
* Returns the subset of `s` for which `p` holds.
*/
def filter(s: Set, p: Int => Boolean): Set = (value: Int) => contains(s, value) && p(value)
/**
* The bounds for `forall` and `exists` are +/- 1000.
*/
val bound = 1000
/**
* 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)
}
/**
* Returns whether there exists a bounded integer within `s`
* that satisfies `p`.
*/
def exists(s: Set, p: Int => Boolean): Boolean = !forall(s, (value: Int) => !p(value))
/**
* Returns a set transformed by applying `f` to each element of `s`.
*/
def map(s: Set, f: Int => Int): Set = (value: Int) => exists(s, (boundedVal: Int) => f(boundedVal) == value)
/**
* Displays the contents of a set
*/
def toString(s: Set): String = {
val xs = for (i <- -bound to bound if contains(s, i)) yield i
xs.mkString("{", ",", "}")
}
/**
* Prints the contents of a set on the console.
*/
def printSet(s: Set) {
println(toString(s))
}
}package objsets
import common._
import TweetReader._
/**
* A class to represent tweets.
*/
class Tweet(val user: String, val text: String, val retweets: Int) {
override def toString: String =
"User: " + user + "\n" +
"Text: " + text + " [" + retweets + "]"
}
/**
* This represents a set of objects of type `Tweet` in the form of a binary search
* tree. Every branch in the tree has two children (two `TweetSet`s). There is an
* invariant which always holds: for every branch `b`, all elements in the left
* subtree are smaller than the tweet at `b`. The elements in the right subtree are
* larger.
*
* Note that the above structure requires us to be able to compare two tweets (we
* need to be able to say which of two tweets is larger, or if they are equal). In
* this implementation, the equality / order of tweets is based on the tweet's text
* (see `def incl`). Hence, a `TweetSet` could not contain two tweets with the same
* text from different users.
*
*
* The advantage of representing sets as binary search trees is that the elements
* of the set can be found quickly. If you want to learn more you can take a look
* at the Wikipedia page [1], but this is not necessary in order to solve this
* assignment.
*
* [1] http://en.wikipedia.org/wiki/Binary_search_tree
*/
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.
*
* Question: Can we implement this method here, or should it remain abstract
* and be implemented in the subclasses?
*/
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
/**
* Returns a new `TweetSet` that is the union of `TweetSet`s `this` and `that`.
*
* Question: Should we implment this method here, or should it remain abstract
* and be implemented in the subclasses?
*/
def union(that: TweetSet): TweetSet = filterAcc( (p) => true, that.filter( (p) => true) )
/**
* Returns the tweet from this set which has the greatest retweet count.
*
* Calling `mostRetweeted` on an empty set should throw an exception of
* type `java.util.NoSuchElementException`.
*
* Question: Should we implement this method here, or should it remain abstract
* and be implemented in the subclasses?
*/
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.
*
* Hint: the method `remove` on TweetSet will be very useful.
* Question: Should we implement this method here, or should it remain abstract
* and be implemented in the subclasses?
*/
def descendingByRetweet: TweetList = {
if (isEmpty) Nil
else {
val maxRetweeted = mostRetweeted
new Cons(maxRetweeted, remove(maxRetweeted).descendingByRetweet)
}
}
def isEmpty: Boolean
/**
* The following methods are already implemented
*/
/**
* Returns a new `TweetSet` which contains all elements of this set, and the
* the new element `tweet` in case it does not already exist in this set.
*
* If `this.contains(tweet)`, the current set is returned.
*/
def incl(tweet: Tweet): TweetSet
/**
* Returns a new `TweetSet` which excludes `tweet`.
*/
def remove(tweet: Tweet): TweetSet
/**
* Tests if `tweet` exists in this `TweetSet`.
*/
def contains(tweet: Tweet): Boolean
/**
* This method takes a function and applies it to every element in the set.
*/
def foreach(f: Tweet => Unit): Unit
}
class Empty extends TweetSet {
def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = acc
def mostRetweeted: Tweet = throw new java.util.NoSuchElementException
def isEmpty: Boolean = true
/**
* The following methods are already implemented
*/
def contains(tweet: Tweet): Boolean = false
def incl(tweet: Tweet): TweetSet = new NonEmpty(tweet, new Empty, new Empty)
def remove(tweet: Tweet): TweetSet = this
def foreach(f: Tweet => Unit): Unit = ()
}
class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet {
def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = {
if (p(elem)) left.filterAcc(p, right.filterAcc(p, acc.incl(elem)))
else left.filterAcc(p, right.filterAcc(p, acc))
}
def mostRetweeted: Tweet = {
def tweetMax(t1: Tweet, t2: Tweet): Tweet = {
if (t1.retweets > t2.retweets) t1
else t2
}
if (left.isEmpty && right.isEmpty) elem
else if (left.isEmpty) tweetMax(right.mostRetweeted, elem)
else if (right.isEmpty) tweetMax(left.mostRetweeted, elem)
else tweetMax(left.mostRetweeted, tweetMax(right.mostRetweeted, elem))
}
def isEmpty: Boolean = false
/**
* The following methods are already implemented
*/
def contains(x: Tweet): Boolean =
if (x.text < elem.text) left.contains(x)
else if (elem.text < x.text) right.contains(x)
else true
def incl(x: Tweet): TweetSet = {
if (x.text < elem.text) new NonEmpty(elem, left.incl(x), right)
else if (elem.text < x.text) new NonEmpty(elem, left, right.incl(x))
else this
}
def remove(tw: Tweet): TweetSet =
if (tw.text < elem.text) new NonEmpty(elem, left.remove(tw), right)
else if (elem.text < tw.text) new NonEmpty(elem, left, right.remove(tw))
else left.union(right)
def foreach(f: Tweet => Unit): Unit = {
f(elem)
left.foreach(f)
right.foreach(f)
}
}
trait TweetList {
def head: Tweet
def tail: TweetList
def isEmpty: Boolean
def foreach(f: Tweet => Unit): Unit =
if (!isEmpty) {
f(head)
tail.foreach(f)
}
}
object Nil extends TweetList {
def head = throw new java.util.NoSuchElementException("head of EmptyList")
def tail = throw new java.util.NoSuchElementException("tail of EmptyList")
def isEmpty = true
}
class Cons(val head: Tweet, val tail: TweetList) extends TweetList {
def isEmpty = false
}
object GoogleVsApple {
val google = List("android", "Android", "galaxy", "Galaxy", "nexus", "Nexus")
val apple = List("ios", "iOS", "iphone", "iPhone", "ipad", "iPad")
lazy val googleTweets: TweetSet = TweetReader.allTweets.filter( tweet => google.exists( keyword => tweet.text.contains(keyword)))
lazy val appleTweets: TweetSet = TweetReader.allTweets.filter( tweet => apple.exists( keyword => tweet.text.contains(keyword)))
/**
* 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
}
object Main extends App {
// Print the trending tweets
GoogleVsApple.trending foreach println
}