Created
August 24, 2011 09:18
-
-
Save seratch/1167669 to your computer and use it in GitHub Desktop.
S-99 P11-P20 My answers
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] = { | |
P10.encode(list) map { | |
case (1, elem) => elem | |
case (len, elem) => (len, elem) | |
case _ => throw new IllegalArgumentException | |
} | |
} | |
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] = { | |
list flatMap { | |
// List#make is deprecated | |
// case (num, elem) => for( i <- 1 to num) yield elem | |
case (num, elem) => List.fill(num)(elem) | |
case _ => throw new IllegalArgumentException | |
} | |
} | |
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)] = { | |
if ( list.isEmpty ) Nil | |
else { | |
val (packed, next) = list span { _ == list.head } | |
next match { | |
case Nil => List((packed.length, packed.head)) | |
case _ => (packed.length, packed.head) :: encodeDirect(next) | |
} | |
} | |
} | |
def test { | |
encodeDirect(Nil) should equal(Nil) | |
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] = list flatMap { e => List(e,e) } | |
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] = { | |
// List#make is deprecated | |
// list flatMap { e => for (i <- 1 to times) yield e } | |
list flatMap { e => List.fill(times)(e) } | |
} | |
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] = { | |
val indicesToDrop = Range(nth-1,list.length,nth) | |
// IndexedSeq is faster than List for random access | |
val iseq = list.toIndexedSeq | |
(list.indices filter { !indicesToDrop.contains(_) } map { | |
i => iseq(i) | |
}).toList | |
} | |
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](n: Int, list: List[T]): (List[T], List[T]) = { | |
// list.splitAt(n) | |
(list.take(n), list.drop(n)) | |
} | |
def test { | |
val n = 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(n, 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] = { | |
val leftTrimmed = list.drop(startIndex) | |
val rightTrimmed = list.dropRight(list.length-endIndex) | |
(leftTrimmed.toSet & rightTrimmed.toSet).toList.sortWith { _.toString < _.toString } | |
} | |
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] = { | |
list.drop(n) ::: list.take(n) | |
} | |
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) = { | |
list splitAt(n) match { | |
case (leftN, t) => (leftN ::: t.tail, t.head) | |
case _ => throw new IllegalArgumentException | |
} | |
} | |
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 | |
// 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