Ninety-Nine Scala Problems – Problem 11 – 20

Problem 11 : Modified run-length encoding.
Modify the result of problem 10 in such a way that if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are transferred as (N E) lists.

object Problem11 {
    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_modified[T](list: List[T]): List[Any] = {
        def encodeHelper[T](packedList: List[Any], result: List[(Int, T)]): List[Any] = {
            packedList match {
                case Nil => Nil
                case (x: List[T]) :: Nil =>
                    if ( x.length == 1)
                        result ::: x
                        else
                    result ::: List((x.length, x.head))
                case (x: List[T]) :: (xs: List[T]) => {
                    if ( x.length == 1)
                        result ::: x ::: encodeHelper(xs, result)
                        else
                    result ::: List((x.length, x.head)) ::: encodeHelper(xs, result)
                }
                case _ => Nil
            }
        }
        encodeHelper(pack(list), Nil)
    }

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

Problem 12 : Decode a run-length encoded list.
Given a run-length code list generated as specified in problem 11. Construct its uncompressed version.

object Problem12 {
    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_modified[T](list: List[T]): List[Any] = {
        def encodeHelper[T](packedList: List[Any], result: List[(Int, T)]): List[Any] = {
            packedList match {
                case Nil => Nil
                case (x: List[T]) :: Nil =>
                    if (x.length == 1)
                        result ::: x
                    else
                        result ::: List((x.length, x.head))
                case (x: List[T]) :: (xs: List[T]) => {
                    if (x.length == 1)
                        result ::: x ::: encodeHelper(xs, result)
                    else
                        result ::: List((x.length, x.head)) ::: encodeHelper(xs, result)
                }
                case _ => Nil
            }
        }
        encodeHelper(pack(list), Nil)
    }

    def decodeModified[T](list: List[Any]): List[T] = {
        def decodeModifiedHelper[T](lst: List[Any], result: List[T]): List[T] = {
            lst match {
                case Nil => result
                case (x: (Int, T)) :: (xs: List[Any]) => {
                    decodeModifiedHelper(xs, result ::: List.fill(x._1)(x._2))
                }
                case (x: T) :: (xs: List[Any]) => {
                    decodeModifiedHelper(xs, result ::: List.fill(1)(x))
                }
                case _ => Nil
            }
        }
        decodeModifiedHelper(list, Nil)
    }

    def main(args: Array[String]) {
        val encodedList = encode_modified(List('a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e'))
        println("Encoded List => " + encodedList)
        val x = decodeModified(encodedList)
        println(x)
    }
}

Problem 14 : Duplicate the elements of a list.

object Problem14 {
    def dupli[T](list: List[T]): List[T] = {
        def dupliHelper[T](lst: List[T], result: List[T]): List[T] = {
            lst match {
                case Nil => result
                case x :: xs => dupliHelper(xs, result ::: List(x, x) )
            }
        }

        dupliHelper(list, Nil)
    }

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

Problem 15 : Replicate the elements of a list a given number of times.

object Problem15 {
    def repli[T](list: List[T], r: Int): List[T] = {
        def repliHelper[T](lst: List[T], result: List[T]): List[T] = {
            lst match {
                case Nil => result
                case x :: xs => repliHelper(xs, result ::: List.fill(r)(x))
            }
        }
        repliHelper(list, Nil)
    }

    def main(args: Array[String]) {
        println(repli(List('a', 'b', 'c'), 3))
    }

}

Problem 16 : Drop every N’th element from a list.

object Problem16 {
    def dropEvery[T](input: List[T], nth: Int): List[T] = {
        def dropHelper(list: List[T], result: List[T], index: Int): List[T] = {
            list match {
                case Nil => result
                case x :: xs => {
                    if (index == nth) {
                        dropHelper(xs, result, 1)
                    }
                    else {
                        dropHelper(xs, result ::: List(x), index + 1)
                    }
                }
            }

        }
        dropHelper(input, Nil, 1)
    }

    def main(args: Array[String]) {
        println(dropEvery(List('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k'), 3))
    }
}

Problem 17 : Split a list into two parts; the length of the first part is given.

object Problem17 {
    def split[T](input: List[T], length: Int): List[List[T]] = {
        def splitHelper[T](list: List[T], left: List[T], right: List[T], index: Int): List[List[T]] = {
            list match
            {
                case Nil => List(left) ::: List(right)
                case x :: xs => {
                    if (index <= length) {
                        splitHelper(xs, left ::: List(x), right, index + 1)
                    } else {
                        splitHelper(xs, left, right ::: List(x), index + 1)
                    }
                }
            }
        }
        splitHelper(input, Nil, Nil, 1)
    }

    def main(args: Array[String]) {
        println(split(List('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k'), 3))
    }

}

Problem 18 : Extract a slice from a list.
Given two indices, i and k, the slice is the list containing the elements between the i’th and k’th element of the original list (both limits included). Start counting the elements with 1.

object Problem18 {
    def slice[T](input: List[T], left: Int, right: Int): List[T] = {
        def sliceHelper(list: List[T], result: List[T], index: Int): List[T] = {
            list match {
                case Nil => result
                case x :: xs => {
                    if (index >= left && index <= right)
                        sliceHelper(xs, result ::: List(x), index + 1)
                    else
                        sliceHelper(xs, result, index + 1)
                }
            }
        }
        sliceHelper(input, Nil, 1)
    }

    def main(args: Array[String]) {
        println(slice (List('a','b','c','d','e','f','g','h','i','k'),3, 7))
    }
}

Problem 19 : Rotate a list N places to the left.

object Problem19 {
    def split[T](input: List[T], length: Int): List[List[T]] = {
        def splitHelper[T](list: List[T], left: List[T], right: List[T], index: Int): List[List[T]] = {
            list match {
                case Nil => List(left) ::: List(right)
                case x :: xs => {
                    if (index <= length) {
                        splitHelper(xs, left ::: List(x), right, index + 1)
                    } else {
                        splitHelper(xs, left, right ::: List(x), index + 1)
                    }
                }
            }
        }
        splitHelper(input, Nil, Nil, 1)
    }

    def rotate[T](input: List[T], at: Int): List[T] = {
        val r: List[List[T]] = if (at >= 0) split(input, at)
        else split(input, input.length + at)
        r match {
            case Nil => Nil
            /*
             * I got confuse here with pattern matching see here for my confusion
             * http://stackoverflow.com/questions/30523159/pattern-matching-for-list-of-list-in-scala
             */
            case x :: xs :: Nil => {
                xs ::: x
            }
        }
    }

    def main(args: Array[String]): Unit = {
        println(rotate(List('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'), 3))
        println(rotate(List('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'), -2))
        println(rotate(List('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'), 0))
        println(rotate(List('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'), 100))
    }

}

Problem 20 : Remove the K’th element from a list.

object Problem20 {
    def split[T](input: List[T], length: Int): List[List[T]] = {
        def splitHelper[T](list: List[T], left: List[T], right: List[T], index: Int): List[List[T]] = {
            list match {
                case Nil => List(left) ::: List(right)
                case x :: xs => {
                    if (index <= length) {
                        splitHelper(xs, left ::: List(x), right, index + 1)
                    } else {
                        splitHelper(xs, left, right ::: List(x), index + 1)
                    }
                }
            }
        }
        splitHelper(input, Nil, Nil, 1)
    }

    def remove_at[T](at:Int, input:List[T]) : List[T] = {
        val r = split(input, at - 1)
        r match  {
            case Nil => Nil
            case x::xs::Nil => x ::: xs.tail
        }
    }

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

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