Calculating distances mod N

You have been collecting data from a Advanced Collecting Device Controller™ for a long time. You check the logs, and to your horror you discover that something has gone terribly wrong: the data only contains the last bits of the numbers!

Luckily, you know the starting value and that the value never changes fast. That means you can recover the rest by just finding the distance from the start.

Challenge

You will write a program or a function to calculate the amount a value has changed, given a modulus N and a list of the intermediate values modulo N.

The change between every pair of numbers is always less than N/2, so there will only be one valid answer for each test case.

You will be given as input an integer N > 2 and a list of values, in a format of your choice. Input may be given via STDIN or command line or function arguments.

You will output a single integer, the amount the original value has changed. Output may be printed to STDOUT or returned.

Rules

• Your program must work for any distance and modulus less than 2^20.
• You may assume that:
• N is at least 3.
• The list has at least 2 values.
• All the values in the list are at least 0 and less than N.
• All changes in the numbers are less than N/2.
• Anything else is an invalid input, and your program may do whatever it wants.
• Standard loopholes, any non-standard libraries and built-in functions for this exact purpose are forbidden.
• This is , so the shortest program in bytes wins.

Example test cases

Input:

3
0 1 2 2 0 1 0 2 1 2 0 1 2 1 1


Output:

4


Explanation (with example value):

Value mod 3: 0 1 2 2 0 1 0 2 1 2 0 1 2 1 1
Value:       0 1 2 2 3 4 3 2 1 2 3 4 5 4 4


Input:

10
5 2 8 9 5


Output:

-10


Explanation (with example value):

Value mod 10:  5  2  8  9  5
Value:        15 12  8  9  5


Invalid inputs:

2
0 0 0 0 0


(too small modulus)

6
2 5 4 2


(too large change between 2 and 5)

