Scala Koans?

scastie.scala

def last[T](ls: List[T]): T = {
  ls match {
    case Nil => throw new Exception("No last element of empty list")
    case h :: Nil => h
    case _ :: tail => last(tail)
  }
}

val test = List(2, 4, 7, 3, 100)
last(test)

def penultimate[T](ls: List[T]): T = {
  ls match {
    case Nil => throw new Exception("No penultimate element of empty list")
    case h :: t if t.length == 1 => h
    case _ :: tail => penultimate(tail)
  }
}

penultimate(test)

def nth[T](n: Int, ls: List[T]): T = {
  if (n >= ls.length)
    throw new Exception("n is greater than list size")
  else if (n == 0)
    ls.head
  else
    nth(n - 1, ls.tail)
}

nth(4, test)

def length[T](ls: List[T]): Long = {
  ls.foldLeft(0) { (acc, _) =>
    acc + 1
  }
}

length(test)

def reverse[T](ls: List[T]): List[T] = {
  ls.foldLeft(List[T]())((acc, l) => l :: acc)
}

reverse(test)

def isPalindrome[T](ls: List[T]): Boolean =
  ls == ls.reverse

isPalindrome(List(1, 3, 6, 3, 1))
isPalindrome(List(0, 1, 33))

def flatten(list: List[Any]): List[Any] = {
  list.foldLeft(List[Any]())((acc, l) =>
    l match {
      case ls: List[_] => acc ++ flatten(ls)
      case s => acc :+ s
  })
}

def deDup[T](list: List[T]): List[T] = {
  list.foldRight(List(list.last))((l, acc) =>
    if (l == acc.head) acc else l :: acc)
}

val symbols = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
deDup(symbols)

def pack[T](list: List[T]): List[List[T]] = {
  if (list.isEmpty) List(List())
  else {
    val (packedSoFar, rest) = list.span(_ == list.head)
    rest match {
      case Nil => List(packedSoFar)
      case _ => packedSoFar :: pack(rest)
    }
  }
}

pack(symbols)

def packLengthEncode[T](list: List[T]): List[(Int, T)] = {
  pack(list).foldRight(List[(Int, T)]())((l, acc) => (l.length, l.head) :: acc)
}

packLengthEncode(symbols)

def runLengthEncode[T](list: List[T]): List[(Int, T)] = {
  if (list.isEmpty) List()
  else {
    val (packedSoFar, rest) = span(list, list.head)
    rest match {
      case Nil => List((packedSoFar.length, packedSoFar.head))
      case _ => (packedSoFar.length, packedSoFar.head) :: runLengthEncode(rest)
    }
  }
}

def span[T](list: List[T], filter: T): (List[T], List[T]) = {

  def run(ls: List[T], acc: (List[T], List[T])): (List[T], List[T]) = {
    ls match {
      case h :: t if h == filter => run(t, (h :: acc._1, acc._2))
      case _ => (acc._1, ls)
    }
  }

  run(list, (List[T](), List[T]()))
}

runLengthEncode(symbols)

def runLengthDecode[T](list: List[(Int, T)]): List[T] = {
  list
    .foldRight(List[T]())((l, acc) => List.fill(l._1)(l._2) ::: acc)
}

runLengthDecode(runLengthEncode(symbols))

def duplicate[T](list: List[T], n: Int = 2): List[T] = {
  list.foldRight(List[T]())((l, acc) => List.fill(n)(l) ::: acc)
}

duplicate(deDup(symbols), 4)

def drop[T](n: Int, list: List[T]): List[T] = {
  var count = 0
  list.foldRight(List[T]())((l, acc) => {
    count += 1
    if (count % n == 0) acc else l :: acc
  })
}

val list = List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k)
drop(3, list)

def rotate[T](n: Int, list: List[T]): List[T] = {
  (list drop n) ++ (list take n)
}

rotate(3, list)

