Make me a minimum magic sum

Question

Keeping this challenge short.

You are given 4 numbers: p1, p2, p3 and p4.

The magic sum of the numbers are defined as follows:

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

You are only allowed to change one of the above integer values (p1, p2, p3 or p4). You need to change the value such that the magic sum of the values attains its minimum value.

For example:

p1, p2, p3, p4 = 17, -6, 15, 33. The value of the magic sum is 78 in this case.

You can change the -6 here to 16, and the value of the magic sum will become 36, which is the minimum attainable value.

Do keep in mind that numbers can be positive or negative integers.

This is code-golf, so least bytes in code wins. Brownie points for using a Practical Language over a Recreational language. May the 4th be with you.

To reiterate:

Sample 1

Input 1

17 -6 15 33

Output 1

36

Explanation 1

The -6 can be replaced with 16 and that gives us the minimum attainable magic sum possible.

Sample 2

Input 2

10 10 10 10

Output 2

0 or 2

either is acceptable

Explanation 2

The minimum attainable magic sum is 0 since the minimum sum of 4 positive integers is 0. If a number has to be changed, then one of the 10's can be changed to a 9 and thus yielding the output 2.

Sample 3

Input 3

1 2 3 4

Output 3

4

Explanation 3

The input by itself yields 6 as its magic sum. Changing the 4 to 1 and the minimum magic sum is attained, which is 4.

Answer 1

Jelly, 6 bytes

ṢŒœIṂḤ

Try it online!

A port of my Python answer.

     (input)        [17, -6, 15, 33]
Ṣ    sort           [-6, 15, 17, 33]
Œœ   odd-even elts  [[-6, 17], [15, 33]]
I    increments     [23, 18]
M    minimum        18
Ḥ    double         36 

Answer 2

Python 2, 44 bytes

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

Try it online!

Sorts the input as a,b,c,d, in ascending order, takes the smaller of c-a and d-b, and doubles it. Why does this work?

First, note that when we change an element to maximize to total cyclic sum of distances, it's optimal (or tied for optimal) to change it to equal a neighbor, such as 17, -6, 15, 33 -> 17, 17, 15, 33. That's because its new total distance to its left and right cyclic neighbors is at least the distance between those neighbors, so making these be equal is the best we can do.

Now, deleting one of two adjacent copies of a number gives the same cyclic sum of distances. In the example, this is 17, 15, 33, giving distances 2 + 18 + 16. So instead of replacing one of the four numbers, it's equivalent to just delete it leaving three numbers, and using the sum of their cyclic distances.

Notice that with 3 numbers, the largest distance is the sum of the two smaller ones. This is because if we sort the numbers to have a ≤ b ≤ c, then |a - c| = |a - b| + |b - c|. In other words, we travel between the largest and smallest number twice, using the medium number as a pit stop one of the times. So, the sum of the three distances is just twice the distance between the minimum and maximum, so (c-a)*2.

So, the question is which number we delete to get the smallest distance between the minimum and maximum of the three numbers that remains. Clearly we delete either the smallest or the largest of the numbers. Calling them a, b, c, d in sorted order, deleting a leaves d - b, and deleting d leaves c - a, and the final result is double whichever is smaller.

Answer 3

R, 66 33 bytes

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

Try it online!

Much shorter with xnor's algorithm (go read their explanation and upvote their post!).

Old version:

R, 66 bytes

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

Try it online!

Takes input as a vector of 4 integers.

This works because the minimum can be attained by setting one of the numbers as equal to one of its neighbours (it is not the only way of attaining the minimum). To see why this is true, find a configuration which achieves the minimum; say we have changed \$p_2\$. Any value of \$p_2\$ such that \$p_1\leq p_2\leq p_3\$ will give the same sum (\$|p_1-p_2|+|p_2-p_3|\$ remains constant), so we can choose \$p_2=p_1\$.

There are 4 ways of choosing which number we change; for each of these, we only have to compute the sum of 3 absolute differences.

The code sets the values in a \$3\times4\$ matrix, where each column represents a subset of size 3 of the 4 numbers. Copy the first row to a 4th row with rbind and compute the absolute differences, then take the minimum of the column sums.

Answer 4

Jelly, 11 10 bytes

I;SASƲ$-ƤṂ

Try it online!

A monadic link that takes a list if integers as input. Should work for arbitrary list size. Works on the basis that the minimum sum can be obtained by testing removing each number from the list, calculating the magic sum and taking the minimum.

Answer 5

Japt -Q, 11 bytes

ñÍó ®r- ÑÃn

Uses @xnor's algorithm, which saved me 4 bytes.

Saved 5 bytes thanks to @Shaggy

Try it

Answer 6

Jelly, 8 bytes

ṁ-Ƥ⁸IA§Ṃ

A monadic Link accepting a list of integers* which yields an integer

_{* can be any number so long as there are more than 1; using same style magic formula summing the neighbours differences wrapping around.}

Try it online!

How?

ṁ-Ƥ⁸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

Answer 7

J, ^{24 20 18} 17 bytes

alternative version using xnor algorithm:

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

how

Two times 2 * the min of [:<./ the 2nd row subtracted from the first row [:-/ of the 2x2 matrix formed by shaping 2 2$ the input sorted down \:~

Try it online!

original answer: J, 24 bytes

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

Try it online!

Using Nick Kennedy's idea.

• 1(...)\.] apply the verb in parens to all outfixes of length 1 (an outfix of length n is a list with n contiguous elements removed, so this produces every possible list with 1 elm removed)
• (1 #. 2 |@-/\ ] , {.) this calculates the magic sum by appending the first elm to the input ] , {. and applying the abs difference |@-/ to infixes of length 2 2 ...\, and summing the result 1 #..
• [:<./ returns the min

Answer 8

05AB1E, 11 7 bytes

Port of @xnor's Jelly answer.
-4 bytes thanks to @Emigna and @Grimy.

{2ô`αß·

Try it online.

7 bytes alternative which only works in the legacy version of 05AB1E (would require a € before the ¥ in the new version):

{2ôø¥W·

Try it online.

Explanation:

{        # 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

Answer 9

C++ (gcc)

full program: 138 bytes

#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;}

Try it online!

core function: 84 bytes

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

Try it online!

Also using the algorithm xnor explained in his Python 2 post.

Answer 10

JavaScript (ES6), 51 bytes

Using xnor's much more clever method:

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

Try it online!

---

Original answer, 96 bytes

Takes input as an array of 4 integers. Probably Definitely not the shortest approach.

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

Try it online!

Answer 11

Wolfram Language (Mathematica), 29 bytes

A port of @xnor's algorithm

2{#3-#}~Min~{#4-#2}&@@Sort@#&

Try it online!

Answer 12

Charcoal, 20 bytes

Ｉ⌊ＥＥθΦθ⁻κμΣＥι↔⁻λ§ι⊕μ

Try it online! Link is to verbose version of code. Turns out I'm using @NickKennedy's idea. Explanation:

   Ｅθ                   Map over input array
     Φθ                 Filter over input array where
       ⁻κμ              Outer and inner indices differ
  Ｅ                     Map over resulting list of lists
           Ｅι           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
Ｉ                       Cast to string and implicitly print

Answer 13

Java 8, 235 bytes

A port of @xnor's Python answer and algorithm

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

Try it online!

Java 10, unproven, 222 bytes

With Java 10, I should be able to replace left side of Scanner declaration with var, although I could not compile it online and thus I can only add it as a trivia. Sorry.

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