Created
August 20, 2011 16:41
-
-
Save seratch/1159315 to your computer and use it in GitHub Desktop.
S-99 P11-P20 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-11-20.scala | |
import org.scalatest.matchers.ShouldMatchers._ | |
class NotImplementedYet extends RuntimeException | |
// P09: Pack consecutive duplicates of list elements into sublists. | |
// If a list contains repeated elements they should be placed in separate sublists. | |
object P09 { | |
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) | |
} | |
} | |
} | |
// P10: Run-length encoding of a list. | |
// Use the result of problem P09 to implement the so-called run-length encoding data compression method. | |
// Consecutive duplicates of elements are encoded as tuples (N, E) | |
// where N is the number of duplicates of the element E. | |
object P10 { | |
def encode[A](ls: List[A]): List[(Int, A)] = P09.pack(ls) map { | |
e => (e.length, e.head) | |
} | |
} | |
// P11: Modified run-length encoding. | |
// Modify the result of problem P10 in such a way that if an element has no duplicates | |
// it is simply copied into the result list. | |
// Only elements with duplicates are transferred as (N, E) terms. | |
object P11 { | |
def encodeModified[T](list: List[T]): List[Any] = { | |
// TODO | |
throw new NotImplementedYet | |
} | |
def test { | |
val list = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e) | |
val expected = List((4, 'a), 'b, (2, 'c), (2, 'a), 'd, (4, 'e)) | |
encodeModified(list) should equal(expected) | |
} | |
} | |
// P12: Decode a run-length encoded list. | |
// Given a run-length code list generated as specified in problem P10, construct its uncompressed version. | |
object P12 { | |
def decode[T](list: List[(Int, T)]): List[T] = { | |
// TODO | |
throw new NotImplementedYet | |
} | |
def test { | |
val list = List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e)) | |
val expected = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e) | |
decode(list) should equal(expected) | |
} | |
} | |
// P13: Run-length encoding of a list (direct solution). | |
// Implement the so-called run-length encoding data compression method directly. | |
// I.e. don't use other methods you've written (like P09's pack); do all the work directly. | |
object P13 { | |
def encodeDirect[T](list: List[T]): List[(Int, T)] = { | |
// TODO | |
throw new NotImplementedYet | |
} | |
def test { | |
val list = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e) | |
val expected = List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e)) | |
encodeDirect(list) should equal(expected) | |
} | |
} | |
// P14: Duplicate the elements of a list. | |
object P14 { | |
def duplicate[T](list: List[T]): List[T] = { | |
// TODO | |
throw new NotImplementedYet | |
} | |
def test { | |
val list = List('a, 'b, 'c, 'c, 'd) | |
val expected = List('a, 'a, 'b, 'b, 'c, 'c, 'c, 'c, 'd, 'd) | |
duplicate(list) should equal(expected) | |
} | |
} | |
// P15: Duplicate the elements of a list a given number of times. | |
object P15 { | |
def duplicateN[T](times: Int, list: List[T]): List[T] = { | |
// TODO | |
throw new NotImplementedYet | |
} | |
def test { | |
val times = 3 | |
val list = List('a, 'b, 'c, 'c, 'd) | |
val expected = List('a, 'a, 'a, 'b, 'b, 'b, 'c, 'c, 'c, 'c, 'c, 'c, 'd, 'd, 'd) | |
duplicateN(times, list) should equal(expected) | |
} | |
} | |
// P16: Drop every Nth element from a list. | |
object P16 { | |
def drop[T](nth: Int, list: List[T]): List[T] = { | |
// TODO | |
throw new NotImplementedYet | |
} | |
def test { | |
val nth = 3 | |
val list = List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k) | |
val expected = List('a, 'b, 'd, 'e, 'g, 'h, 'j, 'k) | |
drop(nth, list) should equal(expected) | |
} | |
} | |
// P17: Split a list into two parts. | |
object P17 { | |
def split[T](lengthOfTheFirstPart: Int, list: List[T]): (List[T], List[T]) = { | |
// TODO | |
throw new NotImplementedYet | |
} | |
def test { | |
val lengthOfTheFirstPart = 3 | |
val list = List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k) | |
val expected = (List('a, 'b, 'c), List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k)) | |
split(lengthOfTheFirstPart, list) should equal(expected) | |
} | |
} | |
// P18: Extract a slice from a list. | |
// Given two indices, I and K, the slice is | |
// the list containing the elements from and including the Ith element up to | |
// but not including the Kth element of the original list. | |
// Start counting the elements with 0. | |
object P18 { | |
def splice[T](startIndex: Int, endIndex: Int, list: List[T]): List[T] = { | |
// TODO | |
throw new NotImplementedYet | |
} | |
def test { | |
val startIndex = 3 | |
val endIndex = 7 | |
val list = List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k) | |
val expected = List('d, 'e, 'f, 'g) | |
splice(startIndex, endIndex, list) should equal(expected) | |
} | |
} | |
// P19: Rotate a list N places to the left. | |
object P19 { | |
def rotate[T](n: Int, list: List[T]): List[T] = { | |
// TODO | |
throw new NotImplementedYet | |
} | |
def test { | |
val n = 3 | |
val list = List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k) | |
val expected = List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'a, 'b, 'c) | |
rotate(n, list) should equal(expected) | |
} | |
} | |
// P20: Remove the Kth element from a list. | |
object P20 { | |
def removeAt[T](n: Int, list: List[T]): (List[T], T) = { | |
// TODO | |
throw new NotImplementedYet | |
} | |
def test { | |
val list = List('a, 'b, 'c, 'd) | |
removeAt(0, list) should equal((List('b, 'c, 'd), 'a)) | |
removeAt(1, list) should equal((List('a, 'c, 'd), 'b)) | |
removeAt(2, list) should equal((List('a, 'b, 'd), 'c)) | |
} | |
} | |
P11.test | |
P12.test | |
P13.test | |
P14.test | |
P15.test | |
P16.test | |
P17.test | |
P18.test | |
P19.test | |
P20.test | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment