## 4/28/09

### My take on 99 problems in Scala (first 22)

A while ago I saw 99 problems in Prolog they looked really good and I started trying to solve them in Scala. Now, thanks to Tony Morris I found that there's a Scala version!
Nice stuff to get your skills up to shape. It helped me to improve my understanding of folds, maps, flatMaps, zips, etc. Also I learned new pattern matching techniques (tuples and guards).
You must really give the exercises a shot!
Here are my solutions:

``` ```
``````package exercises

object NinetyNine {
//P01
def last[A](xs: List[A]): A = xs match {
case x :: Nil => x
case x :: xs => last(xs)
case Nil => throw new NoSuchElementException
}

//P02
def penultimate[A](xs: List[A]): A = xs match {
case x :: y :: Nil => x
case x :: xs => penultimate(xs)
case _ => throw new NoSuchElementException
}

//P03
def nth[A](i: Int, xs: List[A]): A = xs match {
case x :: xs => if (i == 0) x else nth(i - 1, xs)
case _ => throw new NoSuchElementException
}

def nth2[A](i: Int, xs: List[A]): A = xs match {
case x :: xs if (i == 0) => x
case x :: xs if (i > 0) => nth(i - 1, xs)
case _ => throw new NoSuchElementException
}

//P04
def length[A](xs: List[A]): Int = xs match {
case x :: xs => 1 + length(xs)
case Nil => 0
}

//Although straight recursion is fun, using folds is more effective
// folds are abstractions for recursion over data structures

//P04
def length1[A](xs: List[A]): Int = xs.foldLeft(0)((a, b) => a + 1)

//P05
def reverse[A](xs: List[A]): List[A] = xs.foldLeft(Nil: List[A])((a, b) => b :: a)

//P06
def isPalindrome[A](xs: List[A]): Boolean = reverse(xs) == xs

//P07
def flatten[A](xs: List[List[A]]): List[A] = xs.foldRight(Nil: List[A])(
(xs, acc) => xs match {
case ys: List[A] => ys ::: acc
case y: A => y :: acc
})

//P08
def compress[A](xs: List[A]): List[A] =
xs.foldRight(List[A]())((y, ys) =>
if (ys != Nil && ys.head == y) ys else y :: ys)

//P09
def pack[A](xs: List[A]): List[List[A]] = xs match {
case Nil => Nil
case _ => xs.takeWhile(_ == xs.head) :: pack(xs.dropWhile(_ == xs.head)) //can use span too, see P13
}

//P10
def encode[A](xs: List[A]): List[(Int, A)] =

//P11
def encodeModified[A](xs: List[A]): List[Any] =
pack(xs).map(

//Type safe version
def encodeModifiedTypSafe[A](xs: List[A]): List[Either[A, (Int, A)]] =
pack(xs).map(
y =>

//P12
def decode[A](xs: List[(Int, A)]): List[A] = {
def expand(i: Int, a: A): List[A] = if (i == 0) Nil else a :: expand(i - 1, a)
flatten(xs.foldRight(List[List[A]]())((y, ys) => expand(y._1, y._2) :: ys))
}
//is better with flatMap
def decode1[A](xs: List[(Int, A)]): List[A] =
xs.flatMap(ny => List.make(ny._1, ny._2))

//P13
def encodeDirect[A](xs: List[A]): List[(Int, A)] = xs match {
case Nil => Nil
case _ => {
val ys = xs.span(_ == xs.head)
}
}

//P14
def duplicate[A](xs: List[A]): List[A] =
xs.foldRight(Nil: List[A])((y, ys) => y :: y :: ys)
//is better with flatMap
def duplicate1[A](xs: List[A]): List[A] = xs.flatMap(y => y :: y :: Nil)

//P15
def duplicateN[A](n: Int, xs: List[A]): List[A] =
xs.foldRight(Nil: List[A])((y, ys) => (1 to n).toList.map(_ => y) ::: ys)
//is better with flatMap
def duplicateN1[A](n: Int, xs: List[A]): List[A] =
xs.flatMap(y => List.make(n, y))

//P16
def drop[A](n: Int, xs: List[A]): List[A] =
xs.zipWithIndex.filter(_._2 % n != 0).map(_._1)

//P17
def split[A](n: Int, xs: List[A]): (List[A], List[A]) =
xs.splitAt(n) // or (xs.take(n),xs.drop(n))

//ok, that was too easy, let's try recursion
def splitRec[A](n: Int, xs: List[A]): (List[A], List[A]) =
(n, xs) match {
case (0, _) => (Nil, xs)
case (_, y :: ys) => {
val rec = splitRec(n - 1, ys)
(y :: rec._1, rec._2)
}
case (_, Nil) => (xs, Nil)
}

//P18
def slice[A](s: Int, e: Int, xs: List[A]): List[A] =
xs.slice(s, e) // or xs.drop(s).take(e-s)

//with recursion
def sliceRec[A](s: Int, e: Int, xs: List[A]): List[A] =
(s, e, xs) match {
case (0, 0, xs) => Nil
case (0, _, y :: ys) => y :: sliceRec(0, e - 1, ys)
case (_, _, y :: ys) => sliceRec(s - 1, e - 1, ys)
}

//P19
def rotate[A](n: Int, xs: List[A]): List[A] = {
val s = split((if (n > 0) n else n + xs.length), xs)
s._2 ::: s._1
}

//P20
def removeAt[A](n: Int, xs: List[A]): (List[A], A) = {
val (heads, tails) = split(n, xs)
}

//P21
def insertAt[A](e: A, n: Int, xs: List[A]): List[A] = {
val (heads, tails) = split(n, xs)
}
//with recursion
def insertRecAt[A](e: A, n: Int, xs: List[A]): List[A] =
(n, xs) match {
case (0, ys) => e :: ys
case (_, y :: ys) => y :: insertRecAt(e, n - 1, ys)
}

//P22
def range[A](s: Int, e: Int): List[Int] = (s to e).toList

//I don't think is the purpose of the exercise! Again, let's try recursion
def rangeRec(s: Int, e: Int): List[Int] = if (e - s == 0) e :: Nil else s :: rangeRec(s + 1, e)

//recursion and pattern matching with guards
def rangeRecPm(s: Int, e: Int): List[Int] = (e - s) match {
case x if (x > 0) => s :: rangeRecPm(s + 1, e)
case x if (x == 0) => e :: Nil
case _ => error("Invalid range")
}``````
``` } ```
[EDIT: fixed problem 20 ]

Anonymous said...

Hi! Your blog is simply super. you have create a differentiate. Thanks for the sharing this website. it is very useful professional knowledge. Great idea you know about company background.
Customized application development

Techsaga Corporations said...

A Software development company in Noida has to perform in accord with the client's engineering team for ideal results. Techsaga addresses this facet of the software development process most aggressively with our streamlined and well-planned resources.

Unknown said...

Techsaga, as Software development company experts, deliver inspiring, eye-catching designs and measurable campaigns that connect with target audiences, boost online marketing and encourage business growth. We can help you meet your needs across a range of full service online marketing services. Are you looking for help with great content, SEO, PPC campaigns, a full digital marketing strategy, campaign, or something else? No matter what you need, our experts can help you.

Majortotosite Com said...

I am overwhelmed by your post with such a nice topic. Usually I visit your site and get updated through the information you include but today’s blog would be the most appreciable. 토토

Racesite Pro said...

Well done! Also visit my site 경마

Totopick Pro said...

This is a good tip particularly to those fresh to the blogosphere. Brief but very accurate information… Many thanks for sharing this one. A must read post! 사설토토