Skip to content

Instantly share code, notes, and snippets.

@seratch
Created August 20, 2011 16:41
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save seratch/1159315 to your computer and use it in GitHub Desktop.
Save seratch/1159315 to your computer and use it in GitHub Desktop.
S-99 P11-P20 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-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