S99.scala

import scala.annotation.tailrec

object S99 {

  object S99Lists {

    @tailrec
    def last[A](list: List[A]): A = list match {
      case Nil     => throw new IllegalArgumentException
      case List(x) => x
      case _ :: xs => last(xs)
    }

    @tailrec
    def penultimate[A](list: List[A]): A = list match {
      case Nil        => throw new IllegalArgumentException
      case List(x, _) => x
      case _ :: xs    => penultimate(xs)
    }

    @tailrec
    def nth[A](index: Int, list: List[A]): A = (index, list) match {
      case (0, x :: _)           => x
      case (i, _ :: xs) if i > 0 => nth(i - 1, xs)
      case _                     => throw new IndexOutOfBoundsException
    }

    def length[A](list: List[A]): Int = list match {
      case Nil     => 0
      case _ :: xs => 1 + length(xs)
    }

    def reverse[A](list: List[A]): List[A] = {
      def moveElements(args: (List[A], List[A])): List[A] = args match {
        case (result, Nil)      => result
        case (current, x :: xs) => moveElements(x :: current, xs)
      }
      moveElements(Nil, list)
    }

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

    def flatten(list: List[Any]): List[Any] = list match {
      case Nil             => Nil
      case Nil :: ls       => flatten(ls)
      case (x :: xs) :: ls => flatten(x :: xs :: ls)
      case e :: ls         => e :: flatten(ls)
    }

    def compress[A](list: List[A]): List[A] = list match {
      case Nil                      => Nil
      case x :: y :: rest if x == y => compress(x :: rest)
      case x :: rest                => x :: compress(rest)
    }

    def pack[A](list: List[A]): List[List[A]] = {
      def go: (List[A], List[A]) => List[List[A]] = {
        case (l1 @ (hd1 :: _), hd2 :: tl2) if hd1 == hd2 => go(hd2 :: l1, tl2)
        case (l1, hd2 :: tl2)                            => l1 :: go(List(hd2), tl2)
        case (l1, Nil)                                   => List(l1)
      }
      list match {
        case Nil     => Nil
        case x :: xs => go(List(x), xs)
      }
    }

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

    def encodeModified(list: List[Any]): List[Any] = {
      def f(n: Int, x: Any) = if (n == 1) x else (n, x)
      def go: (Int, Any, List[Any]) => List[Any] = {
        case (n, x, y :: ys) if x == y => go(n + 1, x, ys)
        case (n, x, y :: ys)           => f(n, x) :: go(1, y, ys)
        case (n, x, Nil)               => List(f(n, x))
      }
      list match {
        case Nil     => Nil
        case x :: xs => go(1, x, xs)
      }
    }

    def decode[A](list: List[(Int, A)]): List[A] = list match {
      case Nil                    => Nil
      case List((n, _)) if n <= 0 => Nil
      case (n, _) :: tl if n <= 0 => decode(tl)
      case (n, x) :: tl           => x :: decode((n - 1, x) :: tl)
    }

    def encodeDirect[A](list: List[A]): List[(Int, A)] = {
      def go: (Int, A, List[A]) => List[(Int, A)] = {
        case (n, x, y :: ys) if x == y => go(n + 1, x, ys)
        case (n, x, y :: ys)           => (n, x) :: go(1, y, ys)
        case (n, x, Nil)               => List((n, x))
      }
      list match {
        case Nil     => Nil
        case x :: xs => go(1, x, xs)
      }
    }

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

    def duplicateN[A](n: Int, list: List[A]): List[A] = {
      require(n >= 0)
      def go: (Int, List[A]) => List[A] = {
        case (_, Nil)        => Nil
        case (0, _ :: xs)    => go(n, xs)
        case (k, l @ x :: _) => x :: go(k - 1, l)
      }
      go(n, list)
    }

    def drop[A](n: Int, list: List[A]): List[A] = {
      require(n > 0)
      def go: (Int, List[A]) => List[A] = {
        case (_, Nil)     => Nil
        case (1, _ :: xs) => go(n, xs)
        case (k, x :: xs) => x :: go(k - 1, xs)
      }
      go(n, list)
    }

    def split[A](n: Int, list: List[A]): (List[A], List[A]) = {
      require(n <= list.size)
      @tailrec
      def go(k: Int, left: List[A], right: List[A]): (List[A], List[A]) = (k, left, right) match {
        case (0, `left`, `right`)   => (reverse(left), right)
        case (`k`, `left`, x :: xs) => go(k - 1, x :: left, xs)
        case _                      => (throw new RuntimeException): (List[A], List[A])
      }
      go(n, Nil, list)
    }

    def slice[A](start: Int, end: Int, list: List[A]): List[A] = (start, end, list) match {
      case (0, 0, _)                => Nil
      case (a, b, x :: xs) if a > 0 => x :: slice(a - 1, b - 1, xs)
      case (0, b, x :: xs) if b > 0 => x :: slice(0, b - 1, xs)
      case _                        => throw new IndexOutOfBoundsException
    }

