27
\$\begingroup\$

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.

\$\endgroup\$
  • 10
    \$\begingroup\$ +1, but could do with more examples. \$\endgroup\$ – Jonathan Allan May 4 at 20:36
  • 2
    \$\begingroup\$ A fully worked example and a couple more test cases and it's a +1 from me. \$\endgroup\$ – Shaggy May 4 at 22:47
  • \$\begingroup\$ @Shaggy done. where is my +1? :P \$\endgroup\$ – Koishore Roy May 5 at 12:01
  • 1
    \$\begingroup\$ @KoishoreRoy Wouldn't test case 3 be 6 without the change? \$\endgroup\$ – wizzwizz4 May 5 at 13:25
  • \$\begingroup\$ @wizzwizz4 |1 - 2 | + |2 - 3| + |3 - 4| + |4 - 1| = 1+1+1+3 =6. You are correct. Made the edit. \$\endgroup\$ – Koishore Roy May 5 at 13:27

13 Answers 13

14
\$\begingroup\$

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 
\$\endgroup\$
20
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ help me out with a test case here. what if the magic sum is already 0, which the lowest attainable number. in that case, should the answer be 0? or the next lowest number possible. Incase the input is [10,10,10,10], the magic sum is 0. the second lowest possible is 2. Let me know what you think. \$\endgroup\$ – Koishore Roy May 5 at 10:51
  • \$\begingroup\$ What I hear you say, is that you can just ignore the order of the four numbers given (your first step is to sort them). But what if we had asked for five numbers p1 through p5, and still only allowed changing one number? The four-number case seems too easy (only after seeing your answer). \$\endgroup\$ – Jeppe Stig Nielsen May 5 at 16:40
  • \$\begingroup\$ @KoishoreRoy I like your solution of allowing either one. \$\endgroup\$ – xnor May 5 at 18:09
  • \$\begingroup\$ @JeppeStigNielsen Yes, the fact that order doesn't matter is special to 4 numbers, and it happens because after deleting one to make three numbers, all pairs of numbers are cyclically adjacent. With five numbers this wouldn't work (you can surely find an example), and the challenge would be very different. \$\endgroup\$ – xnor May 5 at 18:11
  • \$\begingroup\$ Wish I could upvote twice. Beautiful observation, well explained. \$\endgroup\$ – Jonah May 5 at 19:54
9
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

Japt -Q, 11 bytes

ñÍó ®r- ÑÃn

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

Saved 5 bytes thanks to @Shaggy

Try it

\$\endgroup\$
  • \$\begingroup\$ seems to be working fine, but would you explain why this works? \$\endgroup\$ – Koishore Roy May 4 at 20:21
  • \$\begingroup\$ @KoishoreRoy Added an explanation \$\endgroup\$ – Embodiment of Ignorance May 4 at 20:38
  • \$\begingroup\$ 29 bytes (I think) \$\endgroup\$ – Shaggy May 4 at 21:22
  • \$\begingroup\$ @Shaggy when I updated my answer, I accidentally replaced sum with map, making some golfs invalid, but others are good \$\endgroup\$ – Embodiment of Ignorance May 4 at 21:43
  • \$\begingroup\$ Nicely (further) golfed :) You can save 1 more byte by replacing ÃÃ with a newline. \$\endgroup\$ – Shaggy May 4 at 22:26
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ 7 bytes in legacy: {2ôø¥W· or 8 with in the rewrite. \$\endgroup\$ – Emigna May 6 at 14:36
  • 2
    \$\begingroup\$ 7 bytes in non-legacy: {2ô`αW· \$\endgroup\$ – Grimmy May 6 at 15:04
  • \$\begingroup\$ @Emigna Smart, thanks! \$\endgroup\$ – Kevin Cruijssen May 6 at 16:16
  • \$\begingroup\$ @Grimy Thanks as well! \$\endgroup\$ – Kevin Cruijssen May 6 at 16:16
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 20 bytes

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

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

   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
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 29 bytes

A port of @xnor's algorithm

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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]));}}
\$\endgroup\$
  • 1
    \$\begingroup\$ AFAIK you can just have a function as your submission, like how the other answers have done. No need to include the surrounding class, interface, etc. \$\endgroup\$ – Tau May 6 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.