arithmetic.scala

/* *** Arithmetic *** */

import Math._
import S99Int._

class S99Int(val start: Int) {
  def isPrime: Boolean = {
    (true /: List.range(2, start / 2)) { (decision, n) =>
      decision && start % n != 0
    }
  }
}

object S99Int {
  implicit def int2S99Int(i: Int): S99Int = new S99Int(i)

  def gcd(a: Int, b: Int): Int = {
    // to be implemented
  }
}

// P31
assert(7.isPrime, "7 is prime.");
assert(!14.isPrime, "14 is not prime.");

// P32
assert(gcd(36, 63) == 9, "The GCD of 36 and 63 is 9.")

ninety-nine-problems.scala

/**
 * Ninety-Nine Scala Problems
 * <http://aperiodic.net/phil/scala/s-99/>
 *
 * My solutions to Ninety-Nine Scala Problems, a set of exercises in Scala to
 * build familiarity with functional programming in general and with Scala in
 * particular.  The problems are adapted from Ninety-Nine Prolog Problems
 * <https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/>.
 */

import java.util.Random

def last[A](list: List[A]) : Option[A] = {
  list match {
    case Nil => None
    case head::Nil => Some(head)
    case head::tail => last(tail)
  }
}

def penultimate[A](list: List[A]) : Option[A] = {
  list match {
    case Nil => None
    case head::Nil => None
    case head::next::Nil => Some(head)
    case head::next::tail => penultimate(next::tail)
  }
}

def nth[A](n: Int, list: List[A]) : Option[A] = {
  (n, list) match {
    case (_, Nil) => None
    case (0, head::tail) => Some(head)
    case (n, head::tail) => nth(n - 1, tail)
  }
}

def length[A](list: List[A]) : Int = {
  (0 /: list) { (len, e) => len + 1 }
}

def reverse[A](list: List[A]) : List[A] = {
  list match {
    case Nil => Nil
    case head::tail => reverse(tail):::List(head)
  }
}

def isPalindrome[A](list: List[A]) : Boolean = {
  list == reverse(list)
}

def flatten(list: List[Any]) : List[Any] = {
  list match {
    case Nil => Nil
    case (h::Nil)::tail => flatten(h::tail)
    case (h::t)::tail   => flatten(h::t::tail)
    case Nil::tail      => flatten(tail)
    case head::tail     => head::flatten(tail)
  }
}

assert(flatten(List(List(1, List(2, 3)))) == List(1, 2, 3), "can flatten nested lists")
assert(flatten(List(1, List(2, 3), List(4, 5, List(6, 7, List(8), List())))) == List(1, 2, 3, 4, 5, 6, 7, 8), "can flatten deeply nested lists")
assert(flatten(List(1, 2, 3)) == List(1, 2, 3), "fattening an already-flat list is a no-op")
assert(flatten(List(List(1, 2), 3)) == List(1, 2, 3), "can flatten nested list as first element")
assert(flatten(List()) == Nil, "flattened empty list is an empty list")

def compress[A](list: List[A]) : List[A] = {
  list match {
    case a::b::tail => if (a == b) compress(a::tail) else a::compress(b::tail)
    case _ => list
  }
}

