Zrób mi minimalną magiczną sumę

27

Krótko mówiąc, to wyzwanie.

Otrzymasz 4 liczby: p1, p2, p3 i p4.

Magiczną sumę liczb definiuje się w następujący sposób:

magic_sum = |p1 - p2| + |p2 - p3| + |p3 - p4| + |p4 - p1|

Możesz zmienić tylko jedną z powyższych wartości całkowitych (p1, p2, p3 lub p4). Musisz zmienić wartość tak, aby magiczna suma wartości osiągnęła wartość minimalną.

Na przykład:

p1, p2, p3, p4 = 17, -6, 15, 33. W tym przypadku wartość magicznej sumy wynosi 78.

Możesz zmienić tutaj -6 na 16, a wartość magicznej sumy wyniesie 36, co jest minimalną możliwą do osiągnięcia wartością.

Pamiętaj, że liczby mogą być dodatnimi lub ujemnymi liczbami całkowitymi.

To jest golf golfowy, więc wygrywa najmniej bajtów kodu. Punkty Brownie za używanie języka praktycznego zamiast języka rekreacyjnego. Niech czwarty będzie z tobą.

Powtarzać:

Próbka 1

Wejście 1

17 -6 15 33

Wyjście 1

36

Wyjaśnienie 1

-6 można zastąpić 16, co daje nam minimalną możliwą do osiągnięcia sumę magii.

Próbka 2

Wejście 2

10 10 10 10

Wyjście 2

0 or 2

albo jest do przyjęcia

Wyjaśnienie 2

Minimalna osiągalna suma magiczna wynosi 0, ponieważ minimalna suma 4 dodatnich liczb całkowitych wynosi 0. Jeśli liczba musi zostać zmieniona, wówczas jedną z 10 można zmienić na 9, uzyskując w ten sposób wynik 2.

Próbka 3

Wejście 3

1 2 3 4

Wyjście 3

4

Wyjaśnienie 3

Wkład sam w sobie daje 6 jako magiczną sumę. Zmieniamy 4 na 1 i osiągamy minimalną sumę magiczną, która wynosi 4.

Koishore Roy
źródło
10
+1, ale przydałoby się więcej przykładów.
Jonathan Allan
2
W pełni sprawny przykład i jeszcze kilka przypadków testowych, a to +1ode mnie.
Kudłaty
@ Shaggy gotowe. gdzie jest moja +1? : P
Koishore Roy
1
@KoishoreRoy Czy test 3 nie byłby 6 bez zmiany?
wizzwizz4
@ wizzwizz4 | 1 - 2 | + | 2 - 3 | + | 3 - 4 | + | 4 - 1 | = 1 + 1 + 1 + 3 = 6. Masz rację. Dokonałem edycji.
Koishore Roy

Odpowiedzi:

20

Python 2 , 44 bajty

a,b,c,d=sorted(input())
print min(c-a,d-b)*2

Wypróbuj online!

Sortuje wejście jak a,b,c,d,w porządku rosnącym, bierze mniejszy od c-aa d-b, i podwaja się. Dlaczego to działa?

Po pierwsze, zauważmy, że kiedy zmieniamy element, aby zmaksymalizować do całkowitej cyklicznej sumy odległości, optymalne (lub powiązane z optymalnym) jest to, aby zmienić go na równego sąsiadowi, np 17, -6, 15, 33 -> 17, 17, 15, 33. Jest tak, ponieważ jego nowa całkowita odległość do lewego i prawego cyklicznego sąsiada jest co najmniej odległością między tymi sąsiadami, więc wyrównanie ich jest najlepszym, co możemy zrobić.

Teraz usunięcie jednej z dwóch sąsiadujących kopii liczby daje tę samą cykliczną sumę odległości. W tym przykładzie jest to 17, 15, 33podawanie odległości 2 + 18 + 16. Zamiast zastępować jedną z czterech liczb, wystarczy ją usunąć, pozostawiając trzy liczby i użyć sumy ich cyklicznych odległości.

