S-99: Ninety-Nine Scala Problems

NinetyNine.scala

// http://aperiodic.net/phil/scala/s-99/
// https://gist.github.com/kevincairo/e91ef4e289a1892065d7eb1aef805f0a
import scala.annotation.tailrec
import scala.util.Random.nextInt
import scala.util.Try

def list(range: Range): List[Int]        = range.toList
def rand(range: Range): Int              = range(nextInt(range.length))
def repeat[A](n: Int):    A => List[A]   = List.fill(n)(_: A)
def repeatr[A](r: Range): A => List[A]   = repeat(rand(r))
def test(name: String)(f: => Unit): Unit = println(s"$name ${Try(f).failed.toOption.fold("PASS")(t => s"FAIL: $t")}")

implicit class TypedEquality[A](left: A) {
  def ===(right: A) =
    left == right || { println(s"$left does not equal $right"); false }
}

case class on[A, B](f: A => B) {
  class ToGive(a: A) { def toGive(expected: B) = assert(f(a) === expected) }
  def expect(a: A) = new ToGive(a)
}

// #01 Find the last element of a list.
@tailrec def last[A](list: List[A]): Option[A] = list match {
  case x :: Nil => Some(x)
  case _ :: xs  => last(xs)
  case      Nil => None
}

test("last") {
  assert(last(list(1 to 10)) contains 10)
  assert(last(List(1)) contains 1)
  assert(last(Nil) === None)
}

// #09 Pack consecutive duplicates of list elements into sublists.
def packAdjacentDupes[A](list: List[A]): List[Either[A, List[A]]] = {
  type Grouped = Either[A, List[A]]
  def group[A](a: A, more: List[A]) = if (more.isEmpty) Left(a) else Right(a :: more)

  @tailrec def grouped(elem: A, rest: List[A], acc: List[A] = Nil): (Grouped, List[A]) =
    if (rest.headOption contains elem) grouped(elem, rest.tail, elem :: acc)
    else group(elem, acc) -> rest

  @tailrec def go(list: List[A], acc: List[Grouped]): List[Grouped] = list match {
    case      Nil => reverse(acc)
    case x :: xs  => grouped(x, xs) match { case (dupes, rest) => go(rest, dupes :: acc) }
  }

  go(list, Nil)
}

test("packAdjacentDupes") {
  assert(packAdjacentDupes(Nil) === Nil)
  assert(packAdjacentDupes(List(1)) === List(Left(1)))
  assert(packAdjacentDupes(List(1, 1)) === List(Right(List(1, 1))))

  on(packAdjacentDupes[Int]) expect
    List(     1,             2, 2,        3,       2,             1, 1) toGive
    List(Left(1), Right(List(2, 2)), Left(3), Left(2), Right(List(1, 1)))
}

// #10 Run-length encoding of a list.
def runLengthEncoded[A](list: List[A]): List[(A, Int)] = {
  // packAdjacentDuplicates(list).map {
  //   case Left(x)            => x -> 1
  //   case Right(xs @ x :: _) => x -> xs.length
  // }

  @tailrec def go(list: List[A], acc: List[(A, Int)]): List[(A, Int)] = list match {
    case Nil =>
      reverse(acc)

    case x :: xs =>
      acc match {
        case (`x`, n) :: _ => go(xs, (x, n + 1) :: acc.tail)
        case _             => go(xs, (x,     1) :: acc)
      }
  }

  go(list, Nil)
}

test("runLengthEncoded") {
  assert(runLengthEncoded(Nil) === Nil)
  on(runLengthEncoded[Int]) expect
    List(1,      2, 2,   3,      2,   1, 1) toGive
    List(1 -> 1, 2 -> 2, 3 -> 1, 2 -> 1, 1 -> 2)
}

