Reputation: 1773
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
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
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