Created
August 24, 2011 11:32
-
-
Save seratch/1167860 to your computer and use it in GitHub Desktop.
S-99 P21-P28 blank
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // *** 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