Optimize solution for the given coding problem

user_8265144 0
Viewed 109

I am a newbie in Scala and I am trying to resolve the following simple coding problem:

Write a listOfLists recursive method that takes a number of strings as varargs and then creates a list of lists of strings, with one less string in each, so for example: listOfLists("3","2","1") should give back: List(List("3","2","1"), List("2","1"), List("1"))

The solution I've found is the following:

def listOfLists(strings: String*): List[List[String]] = {
      val strLength = strings.length

      @tailrec
      def recListOfList(result: List[List[String]], accumulator: Int): List[List[String]] = {
          accumulator match {
            case x if x < strLength =>
              recListOfList(result :+ (strings.toList.takeRight(strings.length - accumulator)), accumulator + 1 )
            case _ => result
          }
        }

      val res: List[List[String]] = List(strings.toList)
      recListOfList(res, 1)
}

The solution works, however I think it could be written much more better. A problem I can see is that I convert the varargs to a List with the toList method, but a hint that the problem gave me is to use the eta expansion _* but I don't know how to use it in this context.

Then, I tried to find another way to write in a more efficient way the following instruction:

strings.toList.takeRight(strings.length - accumulator))

but this is the only solution that came up in my mind.

Any review is welcome (also say that this solution is a total mess :D (providing the right reasons))

recursion list optimization scala
5 Answers

This meets all the specified requirements.

def listOfLists(strings: String*): List[List[String]] =
  if (strings.isEmpty) Nil
  else strings.toList :: listOfLists(strings.tail:_*)
user_49931280

You can do this:

def listOfLists(strings: String*): List[List[String]] = {
  @annotation.tailrec
  def loop(remaining: List[String], acc: List[List[String]]): List[List[String]] =
    remaining match {
      case head :: tail =>
        loop(remaining = tail, (head :: tail) :: acc)
      
      case Nil =>
        acc.reverse
    }
  
  loop(remaining = strings.toList, acc = List.empty)
}

I believe the code is self-explanatory; but, feel free to ask any questions you may have.

You can see the code running here.

user_41114040

Not a recursive method but worth noting that tails in the standard library can do most of this. Then map and filter to convert to correct type and filter out empty list.

def listOfLists(strings: String *): List[List[String]] = strings.tails.map(_.toList).filter(_.nonEmpty).toList

Test:

scala> listOfLists("a","b","c")
val res6: List[List[String]] = List(List(a, b, c), List(b, c), List(c))
user_3907080

From Scala 2.13 you can use List.unfold and Option.when:

def listOfLists(strings: String*): List[List[String]] = {
  List.unfold(strings) { s =>
    Option.when(s.nonEmpty)(s.toList, s.tail)
  }
}

Code run at Scastie.

user_23592270

Using almost the same idea you can rewrite your solution in cleaner way:

def listOfLists(strings: String*): List[List[String]] = {
      @tailrec
      def recListOfList(curr: List[String], accumulator: Seq[List[String]]): Seq[List[String]] = {
          curr match {
            case head :: tail => recListOfList(tail, curr +: accumulator)
            case _ => accumulator
          }
        }

      recListOfList(strings.toList, Nil)
        .reverse
        .toList
}

With the splat(_*) operator, which adapts a sequence (Array, List, Seq, Vector, etc.) to varargs parameter you can create a shorter solution, but it will not be tail-recursive:

def listOfLists(strings: String*): List[List[String]] = {
  val curr = strings.toList
  curr match {
   case Nil => Nil    
   case x :: tail => curr :: listOfLists(tail:_*)
  }  
}
user_25012790
Related