Вы уже давно собираете данные с Advanced Collecting Device Controller ™ . Вы проверяете журналы и, к своему ужасу, обнаруживаете, что что-то пошло не так: данные содержат только последние биты цифр!

К счастью, вы знаете начальное значение и оно никогда не меняется быстро. Это означает, что вы можете восстановить остальное, просто найдя расстояние от начала.

Вызов

Вы напишите программу или функцию для расчета суммы, на которую было изменено значение, с учетом модуля Nи списка промежуточных значений по модулю N.

Изменение между каждой парой чисел всегда меньшеN/2 , поэтому для каждого теста будет только один действительный ответ.

В качестве входных данных вы получите целое число N> 2 и список значений в выбранном вами формате. Ввод может быть дан через STDIN или командную строку или аргументы функции.

Вы выведете одно целое число, на которое изменилось исходное значение. Вывод может быть распечатан на STDOUT или возвращен.

правила

• Ваша программа должна работать на любое расстояние и модуль меньше, чем 2^20.
• Вы можете предположить, что:
  • Nпо крайней мере 3.
  • Список имеет как минимум 2 значения.
  • Все значения в списке по крайней мере 0 и меньше, чем N.
  • Все изменения в цифрах меньше, чем N/2.
• Все остальное является неверным вводом, и ваша программа может делать все, что захочет.
• Стандартные лазейки, любые нестандартные библиотеки и встроенные функции для этой цели запрещены.
• Это код-гольф , поэтому выигрывает самая короткая программа в байтах.

Пример тестовых случаев

Входные данные:

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

Выход:

4

Пояснение (с примером значения):

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

Входные данные:

10
5 2 8 9 5

Выход:

-10

Пояснение (с примером значения):

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

Неверные данные:

2
0 0 0 0 0

(слишком маленький модуль)

6
2 5 4 2

(слишком большое изменение между 2 и 5)

TI-BASIC, 15 байтов

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

Принимает список от Ansи модуль от 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 байта

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

Супер прямой ответ. Интересно, есть ли более короткий путь?

Mathematica, 30 байт

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

Это анонимная функция, которая принимает два аргумента. Пример использования:

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

Это работает путь принятия Differencesмежду последовательными элементами, упаковка их в диапазон , -n/2чтобы +n/2с Modи его смещение параметра, а затем принимает общее с Tr(след матрицы, сумма диагональных элементов).

Обратите внимание, что даже без golf это только 43 байта!

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

J, 24 байта

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

Использование:

   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

Попробую еще поиграть в гольф и добавить некоторые объяснения после этого.

Попробуйте это онлайн здесь.

Pyth, 20 19 байтов

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

Украл .:_2у Якуба, идея у Мауриса.

R, 38 байт

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

Это создает безымянную функцию, которая принимает целое число и вектор в качестве входных данных и возвращает одно целое число. Чтобы назвать его, дайте ему имя, например f=function(n,v)....

Ungolfed + объяснение:

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

Примеры:

> 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 байта

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

Мои извинения, это мой первый ответ на этом сайте. Ввод этого в MatLab с последующим использованием ввода ans(modulus_value, [intermediate_values])вернет запрошенное значение, где 'modulus_value' - это значение модуля, а 'interval_values' - это список промежуточных значений, разделенных пробелами или запятыми.

Пример:

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

Анонимная функция имеет преимущество от Matlab mod, diffи sumфункции для вычисления ответа. Сначала вычисляется разница между каждым из промежуточных значений. Затем результат смещается на модуль, деленный на два, что приводит к набору значений разностей, которые связаны [-modulus / 2 modulus / 2]. Затем результат смещается и снова суммируется.

Я думаю, что это может быть больше в гольфе, я скоро вернусь с обновлением. Отдельное спасибо @ 2012rcampion за идею.

Изменить:unwrap функция Matlab здесь почти работает, но это трудно для гольфа. Следующий код возвращает массив, где последним значением является величина, на которую было изменено первое значение: @(x,y)unwrap(y/x*2*pi)/2/pi*x-y(1)

Промежуточные значения масштабируются до диапазона [-pi pi], а затем «разворачиваются» так, что никакое последовательное значение не больше, чем pi друг от друга. Эти значения затем масштабируются и сдвигаются, в результате чего получается массив расстояний от начального значения.

Интересно, но не очень практично для этой задачи: D

Pyth, 29 байт

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

Попробуйте онлайн: Pyth Compiler / Executor

CJam, 27 байтов

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

Проверьте это здесь.

Пип , 39 байт

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

Требуется список данных в качестве аргументов командной строки и модуль STDIN. Если это слишком много, у меня есть версия, которая принимает два аргумента командной строки на 5 байтов больше.

Объяснение:

                                         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)

И просто для того, чтобы доказать, что эта не столь конкурентоспособная оценка больше отражает мои навыки игры в гольф, чем мой язык, вот порт решения Python от Mauris в 30 байтов :

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

Желе , неконкурентоспособное

6 байт. Этот ответ не является конкурирующим, поскольку задача предшествует созданию желе.

Iæ%H}S

Попробуйте онлайн!

Как это устроено

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.