Coursera FP Assignment 1

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