    def rotate[A](d: Int, list: List[A]) = {
      val (left, right) = split(if (d < 0) list.size + d else d, list)
      right ++ left
    }

    def removeAt[A](index: Int, list: List[A]): (List[A], A) = {
      @tailrec
      def go(k: Int, left: List[A], right: List[A]): (List[A], A) = (k, left, right) match {
        case (0, `left`, x :: xs)   => (reverse(left) ++ xs, x)
        case (`k`, `left`, x :: xs) => go(k - 1, x :: left, xs)
        case _                      => throw new IndexOutOfBoundsException
      }
      go(index, Nil, list)
    }

    def insertAt[A](element: A, index: Int, list: List[A]): List[A] = (element, index, list) match {
      case (e, 0, l)       => e :: l
      case (e, i, x :: xs) => x :: insertAt(e, i - 1, xs)
      case _               => throw new IndexOutOfBoundsException
    }

    def range(start: Int, stop: Int): List[Int] = if (start > stop) Nil else start :: range(start + 1, stop)

    def randomSelect[A](n: Int, list: List[A]): List[A] = {
      import scala.util.Random.nextInt
      if (n > 0) {
        val (l, e) = removeAt(nextInt(list.size), list)
        e :: randomSelect(n - 1, l)
      } else Nil
    }

    def lotto(n: Int, m: Int): List[Int] = {
      import scala.util.Random.nextInt
      require(n >= 0)
      if (n == 0) Nil else nextInt(m - 1) + 1 :: lotto(n - 1, m)
    }

    def randomPermute[A](list: List[A]): List[A] = randomSelect(list.size, list)

    def combinations[A](n: Int, list: List[A]): List[List[A]] = {
      def splitAll: List[A] => List[(A, List[A])] = {
        case Nil     => Nil
        case x :: xs => (x, xs) :: splitAll(xs)
      }
      def go: (Int, List[A], List[A]) => List[List[A]] = {
        case (0, current, _)    => List(reverse(current))
        case (_, _, Nil)        => Nil
        case (k, current, rest) => splitAll(rest).flatMap { case (x, xs) => go(k - 1, x :: current, xs) }
      }
      go(n, Nil, list)
    }
  }


  object S99Arithmetic {

    implicit class S99Int(val self: Int) extends AnyVal {

      import math.sqrt

      def isPrime = self == 2 || (self != 1 && self % 2 == 1 && (3 to sqrt(self).toInt by 2).forall(self % _ != 0))

      def isCompareTo(other: Int): Boolean = gcd(self, other) == 1

      def primeFactors: List[Int] = {
        def go(start: Int, rest: Int): List[Int] =
          (start to rest).find(i => i.isPrime && rest % i == 0).map(i => i :: go(i, rest / i)).getOrElse(Nil)
        go(2, self)
      }

      def primeFactorMultiplicity: Map[Int, Int] = {
        require(self > 1)
        def go(start: Int, num: Int, rest: Int): List[(Int, Int)] =
          if (rest % start == 0) go(start, num + 1, rest / start)
          else (start to rest)
            .find(i => i.isPrime && rest % i == 0)
            .map(i => (start, num) :: go(i, 1, rest / i))
            .getOrElse(List((start, num)))
        val Some(firstFactor) = (2 to self).find(n => n.isPrime && self % n == 0)
        Map(go(firstFactor, 1, self / firstFactor): _*)
      }
    }

    @tailrec
    def gcd(a: Int, b: Int): Int = {
      val (max, min) = if (a > b) (a, b) else (b, a)
      val r = max % min
      if (r == 0) min else gcd(min, r)
    }
  }


  object S99Logic {

    def table2(f: (Boolean, Boolean) => Boolean): String =
      s"""A     B     result
         |true  true  ${ f(true, true) }
         |true  false ${ f(true, false) }
         |false true  ${ f(false, true) }
         |false false ${ f(false, false) }""".stripMargin

    def not(a: Boolean): Boolean = !a

    object P46 {
      def and(a: Boolean, b: Boolean): Boolean = a && b
      def or(a: Boolean, b: Boolean): Boolean = a || b
      def nand(a: Boolean, b: Boolean) = !(a && b)
      def nor(a: Boolean, b: Boolean) = !(a || b)
      def xor(a: Boolean, b: Boolean) = a != b
      def impl(a: Boolean, b: Boolean) = !a || b
      def equ(a: Boolean, b: Boolean) = a == b
    }

