S-99 P21-P28 blank

gistfile1.scala

// *** S-99: Ninety-Nine Scala Problems ***
// http://aperiodic.net/phil/scala/s-99/
//
// wget http://www.scala-tools.org/repo-releases/org/scalatest/scal.test_2.9.0-1/1.6.1/scalatest_2.9.0-1-1.6.1.jar
// scala -cp scalatest-*.jar s99-21-28.scala

import org.scalatest.matchers.ShouldMatchers._
import scala.annotation._

class NotImplementedYet extends RuntimeException

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

  def encode[A](ls: List[A]): List[(Int, A)] = pack(ls) map {
    e => (e.length, e.head)
  }
}

object P20 {
  def removeAt[T](n: Int, list: List[T]): (List[T], T) = {
    list splitAt (n) match {
      case (leftN, t) => (leftN ::: t.tail, t.head)
      case _ => throw new IllegalArgumentException
    }
  }
}

// P21: Insert an element at a given position into a list.
object P21 {
  def insertAt[T](element: T, n: Int, list: List[T]): List[T] = {
    list.zipWithIndex.foldLeft(List[T]())({ (result, e) =>
      e match {
	case (_, nn) if nn == n => result ::: (element :: e._1 :: Nil)
	case _ => result :+ e._1
      }
    })
  }

