Group elements in a list by range Scala

Question

Considering the following List in Scala :

List(4, 5, 6, 7, 8, 12, 13, 14, 17, 23, 24, 25)

I want to get the output

List(List(4,8), List(12,14), List(17), List(23,25))

I have this answer Scala List function for grouping consecutive identical elements

But it is working for grouping identical elements in the same List.

How to extend this solution to resolve my current problem?

I have tried this code

def sliceByRange[A <% Int](s: List[A]): List[List[A]] = s match {
      case Nil => Nil
     case x :: xs1 =
    val (first, rest) = s.span(y => y - x == 1)
    first :: sliceByRange(rest)
    }

But it is not working.

Answer 1

Tail-recursive solution

Code

Note that you could also use List[(Int,Int)] as result type instead of List[List[Int]]. This would reflect the fact that the result is a List of ranges more appropriately. Of course then you couldn't turn List(x,x) into List(x) for singleton ranges. But I expect that this will come back to bite you later anyway.

import scala.annotation.tailrec

@tailrec
def split(in: List[Int], acc: List[List[Int]] = Nil): List[List[Int]] = (in,acc) match {
  case (Nil,a) => a.map(_.reverse).reverse
  case (n :: tail, (last :: t) :: tt) if n == last + 1 => split(tail, (n :: t) :: tt)
  case (n :: tail, a ) => split(tail, (n :: n :: Nil) :: a)
}

val result = split(List(4, 5, 6, 7, 8, 12, 13, 14, 17, 23, 24, 25))
println(result)

println("removing duplicates:")
println(result.map{
  case List(x,y) if x == y => List(x)
  case l => l
})

Output

List(List(4, 8), List(12, 14), List(17, 17), List(23, 25))
removing duplicates:
List(List(4, 8), List(12, 14), List(17), List(23, 25))

Answer 2

Here is another example:

val myList = List(4, 5, 7, 8, 12, 13, 14, 17, 23, 24, 25)

def partition(list: List[Int]): (List[Int], List[Int]) = {
    val listPlusOne = (list.head - 1 :: list) // List(1,2,5) => List(0, 1, 2, 5)
    val zipped = list zip listPlusOne // zip List(1,2,5) with List(0, 1, 2, 5) => List((1,0), (2,1), (5,2))

    val (a, b) = zipped span { case (a, b) => b + 1 == a } // (List((1,0), (2,1)), List((5,2)))
    (a.map(_._1), b.map(_._1)) // (List(1, 2),List(5))
}

def group(list: List[Int]): List[List[Int]] = list match {
    case Nil => Nil
    case _ =>
        val (a, b) = partition(list)
        val listA =  List(List(a.head, a.last).distinct) // remove middle numbers..
        val listB = if (b.isEmpty) Nil else group(b)
        listA ++ listB
}

println(group(myList))

A bit more complicated, but it works...

Answer 3

Paraphrasing the answer of the question you referenced:

def split(list: List[Int]) : List[List[Int]] = list match {
  case Nil => Nil
  case h::t =>
    val segment = list.zipWithIndex.takeWhile { case (v, i) => v == h+i }.map(_._1)
    List(h, segment.last).distinct :: split(list drop segment.length)
}

Using zipWithIndex to check for each element whether it's exactly the "next" integer (number should increase "together" with the index). Then - taking only the "boundaries" of the segment and recursively moving on to the rest of the list.

Answer 4

My solution:

def sliceByRange(items: List[Int]) =
  items.sorted.foldLeft(Nil: List[List[Int]]) {
    case (initRanges :+ (head :: Nil), next) if head == next - 1 =>
      initRanges :+ (head :: next :: Nil) // append element to the last range
    case (initRanges :+ (head :: last :: Nil), next) if last == next - 1 =>
      initRanges :+ (head :: next :: Nil) // replace last range
    case (ranges, next) =>
      ranges :+ (next :: Nil) // add new range
  }

Usage:

sliceByRange(List(1, 2, 3, 5, 8, 9, 12, 13, 14, 19))
// List(List(1, 3), List(5), List(8, 9), List(12, 14), List(19))

If you wish to keep middle values you can use the following example:

def makeSegments(items: List[Int]) =
  items.sorted.foldLeft(Nil: List[List[Int]]) {
    case (initSegments :+ lastSegment, next) if lastSegment.last == next - 1 =>
      initSegments :+ (lastSegment :+ next)
    case (segments, next) =>
      segments :+ (next :: Nil)
  }

Usage:

makeSegments(List(1, 2, 3, 5, 8, 9, 12, 13, 14, 19))
// List(List(1, 2, 3), List(5), List(8, 9), List(12, 13, 14), List(19))

When range size at least 3 elements:

def sliceByRange3elements(items: List[Int]) =
  items.sorted.foldLeft(Nil: List[List[Int]]) {
    case (initRanges :+ (head :: last :: Nil), next) if last == next - 1 =>
      initRanges :+ (head :: next :: Nil) // replace last range
    case (initRanges :+ (ll :: Nil) :+ (l :: Nil), next) if ll == next - 2 && l == next - 1 =>
      initRanges :+ (ll :: next :: Nil) // make new range
    case (ranges, next) =>
      ranges :+ (next :: Nil)
  }

Usage (note that (8,9) are not range now):

sliceByRange3elements(List(1, 2, 3, 5, 8, 9, 12, 13, 14, 19))
// List(List(1, 3), List(5), List(8), List(9), List(12, 14), List(19))

You can define printRanges method to more visual output:

def printRanges(ranges: List[List[Int]]) =
  ranges.map({
    case head :: Nil => head.toString
    case head :: last :: Nil => s"$head-$last"
    case _ => ""
  }).mkString(",")

printRanges(
  sliceByRange(List(1, 2, 3, 5, 8, 9, 12, 13, 14, 19)))
// 1-3,5,8-9,12-14,19

printRanges(
  sliceByRange3elements(List(1, 2, 3, 5, 8, 9, 12, 13, 14, 19)))
// 1-3,5,8,9,12-14,19