Zauważ, że przy 3 liczbach największy dystans jest sumą dwóch mniejszych. Dzieje się tak, ponieważ jeśli posortujemy liczby, które mają mieć a ≤ b ≤ c, to |a - c| = |a - b| + |b - c|. Innymi słowy, podróżujemy między największą i najmniejszą liczbą dwa razy, wykorzystując średnią liczbę jako pit stop jeden raz. Tak więc suma trzech odległości jest tylko dwa razy większa od odległości między minimum a maksimum, więc (c-a)*2.

Tak więc pytanie brzmi, którą liczbę usuwamy, aby uzyskać najmniejszą odległość między minimum a maksimum z trzech pozostałych liczb. Oczywiście usuwamy najmniejszą lub największą z liczb. Wywoływanie ich a, b, c, dw posortowanej kolejności, usuwanie aliści d - bi usuwanie dliści c - a, a końcowy wynik jest podwójny, w zależności od tego, która wartość jest mniejsza.

xnor
źródło
pomóż mi tutaj z przypadkiem testowym. co jeśli magiczna suma wynosi już 0, co jest najniższą możliwą do osiągnięcia liczbą. w takim przypadku, czy odpowiedź powinna wynosić 0? lub następna najniższa możliwa liczba. Jeśli wejściowy to [10,10,10,10], magiczna suma wynosi 0. druga najniższa możliwa to 2. Daj mi znać, co myślisz.
Koishore Roy
Słyszę, że mówisz, że możesz po prostu zignorować kolejność czterech podanych liczb (pierwszym krokiem jest ich posortowanie). Ale co, jeśli poprosiliśmy o pięć numerów p1za pośrednictwem p5, i nadal dozwolone tylko zmienia jeden numer? Czterocyfrowy numer wydaje się zbyt łatwy (dopiero po zobaczeniu twojej odpowiedzi).
Jeppe Stig Nielsen
@KoishoreRoy Podoba mi się twoje rozwiązanie pozwalające na jedno z nich.
xnor
@JeppeStigNielsen Tak, fakt, że kolejność nie ma znaczenia, jest szczególny dla 4 liczb i dzieje się tak, ponieważ po usunięciu jednej w celu utworzenia trzech liczb wszystkie pary liczb są cyklicznie przylegające. Przy pięciu liczbach to nie zadziałałoby (z pewnością można znaleźć przykład), a wyzwanie byłoby zupełnie inne.
xnor
Chciałbym móc dwukrotnie głosować. Piękna obserwacja, dobrze wyjaśniona.
Jonasz
9

R , 66 33 bajtów

function(x)2*min(diff(sort(x),2))

Wypróbuj online!

Znacznie krócej dzięki algorytmowi xnor (przeczytaj ich wyjaśnienie i oceń swój wpis!).

Stara wersja:

R , 66 bajtów

function(x,m=matrix(x,3,4))min(colSums(abs(diff(rbind(m,m[1,])))))

Wypróbuj online!

Pobiera dane wejściowe jako wektor 4 liczb całkowitych.

Działa to, ponieważ minimum można osiągnąć, ustawiając jedną z liczb jako równą jednemu z sąsiadów (nie jest to jedyny sposób osiągnięcia minimum). Aby zobaczyć, dlaczego tak jest, znajdź konfigurację, która osiąga minimum; powiedzmy, że zmieniliśmy . Każda wartość taka, że da tę samą sumę ( pozostaje stała), więc możemy wybrać .p2p2p1p2p3|p1p2|+|p2p3|p2=p1

Istnieją 4 sposoby wyboru liczby, którą zmieniamy; dla każdego z nich musimy tylko obliczyć sumę 3 różnic bezwzględnych.

Kod ustawia wartości w macierzy , gdzie każda kolumna reprezentuje podzbiór rozmiaru 3 z 4 liczb. Skopiuj pierwszy wiersz do czwartego wiersza i oblicz różnice bezwzględne, a następnie weź minimum sumy kolumn.3×4rbind

Robin Ryder
źródło
4

Galaretka , 11 10 bajtów

I;SASƲ$-ƤṂ

Wypróbuj online!

Łącze monadyczne, które pobiera listę, jeśli dane wejściowe są liczbami całkowitymi. Powinien działać na dowolny rozmiar listy. Działa na podstawie tego, że minimalną sumę można uzyskać, testując usunięcie każdej liczby z listy, obliczając sumę magiczną i biorąc minimum.

