My solutions to 99 scala problems (http://aperiodic.net/phil/scala/s-99/) adapted from Werner Hatt's 99 Prolog Problems

99-problems.scala

import scala.annotation
import scala.util.Random

// Working with lists

// 1
def findLast[T](l: List[T]): T = l match {
  case t :: Nil => t
  case t :: tail => findLast(tail)
  case Nil => throw new IllegalArgumentException
}

// 2
def findPenultimate[T](l: List[T]): T = l match {
  case Nil => throw new IllegalArgumentException
  case t :: Nil => throw new IllegalArgumentException
  case t :: u :: Nil => t
  case t :: tail => findPenultimate(tail)
}

// 3
def findKth[T](k: Int, l: List[T]): T = k match {
  case 0 => l.head
  case n => findKth(n - 1, l.tail)
}

// 4
def length[T](l: List[T]) = {
  @annotation.tailrec
  def lengthAcc[T](l: List[T], n: Int): Int = l match {
    case Nil => n
    case head :: tail => lengthAcc(tail, n + 1)
  }
  lengthAcc(l, 0)
}

// 5
def reverse[T](l: List[T]) =
  l.foldLeft(List.empty[T]) { (r, h) => h :: r }

// 6
def isPalindrome(l: List[Int]): Boolean =
  (l zip l.reverse) forall { case (x, y) => x == y }

// 7
def flatten(l: List[Any]): List[Any] =
  l.foldLeft(List.empty[Any])((acc, el) => el match {
    case list @ head :: tail => acc ++ flatten(list)
    case x => acc :+ x
  })

// 8
def compress(l: List[Int]): List[Int] = l match {
  case Nil => Nil
  case xs :: ls => xs :: compress(ls dropWhile (_ == xs))
}

// 9
def pack[A](l: List[A]): List[List[A]] = l.foldRight(List.empty[List[A]])((xs, ls) =>
    if (ls.isEmpty || ls.head.head != xs) {
      List(xs) :: ls
    } else {
      (xs :: ls.head) :: ls.tail
    })

// 10
def encode[A](l: List[A]): List[(A, Int)] = pack(l) map (ls => (ls.head, ls.length))

// 11
def encodeModified[A](l: List[A]): List[Any] = encode(l) map (t2 => if (t2._2 == 1) t2._1 else t2)

// 12
def decode[A](l: List[(Int, A)]) = l flatMap {
  case (count, value) => List.fill(count)(value)
}

// 13
def encodeDirect[A](l: List[A]): List[(Int, A)] = l.foldRight(List.empty[(Int, A)])((a, l) =>
    if (l.isEmpty || a != l.head._2) {
      (1, a) :: l
    } else {
      (l.head._1 + 1, a) :: l.tail
    })

// 14
def duplicate[A](l: List[A]) = l.foldRight(List.empty[A])((x, acc) => x :: x :: acc)

// 15
def duplicateN[A](n: Int, l: List[A]) = l flatMap (List.fill(n)(_))

// 16
def drop[A](n: Int)(l: List[A]) = l.foldRight((1, List.empty[A])) {
  case (el, (count, l)) => if (count % n == 0) (count + 1, l) else (count + 1, el :: l)
}._2

// 17
def split[A](n: Int)(l: List[A]) = (l.take(n), l.drop(n))

def splitManual[A](n: Int)(l: List[A]) = {
  @annotation.tailrec
  def go(count: Int, l: List[A], acc: List[A]): (List[A], List[A]) = l match {
    case Nil => (acc.reverse, Nil)
    case list @ x :: xs => count match {
      case `n` => (acc.reverse, list)
      case _ => go(count + 1, xs, x :: acc)
    }
  }
  go(0, l, List.empty[A])
}

// 18
def slice[A](start: Int, end: Int)(l: List[A]) = l.foldRight((l.length - 1, List.empty[A])) {
  case (el, (index, acc)) => if (index >= start && index < end) (index - 1, el :: acc) else (index - 1, acc)
}._2

// 19
def rotate[A](n: Int)(l: List[A]): List[A] = {
  val rot = if (n < 0) l.length - (-n % l.length) else n % l.length
  l.drop(rot) ++ l.take(rot)
}

// 20
def removeAt[A](k: Int)(l: List[A]): (List[A], A) = {
  @annotation.tailrec
  def removeAtTailRec(k: Int, l: List[A], acc: List[A]): (List[A], A) =
    if (k == 0) (acc.reverse ++ l.tail, l.head) else removeAtTailRec(k - 1, l.tail, l.head :: acc)
  removeAtTailRec(k, l, List.empty[A])
}

// 21
def insertAt[A](el: A, k: Int)(l: List[A]): List[A] = if (k == 0) el :: l else l.head :: insertAt(el, k - 1)(l.tail)

// 22
def range(start: Int, end: Int): List[Int] = if (start == end) List(end) else start :: range(start + 1, end)

// 23
def randomSelect[A](n: Int)(l: List[A]): List[A] = if (n == 0) Nil else {
  val (xs, s) = removeAt(Random.nextInt(l.length))(l)
  s :: randomSelect(n - 1)(xs)
}

// 24
def lotto(n: Int, m: Int) = randomSelect(n)(range(1, m))

// 25
def randomPermute[A](l: List[A]): List[A] = randomSelect(l.length)(l)

// 26

// bad implementation. generates permutations and then converts toSet to
// eliminate duplicates
def combinations[A](n: Int)(l: List[A]): List[List[A]] = {
  def go(n: Int)(l: List[A]): List[List[A]] =
    if (n == 1) l map (List(_)) else {
      range(0, l.length - 1).flatMap { case index =>
        val (elRemoved, el) = removeAt(index)(l)
        combinations(n-1)(elRemoved).map { case combo =>
          el :: combo
        }
      }
    }
  val x = go(n)(l).map(_.toSet).toSet
  x.map(_.toList).toList
}

// 27.a
def group3[A](l: List[A]): List[List[List[A]]] = for {
  groupOf2 <- combinations(2)(l)
  membersWithoutGroupOf2 = l filterNot (groupOf2 contains _)
  groupOf3 <- combinations(3)(membersWithoutGroupOf2)
} yield List(groupOf2, groupOf3)

// 27.b
def group[A](sizes: List[Int])(l: List[A]): List[List[List[A]]] = sizes match {
  case x :: Nil => List(combinations(x)(l))
  case x :: xs => for {
    combo <- combinations(x)(l)
    remaining = l.filterNot(combo.contains(_))
    groupWithoutCombo <- group(xs)(remaining)
  } yield (combo :: groupWithoutCombo)
}

// 28
def lsort[A](l: List[List[A]]): List[List[A]] = l sortWith (_.length < _.length)

// Logic and Codes
// 46
val and = (a: Boolean, b: Boolean) => a && b
val or = (a: Boolean, b: Boolean) => a || b
val nand = (a: Boolean, b: Boolean) => !and(a, b)
val xor = (a: Boolean, b: Boolean) => or(a, b) && nand(a, b)
val equ = (a: Boolean, b: Boolean) => a == b
def table2(f: (Boolean, Boolean) => Boolean): Unit = {
  println("A     B     result")
  println(s"true  true  ${f(true, true)}")
  println(s"true  false ${f(true, false)}")
  println(s"false true  ${f(false, true)}")
  println(s"false false ${f(false, false)}")
}

// 49
def gray(n: Int): List[String] = if (n == 1) {
  List("0", "1")
} else {
  gray(n - 1) flatMap { el =>
    List("1" + el, "0" + el)
  }
}

// 50
import scala.collection.mutable.PriorityQueue

trait Node {
  val weight: Int
}
case class Internal(weight: Int, left: Node, right: Node) extends Node
case class Leaf(weight: Int, symbol: String) extends Node

object HuffmanOrdering extends Ordering[Node] {
  def compare(a: Node, b: Node) = b.weight compare a.weight
}

def huffman(l: List[(String, Int)]): List[(String, String)] = {
  def makeTree: Node = {
    val q = new PriorityQueue()(HuffmanOrdering)
    q ++= (l map (p => Leaf(p._2, p._1)))
    while (q.size > 1) {
      val node1 = q.dequeue
      val node2 = q.dequeue
      val node3 = Internal(node1.weight + node2.weight, node1, node2)
      q.enqueue(node3)
    }
    q.dequeue
  }

  def encode(node: Node, repr: String): List[(String, String)] = node match {
    case Leaf(_, symbol) => List((symbol, repr))
    case Internal(_, left, right) => encode(left, repr + "0") ++ encode(right, repr + "1")
  }

  encode(makeTree, "")
}