Commits

Tim Moore committed cfd5bf4

First set of solutions

Comments (0)

Files changed (1)

src/main/scala/s99/ListsSolutions.scala

 
 trait ListsSolutions {
 
-  def last[T](list: List[T]): T = ???
-  def penultimate[T](list: List[T]): T = ???
-  def nth[T](n: Int, list: List[T]): T = ???
-  def length[T](list: List[T]): Int = ???
-  def reverse[T](list: List[T]): List[T] = ???
-  def isPalindrome[T](list: List[T]): Boolean = ???
-  def flatten(list: List[Any]): List[Any] = ???
-  def compress[T](list: List[T]): List[T] = ???
+  def last[T](list: List[T]): T = list match {
+    case Nil => throw new IndexOutOfBoundsException
+    case _ :: last :: Nil => last
+    case _ :: tail => last(tail)
+  }
+
+  def penultimate[T](list: List[T]): T = list match {
+    case Nil => throw new IndexOutOfBoundsException
+    case _ :: penultimate :: _ :: Nil => penultimate
+    case _ :: tail => penultimate(tail)
+  }
+
+  def nth[T](n: Int, list: List[T]): T = (n, list) match {
+    case (x, Nil) => throw new IndexOutOfBoundsException(String.valueOf(x))
+    case (0, head :: _) => head
+    case (x, _ :: tail) => nth(x - 1, tail)
+  }
+
+  def length[T](list: List[T]): Int = list match {
+    case Nil => 0
+    case _ :: tail => 1 + length(tail)
+  }
+
+  def reverse[T](list: List[T]): List[T] = list match {
+    case Nil => Nil
+    case head :: tail => reverse(tail) :+ head
+  }
+
+  def isPalindrome[T](list: List[T]): Boolean = list == reverse(list)
+
+  def flatten(list: List[Any]): List[Any] = list match {
+    case Nil => Nil
+    case (head: List[_]) :: tail => flatten(head) ::: flatten(tail)
+    case head :: tail => head :: flatten(tail)
+  }
+
+  def compress[T](list: List[T]): List[T] = list match {
+    case Nil => Nil
+    case head :: next :: tail if (head == next) => compress(next :: tail)
+    case head :: tail => head :: compress(tail)
+  }
+
   def pack[T](list: List[T]): List[List[T]] = ???
+
   def encode[T](list: List[T]): List[(Int, T)] = ???
+
   def encodeModified[T](list: List[T]): List[Any] = ???
+
   def decode[T](list: List[(Int, T)]): List[T] = ???
+
   def encodeDirect[T](list: List[T]): List[(Int, T)] = ???
-  def duplicate[T](list: List[T]): List[T] = ???
-  def duplicateN[T](n: Int, list: List[T]): List[T] = ???
+
+  def duplicate[T](list: List[T]): List[T] = duplicateN(2, list)
+
+  def duplicateN[T](n: Int, list: List[T]): List[T] = (n, list) match {
+    case (_, Nil) => Nil
+    case (0, _ :: tail) => duplicateN(n, tail)
+    case (x, head :: tail) => head :: duplicateN(x - 1, head :: Nil) ::: duplicateN(n, tail)
+  }
+
   def drop[T](n: Int, list: List[T]): List[T] = ???
+
   def split[T](n: Int, list: List[T]): (List[T], List[T]) = ???
+
   def slice[T](i: Int, j: Int, list: List[T]): List[T] = ???
+
   def rotate[T](n: Int, list: List[T]): List[T] = ???
+
   def removeAt[T](i: Int, list: List[T]): (List[T], T) = ???
+
   def insertAt[T](t: T, i: Int, list: List[T]): List[T] = ???
+
   def range[T](i: Int, j: Int): List[Int] = ???
+
   def randomSelect[T](n: Int, list: List[T]): List[T] = ???
+
   def lotto[T](i: Int, j: Int): List[Int] = ???
+
   def randomPermute[T](list: List[T]): List[T] = ???
+
   def combinations[T](n: Int, list: List[T]): List[List[T]] = ???
+
   def group3[T](list: List[T]): List[List[List[T]]] = ???
+
   def groups[T](ns: List[Int], list: List[T]): List[List[List[T]]] = ???
+
   def lsort[T](list: List[List[T]]): List[List[T]] = ???
+
   def lsortFreq[T](list: List[List[T]]): List[List[T]] = ???
 
 }