Functional Programming Principles in Scala (1)

This is online course, named functional programming principles in Scala. I use this course to practice my Scala programming. So here I do summary of my solutions according to its assignments online. Please I don’t follow its restriction, I only want to implement my solution by Scala. Don’t compare my idea with their online course exactly. Follow your heart. 🙂

Exercise 1: Pascal’s Triangle.

Do this exercise by implementing the pascal function, which takes a column c and a row r, counting from 0 and returns the number at that spot in the triangle. For example,pascal(0,2)=1, pascal(1,2)=2 and pascal(1,3)=3

def pascal(c: Int, r: Int): Int = {
  if (c == 0 || c == r) 1
  else pascal(c - 1, r - 1) + pascal(c, r - 1)
}
pascal(0, 2) // output: 1
pascal(1, 2) // output: 2
pascal(1, 3) // output: 3

Exercise 2: Parentheses Balancing

Write a function which verifies the balancing of parentheses in a string, which we represent as a List[Char] not a String. For example, the function should return true for the following strings:

  • (if (zero? x) max (/ 1 x))
  • I told him (that it’s not (yet) done). (But he wasn’t listening)

The function should return false for the following strings:

  • 🙂
  • ())(

The last example shows that it’s not enough to verify that a string contains the same number of opening and closing parentheses.

import scala.collection.mutable.Stack
def balance(chars: List[Char]): Boolean = {
  val stack = new Stack[Char]()
  var flag = true
  for (c <- chars if flag == true) {
    if (c == '(') stack.push(c)
    else if (c == ')') {
      if (stack.size == 0) flag = false
      else stack.pop
    }
  }
  if (stack.size == 0 && flag == true) flag = true
  else flag = false
  flag
}
balance("(if (zero? x) max (/ 1 x))".toList) // output: true
balance("I told him (that it’s not (yet) done). (But he wasn’t listening)".toList) // output: true
balance(":-)".toList) // output: false
balance("())(".toList) // output: false

Exercise 3: 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. For example, there are 3 ways to give change for 4 if you have coins with denomination 1 and 2: 1+1+1+1, 1+1+2, 2+2.

def countChange(money: Int, coins: List[Int]): Int = {
  if (money <= 0) 0
  else if (money == 1) 1
  else {
    var sum: Int = 0
    for (coin <- coins) {
      sum += countChange(money - coin, coins)
    }
    sum
  }
}

countChange(4, List(1,2)) // output: 3
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s