Você coleciona dados de um Advanced Collecting Device Controller ™ há muito tempo. Você verifica os logs e, para seu horror, descobre que algo deu muito errado: os dados contêm apenas os últimos bits dos números!

Felizmente, você sabe o valor inicial e que o valor nunca muda rapidamente. Isso significa que você pode recuperar o resto apenas encontrando a distância desde o início.

Desafio

Você escreverá um programa ou uma função para calcular a quantidade que um valor mudou, dado um módulo Ne uma lista do módulo de valores intermediários N.

A mudança entre cada par de números é sempre menor queN/2 , portanto, haverá apenas uma resposta válida para cada caso de teste.

Você receberá como entrada um número inteiro N> 2 e uma lista de valores, em um formato de sua escolha. A entrada pode ser fornecida via STDIN ou linha de comando ou argumentos de função.

Você produzirá um único inteiro, a quantidade que o valor original mudou. A saída pode ser impressa em STDOUT ou retornada.

Regras

• Seu programa deve funcionar para qualquer distância e módulo menor que 2^20.
• Você pode assumir que:
  • Né pelo menos 3.
  • A lista possui pelo menos 2 valores.
  • Todos os valores na lista são pelo menos 0 e menores que N.
  • Todas as alterações nos números são menores que N/2.
• Qualquer outra coisa é uma entrada inválida, e seu programa pode fazer o que quiser.
• São proibidas brechas padrão, quaisquer bibliotecas não padrão e funções internas para esse fim exato.
• Isso é código-golfe , então o programa mais curto em bytes vence.

Casos de teste de exemplo

Entrada:

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

Resultado:

4

Explicação (com valor de exemplo):

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

Entrada:

10
5 2 8 9 5

Resultado:

-10

Explicação (com valor de exemplo):

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

Entradas inválidas:

2
0 0 0 0 0

(módulo muito pequeno)

6
2 5 4 2

(alteração muito grande entre 2 e 5)

TI-BASIC, 15 bytes

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

Retira a lista Anse o módulo de 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 resposta direta. Gostaria de saber se existe um caminho mais curto.

Mathematica, 30 bytes

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

Esta é uma função anônima que recebe dois argumentos. Exemplo de uso:

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

Isso funciona usando os Differenceselementos sucessivos, agrupando-os no intervalo -n/2para+n/2 with Mode seu parâmetro de deslocamento e, em seguida, considerando o total com Tr(rastreamento da matriz, soma dos elementos diagonais).

Note que mesmo sem ser golpeado, são apenas 43 bytes!

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

J, 24 bytes

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

Uso:

   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

Vai tentar jogar mais e adicionar algumas explicações depois disso.

Experimente online aqui.

Pitão, 20 19 bytes

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

Roubou .:_2de Jakube, idéia de Mauris.

R, 38 bytes

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

Isso cria uma função sem nome que aceita um número inteiro e um vetor como entrada e retorna um único número inteiro. Para chamá-lo, dê um nome, por exemplof=function(n,v)... .

Ungolfed + explicação:

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

Exemplos:

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

Lamentamos, esta é a minha primeira resposta neste site. Digitar isso no MatLab e, em seguida, usar a entrada ans(modulus_value, [intermediate_values])retornará o valor solicitado, onde 'modulus_value' é o valor do módulo e 'intermed_values' é uma lista dos valores intermediários separados por espaços ou vírgulas.

Exemplo:

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

A função anônima aproveita MatLab de mod, diffesum funções para calcular a resposta. Primeiro, a diferença entre cada um dos valores intermediários é calculada. O resultado é então compensado pelo módulo dividido por dois, resultando em um conjunto de valores de diferença vinculados por [-modulus / 2 modulus / 2]. O resultado é então deslocado e somado novamente.

Eu acho que isso pode ser mais golfe, volto em breve com uma atualização. Agradecimentos especiais a @ 2012rcampion pela ideia.

Edit: A unwrapfunção do Matlab quase funciona aqui, mas é difícil jogar golfe. O código a seguir retorna uma matriz em que o último valor é a quantidade que o primeiro valor alterou: @(x,y)unwrap(y/x*2*pi)/2/pi*x-y(1)

Os valores intermediários são redimensionados para o intervalo de [-pi pi] e, em seguida, "desembrulhados", de modo que nenhum valor consecutivo tenha mais do que pi separados. Esses valores são redimensionados e alterados, resultando em uma matriz de distâncias do valor inicial.

Interessante, mas não muito prático para este desafio: D

Pitão, 29 bytes

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

Experimente on-line: Compilador / Executor Pyth

CJam, 27 bytes

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

Teste aqui.

Pip , 39 bytes

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

Requer a lista de dados como argumentos de linha de comando e o módulo em STDIN. Se isso for muito exagerado, eu tenho uma versão que usa dois argumentos da linha de comando por mais 5 bytes.

Explicação:

                                         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)

E apenas para provar que essa pontuação não tão competitiva reflete mais minhas habilidades no golfe do que minha linguagem, aqui está um exemplo da solução Python da Mauris em 30 bytes :

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

Geléia , não concorrente

6 bytes Esta resposta não é competitiva, pois o desafio antecede a criação do Jelly.

Iæ%H}S

Experimente online!

Como funciona

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.