Ninety-Nine Scala Problems – Problem 1 – 10

This one is inspired by Ninety-Nine Haskell Problems. Since both are functional languages, I am giving a try to solve the problems in Scala.

Problem 1 : Find the last element of a list.

object Problem1 {
    def myLast[T](list: List[T]): Option[T] = list match {
        case Nil => None
        case x :: Nil => Some(x)
        case x :: xs => myLast(xs)
    }

    def main(args: Array[String]) {
        assert(myLast(1 to 10 toList) == Some(10))
        assert(myLast(List(1)) == Some(1))
        assert(myLast(Nil) == None)

        assert(myLast('a' to 'z' toList) == Some('z'))

    }
}

Problem 2 : Find the last but one element of a list.

object Problem2 {
    def myButLast[T](list: List[T]): Option[T] = list match {
        case Nil => None
        case x :: Nil => Some(x)
        case x :: xs => {
            if (xs.length == 1) Some(x)
            else
                myButLast(xs)
        }
    }

    def main(args: Array[String]): Unit = {
        assert(myButLast(1 to 10 toList) == Some(9))
        assert(myButLast(List(1)) == Some(1))
        assert(myButLast(Nil) == None)

        assert(myButLast('a' to 'z' toList) == Some('y'))
    }
}

Problem 3 : Find the K’th element of a list. The first element in the list is number 1.

object Problem3 {
    def elementAt[T](list: List[T], index: Int): Option[T] = {

        def loop(subList: List[T]): Option[T] = subList match {
            case Nil => None
            case x :: xs => {
                if (xs.length == list.length - index) Some(x)
                else loop(xs)
            }
        }

        if (index > list.length) None
        if (index < 0) None

        loop(list)
    }

    def main(args: Array[String]) {
        assert(elementAt(1 to 10 toList, 5) == Some(5))
        assert(elementAt('a' to 'z' toList, 10) == Some('j'))
        assert(elementAt(Nil, 10) == None)
        assert(elementAt('a' to 'z' toList, 100) == None)
        assert(elementAt('a' to 'z' toList, -1) == None)

    }
}

Problem 4 : Find the number of elements of a list.

object Problem4 {
    def myLength[T](list: List[T]): Int = list match {
        case Nil => 0
        case x :: xs => 1 + myLength(xs)
    }

    def main(args: Array[String]): Unit = {
        assert(myLength(1 to 10 toList) == 10)
        assert(myLength('a' to 'z' toList) == 26)
        assert(myLength("Hello, world!" toList) == 13)
    }
}

Problem 5 : Reverse a list.

object Problem5 {
    def myReverse[T](list: List[T]): List[T] = list match {
        case Nil => Nil
        case x::xs => myReverse(xs) ::: List(x)
    }

    def main(args: Array[String]): Unit = {
        assert( myReverse(1 to 10 toList) == (10 to 1 by -1 toList))
        assert( myReverse(List('a','b','c','d','e')) == (List('e','d','c','b','a')))
    }
}

Problem 6 : Find out whether a list is a palindrome. A palindrome can be read forward or backward; e.g. (x a m a x).

object Problem6 {
    def isPalindrome[T](list : List[T]) : Boolean = list match {
        case Nil => true
        case x::Nil => true
        case x::xs => (list.head == list.last) && isPalindrome(list.tail.init)
    }
    def main(args: Array[String]) {
        assert ( isPalindrome(List(1,2,3)) == false)
        assert ( isPalindrome("madamimadam".toList) == true )
        assert ( isPalindrome(List(1,2,4,8,16,8,4,2,1)) == true )
    }
}

Problem 7 :Flatten a nested list structure.

object Problem7 {
    def myflatten[T](list: List[T]): List[T] = list match {
        case Nil => list
        case (x: List[T]) :: xs => myflatten(x) ::: myflatten(xs)
        case x :: xs => x :: myflatten(xs)

    }

    def main(args: Array[String]) {
        println(myflatten(List('a', List('b', List('c', 'd'), 'e'))))
        println(myflatten(List('X', ('a' to 'z' toList))))
    }
}

Problem 8 : Eliminate consecutive duplicates of list elements.

object Problem8 {
    def compress[T](list: List[T]): List[T] = list match {
        case Nil => Nil
        case x :: xs => x :: compress(xs.dropWhile(_ == x))

    }

    def main(args: Array[String]): Unit = {
        val a = List('a', 'a', 'a', 'a', 'b', 'b', 'b', 'b', 'c', 'c')
        println("Result ----> " + compress(a))
        val b = List('a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e')
        println("Result ----> " + compress(b))
        println("Result ----> " + compress('a' to 'z' toList))

    }
}

Problem 9: Pack consecutive duplicates of list elements into sublists. If a list contains repeated elements they should be placed in separate sublists.


/**
 * Problem 9
 * (**) Pack consecutive duplicates of list elements into sublists. If a list contains repeated elements they should be placed in separate sublists.
 * Example:
 * (pack '(a a a a b c c a a d e e e e))
 * ((A A A A) (B) (C C) (A A) (D) (E E E E))
 */
object Problem9 {
    def pack(list: List[Any]): List[Any] = {
        if (list.isEmpty) List(List())
        else {
            val (packed, next) = list span {
                _ == list.head
            }
            if (next == Nil) List(packed)
            else packed :: pack(next)
        }
    }

    def main(args: Array[String]) {
        println(pack(List('a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e')))
    }

}

Problem 10 : Run-length encoding of a list. Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as lists (N E) where N is the number of duplicates of the element E.

/**
 *
 * Run-length encoding of a list. Use the result of problem P09 to implement the so-called run-length encoding data
 * compression method. Consecutive duplicates of elements are encoded as lists (N E) where N is the number of
 * duplicates of the element E.
 * Example:
 * (encode '(a a a a b c c a a d e e e e))
 * ((4 A) (1 B) (2 C) (2 A) (1 D)(4 E))
 *
 */
object Problem10 {

    def pack(list: List[Any]): List[Any] = {
        if (list.isEmpty) List(List())
        else {
            val (packed, next) = list span {
                _ == list.head
            }
            if (next == Nil) List(packed)
            else packed :: pack(next)
        }
    }

    def encode[T](list: List[T]): List[(Int, T)] = {
        def encodeHelper[T](packedList: List[Any], result: List[(Int, T)]): List[(Int, T)] = {
            packedList match {
                case Nil => Nil
                case (x: List[T]) :: Nil =>
                    result ::: List((x.length, x.head))
                case (x: List[T]) :: (xs: List[T]) =>
                    result ::: List((x.length, x.head)) ::: encodeHelper(xs, result)
                case _ => Nil
            }
        }
        encodeHelper(pack(list), Nil)
    }

    def main(args: Array[String]): Unit = {
        println(encode(List('a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e')))
    }
}

Advertisements

2 thoughts on “Ninety-Nine Scala Problems – Problem 1 – 10

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