Here’s a challenge: cycle an array in-place. That is, given an array \([x_0, x_1, \dots, x_{n-1}]\) and a number \(m\), you must make \([x_m, x_{m+1}, \dots, x_{n-1}, x_0, x_1, \dots, x_{m-1}]\) using only a constant amount of additional memory.
Solution: Here’s the solution presented by Jon Bently in Programming Pearls. The idea is to use three sub-array reversals.
First, reverse \([0, m-1]\) to get:
\[[x_{m-1}, x_{m-2}, \dots, x_0, x_m, x_{m+1}, \dots, x_{n-1}]\]
Second, reverse \([m, n-1]\) to get:
\[[x_{m-1}, x_{m-2}, \dots, x_0, x_{n-1}, x_{n-2}, \dots, x_m]\]
Finally, reverse \([0, n-1]\) to get:
\[[x_m, x_{m+1}, \dots, x_{n-1}, x_0, x_1, \dots, x_{m-1}]\]
In addition to its startling simplicity, this solution also has a lovely mnemonic: hold your hands in front so that you’re looking directly at your palms; flip one hand so that you can see it’s back; flip the other so that you’re now looking at the backs of your hands; now flip both hands together so that you see the palms again.
===----0 | ----3 | ----3 | 4----===
-\--1 | ----2 | ----2 | 5--/-
-|--2 | ----1 | ----1 | 6--|-
----3 | ===----0 | ===----0 | 7----
4----=== | 4----=== | 7---- | ===----0
5--/- | 5--/- | 6---- | -\--1
6--|- | 6--|- | 5---- | -|--2
7---- | 7---- | 4----=== | ----3
Speaking of Programming Pearls, I think it’s one of the few coding books worth owning. It’s filled with clever solutions to all sorts of software problems and you uncover something new with every reading.