assert(compress(List('a, 'a, 'a, 'b, 'b)) == List('a, 'b), "can compress a list")
assert(compress(List('a, 'b)) == List('a, 'b), "does not over-compress")
assert(compress(List()) == List(), "compress does not choke on an empty list")

def pack[A](list: List[A]) : List[List[A]] = {
  list match {
    case Nil => Nil
    case head::_ => (list.takeWhile { _ == head })::pack(list.dropWhile { _ == head })
  }
}

assert(pack(List('a, 'a, 'b, 'b, 'b)) == List(List('a, 'a), List('b, 'b, 'b)), "can pack lists")
assert(pack(List('a, 'a, 'b, 'b, 'a)) == List(List('a, 'a), List('b, 'b), List('a)), "pack handles isolated runs of the same value")

def encode[A](list: List[A]) : List[(Int, A)] = {
  pack(list).map { run => (run.length, run.head) }
}

assert(encode(List('a, 'a, 'b, 'b, 'b)) == List((2, 'a), (3, 'b)), "can encode lists")
assert(encode(List('a, 'a, 'b, 'b, 'a)) == List((2, 'a), (2, 'b), (1, 'a)), "encode handles isolated runs of the same value")

def encodeModified[A](list: List[A]) : List[Any] = {
  pack(list).map { run => if (run.length == 1) run.head else (run.length, run.head) }
}

assert(encodeModified(List('a, 'a, 'c, 'b, 'b, 'b)) == List((2, 'a), 'c, (3, 'b)), "does not encode single appearances of a value")

def decode[A](list: List[(Int, A)]) : List[A] = {
  def makeRun(length: Int, value: A) : List[A] = {
    length match {
      case 0 => Nil
      case n => value::makeRun(n - 1, value)
    }
  }
  list match {
    case Nil => Nil
    case (length, value)::tail => makeRun(length, value):::decode(tail)
  }
}

assert(decode(List((2, 'a), (3, 'b))) == List('a, 'a, 'b, 'b, 'b), "can decode lists")
assert(decode(List((2, 'a), (2, 'b), (1, 'a))) == List('a, 'a, 'b, 'b, 'a), "decode handles isolated runs of the same value")

def encodeDirect[A](list: List[A]) : List[(Int, A)] = {
  list match {
    case Nil => Nil
    case head::_ =>
      val (run, rest) = list.span { _ == head }
      (run.length, head)::encodeDirect(rest)
  }
}

assert(encodeDirect(List('a, 'a, 'b, 'b, 'b)) == List((2, 'a), (3, 'b)), "can encode lists")
assert(encodeDirect(List('a, 'a, 'b, 'b, 'a)) == List((2, 'a), (2, 'b), (1, 'a)), "encode handles isolated runs of the same value")

def duplicate[A](list: List[A]) : List[A] = {
  list match {
    case Nil => Nil
    case h::t => h::h::duplicate(t)
  }
}

assert(duplicate(List('a, 'b, 'c, 'c, 'd)) == List('a, 'a, 'b, 'b, 'c, 'c, 'c, 'c, 'd, 'd), "duplicates each list element in place")

def duplicateN[A](n: Int, list: List[A]) : List[A] = {
  def mkList[B](length: Int, value: B) : List[B] = {
    if (length > 0) value::mkList(length - 1, value) else Nil
  }
  list match {
    case Nil => Nil
    case h::t => mkList(n, h):::duplicateN(n, t)
  }
}

assert(duplicateN(2, List('a, 'b, 'c, 'c, 'd)) == List('a, 'a, 'b, 'b, 'c, 'c, 'c, 'c, 'd, 'd), "duplicates each list element in place")
assert(duplicateN(3, List('a, 'b, 'c, 'c, 'd)) == List('a, 'a, 'a, 'b, 'b, 'b, 'c, 'c, 'c, 'c, 'c, 'c, 'd, 'd, 'd), "duplicates each list element three times")
assert(duplicateN(1, List('a, 'b, 'c, 'c, 'd)) == List('a, 'b, 'c, 'c, 'd), "duplicating with an argument of 1 is a no-op")

def drop[A](interval: Int, list: List[A]) : List[A] = {
  def recursiveDrop[A](n: Int, l: List[A]) : List[A] = {
    (n, l) match {
      case (_, Nil) => Nil
      case (1, h::t) => recursiveDrop(interval, t)
      case (n, h::t) => h::recursiveDrop(n - 1, t)
    }
  }
  recursiveDrop(interval, list)
}

assert(drop(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k)) == List('a, 'b, 'd, 'e, 'g, 'h, 'j, 'k), "drops every third element from a list")

def split[A](firstPartLength: Int, list: List[A]) : (List[A], List[A]) = {
  val (first, last) = list.zipWithIndex.span { e => e._2 < firstPartLength }
  (first.map { _._1 }, last.map { _._1 })
}

assert(split(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k)) == (List('a, 'b, 'c),List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k)),
  "splits a list into two parts")

def slice[A](start: Int, end: Int, list: List[A]) : List[A] = {
  list.drop(start).take(end - start)
}

assert(slice(3, 7, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k)) == List('d, 'e, 'f, 'g),
  "retrieves a portion of a list with slice")

def rotate[A](n: Int, list: List[A]) : List[A] = {
  val places = (if (n >= 0) n else list.length + n) % list.length
  list.drop(places):::list.take(places)
}

assert(rotate(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k)) == List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'a, 'b, 'c),
  "rotates list 3 places to the left")
assert(rotate(-2, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k)) == List('j, 'k, 'a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i),
  "rotates list 2 places to the right")

def removeAt[A](index: Int, list: List[A]) : (List[A], Option[A]) = (index, list) match {
  case (_, Nil) => (Nil, None)
  case (0, h::t) => (t, Some(h))
  case (n, h::t) => {
    val (remainder, value) = removeAt(n - 1, t)
    (h::remainder, value)
  }
}

assert(removeAt(1, List('a, 'b, 'c, 'd)) == (List('a, 'c, 'd), Some('b)), "removes the second element from a list")
assert(removeAt(6, List('a, 'b, 'c, 'd)) == (List('a, 'b, 'c, 'd), None), "removeAt gracefully handles a list that is too short")

def insertAt[A](value: A, position: Int, list: List[A]) : List[A] = (position, list) match {
  case (0, _) => value::list
  case (_, Nil) => value::Nil
  case (_, h::t) => h::insertAt(value, position - 1, t)
}

assert(insertAt('new, 1, List('a, 'b, 'c, 'd)) == List('a, 'new, 'b, 'c, 'd), "inserts a value at the second position in a list")

def range(start: Int, end: Int) : List[Int] = {
  def builder(n: Int, l: List[Int]) : List[Int] = {
    if (n >= start) builder(n - 1, n::l) else l
  }
  builder(end, Nil)
}

assert(range(4, 9) == List(4, 5, 6, 7, 8, 9), "creates a list with all integers in a given inclusive range")

def randomSelect[A](count: Int, source: List[A]): List[A] = {
  if (count > 0) {
    val index = (new Random()).nextInt(source.length)
    val (remaining, Some(value)) = removeAt(index, source)
    value::randomSelect(count - 1, remaining)
  } else {
    Nil
  }
}

val randomSelectSource = List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h)
val randomSelection = randomSelect(3, randomSelectSource)
assert(randomSelection.length == 3, "selects 3 elements from a list")
assert(randomSelection.forall { randomSelectSource.contains(_) }, "every selected value actually comes from the list")
assert(randomSelection == randomSelection.removeDuplicates, "randomSelect does not select the same element twice")

def lotto(count: Int, limit: Int): List[Int] = {
  randomSelect(count, range(1, limit))
}

assert(lotto(6, 49).length == 6, "lotto generates 6 random numbers")
assert(lotto(6, 49).forall { n => n >= 1 && n <= 49 }, "lotto generates numbers between 1 and 49")
val lottoSample = lotto(6, 49)
assert(lottoSample == lottoSample.removeDuplicates, "all of the numbers that lotto generates are different")

def randomPermute[A](list: List[A]): List[A] = {
  randomSelect(list.length, list)
}

assert(randomPermute(List('a, 'b, 'c, 'd, 'e, 'f)).length == 6, "randomPermute produces a list of the same length as its input")
assert(randomPermute(List('a, 'b, 'c, 'd, 'e, 'f)).forall { n => List('a, 'b, 'c, 'd, 'e, 'f).contains(n) },
  "all of the elements produced by randomPermute are contained in the original list")
val randomPermuteSample = randomPermute(List('a, 'b, 'c, 'd, 'e, 'f))
assert(randomPermuteSample == randomPermuteSample.removeDuplicates, "all of the elements that randomPermute generates are different")

def fact(n: Int): Int = n match {
  case 1 => 1
  case _ => n * fact(n - 1)
}

// binomial coefficient
def C(n: Int, k: Int): Int = {
  fact(n) / (fact(k) * fact(n - k))
}

def combinations[A](n: Int, list: List[A]): List[List[A]] = (n, list) match {
  case (0, _) => Nil
  case (_, Nil) => Nil
  case (1, _) => list.map { List(_) }
  case (_, h::t) => (combinations(n - 1, t).map { h::_ }):::combinations(n, t)
}

assert(C(7, 3) == 35, "7 choose 3 is 35")
assert(C(12, 3) == 220, "12 choose 3 is 220")
assert(combinations(3, List('a, 'b, 'c, 'd, 'e, 'f)).length == C(6, 3),
  "there are 20 possible combinations of 3 elements each given 6 elements to choose from")