    implicit class P47(val self: Boolean) extends AnyVal {
      def and(other: Boolean): Boolean = self && other
      def or(other: Boolean): Boolean = self || other
      def nand(other: Boolean): Boolean = !(self && other)
      def nor(other: Boolean): Boolean = !(self || other)
      def xor(other: Boolean): Boolean = self != other
      def impl(other: Boolean): Boolean = !self || other
      def equ(other: Boolean): Boolean = self == other
    }
  }


  object S99BinaryTrees {

    sealed trait Tree[+A]

    case class Node[+A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A] {
      override def toString: String = s"T($value $left $right)"
    }

    case object End extends Tree[Nothing] {
      override def toString: String = "."
    }

    object Node {
      def apply[A](value: A): Node[A] = Node(value, End, End)
    }

    object Tree {
      def cBalanced[A](n: Int, x: A): List[Node[A]] = Nil
    }
  }
}

Spec.scala

import org.scalatest.{FlatSpec, Matchers}

class Spec extends FlatSpec with Matchers {

  {
    import S99.S99Lists
    import S99.S99Lists._

    "P01" should "work" in {
      last(List(1, 1, 2, 3, 5, 8)) should be(8)
    }

    "P02" should "work" in {
      penultimate(List(1, 1, 2, 3, 5, 8)) should be(5)
    }

    "P03" should "work" in {
      nth(2, List(1, 1, 2, 3, 5, 8)) should be(2)
    }

    "P04" should "work" in {
      S99Lists.length(List(1, 1, 2, 3, 5, 8)) should be(6)
    }

    "P05" should "work" in {
      reverse(List(1, 1, 2, 3, 5, 8)) should be(List(8, 5, 3, 2, 1, 1))
    }

    "P06" should "work" in {
      isPalindrome(List(1, 2, 3, 2, 1)) should be(true)
    }

    "P07" should "work" in {
      flatten(List(List(1, 1), 2, List(3, List(5, 8)))) should be(List(1, 1, 2, 3, 5, 8))
    }

    "P08" should "work" in {
      compress(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) should be(List('a, 'b, 'c, 'a, 'd, 'e))
    }

    "P09" should "work" in {
      pack(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) should be(
        List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))
      )
    }

    "P10" should "work" in {
      encode(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) should be(
        List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e))
      )
    }

    "P11" should "work" in {
      encodeModified(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) should be(
        List((4, 'a), 'b, (2, 'c), (2, 'a), 'd, (4, 'e))
      )
    }

    "P12" should "work" in {
      decode(List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e))) should be(
        List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
      )
    }

    "P13" should "work" in {
      encodeDirect(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) should be(
        List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e))
      )
    }

    "P14" should "work" in {
      duplicate(List('a, 'b, 'c, 'c, 'd)) should be(List('a, 'a, 'b, 'b, 'c, 'c, 'c, 'c, 'd, 'd))
    }

    "P15" should "work" in {
      duplicateN(3, List('a, 'b, 'c, 'c, 'd)) should be(
        List('a, 'a, 'a, 'b, 'b, 'b, 'c, 'c, 'c, 'c, 'c, 'c, 'd, 'd, 'd)
      )
    }

    "P16" should "work" in {
      drop(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k)) should be(List('a, 'b, 'd, 'e, 'g, 'h, 'j, 'k))
    }

    "P17" should "work" in {
      split(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k)) should be(
        (List('a, 'b, 'c), List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
      )
    }

    "S24" should "work" in {
      val result = lotto(6, 49)
      result.size should be(6)
      result.forall(n => 0 <= n && n <= 49) should be(true)
    }

    "P26" should "work" in {
      val result = combinations(3, List('a, 'b, 'c, 'd, 'e, 'f))
      result.size should be(20)
      result.forall(_.toSet.size == 3) should be(true)
    }
  }


  {
    import S99.S99Arithmetic.{S99Int, gcd}

    "P31" should "work" in {
      7.isPrime should be(true)
      91.isPrime should be(false)
      97.isPrime should be(true)
    }

    "P32" should "work" in {
      gcd(36, 63) should be(9)
    }

    "P33" should "work" in {
      35.isCompareTo(64) should be(true)
    }

    "P35" should "work" in {
      315.primeFactors should be(List(3, 3, 5, 7))
    }

    "P36" should "work" in {
      315.primeFactorMultiplicity should be(Map((3, 2), (5, 1), (7, 1)))
    }
  }

  {
    import S99.S99Logic
    import S99.S99Logic.table2

    "P46" should "work" in {
      import S99.S99Logic.P46.{and, or}
      table2((a, b) => and(a, or(a, b))) should be(
        """A     B     result
          |true  true  true
          |true  false true
          |false true  false
          |false false false""".stripMargin
      )
    }

    "P47" should "work" in {
      import S99.S99Logic.P47
      table2((a, b) => a and (a or S99Logic.not(b))) should be(
        """A     B     result
          |true  true  true
          |true  false true
          |false true  false
          |false false false""".stripMargin
      )
    }
  }
}