Calculating distances mod N

Question

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 code-golf, 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)

Answer 1

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.

Answer 2

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]]

Answer 3

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.

Answer 4

Pyth, 20 19 bytes

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

Stole .:_2 from Jakube, idea from Mauris.

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

Pyth, 29 bytes

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

Try it online: Pyth Compiler/Executor

Answer 9

CJam, 27 bytes

0q~:_2ewf{~\m1$2/:I+\,=I-+}

Test it here.

Answer 10

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)
Qn                                       Read n from stdin
                            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)

Answer 11

Jelly

6 bytes

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.