// #11 Modified run-length encoding.
def oneOrRunLengthEncoded[A](list: List[A]): List[Either[A, (A, Int)]] = {
  // packAdjacentDuplicates(list).map {
  //   case Left(x) => Left(x)
  //   case Right(xs @ x :: _) => Right(x -> xs.lenght)
  // }

  type OneOrEncoded = Either[A, (A, Int)]

  @tailrec def go(list: List[A], acc: List[OneOrEncoded]): List[OneOrEncoded] = list match {
    case Nil =>
      reverse(acc)

    case x :: xs =>
      acc match {
        case Right((`x`, n)) :: _ => go(xs, Right((x, n + 1)) :: acc.tail)
        case       Left(`x`) :: _ => go(xs, Right((x,     2)) :: acc.tail)
        case _                    => go(xs,           Left(x) :: acc)
      }
  }

  go(list, Nil)
}

test("oneOrRunLengthEncoded") {
  assert(oneOrRunLengthEncoded(Nil) === Nil)
  assert(oneOrRunLengthEncoded(List(42)) === List(Left(42)))
  assert(oneOrRunLengthEncoded(List(42, 42)) === List(Right(42 -> 2)))
  on(oneOrRunLengthEncoded[Int]) expect
    List(     1,        2, 2, 2,      3,       2,        1, 1) toGive
    List(Left(1), Right(2 -> 3), Left(3), Left(2), Right(1 -> 2))
}

// #12 Decode a run-length encoded list.
def decodeRunLengthEncoded[A](list: List[(A, Int)]): List[A] = {
  @tailrec def fill(a: A, n: Int, acc: List[A]): List[A] =
    if (n <= 0) acc else fill(a, n - 1, a :: acc)

  @tailrec def go(list: List[(A, Int)], acc: List[A]): List[A] = list match {
    case Nil => reverse(acc)
    case (a, n) :: rest => go(rest, fill(a, n, acc))
  }

  go(list, Nil)
}

test("decodeRunLengthEncoded") {
  assert(decodeRunLengthEncoded(Nil) === Nil)
  for (i <- 0 to 10) assert(decodeRunLengthEncoded(List("foo" -> i)) === List.fill(i)("foo"))
  on(decodeRunLengthEncoded[Symbol]) expect
    List('a -> 4,        'b -> 1, 'c -> 2, 'a -> 2, 'd -> 1, 'e -> 4) toGive
    List('a, 'a, 'a, 'a, 'b,      'c, 'c,  'a, 'a,  'd,      'e, 'e, 'e, 'e)
}

// #13 Run-length encoding of a list (direct solution). -- my #10 basically does this already

// #14 Duplicate the elements of a list.
def duplicateEach[A](list: List[A]): List[A] = {
  @tailrec def go(list: List[A], acc: List[A]): List[A] = list match {
    case Nil => reverse(acc)
    case x :: xs => go(xs, x :: x :: acc)
  }

  go(list, Nil)
}

test("duplicateEach") {
  assert(duplicateEach(Nil) === Nil)
  assert(duplicateEach(List(1)) === List(1, 1))
  assert(duplicateEach(List('a, 'b, 'b, 'c)) === List('a, 'a, 'b, 'b, 'b, 'b, 'c, 'c))
}

// #15 Duplicate the elements of a list a given number of times.
def duplicateEachN[A](i: Int, list: List[A]): List[A] = {
  @tailrec def dup(n: Int, a: A, onto: List[A]): List[A] = if (n > 0) dup(n - 1, a, a :: onto) else onto

  @tailrec def go(list: List[A], acc: List[A]): List[A] = list match {
    case Nil => reverse(acc)
    case x :: xs => go(xs, acc = dup(n = i, x, acc))
  }

  go(list, Nil)
}

test("duplicateEachN") {
  assert(duplicateEachN(1, Nil) === Nil)
  assert(duplicateEachN(0, List('a)) === Nil)
  assert(duplicateEachN(1, List('a)) === List('a))
  assert(duplicateEachN(3, List('a, 'b, 'b, 'c)) === List('a, 'a, 'a , 'b, 'b, 'b, 'b, 'b, 'b, 'c, 'c, 'c))
}