Rotate Array right in pure-functional Scala - using an unusual immutable efficient approach

Algorithm goal

Rotating the array \([1,2,3]\) by 1 element to the right returns an array \([3,1,2]\). Example:

Array before:
123
Array after rotating by \(n = 1\):
312
Array after rotating by \(n = 2\):
231

Rotating the array \([1,2,3]\) 3 times returns us to the original array \([1,2,3]\).

Explanation

The most tricky part is finding the trick - which is to join two Arrays side-by-side, and then slice that array to get a continuous slice that simulates a rotation - no mutations needed!

In Scala, we use the View concept to turn our array \([1,2,3]\) into an array \([1,2,3,1,2,3]\) with concatenation (without doing any allocations yet!), and then select the expected slice. (this is © from www.scala-algorithms.com)

For example, when \(n = 1\):

Array before:
123123

The rest of the Explanation is available for subscribers.

or

'Unlimited Scala Algorithms' gives you access to all the Scala Algorithms!

Upon purchase, you will be able to Register an account to access all the algorithms on multiple devices.

Scala Concepts & Hints

Drop, Take, dropRight, takeRight

Scala's `drop` and `take` methods typically remove or select `n` items from a collection.

assert(List(1, 2, 3).drop(2) == List(3))

assert(List(1, 2, 3).take(2) == List(1, 2))

assert(List(1, 2, 3).dropRight(2) == List(1))

assert(List(1, 2, 3).takeRight(2) == List(2, 3))

assert((1 to 5).take(2) == (1 to 2))

Read more

View

The .view syntax creates a structure that mirrors another structure, until "forced" by an eager operation like .toList, .foreach, .forall, .count.

Read more

Algorithm in Scala

9 lines of Scala (version 2.13), showing how concise Scala can be!

This solution is available for access!

or

'Unlimited Scala Algorithms' gives you access to all the Scala Algorithms!

Upon purchase, you will be able to Register an account to access all the algorithms on multiple devices.

Test cases in Scala

assert(countToDrop(length = 0, rightShift = 0) == 0)
assert(countToDrop(length = 1, rightShift = 0) == 1)
assert(countToDrop(length = 5, rightShift = 0) == 5)
assert(countToDrop(length = 5, rightShift = 1) == 4)
assert(countToDrop(length = 5, rightShift = 5) == 5)
assert(countToDrop(length = 4, rightShift = 2) == 2)
assert(rotateArrayRight(Array(), 3).isEmpty)
assert(rotateArrayRight(Array(1), 3).toVector == Vector(1))
assert(rotateArrayRight(Array(1, 2), 0).toVector == Vector(1, 2))
assert(
  rotateArrayRight(Array(1, 2, 3, 4), 1).toVector == Vector(4, 1, 2, 3)
)
assert(
  rotateArrayRight(Array(1, 2, 3, 4), 5).toVector == Vector(4, 1, 2, 3)
)
def countToDrop(length: Int, rightShift: Int): Int = ???

def rotateArrayRight(arr: Array[Int], rightShift: Int): Array[Int] = ???