Create a gist now

Instantly share code, notes, and snippets.

S-99 P21-P28 blank
// *** S-99: Ninety-Nine Scala Problems ***
// http://aperiodic.net/phil/scala/s-99/
//
// wget http://www.scala-tools.org/repo-releases/org/scalatest/scalatest_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._
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] = {
// TODO
throw new NotImplementedYet
}
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] = {
// TODO
throw new NotImplementedYet
}
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] = {
// TODO
throw new NotImplementedYet
}
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] = {
// TODO
throw new NotImplementedYet
}
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] = {
// TODO
throw new NotImplementedYet
}
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:
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment