shinyhappy

Coursera FP in Scala Course Assignments Code

Assigment 1

Seans's solutions

;; 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))))

Nick's solutions

  /**
   * 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)
  }

Assigment 2

Seans's solutions

Nick's solutions

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))
  }
}