def removeAt[T](n: Int, list: List[T]): (List[T], T) = {
  list.splitAt(n) match {
    case (_, Nil) => throw new Exception("No such position to insert at")
    case (before, target :: Nil) => (before, target)
    case (before, target :: after) => (before ::: after, target)
  }
}

removeAt(list.length - 1, list)

def insertAt[T](item: T, position: Int, list: List[T]): List[T] = {
  list.splitAt(position) match {
    case (_, Nil) => throw new Exception("No Such position to insert at")
    case (before, after) => before ::: (item :: after)
  }
}

insertAt('hello, 2, list)

val projects = Map(
  "Project Foo" -> Map("hoursRemaining" -> 6, "isCapex" -> false),
  "Project Bar" -> Map("hoursRemaining" -> 6, "isCapex" -> true),
  "Project Baz" -> Map("hoursRemaining" -> 3, "isCapex" -> true)
)

projects.values
  .filter {
    _.getOrElse("isCapex", false) match {
      case x: Boolean => x
      case _ => false
    }
  }
  .map(_.getOrElse("hoursRemaining", 0) match {
    case x: Int => x
    case _ => 0
  })
  .sum

def chooseFrom(lo: Int, hi: Int, rand: java.util.Random): Int =
  if (hi == lo) hi
  else lo + rand.nextInt(Integer.MAX_VALUE) % (hi - lo)

def randomSelect[T](n: Int, list: List[T], rand: java.util.Random): List[T] = {
  if (n <= 0)
    Nil
  else {
    val (remaining, removed) = removeAt(rand.nextInt(list.length), list)
    removed :: randomSelect(n - 1, remaining, rand)
  }
}

randomSelect(list.length, list, new java.util.Random())

def range(start: Int, end: Int): List[Int] = {
  (start to end).toList
}

range(3, 10)

def lonelyInteger(list: List[Int]): Int = {
  list
    .foldLeft(List[Int]())((acc, l) =>
      if (list.filter(_ == l).size == 1) l :: acc else acc)
    .head
}

def betterLonelyInteger(list: List[Int]) = {
  list.foldLeft(0) { _ ^ _ }
}

val lonelyList = List(1, 3, 6, 6, 3, 10, 1)

lonelyInteger(lonelyList)
betterLonelyInteger(lonelyList)

// def median(stream: Stream[Int]): Int = {
// 		stream
// }

def sumLetters(word: String): Int = {
  val base = 'a'.asDigit - 1
  word.foldLeft(0)((acc, c) => acc + c.asDigit - base)
}

sumLetters("hardwork")
sumLetters("knowledge")
sumLetters("attitude")
sumLetters("nonsense")

def lotto(n: Int, max: Int): List[Int] = {
  val rand = new java.util.Random()
  randomSelect(n, range(1, max), rand)
}

lotto(10, 59)

def getDependenciesList[A](ds: Traversable[(A, A)]): Map[A, Set[A]] = {
  ds.foldLeft(Map[A, Set[A]]())((acc, edge) =>
    acc
      + (edge._2 -> acc.getOrElse(edge._2, Set()))
      + (edge._1 -> (acc.getOrElse(edge._1, Set()) + edge._2))
  )
}

import scala.annotation.tailrec
def topologicalSort[A](edges: Traversable[(A, A)]): Iterable[A] = {
  
  @tailrec
  def tsort(depsMap: Map[A, Set[A]], done: Iterable[A]): Iterable[A] = {
    val (noDeps, stillHasDeps) = depsMap.partition { _._2.isEmpty }

    if (noDeps.isEmpty) {
      if (stillHasDeps.isEmpty) done else Nil
    } else {
      val found = noDeps.keys
      tsort(stillHasDeps.mapValues { _ -- found }, done ++ found)
    }
  }

  val depsMap = getDependenciesList(edges)
  tsort(depsMap, Seq())
}

val sequence = Seq((1, 2), (2, 4), (3, 4), (3, 2), (1,3), (4, 5), (3,6), (6,4))
topologicalSort(sequence)