Anda telah mengumpulkan data dari Advanced Collecting Device Controller ™ sejak lama. Anda memeriksa log, dan Anda terkejut menemukan sesuatu yang sangat salah: data hanya berisi bit terakhir dari angka!

Untungnya, Anda tahu nilai awalnya dan bahwa nilainya tidak pernah berubah dengan cepat. Itu berarti Anda dapat memulihkan sisanya hanya dengan mencari jarak dari awal.

Tantangan

Anda akan menulis sebuah program atau fungsi untuk menghitung jumlah nilai yang telah berubah, diberikan modulus Ndan daftar nilai-nilai menengah moduloN .

Perubahan antara setiap pasangan angka selalu kurang dariN/2 , jadi hanya akan ada satu jawaban yang valid untuk setiap kasus uji.

Anda akan diberikan sebagai input integer N> 2 dan daftar nilai, dalam format pilihan Anda. Input dapat diberikan melalui STDIN atau baris perintah atau argumen fungsi.

Anda akan menghasilkan bilangan bulat tunggal, jumlah nilai aslinya telah berubah. Output dapat dicetak ke STDOUT atau dikembalikan.

Aturan

• Program Anda harus bekerja untuk jarak apa pun dan modulus kurang dari 2^20.
• Anda dapat berasumsi bahwa:
  • Nsetidaknya 3.
  • Daftar memiliki setidaknya 2 nilai.
  • Semua nilai dalam daftar setidaknya 0 dan kurang dari N.
  • Semua perubahan dalam angka kurang dari N/2.
• Yang lainnya adalah input yang tidak valid, dan program Anda dapat melakukan apa pun yang diinginkannya.
• Celah standar, semua perpustakaan non-standar, dan fungsi bawaan untuk tujuan yang tepat ini dilarang.
• Ini adalah kode-golf , jadi program terpendek dalam byte menang.

Contoh kasus uji

Memasukkan:

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

Keluaran:

4

Penjelasan (dengan nilai contoh):

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

Memasukkan:

10
5 2 8 9 5

Keluaran:

-10

Penjelasan (dengan nilai contoh):

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

Input tidak valid:

2
0 0 0 0 0

(modulus terlalu kecil)

6
2 5 4 2

(perubahan terlalu besar antara 2 dan 5)

TI-BASIC, 15 byte

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

Mengambil daftar dari Ansdan modulus dari 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 byte

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

Jawaban super lurus ke depan. Saya ingin tahu apakah ada cara yang lebih pendek.

Mathematica, 30 byte

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

Ini adalah fungsi anonim yang membutuhkan dua argumen. Contoh penggunaan:

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

Ini bekerja dengan mengambil Differencesantara unsur-unsur berturut-turut, membungkus mereka untuk kisaran -n/2untuk +n/2dengan Moddan parameter offset, kemudian mengambil total denganTr (matriks jejak, jumlah dari elemen diagonal).

Perhatikan bahwa bahkan yang tidak diserang hanya 43 byte!

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

J, 24 byte

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

Pemakaian:

   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

Akan mencoba bermain golf lebih banyak dan menambahkan beberapa penjelasan setelah itu.

Cobalah online di sini.

Pyth, 20 19 byte

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

Mencuri .:_2dari Jakube, ide dari Mauris.

R, 38 byte

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

Ini menciptakan fungsi tanpa nama yang menerima integer dan vektor sebagai input dan mengembalikan integer tunggal. Untuk menyebutnya, berikan nama, misf=function(n,v)... .

Penjelasan + tidak dikumpulkan:

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

Contoh:

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

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

Maaf, ini jawaban pertama saya di situs web ini. Mengetikkan ini di MatLab kemudian menggunakan input ans(modulus_value, [intermediate_values])akan mengembalikan nilai yang diminta, di mana 'modulus_value' adalah nilai modulus, dan 'intermediate_values' adalah daftar nilai-nilai antara yang dipisahkan oleh spasi atau koma.

Contoh:

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

Fungsi anonim mengambil keuntungan dari MatLab ini mod, diffdan sumfungsi untuk menghitung jawabannya. Pertama, perbedaan antara masing-masing nilai antara dihitung. Hasilnya kemudian diimbangi oleh modulus dibagi dua, menghasilkan seperangkat nilai perbedaan yang terikat oleh [-modulus / 2 modulus / 2]. Hasilnya kemudian diimbangi dan dijumlahkan kembali.

Saya pikir ini bisa lebih banyak golf, saya akan segera kembali dengan pembaruan. Terima kasih khusus kepada @ 2012rcampion untuk idenya.

Sunting:unwrap Fungsi Matlab hampir berfungsi di sini, tetapi sulit untuk bermain golf. Kode berikut mengembalikan array di mana nilai terakhir adalah jumlah nilai pertama yang diubah: @(x,y)unwrap(y/x*2*pi)/2/pi*x-y(1)

Nilai-nilai perantara diskalakan ke kisaran [-pi pi], lalu "tidak terbuka" sehingga tidak ada nilai berurutan yang lebih dari pi terpisah. Nilai-nilai ini kemudian diskalakan ulang dan digeser, menghasilkan array jarak dari nilai awal.

Menarik, tetapi tidak terlalu praktis untuk tantangan ini: D

Pyth, 29 byte

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

Cobalah secara online: Pyth Compiler / Executor

CJam, 27 byte

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

Uji di sini.

Pip , 39 byte

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

Membutuhkan daftar data sebagai argumen baris perintah dan modulus pada STDIN. Jika itu terlalu banyak, saya memiliki versi yang membutuhkan dua baris perintah args untuk 5 byte lebih.

Penjelasan:

                                         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)

Dan hanya untuk membuktikan bahwa skor yang tidak terlalu kompetitif ini lebih mencerminkan kemampuan golf saya daripada bahasa saya, inilah port solusi Python Mauris dalam 30 byte :

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

Jelly , tidak bersaing

6 byte Jawaban ini tidak bersaing, karena tantangan mendahului pembuatan Jelly.

Iæ%H}S

Cobalah online!

Bagaimana itu bekerja

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.