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)] =
    pack(xs).map(y => (y.length, y.head))

  //P11
  def encodeModified[A](xs: List[A]): List[Any] =
    pack(xs).map(
      y => if (y.length == 1) y.head else (y.length, y.head))

  //Type safe version
  def encodeModifiedTypSafe[A](xs: List[A]): List[Either[A, (Int, A)]] =
    pack(xs).map(
      y =>
        if (y.length == 1) Left(y.head)
        else Right(y.length, y.head))

  //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)
      (ys._1.length, xs.head) :: encodeDirect(ys._2)
    }
  }

  //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)
    (heads ::: tails.tail, tails.head)
  }

  //P21
  def insertAt[A](e: A, n: Int, xs: List[A]): List[A] = {
    val (heads, tails) = split(n, xs)
    heads ::: e :: tails
  }
  //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
  //a little more readable
  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 ]

3 comments:

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.