# 99 scala problems - part 1

by on August 9, 2012

In order to get some more practice on programming in scala I started solving some problems of the probably well known 99 problems of other functional programming languages. I first found that kind of series on the haskell wiki that mentions the origin being the Ninety-Nine Prolog Problems.

This post now contains my solutions to the first 10 problems mentioned on the haskell wiki translated to scala. This first problems target the handling of lists being one of the most important data structure in functional programming.

#### Problem 1: Find the last element of a list

``````class Problem001 extends Problem {

def number = 1

def getLast[T](input : List[T]) : T = {
input match {
case Nil => throw new IllegalArgumentException("empty list")
case _ :: tail => getLast(tail)
}
}

def test() = {
getLast(List(1, 2, 3, 4)) == 4
}
}``````

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

``````class Problem002 extends Problem {

def number = 2

def lastButOne[T](list : List[T]) : T = {
list match {
case Nil => throw new IllegalArgumentException("empty list")
case _ :: Nil => throw new IllegalArgumentException("list with one element only")
case last :: _ :: Nil => last
case _ :: tail => lastButOne(tail)
}
}

def test() = {
lastButOne(List(1,2,3,4)) == 3
}
}``````

#### Problem 3: Find the N-th element of a list

``````class Problem003 extends Problem {

def number = 3

def getNth[T](list : List[T], n : Int) : T = {
list match {
case Nil => throw new IllegalArgumentException("index out of bounds")
case _ :: tail => getNth(tail, n-1)
}
}

def test() = {
val lst = List(1,2,3,4,5)
getNth(lst, 3) == 3 &&
getNth(lst, 1) == 1 &&
getNth(lst, 5) == 5
}
}``````

#### Problem 4: Count the elements in a list

The first element in the list is number 1.

``````class Problem004 extends Problem {

def number = 4

def numElements[T](list : List[T]) = {
def inner(lst : List[T], i : Int) : Int = {
lst match {
case Nil => i
case _ :: tail => inner(tail, i+1)
}
}
inner(list, 0)
}

def test() = {
val lst = List.range(0, 10)

numElements(lst) == 10 &&
numElements(List()) == 0
}
}``````

#### Problem 5: Reverse a list

``````class Problem005 extends Problem {

def number = 5

def rev[T](list : List[T]) = {
def inner(lst : List[T], res : List[T]) : List[T] = {
lst match {
case Nil => res
}
}
inner(list, List())
}

def test() = {
rev(List(1,2,3,4,5)) == List(5,4,3,2,1)
}
}``````

#### Problem 6: Check whether a list is a palindrome

A palindrome can be read forward or backward (i.e. `12321`)

``````class Problem006 extends Problem {

def number = 6

def isPalindrome[T](list : List[T]) = {
list == list.reverse
}

def test() = {
isPalindrome(List(1,2,3,2,1)) &&
!isPalindrome(List(1,3,1,2))
}
}``````

#### Problem 7: Flatten a list of lists

``````class Problem007 extends Problem {

def number = 7

def flattenList[T](list : List[List[T]]) = {
def inner(list : List[List[T]], res : List[T]) : List[T] = {
list match {
case Nil => res
inner(tail, head.foldLeft(res)((l, h) => h :: l))
}
}
inner(list, List()) reverse
}

def test() = {
val lst = List(List(1,2), List(3), List(4,5,6))

flattenList(lst) == List(1,2,3,4,5,6)
}
}``````

#### Problem 8: Eliminate consecutive duplicates of list elements

``````class Problem008 extends Problem {

def number = 8

def compress[T](list : List[T]) = {
def inner(lst : List[T], last : T, res : List[T]) : List[T] = {
lst match {
case Nil => res
case head :: tail if head == last => inner(tail, last, res)
}
}
list match {
case Nil => Nil
}
}

def test() = {
val lst = "aaabbbbbcccdefff".toList

compress(lst) == "abcdef".toList
}
}``````

#### Problem 9: Pack consecutive duplicates of list elements into sublists

If a list contains repeated elements they should be placed in separate sublists.

``````class Problem009 extends Problem {

def number = 9

def pack[T](list : List[T]) = {
def inner(lst : List[T], last : List[T], res : List[List[T]]) : List[List[T]] = {
lst match {
case Nil => last :: res
case hd :: tl if hd == last.head => inner(tl, hd :: last, res)
case hd :: tl => inner(tl, List(hd), last :: res)
}
}
list match {
case Nil => Nil
}
}

def test() = {
val lst = "aaaabbbcdeeee".toList

pack(lst) == List("aaaa".toList, "bbb".toList, List('c'), List('d'), "eeee".toList)
}
}``````

#### Problem 10: Run-length encoding of a list

Use the result of problem 9 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as tuples (`N E`) where `N` is the number of duplicates of the element `E`.

``````class Problem010 extends Problem {

def number = 10

def encode[T](list : List[T]) = {
def inner(lst : List[T], last : (Int, T), res : List[(Int, T)]) : List[(Int, T)] = {
val (count, elem) = last
lst match {
case Nil => last :: res
case hd :: tl if hd == elem => inner(tl, last.copy(_1 = count+1), res)
case hd :: tl => inner(tl, (1, hd), last :: res)
}
}
list match {
case Nil => Nil
case hd :: tl => inner(tl, (1, hd), List()) reverse
}
}

def test() = {
val lst = "aaabbcddeeeee".toList

encode(lst) == List((3, 'a'), (2, 'b'), (1, 'c'), (2, 'd'), (5, 'e'))
}
}``````

This post is tagged with scala and programming