R, 62 58 bytes
function(a,l)diag(diffinv(matrix(a,max(a)*l+1,l))[a+2,])-a
An alternative to the other R solution. In the comments JayCe made a mention of cumsum
which triggered something in my brain to use diffinv
and matrix recycling instead of rep
.
###Explanation:
Given input array a
, let M=max(a)
and l=length(a)
.
Observe that M+l
is the maximum possible index we'd need to access, and that M+l<=M*l+1
, since if M,l>1
,M+l<=M*l
(with equality only when M=l=2
) and if l==1
or M==1
, then M+l==M*l+1
.
By way of example, let a=c(4,3,2,1)
. Then M=l=4
.
We construct the M*l+1 x l
matrix in R by matrix(a,max(a)*l+1,l)
. Because R recycles a
in column-major order, we end up with a matrix repeating the elements of a
as such:
[,1] [,2] [,3] [,4]
[1,] 4 3 2 1
[2,] 3 2 1 4
[3,] 2 1 4 3
[4,] 1 4 3 2
[5,] 4 3 2 1
[6,] 3 2 1 4
[7,] 2 1 4 3
[8,] 1 4 3 2
[9,] 4 3 2 1
[10,] 3 2 1 4
[11,] 2 1 4 3
[12,] 1 4 3 2
[13,] 4 3 2 1
[14,] 3 2 1 4
[15,] 2 1 4 3
[16,] 1 4 3 2
[17,] 4 3 2 1
Each column is the cyclic successors of each element of a
, with a
across the first row; this is due to the way that R recycles its arguments in a matrix.
Next, we take the inverse "derivative" with diffinv
, essentially the cumulative sum of each column with an additional 0
as the first row, generating the matrix
[,1] [,2] [,3] [,4]
[1,] 0 0 0 0
[2,] 4 3 2 1
[3,] 7 5 3 5
[4,] 9 6 7 8
[5,] 10 10 10 10
[6,] 14 13 12 11
[7,] 17 15 13 15
[8,] 19 16 17 18
[9,] 20 20 20 20
[10,] 24 23 22 21
[11,] 27 25 23 25
[12,] 29 26 27 28
[13,] 30 30 30 30
[14,] 34 33 32 31
[15,] 37 35 33 35
[16,] 39 36 37 38
[17,] 40 40 40 40
[18,] 44 43 42 41
In the first column, entry 6=4+2
is equal to 14=4 + (3+2+1+4)
, which is the cyclic successor sum (CSS) plus a leading 4
. Similarly, in the second column, entry 5=3+2
is equal to 10=3 + (4+1+2)
, and so forth.
So in column i
, the a[i]+2
nd entry is equal to CSS(i)+a[i]
. Hence, we take rows indexed by a+2
, yielding a square matrix:
[,1] [,2] [,3] [,4]
[1,] 14 13 12 11
[2,] 10 10 10 10
[3,] 9 6 7 8
[4,] 7 5 3 5
The entries along the diagonal are equal to the cyclic successor sums plus a
, so we extract the diagonal and subtract a
, returning the result as the cyclic successor sums.