Skip to content

Instantly share code, notes, and snippets.

@seratch

seratch/gist:1183495

Created August 31, 2011 13:06
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save seratch/1183495 to your computer and use it in GitHub Desktop.
Save seratch/1183495 to your computer and use it in GitHub Desktop.
Download ZIP
S-99 P21-P28 My Work
Raw
gistfile1.scala
// *** 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 scal.test-*.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] = {
list.splitAt(n) match {
//case (pre,post) => pre ::: List(element) ::: post
case (pre,post) => pre ::: element :: post
case _ => throw new IllegalArgumentException
}
}
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] = {
// Range(from, to+1).toList
// from to to toList
def recursive(to: Int, result: List[Int]): List[Int] = {
if (to < from) result
else recursive(to-1, to :: result)
}
//recursive(to, Nil)
def unfoldr(start: Int)(func: Int => Option[(Int,Int)]): List[Int] = {
func(start) match {
case None => Nil
case Some((i, j)) => i :: unfoldr(j)(func)
}
}
unfoldr(from) { i =>
if (i > to) None
else Some((i, i+1))
}
}
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] = {
util.Random.shuffle(list).take(length)
}
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] = {
// util.Random.shuffle(Range(0,max).toList).take(length)
P23.randomSelect(length, Range(0,max).toList)
}
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] = {
// util.Random.shuffle(list)
byFisherYatesShuffle(list)
}
private def byFisherYatesShuffle[T](list: List[T]): List[T] = {
val r = new util.Random
val arr = list.toBuffer
for ( i <- arr.length-1 to 1 by -1) {
val j = r.nextInt(i+1)
val t = arr(i)
arr.update(i, arr(j))
arr.update(j, t)
}
arr.toList
}
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]] = {
if (n == 0) List(Nil)
else {
def execute(ls: List[T]): List[List[T]] = {
val head = ls.head
val tailCombis = combinations(n-1, ls.tail)
tailCombis map { tailCombi: List[T] => { head :: tailCombi } }
}
val f = execute _
sublists(list) flatMap f
}
}
def sublists[A](list: List[A]) : List[List[A]] = {
list match {
case Nil => Nil
case _ :: tail => list :: sublists(tail)
}
}
def test {
{
val n = 2
val list = List('a, 'b, 'c, 'd, 'e, 'f)
val result = combinations(n, list)
val expected = List(
List('a, 'b), List('a, 'c), List('a, 'd), List('a, 'e),
List('a, 'f), List('b, 'c), List('b, 'd), List('b, 'e),
List('b, 'f), List('c, 'd), List('c, 'e), List('c, 'f),
List('d, 'e), List('d, 'f), List('e, 'f)
)
result should equal(expected)
}
{
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]]] = {
/*
P26.combinations(2, list) flatMap {
case two => {
val withoutTwo = list filterNot { e => two.contains(e) }
P26.combinations(3, withoutTwo) map {
case three => {
val four = withoutTwo filterNot { e => three.contains(e) }
List(two, three, four)
}
}
}
}
*/
for {
a <- P26.combinations(2, list)
notInA = list filterNot { a.contains _ }
b <- P26.combinations(3, notInA)
} yield List(a, b, notInA filterNot { b contains _ })
}
// 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]]] = {
nums match {
case Nil => List(Nil)
case n :: numtail => P26.combinations(n, members) flatMap {
case combi => {
val notInCombi = members filterNot { combi contains _ }
group(numtail, notInCombi) map { grouped => combi :: grouped }
}
}
}
}
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]] = {
listOfLists sortWith { (a,b) => a.length < b.length }
}
// 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]] = {
// val freqs = Map(P10.encode(list map { _.length } sort { _ < _ }) map { _.swap }:_*)
val lengthList = list map { _.length } sortWith { (a,b) => a < b } // List(1, 2, 2, 2, 3, 3, 4)
val encoded = P10.encode(lengthList)) // List((1,1), (3,2), (2,3), (1,4))
val swapedEncoded = encoded map { e => e.swap } // List((1,1), (2,3), (3,2), (4,1))
val freqs = Map(swapedEncoded: _*) // frequencies of length
list sortWith { (a,b) => freqs(a.length) < freqs(b.length) }
}
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