LowFieldTheory
LowFieldTheory

Reputation: 1773

Scala, P08 - pack

I'm doing the packing problem from P08 from the 99 Problems, I think I'm doing this right but there's something wrong with the syntax of Scala that I think I don't know..

def pack(list: List[Char]): List[List[Char]] = {
  @tailrec 
  def checkNext(a: List[List[Char]], prev: Char, l: List[Char] ): List[List[Char]] = {
    if (!l.nonEmpty) a
    else {
      val res = if (prev==l.head) List(a.head:::List(l.head)) else a:::List(List(l.head))       
      checkNext(res, l.head, l.tail)
    }
  }
  checkNext(List(List(list.head)), list.head, list.tail)
}

EDIT: sorry everyone, yes it compiles perfectly, but instead of doing what it is supposed to do, it merges everything and I cannot understand why. It should group nearby equal letters into lists of char, example:

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))

Upvotes: 3

Views: 524

Answers (2)

Marth
Marth

Reputation: 24802

You are adding characters to the wrong list : you want to append to a.last (the list you are currently working on), not a.head (which contains the list of the first equal characters you found).

def pack(list: List[Char]): List[List[Char]] = {
  def checkNext(a: List[List[Char]], prev: Char, l: List[Char] ): List[List[Char]] = {
    if (!l.nonEmpty) a
    else {
      val res = if (prev==l.head) a.init:+(a.last:+l.head) // a.last contains the list you are currently adding to,
                                                           // a.init's list are all completed
                else a:+List(l.head) // start a new list of character
      checkNext(res, l.head, l.tail)
    }
  }
  checkNext(List(List(list.head)), list.head, list.tail)
}

Note that this code has horrible performance, as appending is O(n) (so you should pretty much always try to replace (at least when inside a loop) it with prepend (which is O(1))).

A better way to do this is to first reverse the input list and then prepend elements to the result list :

def pack(list: List[Char]): List[List[Char]] = {
  def checkNext(a: List[List[Char]], prev: Char, l: List[Char]): List[List[Char]] = {
    if (!l.nonEmpty) a
    else {
      val res = if (prev == l.head) ((l.head::a.head)::a.tail) else List(l.head)::a
      checkNext(res, l.head, l.tail)
    }
  }
  checkNext(List(List[Char](list.last)), list.last, list.init.reverse) 
}

or the more idiomatic :

def pack(list: List[Char]) = {
  def checkNext(a: List[List[Char]], prev: Char, l: List[Char]): List[List[Char]] = l match {
    case Nil => a
    case h::tail if h == prev => checkNext((h::a.head)::a.tail,h,tail)
    case h::tail => checkNext(List(h)::a,h,tail)
  }
  checkNext(List(List[Char](list.last)), list.last, list.init.reverse) 
}

Upvotes: 2

monnef
monnef

Reputation: 4053

When you found the character is repeating you're appending to a wrong list. My result of fiddling around:

object P08SO extends App {
  // this method packs by adding to the beginning of the result and at the end it uses reverse
  def pack1[A](inputList: List[A]): List[List[A]] = {
    @tailrec
    def checkNext(result: List[List[A]], prev: A, input: List[A]): List[List[A]] =
      if (input.isEmpty) result
      else
        checkNext(
          if (input.head == prev) (input.head :: result.head) :: result.tail
          else List(input.head) :: result,
          input.head, input.tail)

    if (inputList.isEmpty) Nil
    else checkNext(List(List(inputList.head)), inputList.head, inputList.tail).reverse
  }

  // packs directly in right order
  // but IMO there's a quite significant performance cost (last and init have to iterate through entire list)
  def pack2[A](inputList: List[A]): List[List[A]] = {
    @tailrec
    def checkNext(result: List[List[A]], prev: A, input: List[A]): List[List[A]] =
      if (input.isEmpty) result
      else
        checkNext(
          if (input.head == prev) result.init ::: List(input.head :: result.last)
          else result ::: List(List(input.head)),
          input.head, input.tail)

    if (inputList.isEmpty) Nil
    else checkNext(List(List(inputList.head)), inputList.head, inputList.tail)
  }

  List[(String, List[Any])](
    "empty" -> List(),
    "one string" -> List("str"),
    "ints" -> List(0, 0, 0, 1, 1, 2, 3, 4, 4, 4, 4, 5, 6),
    "chars" -> "abbbcdeeffff".toList
  ).foreach(
    testVal => {
      println(s"pack1 - ${testVal._1}: ${pack1(testVal._2)}")
      println(s"pack2 - ${testVal._1}: ${pack2(testVal._2)}")
    }
  )
}

Output:

pack1 - empty: List()
pack2 - empty: List()
pack1 - one string: List(List(str))
pack2 - one string: List(List(str))
pack1 - ints: List(List(0, 0, 0), List(1, 1), List(2), List(3), List(4, 4, 4, 4), List(5), List(6))
pack2 - ints: List(List(0, 0, 0), List(1, 1), List(2), List(3), List(4, 4, 4, 4), List(5), List(6))
pack1 - chars: List(List(a), List(b, b, b), List(c), List(d), List(e, e), List(f, f, f, f))
pack2 - chars: List(List(a), List(b, b, b), List(c), List(d), List(e, e), List(f, f, f, f))

Upvotes: 1

Related Questions