The rotunda shift

A museum rotunda holds its exhibits on a ring of numbered plinths. Every Monday the curator turns the display, and the crate store is full, so nothing may be set down on the floor.

The problem

The plinths are numbered 0 to n - 1 clockwise, and plinths[i] is the accession number of the exhibit on plinth i. The Monday shift moves every exhibit k plinths clockwise: what stands on plinth i ends up on plinth (i + k) % n, and the exhibits at the end of the ring wrap round to the front.

With no spare floor, you may not build a second ring and copy into it. The porters carry one exhibit at a time between plinths — rearrange the ring in a constant amount of extra room.

Report the ring after the shift.

Input. plinths — the accession numbers in plinth order. k — a non-negative integer, plinths to turn clockwise.

Output. The same list, rearranged in place.

Example.

plinths = [11, 24, 37, 42, 58, 63, 79], k = 3   ->  [58, 63, 79, 11, 24, 37, 42]

The last three exhibits wrap to the front; everything else slides three places along.

A second example, where the turn exceeds the ring:

plinths = [4, 8, 15, 16], k = 10   ->  [15, 16, 4, 8]

Ten places round a ring of four is two full turns plus two, and a full turn changes nothing, so this is a shift of 2.

Constraints.

• 1 <= len(plinths) <= 10^5
• 0 <= k <= 10^9
• 1 <= plinths[i] <= 10^6, accession numbers distinct
• Extra space O(1) — no second ring

Hints

Approach

Brute force

Turn the ring one plinth at a time, k times. Each turn moves all n exhibits, so this is k · n carries — 10¹⁴ at n = 10^5 and k = 10^9. Copying into a fresh ring costs n carries but needs n plinths of floor the rotunda has not got.

The insight

Turning the ring by k is three reversals: reverse the whole ring, then reverse the first k plinths and the remaining n - k separately.

Reversing everything brings the last k exhibits to the front, where they belong, but leaves both blocks running backwards. Reversing each block puts its own order right again, and the blocks never cross, so the two fixes do not interfere. A reversal is two indices walking toward each other and swapping — one exhibit in the porters' hands at a time. Reduce k modulo n first, so the block boundary lands inside the ring.

Algorithm

1. Let n = len(plinths); set k = k % n. If k == 0, nothing moves.
2. Reverse the whole ring, indices 0 to n - 1.
3. Reverse indices 0 to k - 1.
4. Reverse indices k to n - 1.
5. Return the ring.

Complexity

Time O(n) — the three reversals swap n/2 + k/2 + (n − k)/2 = n pairs, independent of k. Space O(1) — one exhibit in hand and two indices.

Solution

"""The rotunda shift — an in-place rotation built from three reversals."""


def reverse(plinths, lo, hi):
    """Reverse the closed range lo..hi, one exhibit in hand at a time."""
    while lo < hi:
        plinths[lo], plinths[hi] = plinths[hi], plinths[lo]
        lo += 1
        hi -= 1


def solve(plinths, k):
    n = len(plinths)
    if n == 0:
        return plinths
    # A turn of n restores the ring, so only k mod n does any work; this also
    # keeps the block boundary inside the ring.
    k %= n
    if k == 0:
        return plinths
    reverse(plinths, 0, n - 1)      # last k exhibits are now in front, backwards
    reverse(plinths, 0, k - 1)      # fix the order inside the wrapped block
    reverse(plinths, k, n - 1)      # fix the order inside the rest
    return plinths

TESTS = [
    (([11, 24, 37, 42, 58, 63, 79], 3), [58, 63, 79, 11, 24, 37, 42]),
    (([4, 8, 15, 16], 10), [15, 16, 4, 8]),
    (([4, 8, 15, 16], 0), [4, 8, 15, 16]),
    (([1, 2, 3, 4, 5, 6], 6), [1, 2, 3, 4, 5, 6]),
    (([7], 5), [7]),
    (([2, 9], 1), [9, 2]),
    (([11, 24, 37, 42, 58, 63, 79], 1), [79, 11, 24, 37, 42, 58, 63]),
]

Pitfalls

• Skipping k %= n. With n = 4 and k = 10, step 3 walks to index 9 and raises an IndexError; written with slices it silently reverses the whole ring instead, returning [16, 15, 8, 4].
• Reversing the two blocks without reversing the whole ring first. The first example gives [37, 24, 11, 79, 63, 58, 42] — every exhibit present, every one in the wrong place.
• Turning the wrong way. The exhibit that ends on plinth 0 comes from plinth n - k, not plinth k. Splitting at k gives [42, 58, 63, 79, 11, 24, 37], an anticlockwise shift.

Variants

• Empty pockets to the tail — also rearranges a row in place, but it compacts rather than turns, and the survivors keep their original order.
• The same three reversals rotate a fixed-size ring buffer without moving its read and write heads.