• A format of your choice is a slippery slope. Can my GolfScript solution rely on an input list looking like :^;[5 2 8 9 5](\  ? – Lynn May 13 '15 at 13:16
• @Mauris Generally, no... "a format of your choice" is usually assumed to mean "a conventional representation in your language of choice". – Martin Ender May 13 '15 at 13:42
• You can, however, rely on the input list looking like "10 5 2 8 9 5" or "10,5 2 8 9 5" or "10 5,2,8,9,5". – Sparr May 13 '15 at 14:00

TI-BASIC, 15 bytes

Input N
sum(N/πtan⁻¹(tan(ΔList(πAns/N


Takes the list from Ans and the modulus from Input.

                       πAns/N    ; Normalize the list to [0,π)
ΔList(          ; Take differences, which are in the range (-π,π)
tan⁻¹(tan(                ; Modulo, but shorter. Now elements are in (-π/2,π/2)
N/π                          ; Multiply by N/π. These are displacements at each step.
sum(                             ; Add up all the displacements


Python 2, 53 bytes

lambda n,l:sum((b-a+n/2)%n-n/2for a,b in zip(l,l[1:]))


Super straight forward answer. I wonder if there is a shorter way.

• I missed that bit. Thanks. – Lynn May 13 '15 at 13:01
• @Jakube I already did it - I wasn't aware of .:_2 to generate pairs until I saw your answer - I was using zip. – orlp May 13 '15 at 16:42
• @Jakube I got it down to 19 :) – orlp May 13 '15 at 16:44

Mathematica, 30 bytes

Tr@Mod[Differences@#2,#,-#/2]&


This is an anonymous function which takes two arguments. Example usage:

Tr@Mod[Differences@#2,#,-#/2]&[3, {0, 1, 2, 2, 0, 1, 0, 2, 1, 2, 0, 1, 2, 1, 1}]
(* 4 *)
Tr@Mod[Differences@#2,#,-#/2]&[10, {5, 2, 8, 9, 5}]
(* -10 *)


This works by taking the Differences between successive elements, wrapping them to the range -n/2 to +n/2 with Mod and its offset parameter, then taking the total with Tr (matrix trace, sum of diagonal elements).

Note that even ungolfed it's only 43 bytes!

f[n_, l_] := Total[Mod[Differences[l], n, -n/2]]

• @ is unnecessary when you're already calling the function with square brackets. Having both is a syntax error. – David Zhang May 14 '15 at 9:11
• @DavidZhang Whoops, don't know what I was thinking. Serves me right for trying to answer without opening Mathematica! – 2012rcampion May 14 '15 at 12:14

J, 24 bytes

[+/@(]-(>-:)~*[)[|2-~/\]


Usage:

   f=:[+/@(]-(>-:)~*[)[|2-~/\]

3 f 0 1 2 2 0 1 0 2 1 2 0 1 2 1 1
4

10 f 5 2 8 9 5
_10


Will try to golf more and add some explanation after that.

Try it online here.

• Sure its J and not CJam ? :P – Optimizer May 13 '15 at 12:00

Pyth, 20 19 bytes

sm-J/Q2%+-FdJQ.:vw2


Stole .:_2 from Jakube, idea from Mauris.

R, 38 bytes

function(n,v)sum((diff(v)+n/2)%%n-n/2)


This creates an unnamed function that accepts an integer and a vector as input and returns a single integer. To call it, give it a name, e.g. f=function(n,v)....

Ungolfed + explanation:

f <- function(n, v) {
# Compute the differences between sequential elements of v
d <- diff(v)

# Add n/2 to the differences and get the result modulo n
m <- (d + n/2) %% n

# Subtract n/2 then sum the vector
sum(m - n/2)
}


Examples:

> f(3, c(0, 1, 2, 2, 0, 1, 0, 2, 1, 2, 0, 1, 2, 1, 1))
[1] 4

> f(10, c(5, 2, 8, 9, 5))
[1] -10


MatLab, 33 bytes

@(x,y)sum(mod(diff(y)+x/2,x)-x/2)


My apologies, this is my first answer on this website. Typing this in MatLab then using the input ans(modulus_value, [intermediate_values]) will return the requested value, where 'modulus_value' is the modulus value, and 'intermediate_values' is a list of the intermediate values separated by either spaces or commas.

Example:

ans(3, [0 1 2 2 0 1 0 2 1 2 0 1 2 1 1])


The anonymous function takes advantage of MatLab's mod, diff, and sum functions to compute the answer. First, the difference between each of the intermediate values is calculated. The result is then offset by the modulus divided by two, resulting in a set of difference values that is bound by [-modulus/2 modulus/2]. The result is then offset and summed again.

I think this can be golfed more, I'll be back soon with an update. Special thanks to @2012rcampion for the idea.

Edit: Matlab's unwrap function almost works here, but it's tough to golf. The following code returns an array where the last value is the amount the first value has changed: @(x,y)unwrap(y/x*2*pi)/2/pi*x-y(1)

The intermediate values are scaled to the range of [-pi pi], then "unwrapped" such that no consecutive value is more than pi apart. These values are then re-scaled and shifted, resulting in an array of distances from the starting value.

Interesting, but not very practical for this challenge :D

Pyth, 29 bytes

+sm**._K-Fdvz>y.aKvz.:Q2-eQhQ


Try it online: Pyth Compiler/Executor

• Input is space-separated, not comma-separated; your program doesn't seem to handle this. – Lynn May 13 '15 at 12:56
• @Mauris "a list of values, in a format of your choice" – Jakube May 13 '15 at 12:57
• Oh, my bad! I totally missed that part of the spec. – Lynn May 13 '15 at 13:01

0q~:_2ewf{~\m1$2/:I+\,=I-+}  Test it here. Pip, 39 bytes Qn$+({a>n/2?a-na<-n/2?a+na}Mg@>1-g@<-1)


Requires the list of data as command-line arguments and the modulus on STDIN. If that's too much of a stretch, I have a version that takes two command-line args for 5 bytes more.

Explanation:

                                         g is list of cmdline args (implicit)
g@>1         All but the first of the cmdline args
-g@<-1   ...minus all but the last of the cmdline args
(i.e. a list of the differences of adjacent items)
{                    }M             ...to which, map the following function:
a>n/2?a-n                            If diff is too big, subtract n;
a<-n/2?a+n                  else if too small, add n;
a                 else return unchanged
$+( ) Sum; print (implicit)  And just to prove that this not-so-competitive score is more reflective on my golfing skills than my language, here's a port of Mauris's Python solution in 30 bytes: Qn$+({(n/2-\$-a)%n-n/2}MgZg@>1)


Jelly, non-competing

6 bytes This answer is non-competing, since the challenge predates the creation of Jelly.

Iæ%H}S


Try it online!

How it works

Iæ%H}S    Main link. Left input: A (list). Right input: N (integer).

I         Compute the increments (deltas of consecutive elements) of A.
H}     Halve the right input (N).
æ%       Mod the increments into (-N/2, N/2].
S    Take the sum of all results.