Nick Kennedy
źródło
3

Galaretka , 8 bajtów

ṁ-Ƥ⁸IA§Ṃ

Monadyczny link akceptujący listę liczb całkowitych *, który daje liczbę całkowitą

* może być dowolną liczbą, o ile jest ich więcej niż 1; używając magicznej formuły w tym samym stylu, sumując otaczające się różnice sąsiadów.

Wypróbuj online!

W jaki sposób?

ṁ-Ƥ⁸IA§Ṃ - Link: list of integers, X       e.g. [17,-6,15,33]
 -Ƥ      - for overlapping "outfixes" of length length(X)-1:
         -                                      [[-6,15,33],[17,15,33],[17,-6,33],[17,-6,15]]
ṁ  ⁸     -   mould like X                       [[-6,15,33,-6],[17,15,33,17],[17,-6,33,17],[17,-6,15,17]]
    I    - incremental differences              [[21,18,-39],[-2,18,-16],[-23,39,-16],[-23,21,2]]
     A   - absolute (vectorises)                [[21,18,39],[2,18,16],[23,39,16],[23,21,2]]
      §  - sums                                 [78,36,78,46]
       Ṃ - minimum                              36
Jonathan Allan
źródło
3

Japt -Q , 11 bajtów

ñÍó ®r- ÑÃn

Wykorzystuje algorytm @ xnor, który oszczędził mi 4 bajty.

Zaoszczędź 5 bajtów dzięki @Shaggy

Spróbuj

Wcielenie ignorancji
źródło
wydaje się działać dobrze, ale czy mógłbyś wyjaśnić, dlaczego to działa?
Koishore Roy
@KoishoreRoy Dodano wyjaśnienie
of Ignorance
29 bajtów (tak myślę )
Kudłaty
@ Kudłaty, kiedy zaktualizowałem swoją odpowiedź, przypadkowo zastąpiłem sumę mapą, co powoduje, że niektóre golfy są nieważne, ale inne są dobre
Embodiment of Ignorance
Ładnie (dalej) grał w golfa :) Możesz zaoszczędzić 1 bajt, zastępując ÃÃgo nową linią.
Kudłaty
3

J , 24 20 18 17 bajtów

alternatywna wersja wykorzystująca algorytm xnor:

2*[:<./2 2-/@$\:~

w jaki sposób

Dwa razy 2 *min [:<./. 2. rzędu odjęty od pierwszego rzędu [:-/macierzy 2x2 utworzonego przez ukształtowanie 2 2$posortowanego sortowania w dół\:~

Wypróbuj online!

oryginalna odpowiedź: J , 24 bajty

[:<./1(1#.2|@-/\],{.)\.]

Wypróbuj online!

Wykorzystując pomysł Nicka Kennedy'ego.

  • 1(...)\.] zastosuj czasownik w parens do wszystkich outfiksów o długości 1 (outfix o długości n jest listą z n usuniętymi ciągłymi elementami, więc powstaje każda możliwa lista z usuniętym 1 wiązem)
  • (1 #. 2 |@-/\ ] , {.)oblicza to sumę magiczną, dodając pierwszy wiąz do wejścia ] , {.i stosując różnicę abs |@-/do przyrostków o długości 2 2 ...\i sumując wynik 1 #..
  • [:<./ zwraca min
Jonasz
źródło
2

05AB1E , 11 7 bajtów

Odpowiedź Portu @xnor 's Jelly .
-4 bajty dzięki @Emigna i @Grimy .

{2ô`αß·

Wypróbuj online.

7 bajtów alternatywę , która działa tylko w starszej wersji 05AB1E (wymagałaby zanim ¥w nowej wersji):

{2ôø¥W·

Wypróbuj online.

Wyjaśnienie:

{        # Sort the (implicit) input-list
         #  i.e. [17,-6,15,33] → [-6,15,17,33]
 2ô      # Split this list into parts of size 2
         #  → [[-6,15],[17,33]]
   `     # Push both separated to the stack
    α    # And take their absolute differences
         #  → [23,18]
     ß   # Pop and push the minimum
         #  → 18
      ·  # Double it (and output implicitly as result)
         #  → 36

{        # Sort the (implicit) input-list
         #  i.e. [17,-6,15,33] → [-6,15,17,33]
 2ô      # Split this list into parts of size 2
         #  → [[-6,15],[17,33]]
   ø     # Zip/transpose, swapping rows/columns
         #  → [[-6,17],[15,33]]
    ¥    # Get the deltas/forward differences of the inner lists
         #  → [[23],[18]]
     W   # Get the flattened minimum (without popping)
         #  → 18
      ·  # Double it (and output implicitly as result)
         #  → 36
Kevin Cruijssen
źródło
1
7 bajtów w starszej wersji: {2ôø¥W·lub 8 z w przepisaniu.
Emigna
2
7 bajtów spoza dziedzictwa:{2ô`αW·
Grimmy
@Emigna Smart, dzięki!
Kevin Cruijssen
@Grimy Dziękuję również!
Kevin Cruijssen
1

C ++ (gcc)

pełny program: 138 bajtów

#include<iostream>
#include<regex>
using namespace std;int main(){int a[4];for(int&b:a)cin>>b;sort(a,a+4);cout<<min(a[2]-*a,a[3]-a[1])*2;}

Wypróbuj online!

funkcja podstawowa: 84 bajty

#include<regex>
int m(int*a){std::sort(a,a+4);return std::min(a[2]-*a,a[3]-a[1])*2;}

Wypróbuj online!

Również za pomocą algorytmu xnor wyjaśnionego w jego poście w języku Python 2.

movatica
źródło
0

Węgiel drzewny , 20 bajtów

I⌊EEθΦθ⁻κμΣEι↔⁻λ§ι⊕μ

Wypróbuj online! Link jest do pełnej wersji kodu. Okazuje się, że korzystam z pomysłu @ NickKennedy. Wyjaśnienie:

   Eθ                   Map over input array
     Φθ                 Filter over input array where
       ⁻κμ              Outer and inner indices differ
  E                     Map over resulting list of lists
           Eι           Map over remaining values in list
                §ι⊕μ    Get the next value in the list
             ↔⁻λ        Compute the absolute difference with the current value
          Σ             Take the sum of absolute differences
 ⌊                      Take the minimum sum
I                       Cast to string and implicitly print
Neil
źródło
0

JavaScript (ES6), 51 bajtów

Używając znacznie bardziej sprytnej metody xnor :

a=>([a,b,c,d]=a.sort((a,b)=>a-b),b+c<a+d?c-a:d-b)*2

Wypróbuj online!


Oryginalna odpowiedź, 96 bajtów

Pobiera dane wejściowe jako tablicę 4 liczb całkowitych. Prawdopodobnie zdecydowanie nie najkrótsze podejście.

a=>a.map(m=x=>a.map((y,i)=>a[m=a.map(v=>s+=Math.abs(p-(p=v)),a[i]=x,p=a[3],s=0)|m<s?m:s,i]=y))|m

Wypróbuj online!

Arnauld
źródło
0

Java 8 , 235 bajtów

Port odpowiedzi i algorytmu Python @ xnor

import java.util.*;interface M{static void main(String[]A){Scanner I=new Scanner(System.in);int a[]={0,0,0,0};for(int i=0;i<4;a[i++]=I.nextInt());java.util.Arrays.sort(a);System.out.print(2*(a[2]-a[0]>a[3]-a[1]?a[3]-a[1]:a[2]-a[0]));}}

Wypróbuj online!

Java 10 , niesprawdzony, 222 bajty

W Javie 10 powinienem być w stanie zamienić lewą stronę deklaracji skanera na var, chociaż nie mogłem go skompilować online, dlatego mogę go dodać tylko jako ciekawostkę. Przepraszam.

interface M{static void main(String[]A){var I=new java.util.Scanner(System.in);int a[]={0,0,0,0};for(int i=3;i<4;a[i++]=I.nextInt());java.util.Arrays.sort(a);System.out.print(2*(a[2]-a[0]>a[3]-a[1]?a[3]-a[1]:a[2]-a[0]));}}
Pył diamentowy
źródło
1
AFAIK możesz po prostu mieć funkcję przesłania, podobnie jak inne odpowiedzi. Nie trzeba dołączać otaczającej klasy, interfejsu itp.
Tau