# Sliding through collections

Nov 22, 2015

The other day I found myself trying to solve one of those math puzzles which had to do with doing computations on subsets of a very large number to then obtain a final result. Something along the lines of:

“Given the string representing the number 127361827391827309127381263, what would be the biggest product of its internal consecutive numbers grouped by 5?”

So I jumped straight into implementing a function that, using an accumulator recursively, would come up with a list containing all the subset combinations:

```
def slices(size: Int, digits: String): List[List[Char]] = {
def sliceAcc(size: Int, digits: String, acc: List[List[Char]]): List[List[Char]] = {
if (digits.length < size) acc
else sliceAcc(size, digits.drop(1), acc ++ List(digits.take(size).toList))
}
sliceAcc(size, digits, Nil)
}
scala> slices(2, "1234567890")
res0: List[List[Char]] = List(List(1, 2), List(2, 3), List(3, 4), List(4, 5), List(5, 6), List(6, 7), List(7, 8), List(8, 9), List(9, 0))
```

Although this works, it looks a bit messy. It’s not just the fact of using an accumulator, but also the reduction of the input is not clear enough.

Luckily, later I found a way to do exactly this which was already built in in the Scala collections!

# Sliding

The “sliding” function is defined by the Scala’s Iterator trait like so:

`def sliding[B >: A](size: Int, step: Int = 1): GroupedIterator[B]`

Its signature indicates that a GroupedIterator is returned. GroupIterator differs from Iterator (amongst other things) by defining a strategy for dealing with elements which do not evenly fit in grouping operations such as “sliding”. We’ll see an example in a bit.

So by using “sliding”, the whole of my “slices” function could have been achieved with a simple one-liner:

```
"1234567890".toList.sliding(2).toList
res1: List[List[Char]] = List(List(1, 2), List(2, 3), List(3, 4), List(4, 5), List(5, 6), List(6, 7), List(7, 8), List(8, 9), List(9, 0))
```

The second parameter of “sliding” allows us to define a jump between where the previous partition was made before start grouping again.

```
"1234567890".toList.sliding(3, 2).toList
res2: List[List[Char]] = List(List(1, 2, 3), List(3, 4, 5), List(5, 6, 7), List(7, 8, 9), List(9, 0))
```

Notice that in here we get 4 groups of 3 and a single group with 2 elements. Depending on the use case, this behaviour might not be desired. What we might need instead, are those values that form a complete group. Here’s where the strategy defined in the GroupedIterator comes into play. It provides a method **withPartials()** which accepts a boolean to indicate whether we want to discard partial results.

```
"1234567890".iterator.sliding(3, 2).withPartial(false).toList
res3: List[Seq[Char]] = List(List(1, 2, 3), List(3, 4, 5), List(5, 6, 7), List(7, 8, 9))
```

Finally, calling “sliding” with the same value in both parameters is equivalent to using the function “grouped”.

```
"1234567890".toList.sliding(2, 2).toList
res4: List[List[Char]] = List(List(1, 2), List(3, 4), List(5, 6), List(7, 8), List(9, 0))
"1234567890".toList.grouped(2).toList
res5: List[List[Char]] = List(List(1, 2), List(3, 4), List(5, 6), List(7, 8), List(9, 0))
```

# Use cases

I find this method very useful to help finding solutions to mathematical problems like the one described at the beginning of the post.

Considering the problem again: “Given the string representing the number 127361827391827309127381263, what would be the biggest product of its internal consecutive numbers grouped by 5?”

What we are really looking for is 127361**82739**1827309127381263, its product yielding a result of 3024.

```
"127361827391827309127381263".map(_.asDigit).sliding(5).map(_.product).max
res6: Int = 3024
```

So we have just transformed the input into digits, created the groups of 5 with “sliding”, mapped over the groups applying the product of its numbers and finally picking its maximum value. Neat!

But can we also use this function in something closer to a real world scenario?

Well, lets imagine an overly-simplified example on a city-break quoting system. We want to allow our customers to find out what is the cheapest price to travel to a destination for a certain amount of days on any day for the following month.

The system would have a service to obtain the best price for a destination based on a list of consecutive days:

`def price(destination: Destination, travelDates: Seq[DateTime]): Money`

The only thing we need, is call this service for all possible dates within the next month. And we can do that by using “sliding”:

```
val nextMonthDays:Iterator[DateTime] = Iterator.iterate(new DateTime())(_ plusDays 1) takeWhile (_ isBefore new DateTime().plusMonths(1))
def findBestPriceForNextMonth(destination: Destination, numberOfDays: Int): Money = {
val possibleDates = nextMonthDays.sliding(numberOfDays)
possibleDates.map(days => price(destination, days)).min
}
findBestPriceForNextMonth("Barcelona", 4)
```

In this particular example, we would find the cheapest price to go to Barcelona for 4 days during the next month.

Header Image: Matteo Dunchi via Flickr

Tweet