1import org.scalatest._
 2import org.sixtoten.SixToTen._
 3
 4class SixToTenSuite extends FunSuite {
 5  val poli_list = List(1, 2, 3, 2, 1)
 6  val not_poli_list = List(1, 2, 3, 4)
 7
 8  test("6. Find out whether a list is a palindrome") {
 9    assert(isPolindrome(poli_list))
10    assert(!isPolindrome(not_poli_list))
11    assert(isPolindrome(Nil))
12
13    assert(isPolindrome_recursive(poli_list))
14    assert(!isPolindrome_recursive(not_poli_list))
15    assert(isPolindrome_recursive(Nil))
16
17    assert(isPolindrome_recursive2(poli_list))
18    assert(!isPolindrome_recursive2(not_poli_list))
19    assert(isPolindrome_recursive2(Nil))
20  }
21
22  test("7. Flatten a nested list structure.") {
23    assert(flatten(List(List(1, 1), 2, List(3, List(5, 8)))) == List(1, 1, 2, 3, 5, 8))
24    assert(flatten(List(List(1, List(1)), 2, List(3, List(5, 8)))) == List(1, 1, 2, 3, 5, 8))
25  }
26
27  test("8. Eliminate consecutive duplicates of list elements") {
28    assert(compress(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) == List('a, 'b, 'c, 'a, 'd, 'e))
29    assert(compress_foldLeft(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) == List('a, 'b, 'c, 'a, 'd, 'e))
30    assert(compress_foldRight(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) == List('a, 'b, 'c, 'a, 'd, 'e))
31  }
32
33  test("9. Pack consecutive duplicates of list elements into sublists ") {
34    assert(pack_foldRight(List()) == List(List()))
35    assert(pack_foldRight(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) == List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e)))
36  }
37
38  test("10. Run-length encoding of a list") {
39    assert(encode_foldRight(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) == List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e)))
40  }
41}

  1package org.sixtoten
  2
  3import scala.annotation.tailrec
  4
  5object SixToTen {
  6  def isPolindrome[A](xs: List[A]): Boolean = xs == xs.reverse
  7
  8  // in the scala 99 problems blog, the author wants to make it tail recursive even it is already, so I put this annotation here
  9  @tailrec
 10  def isPolindrome_recursive[A](xs: List[A]): Boolean = xs match {
 11    case Nil => true
 12    case head :: Nil => true
 13      // it didn't matter on tailrec to use && operator or if statement like below
 14    case head :: tail => (tail.last == head) && isPolindrome_recursive(tail.init)
 15  }
 16
 17  // scala 99 problems blog author creates an extractor for head, last and init
 18  // then he uses that in pattern matching. too much extra steps for me but just to learn it I'll do it, too
 19  @tailrec
 20  def isPolindrome_recursive2[A](xs: List[A]): Boolean = xs match {
 21    case Nil => true
 22    case head :: Nil => true
 23    case hli(head, last, init) => if(last != head) false else isPolindrome_recursive2(init)
 24  }
 25
 26  // flatten(List(List(1, 1), 2, List(3, List(5, 8))))
 27
 28  // i wanted to make it a little bit interesting by adding an extra level of List
 29  // but it shouldn't matter because we are going to make it recursive
 30
 31  // flatten(List(List(1, List(1)), 2, List(3, List(5, 8))))
 32
 33  // i didn't know that lists can be non-homogenious
 34  // thanks to type inference of scala, the type of the list is in that case List[Any], not List[Int]
 35  // so you just couldn't use any type patterns in your pattern matches
 36  def flatten(l: List[Any]): List[Any] = l flatMap {
 37    case ls: List[_] => flatten(ls)
 38    case h => List(h)
 39  }
 40
 41  // compress(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) == List('a, 'b, 'c, 'a, 'd, 'e)
 42  def compress[A](xs: List[A]): List[A] = {
 43    @tailrec
 44    def iter(prev: A, rest: List[A], acc: List[A]): List[A] = rest match {
 45      case Nil => acc
 46      case head :: tail => if(head == prev) iter(head, tail, acc) else iter(head, tail, head :: acc)
 47    }
 48
 49    iter(xs.head, xs.tail, List(xs.head)).reverse
 50  }
 51
 52  // compress(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) == List('a, 'b, 'c, 'a, 'd, 'e)
 53  def compress_foldLeft[A](xs: List[A]): List[A] = xs.foldLeft(List[A]()){
 54    case (acc, x) if acc.isEmpty => List(x)
 55    case (acc, x) => if(acc.head != x) x :: acc else acc
 56  }.reverse
 57
 58  // compress(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) == List('a, 'b, 'c, 'a, 'd, 'e)
 59  // override def foldRight[B](z: B)(op: (A, B) => B): B =
 60  //    reverse.foldLeft(z)((right, left) => op(left, right))
 61  def compress_foldRight[A](xs: List[A]): List[A] = xs.foldRight(List[A]()){
 62    case (x, acc) if acc.isEmpty => List(x)
 63    case (x, acc) => if(acc.head != x) x :: acc else acc
 64  }
 65
 66  // pack(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) == List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))
 67  def pack_foldRight[A](xs: List[A]): List[List[A]] = xs.foldRight(List[List[A]](List[A]())){
 68    case (x, acc) => {
 69      val hxs = acc.head
 70
 71      if(hxs.isEmpty) List(x) :: acc.tail
 72      else if(hxs.head == x) (x :: hxs) :: acc.tail
 73      else List(x) :: acc
 74    }
 75  }
 76
 77  //encode_foldRight(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) == List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e))
 78  def encode_foldRight(xs: List[Symbol]): List[(Int, Symbol)] = xs.foldRight(List[(Int, Symbol)]((0, null))) {
 79    case (x, acc: List[(Int, Symbol)]) => {
 80      val tpl = acc.head
 81
 82      if(tpl._2 == null) (1, x) :: acc.tail
 83      else if(tpl._2 == x) (tpl._1 + 1, x) :: acc.tail
 84      else (1, x) :: acc
 85    }
 86  }
 87}
 88
 89object hli {
 90  def unapply[A](arg: List[A]): Option[(A, A, List[A])] = arg match {
 91    case Nil => None
 92    case head :: Nil => Some(head, head, Nil)
 93    case head :: tail => Some(head, tail.last, tail.init)
 94  }
 95}
 96
 97/*
 98   WHAT I'VE LEARNED?
 99
100   * You can create extractors (see hli) to use in pattern matches
101   * It turns out that "foldRight" is same as using "reverse + foldLeft" for a List type. It is cheaper to reverse the
102      list once and foldLeft than to access the last element in every iteration. If we would work for a Vector type
103      than it would probably make sence to use the original foldRight function because you can directly access with an index
104   * I had one seen Symbols in Ruby, too. I haven't understand it and now I have to! To be able to compare strings faster,
105      and not character by character, we can use symbols instead: same symbols are represented in the
106      same memory (interning). So it is O(1) to compare Symbols. see: https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#intern()
107*/

1git clone https://github.com/dhalsim/scala-exercises.git
2cd scala-exercises
3sbt test