Od dłuższego czasu zbierasz dane z Advanced Collecting Device Controller ™ . Sprawdzasz dzienniki i ku swojemu przerażeniu odkrywasz, że coś poszło nie tak: dane zawierają tylko ostatnie bity liczb!

Na szczęście znasz wartość początkową i ta wartość nigdy się nie zmienia szybko. Oznacza to, że możesz odzyskać resztę, znajdując odległość od początku.

Wyzwanie

Napisz program lub funkcję do obliczenia kwoty, którą zmieniła wartość, biorąc pod uwagę moduł Ni listę wartości pośrednich modulo N.

Zmiana między każdą parą liczb jest zawsze mniejsza niżN/2 , więc dla każdego przypadku testowego będzie tylko jedna poprawna odpowiedź.

Jako dane wejściowe otrzymasz liczbę całkowitą N> 2 i listę wartości, w wybranym przez ciebie formacie. Dane wejściowe można podawać za pomocą argumentów STDIN, wiersza polecenia lub funkcji.

Wyprowadzisz jedną liczbę całkowitą, kwotę, którą zmieniła pierwotna wartość. Dane wyjściowe można wydrukować do STDOUT lub zwrócić.

Zasady

• Twój program musi działać dla dowolnej odległości i modułu mniejszej niż 2^20.
• Możesz założyć, że:
  • Njest przynajmniej 3.
  • Lista ma co najmniej 2 wartości.
  • Wszystkie wartości na liście wynoszą co najmniej 0 i mniej niż N.
  • Wszystkie zmiany liczb są mniejsze niż N/2.
• Cokolwiek innego jest niepoprawnym wejściem, a Twój program może robić, co chce.
• Standardowe luki, niestandardowe biblioteki i wbudowane funkcje do tego konkretnego celu są zabronione.
• To jest golf golfowy , więc wygrywa najkrótszy program w bajtach.

Przykładowe przypadki testowe

Wejście:

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

Wynik:

4

Objaśnienie (z przykładową wartością):

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

Wejście:

10
5 2 8 9 5

Wynik:

-10

Objaśnienie (z przykładową wartością):

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

Nieprawidłowe dane wejściowe:

2
0 0 0 0 0

(zbyt mały moduł)

6
2 5 4 2

(zbyt duża zmiana między 2 a 5)

TI-BASIC, 15 bajtów

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

Pobiera listę Ansi moduł z 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 bajty

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

Super prosta odpowiedź. Zastanawiam się, czy istnieje krótsza droga.

Mathematica, 30 bajtów

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

Jest to anonimowa funkcja, która przyjmuje dwa argumenty. Przykładowe użycie:

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 *)

Działa się biorąc Differencesmiędzy kolejnymi elementami owijanie ich w zakresie -n/2do +n/2z Modi jego przesunięcie parametrów, przy czym łącznie z Tr(ślad macierzy, suma elementów diagonalnych).

Zauważ, że nawet bez golfa ma tylko 43 bajty!

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

J, 24 bajty

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

Stosowanie:

   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

Spróbuję więcej grać w golfa i dodam trochę wyjaśnień.

Wypróbuj online tutaj.

Pyth, 20 19 bajtów

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

Ukradł .:_2Jakube, pomysł Maurisa.

R, 38 bajtów

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

Tworzy to nienazwaną funkcję, która przyjmuje liczbę całkowitą i wektor jako dane wejściowe i zwraca jedną liczbę całkowitą. Aby to nazwać, nadaj mu nazwę, np f=function(n,v)....

Niegolfowane + wyjaśnienie:

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)
}

Przykłady:

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

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

Przepraszam, to moja pierwsza odpowiedź na tej stronie. Wpisanie tego w MatLab, a następnie użycie danych wejściowych ans(modulus_value, [intermediate_values])zwróci żądaną wartość, gdzie „wartość modułu” to wartość modułu, a „wartości_pośrednie” to lista wartości pośrednich oddzielonych spacjami lub przecinkami.

Przykład:

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

Funkcja anonimowy korzysta z Matlaba mod, difforaz sumfunkcje, aby obliczyć odpowiedź. Najpierw obliczana jest różnica między każdą z wartości pośrednich. Wynik jest następnie kompensowany przez moduł podzielony przez dwa, w wyniku czego powstaje zestaw wartości różnic, które są ograniczone przez [-modulus / 2 moduł / 2]. Wynik jest następnie kompensowany i sumowany ponownie.

Myślę, że można to pograć bardziej w golfa, wkrótce wrócę z aktualizacją. Specjalne podziękowania dla @ 2012rcampion za pomysł.

Edycja:unwrap Funkcja Matlaba prawie tutaj działa, ale trudno jest grać w golfa. Poniższy kod zwraca tablicę, w której ostatnia wartość jest wartością, którą zmieniła pierwsza wartość: @(x,y)unwrap(y/x*2*pi)/2/pi*x-y(1)

Wartości pośrednie są skalowane do zakresu [-pi pi], a następnie „rozpakowywane” tak, że żadna kolejna wartość nie jest więcej niż pi od siebie. Wartości te są następnie ponownie skalowane i przesuwane, co daje tablicę odległości od wartości początkowej.

Interesujące, ale niezbyt praktyczne dla tego wyzwania: D

Pyth, 29 bajtów

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

Wypróbuj online: Pyth Compiler / Executor

CJam, 27 bajtów

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

Sprawdź to tutaj.

Pip , 39 bajtów

Qn$+({a>n/2?a-na<-n/2?a+na}Mg@>1-g@<-1)

Wymaga listy danych jako argumentów wiersza poleceń i modułu STDIN. Jeśli to zbyt duży odcinek, mam wersję, która wymaga dwóch argumentów wiersza polecenia za 5 bajtów więcej.

Wyjaśnienie:

                                         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)

I tylko, aby udowodnić, że ten mało konkurencyjny wynik bardziej odzwierciedla moje umiejętności gry w golfa niż mój język, oto port rozwiązania Python Maurisa w 30 bajtach :

Qn$+({(n/2-$-a)%n-n/2}MgZg@>1)

Galaretka , niekonkurująca

6 bajtów Ta odpowiedź nie konkuruje, ponieważ wyzwanie poprzedza powstanie galaretki.

Iæ%H}S

Wypróbuj online!

Jak to działa

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.