  def test {
    {
      val element = 'new
      val n = 0
      val list = List('a, 'b, 'c, 'd)
      val expected = List('new, 'a, 'b, 'c, 'd)
      insertAt(element, n, list) should equal(expected)
    }
    {
      val element = 'new
      val n = 1
      val list = List('a, 'b, 'c, 'd)
      val expected = List('a, 'new, 'b, 'c, 'd)
      insertAt(element, n, list) should equal(expected)
    }
    {
      val element = 'new
      val n = 2
      val list = List('a, 'b, 'c, 'd)
      val expected = List('a, 'b, 'new, 'c, 'd)
      insertAt(element, n, list) should equal(expected)
    }
  }
}

// P22: Create a list containing all integers within a given range.
object P22 {
  def range(from: Int, to: Int): List[Int] = {
    from to to toList
  }

  def test {
    {
      val from = 4
      val to = 9
      val expected = List(4, 5, 6, 7, 8, 9)
      range(from, to) should equal(expected)
    }
    {
      val from = 0
      val to = 3
      val expected = List(0, 1, 2, 3)
      range(from, to) should equal(expected)
    }
  }
}

// P23: Extract a given number of randomly selected elements from a list.
object P23 {
  def randomSelect[T](length: Int, list: List[T]): List[T] = {
    import scala.util.Random
    @tailrec def f(n: Int, src: List[T], dst: List[T]): Pair[List[T], List[T]] = {
      n match {
	case 0 => (src, dst)
	case _ => {
	  val (rest, removed) = P20.removeAt(Random.nextInt(src.size), src)
	  f(n - 1, rest, removed :: dst)
        }
      }
    }
    f(length, list, List())._2
  }

  def test {
    {
      val length = 3
      val list = List('a, 'b, 'c, 'd, 'f, 'g, 'h)
      val result1 = randomSelect(length, list)
      result1.size should equal(length)
      val result2 = randomSelect(length, list)
      result2.size should equal(length)
      (result1 zip result2 zip list filter {
        case ((a, b), c) => a == b && b == c && c == a
      }).size should be < length
    }
  }
}

// P24: Lotto: Draw N different random numbers from the set 1..M.
object P24 {
  def lotto(length: Int, max: Int): List[Int] = {
    P23.randomSelect(length, 1 to max toList)
  }

  def test {
    {
      val length = 6
      val max = 49
      val expected = List(23, 1, 17, 33, 21, 37)
      val result = lotto(length, max)
      result foreach {
        case each => each should be <= max
      }
      result.size should equal(6)
    }
  }
}

// P25: Generate a random permutation of the elements of a list.
//   Hint: Use the solution of problem P23.
object P25 {
  def randomPermute[T](list: List[T]): List[T] = {
    P23.randomSelect(list.size, list)
  }

  def test {
    {
      val list = List('a, 'b, 'c, 'd, 'e, 'f)
      val result1 = randomPermute(list)
      result1.size should equal(list.length)
      val result2 = randomPermute(list)
      result2.size should equal(list.length)
      (result1 zip result2 zip list filter {
        case ((a, b), c) => {
          a == b && b == c && c == a
        }
      }).size should be < list.length
    }
  }
}

// P26: Generate the combinations of K distinct objects chosen from the N elements of a list.
// In how many ways can a committee of 3 be chosen from a group of 12 people?
// We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficient).
// For pure mathematicians, this result may be great. But we want to really generate all the possibilities.
object P26 {
  def combinations[T](n: Int, list: List[T]): List[List[T]] = {
    // TODO
    throw new NotImplementedYet
  }

  def test {
    {
      val n = 3
      val list = List('a, 'b, 'c, 'd, 'e, 'f)
      val expected: List[List[Symbol]] =
        List(
          List('a, 'b, 'c), List('a, 'b, 'd),
          List('a, 'b, 'e), List('a, 'b, 'f),
          List('a, 'c, 'd), List('a, 'c, 'e),
          List('a, 'c, 'f), List('a, 'd, 'e),
          List('a, 'd, 'f), List('a, 'e, 'f),
          List('b, 'c, 'd), List('b, 'c, 'e),
          List('b, 'c, 'f), List('b, 'd, 'e),
          List('b, 'd, 'f), List('b, 'e, 'f),
          List('c, 'd, 'e), List('c, 'd, 'f),
          List('c, 'e, 'f), List('d, 'e, 'f)
        )
      val result = combinations(n, list)
      result.size should equal(20)
      result should equal(expected)
    }
  }
}

// P27: Group the elements of a set into disjoint subsets.
object P27 {

  // a) In how many ways can a group of 9 people work in 3 disjoint subgroups of 2, 3 and 4 persons?
  //   Write a function that generates all the possibilities.
  def group3(list: List[String]): List[List[List[String]]] = {
    // TODO
    throw new NotImplementedYet
  }

  // b) Generalize the above predicate in a way that we can specify a list of group sizes
  //   and the predicate will return a list of groups.
  def group(nums: List[Int], members: List[String]): List[List[List[String]]] = {
    // TODO
    throw new NotImplementedYet
  }

  def test {
    {
      val list = List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida")
      val result = group3(list)
      result.size should equal(1260)
    }
    {
      val nums = List(2, 2, 5)
      val list = List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida")
      val result = group(nums, list)
      result.size should equal(756)
    }
  }
}

// P28: Sorting a list of lists according to length of sublists.
object P28 {

  // a) We suppose that a list contains elements that are lists themselves.
  //   The objective is to sort the elements of the list according to their length.
  //   E.g. short lists first, longer lists later, or vice versa.
  def lsort[T](listOfLists: List[List[T]]): List[List[T]] = {
    // TODO
    throw new NotImplementedYet
  }

  // b) Again, we suppose that a list contains elements that are lists themselves.
  //   But this time the objective is to sort the elements according to their length frequency;
  //   i.e. in the default, sorting is done ascendingly, lists with rare lengths are placed,
  //   others with a more frequent length come later.
  def lsortFreq[T](list: List[List[T]]): List[List[T]] = {
    // TODO
    throw new NotImplementedYet
  }

  def test {
    {
      val listOfLists = List(List('a, 'b, 'c), List('d, 'e), List('f, 'g, 'h), List('d, 'e), List('i, 'j, 'k, 'l), List('m, 'n), List('o))
      val expected = List(List('o), List('d, 'e), List('d, 'e), List('m, 'n), List('a, 'b, 'c), List('f, 'g, 'h), List('i, 'j, 'k, 'l))
      lsort(listOfLists) should equal(expected)
    }
    {
      val listOfLists = List(List('a, 'b, 'c), List('d, 'e), List('f, 'g, 'h), List('d, 'e), List('i, 'j, 'k, 'l), List('m, 'n), List('o))
      val expected = List(List('i, 'j, 'k, 'l), List('o), List('a, 'b, 'c), List('f, 'g, 'h), List('d, 'e), List('d, 'e), List('m, 'n))
      lsortFreq(listOfLists) should equal(expected)
    }
  }
}

P21.test
P22.test
P23.test
P24.test
P25.test
P26.test
P27.test
P28.test

// vim: set ts=4 sw=4 et: