Wyzwanie

Otrzymujesz tablicę liczb całkowitych. Za pomocą ruchu możesz zwiększyć lub zmniejszyć element tablicy o 1 . Twoim zadaniem jest wyrównanie tablicy, czyli wyrównanie wszystkich elementów tablicy poprzez wykonanie niektórych ruchów . Ale to nie wystarczy! Chcemy także, aby jak kilka ruchów , jak to możliwe .$a$

Wkład

• Niepusty Tablica liczb całkowitych$a$
• Opcjonalnie, długość od .$a$

Wydajność

• Minimalną liczbę ruchów potrzebnych do wyrównania tablicy .$a$

Zasady

• Standardowe zasady dotyczące prawidłowych zgłoszeń , I / O , luki zastosowania.
• To jest golf golfowy , więc wygrywa najkrótsze rozwiązanie (w bajtach). Jak zwykle, nie pozwól, aby absurdalnie krótkie rozwiązania w językach golfowych zniechęcały Cię do publikowania dłuższych odpowiedzi w wybranym języku.
• Nie jest to regułą, ale twoja odpowiedź będzie lepiej odebrana, jeśli będzie zawierała link do przetestowania rozwiązania i wyjaśnienie, jak to działa.

Przykłady

Input                       --> Output

[10]                        --> 0
[-1, 0, 1]                  --> 2
[4, 7]                      --> 3
[6, 2, 3, 8]                --> 9
[5, 8, 12, 3, 2, 8, 4, 5]   --> 19
[1,10,100]                  --> 99

Wolfram Language (Mathematica) , 19 bajtów

Tr@Abs[#-Median@#]&

Wypróbuj online!

Dla tablicy liczb całkowitych 1D Trdziała tak samo jak Total.

W jaki sposób?

Proste zastosowanie nierówności trójkąta.

...

Pierwotnie zamierzałem napisać tutaj dowód, ale potem zdecydowałem się poszukać /math/ zamiast tego i znalazłem Medianę Minimalizuje Suma Absolutnych Odchyleń ( Norma )${L}_{1}$ .

Znając nazwę operatora, jest to alternatywne rozwiązanie 19-bajtowe:

Norm[#-Median@#,1]&

JavaScript (Node.js) , 50 48 bajtów

Zaoszczędź 2 bajty dzięki Arnauldowi

a=>a.sort((x,y)=>x-y,r=0).map(n=>r+=a.pop()-n)|r

Wypróbuj online!

Posortuj tablicę rosnąco, a następnie zsumuj:

  a[last]   -a[0] // moves to equalise this pair
+ a[last-1] -a[1] // + moves to equalise this pair
+ ...etc

05AB1E , 4 bajty

ÅmαO

Wypróbuj online!

Wyjaśnienie

Åm     # push median of input
  α    # absolute difference with each in input
   O   # sum

Perl 6 , 29 28 bajtów

-1 bajt dzięki nwellnhof

{sum (.sort[*/2]X-$_)>>.abs}

Wypróbuj online!

Wyjaśnienie

{                          }  # Anonymous code block
      .sort[*/2]              # Get the median of the input array
                X-$_          # Subtract all elements from the median
     (              )>>.abs   # Get the absolute of each value
 sum                          # Sum the values

Japt, 7 bajtów

£xaXÃrm

Spróbuj

Wyjaśnienie

            :Implicit input of array U
£           :Map each X
  aX        :  Absolute difference between X and each element in U
 x          :  Reduce by addition
    Ã       :End map
     rm     :Reduce by minimum

JavaScript (ES6), 60 56 55 bajtów

Zaoszczędzono 1 bajt dzięki @Shaggy

a=>a.map(r=k=>r=a.map(n=>m+=n>k?n-k:k-n,m=0)|m>r?r:m)|r

Wypróbuj online!

W jaki sposób?

Jeśli nie brakuje mi jakiegoś triku, obliczenie mediany w JS okazuje się dłuższe. Prawdopodobnie około 65 bajtów z powodu wymaganego wywołania zwrotnego w sort()celu obejścia domyślnego sortowania leksykograficznego i dość długiego Math.abs():

a=>a.sort((a,b)=>b-a).map(n=>s+=Math.abs(n-a[a.length>>1]),s=0)|s

Zamiast tego próbujemy wszystkich wartości w oryginalnej tablicy jako wartości wyrównującej .

Haskell , 34 bajty

f l=minimum[sum$abs.(m-)<$>l|m<-l]

Wypróbuj online!

Znajduje całkowitą odległość wszystkich elementów od mediany, testując każdy element na liście jako potencjalną medianę i biorąc najmniejszy wynik.

Galaretka , 4 bajty

ạÆṁS

Wypróbuj online!

Jak to działa

ạÆṁS – Full program. Takes an array A of integers as input from argument 1.
 Æṁ  – Median. For odd-length A, middle element of S. For even-length A, the
       arithmetic mean of the two middle elements of S. Where S = A sorted.
ạ    – Absolute difference of each element with the median.
   S – Sum.

Python 2 , 46 bajtów

lambda l,n:sum(l[-~n/2:l.sort()])-sum(l[:n/2])

Wypróbuj online!

nJako argument przyjmuje długość listy . Oblicza sumę górnej połowy minus sumę dolnej połowy, dzieląc posortowaną listę na pierwszy n/2i ostatni n/2element.

Wyrażenie l[-~n/2:l.sort()]odpowiada obliczeniowej l.sort(), która modyfikuje się listę w miejscu, to sposób l[-~n/2:None], w którym lista ignoruje krojenia górna granica Noneże l.sort()wyprodukowane. Może się wydawać, że lista została posortowana zbyt późno, aby można ją było odpowiednio pociąć, ale Python wydaje się oceniać argumenty plasterka przed „zablokowaniem” listy, która ma zostać pocięta.

Python 2 , 47 bajtów

lambda l,n:sum(abs(x-sorted(l)[n/2])for x in l)

Wypróbuj online!

Nudna metoda sumowania odległości każdej wartości od mediany. nJako argument przyjmuje długość .

Python , 51 bajtów

f=lambda l:l>l[l.sort():1]and l[-1]-l[0]+f(l[1:-1])

Wypróbuj online!

Sortuje listę na miejscu, a następnie wielokrotnie dodaje ostatni (najwyższy pozostały) wpis minus pierwszy (najniższy pozostały) wpis i powraca na liście bez tych elementów, aż pozostanie tylko 0 lub 1. Usings pops”dostaje taką samą długość: l.pop()-l.pop(0)+f(l).

l.sort()Tkwi w miejscu, gdzie Nonejest zwracana nie ma żadnego wpływu. Plaster l[None:1]jest taki sam, jak l[:1]ponieważ Nones w plasterkach są ignorowane.

Python , 54 bajty

lambda l:sum(l.pop()-l.pop(0)for _ in l[1:l.sort():2])

Wypróbuj online!

Urocze zrozumienie listy, które ignoruje iterację argumentu i modyfikuje listę przez wielokrotne wstawianie pierwszego i ostatniego elementu. Zapewniamy, że zrozumienie listy odbywa się len(l)//2razy, powtarzając każdy inny element lpomijania pierwszego, wykonanego z l[1::2]. l.sort()Producing Nonemoże tkwić w nieużywanym końcowego kawałek argumentu.

APL (Dyalog), 12 bajtów

{⌊/+/|⍵∘.-⍵}

Brutuj siły, testując każdą liczbę jako korektor. Nie jestem pewien, czy milczenie jest krótsze, ale nie mogę tego rozgryźć.

TIO

TI-Basic, 18 6 bajtów

sum(abs(Ans-median(Ans

-12 bajtów od Miszy Ławrow ( od jakiegoś czasu nie używałem TI-Basic i zapomniałem, że listy to potrafią)

TI-Basic to tokenizowany język . Wszystkie tokeny użyte w tej odpowiedzi są jednobajtowe.

Pobiera dane wejściowe jako {1,2,3,4}:prgmNAME

Zasadniczo ten sam pomysł jak w przypadku większości innych odpowiedzi: odejmij przez medianę, a następnie weź sumę.

Wyjaśnienie:

sum(abs(Ans-median(Ans
sum(                    # 1 byte, Add up:
    abs(                # 1 byte, the absolute values of
        Ans-median(Ans  # 4 bytes, the differences between each element and the list's median

Röda , 33 bajty

{|a|a|abs _-[sort(a)][#a//2]|sum}

Wypróbuj online!

Wyjaśnienie:

{|a| /* Anonymous function with parameter a */
  a|         /* Push items in a to the stream */
             /* For each _ in the stream: */
  abs        /*   Abstract value of */\
  _-         /*   the value from stream minus */\
  [sort(a)][ /*     the value in the sorted version of a at index */
    #a//2    /*       length of a / 2 (the median) */
  ]|
  sum        /* Sum of all values in the stream */
}

R , 29 bajtów

sum(abs(median(a<-scan())-a))

Wypróbuj online!

Attache , 18 bajtów

Sum##Abs@`-#Median

Wypróbuj online!

Wyjaśnienie

Sum##Abs@`-#Median
            Median    take the median of the input list
     Abs@`-#          absolute difference with the original list
Sum##                 sum of all elements

jot , 15 bajtów

[:<./1#.|@-/~"{

Zasadniczo to samo co rozwiązanie Shaggy's Japt.

Wypróbuj online!

Jak to działa?

|@-/~"{- tworzy tabelę /~bezwzględnych różnic |@-między poszczególnymi liczbami"{

   |@-/~"{ 6 2 3 8
0 4 3 2
4 0 1 6
3 1 0 5
2 6 5 0

1#. sumuje każdy wiersz

   1#.|@-/~"{ 6 2 3 8
9 11 9 13

[:<./ znajduje najmniejszy przedmiot (zmniejsz o minimum)

   ([:<./1#.|@-/~"{) 6 2 3 8
9

Węgiel drzewny , 16 11 bajtów

Ｉ⌊ＥθΣＥθ↔⁻ιλ

Wypróbuj online! Link jest do pełnej wersji kodu. Edycja: Zapisano 5 bajtów dzięki @Arnauld. Wyjaśnienie:

  Ｅθ        Map over input array
     Ｅθ     Map over input array
         ι  Outer value
          λ Inner value
        ⁻   Difference
       ↔    Absolute value
    Σ       Sum
 ⌊          Minimum
Ｉ           Cast to string
            Implicitly print

Visual C #, 138 bajtów

int s=0;foreach(string i in a)s+=int.Parse(i);int x=s/a.Length;int o=0;foreach(string i in a)o+=Math.Abs(int.Parse(i)-x);Console.Write(o);

bez golfa:

int s = 0;                    // Takes a string array of arguments a as input
foreach (string i in a)       
     s += int.Parse(i);       // s as sum of the array elements
int x = s / a.Length;         // calculating the target value of all elements
int o = 0;                    // o as minimum number of moves
foreach (string i in a)
     o += Math.Abs(int.Parse(i) - x);    // summing up the moves to the target value
Console.Write(o);

Wypróbuj online!

C (gcc), 100 93 bajtów

e(q,u,a,l,i,z)int*q;{i=1<<31-1;for(a=u;a--;i=z<i?z:i)for(l=z=0;l<u;)z+=abs(q[l++]-q[a]);q=i;}

Brute-force solution, próbuje wyrównać z każdym elementem. Wypróbuj online tutaj .

Dzięki pułapowi do gry w golfa 7 bajtów.

Nie golfowany:

e(q, u, a, l, i, z) int *q; { // function taking an array of int and its length; returns an int (extra parameters are variables and don't have to be passed when calling e())
    i = 1 << 31 - 1; // construt the maximum value of a signed 4-byte integer
    for(a = u; a--; i = z < i ? z : i) // loop through the array, testing each element as the equalizer; if the number of moves is smaller than the current minimum, set it as the new minimum
        for(l = z = 0; l < u; ) // loop through the array ...
            z += abs(q[l++] - q[a]); // ... and sum the number of moves it takes to equalize each element
    q = i; // return the minimum number of moves
}

PHP, 78 bajtów

Sortuje tablicę, a następnie przechodzi przez kopię, usuwając elementy z oryginału i sumując absolutną różnicę, którą należy zmniejszyć o połowę, aby uzyskać zwrot.

function m($n){sort($n);foreach($n as$i)$r+=abs(array_pop($n)-$i);return$r/2;}

var_dump(
    m([10]),
    m([-1, 0, 1]),
    m([4, 7]),
    m([6, 2, 3, 8]),
    m([5, 8, 12, 3, 2, 8, 4, 5]),
    m([1,10,100])
);

Wydajność:

int(0)
int(2)
int(3)
int(9)
int(19)
int(99)

PHP, 69 bajtów

function($a,$c){for(sort($a);$c-->$d;)$s+=$a[$c]-$a[+$d++];return$s;}

funkcja anonimowa. Wypróbuj online .

JavaScript (Node.js) , 52 bajty

f=a=>(v=a.sort((x,y)=>x-y).pop()-a.shift())?v+f(a):0

Wypróbuj online!

Java (JDK), 112 bajtów

Grał w golfa

private static int e(int[]a){int s=0;for(int i:a){s+=i;}s/=a.length;int r=0;for(int i:a){r+=abs(s-i);}return r;}

Nie golfił

private static int equalize(int[] array) {
    int sum = 0;
    for (int i : array) {
        sum += i;
    }
    sum /= array.length;
    int ret = 0;
    for (int i : array) {
        ret += abs(sum-i);
    }
    return ret;
}

Kotlin Android, 200 bajtów

fun m(a:IntArray){var d=0;var s=0;var p=a.max()!!.times(a.size);var x =0;for(i in a.indices){x=a[i];d=0;s=0;while(d<a.size){if(x-a[d]<0)s=((x-a[d])*-1)+s;else s=((x-a[d]))+s;d++};if(p>s)p=s};print(p)}

Wypróbuj online