Faites-moi une somme magique minimum

27

Garder ce défi court.

On vous donne 4 nombres: p1, p2, p3 et p4.

La somme magique des nombres est définie comme suit:

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

Vous êtes uniquement autorisé à modifier l'une des valeurs entières ci-dessus (p1, p2, p3 ou p4). Vous devez modifier la valeur de sorte que la somme magique des valeurs atteigne sa valeur minimale.

Par exemple:

p1, p2, p3, p4 = 17, -6, 15, 33. La valeur de la somme magique est de 78 dans ce cas.

Vous pouvez changer le -6 ici à 16, et la valeur de la somme magique deviendra 36, ​​qui est la valeur minimale atteignable.

Gardez à l'esprit que les nombres peuvent être des entiers positifs ou négatifs.

C'est le code-golf, donc le moins d'octets dans le code gagne. Brownie souligne l'utilisation d'un langage pratique par rapport à un langage récréatif. Que le 4 soit avec toi.

Recommencer:

Échantillon 1

Entrée 1

17 -6 15 33

Sortie 1

36

Explication 1

Le -6 peut être remplacé par 16 et cela nous donne la somme magique minimale possible.

Échantillon 2

Entrée 2

10 10 10 10

Sortie 2

0 or 2

soit est acceptable

Explication 2

La somme magique minimale atteignable est 0 puisque la somme minimale de 4 entiers positifs est 0. Si un nombre doit être changé, alors l'un des 10 peut être changé en 9 et ainsi donner la sortie 2.

Échantillon 3

Entrée 3

1 2 3 4

Sortie 3

4

Explication 3

L'entrée en elle-même donne 6 comme somme magique. Changer le 4 en 1 et la somme magique minimum est atteinte, qui est 4.

Koishore Roy
la source
10
+1, mais pourrait faire avec plus d'exemples.
Jonathan Allan
2
Un exemple pleinement travaillé et quelques autres cas de test et c'est un +1de moi.
Shaggy
@Shaggy done. où est mon +1? : P
Koishore Roy
1
@KoishoreRoy Le test 3 ne serait-il pas 6 sans le changement?
wizzwizz4
@ wizzwizz4 | 1 - 2 | + | 2 - 3 | + | 3 - 4 | + | 4 - 1 | = 1 + 1 + 1 + 3 = 6. Vous avez raison. J'ai fait le montage.
Koishore Roy

Réponses:

20

Python 2 , 44 octets

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

Essayez-le en ligne!

Trie l'entrée comme a,b,c,d,dans l'ordre croissant, prend le plus petit de c-aet d-b, et le double. Pourquoi ça marche?

Tout d'abord, notez que lorsque nous modifions un élément pour maximiser la somme cyclique totale des distances, il est optimal (ou lié pour optimal) de le changer pour égaler un voisin, tel que 17, -6, 15, 33 -> 17, 17, 15, 33. C'est parce que sa nouvelle distance totale à ses voisins cycliques gauche et droit est au moins la distance entre ces voisins, donc les rendre égaux est le mieux que nous puissions faire.

Maintenant, la suppression d'une des deux copies adjacentes d'un nombre donne la même somme cyclique des distances. Dans l'exemple, il s'agit de 17, 15, 33donner des distances 2 + 18 + 16. Ainsi, au lieu de remplacer l'un des quatre nombres, il suffit de le supprimer en laissant trois nombres et en utilisant la somme de leurs distances cycliques.

Notez qu'avec 3 nombres, la plus grande distance est la somme des deux plus petits. C'est parce que si nous trions les nombres à avoir a ≤ b ≤ c, alors |a - c| = |a - b| + |b - c|. En d'autres termes, nous voyageons deux fois entre le plus grand et le plus petit nombre, en utilisant le nombre moyen comme arrêt au stand l'une des fois. Ainsi, la somme des trois distances n'est que le double de la distance entre le minimum et le maximum, donc (c-a)*2.

Donc, la question est de savoir quel nombre nous supprimons pour obtenir la plus petite distance entre le minimum et le maximum des trois nombres qui reste. De toute évidence, nous supprimons le plus petit ou le plus grand des nombres. Les appeler a, b, c, ddans l'ordre trié, supprimer les afeuilles d - bet supprimer les dfeuilles c - a, et le résultat final est le double de ce qui est le plus petit.

xnor
la source
aidez-moi avec un cas de test ici. que faire si la somme magique est déjà 0, ce qui est le plus petit nombre atteignable. dans ce cas, la réponse devrait-elle être 0? ou le prochain nombre le plus bas possible. Dans le cas où l'entrée est [10,10,10,10], la somme magique est 0. la deuxième plus basse possible est 2. Faites-moi savoir ce que vous pensez.
Koishore Roy
Ce que je vous entends dire, c'est que vous pouvez simplement ignorer l'ordre des quatre nombres donnés (votre première étape consiste à les trier). Mais si nous avions demandé cinq numéros p1par p5, et encore seulement permis de changer un numéro? Le cas à quatre chiffres semble trop facile (seulement après avoir vu votre réponse).
Jeppe Stig Nielsen
@KoishoreRoy J'aime votre solution d'autoriser l'un ou l'autre.
xnor
@JeppeStigNielsen Oui, le fait que l'ordre n'a pas d'importance est spécial pour 4 numéros, et cela se produit car après avoir supprimé un pour en faire trois, toutes les paires de nombres sont cycliquement adjacentes. Avec cinq chiffres, cela ne fonctionnerait pas (vous pouvez sûrement trouver un exemple), et le défi serait très différent.
xnor
J'aimerais pouvoir voter deux fois. Belle observation, bien expliquée.
Jonah
9

R , 66 33 octets

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

Essayez-le en ligne!

Beaucoup plus court avec l'algorithme de xnor (allez lire leur explication et voter positivement!).

Ancienne version:

R , 66 octets

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

Essayez-le en ligne!

Prend l'entrée comme un vecteur de 4 entiers.

Cela fonctionne parce que le minimum peut être atteint en définissant l'un des nombres comme égal à l'un de ses voisins (ce n'est pas le seul moyen d'atteindre le minimum). Pour voir pourquoi cela est vrai, trouvez une configuration qui atteint le minimum; disons que nous avons changé . Toute valeur de telle que donnera la même somme ( reste constante), nous pouvons donc choisir .p2p2p1p2p3|p1p2|+|p2p3|p2=p1

Il y a 4 façons de choisir le numéro que nous changeons; pour chacun d'eux, il suffit de calculer la somme de 3 différences absolues.

Le code définit les valeurs dans une matrice , où chaque colonne représente un sous-ensemble de taille 3 sur les 4 nombres. Copiez la première ligne sur une 4ème ligne avec et calculez les différences absolues, puis prenez le minimum des sommes de colonne.3×4rbind

Robin Ryder
la source
4

Gelée , 11 10 octets

I;SASƲ$-ƤṂ

Essayez-le en ligne!

Un lien monadique qui prend une liste si des entiers en entrée. Devrait fonctionner pour une taille de liste arbitraire. Fonctionne sur la base que la somme minimale peut être obtenue en testant la suppression de chaque nombre de la liste, en calculant la somme magique et en prenant le minimum.

Nick Kennedy
la source
3

Gelée , 8 octets

ṁ-Ƥ⁸IA§Ṃ

Un lien monadique acceptant une liste d'entiers * qui donne un entier

* peut être n'importe quel nombre tant qu'il y en a plus de 1; en utilisant la même formule magique de style résumant les différences entre voisins.

Essayez-le en ligne!

Comment?

ṁ-Ƥ⁸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
la source
3

Japt -Q , 11 octets

ñÍó ®r- ÑÃn

Utilise l'algorithme @ xnor, qui m'a fait économiser 4 octets.

5 octets enregistrés grâce à @Shaggy

Essayez-le

Incarnation de l'ignorance
la source
semble bien fonctionner, mais pourriez-vous expliquer pourquoi cela fonctionne?
Koishore Roy
@KoishoreRoy Ajout d'une explication
Incarnation de l'ignorance
29 octets (je pense )
Shaggy
@Shaggy quand j'ai mis à jour ma réponse, j'ai accidentellement remplacé sum par map, rendant certains golfs invalides, mais d'autres sont bons
Embodiment of Ignorance
Joliment (plus loin) joué au golf :) Vous pouvez économiser 1 octet de plus en le remplaçant ÃÃpar une nouvelle ligne.
Shaggy
3

J , 24 20 18 17 octets

version alternative utilisant l'algorithme xnor:

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

Comment

Deux fois 2 *le min de [:<./la 2e ligne soustrait de la première ligne [:-/de la matrice 2x2 formée en façonnant 2 2$l'entrée triée\:~

Essayez-le en ligne!

réponse d'origine: J , 24 octets

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

Essayez-le en ligne!

En utilisant l'idée de Nick Kennedy.

  • 1(...)\.] appliquer le verbe entre parenthèses à tous les outfixes de longueur 1 (un outfix de longueur n est une liste avec n éléments contigus supprimés, donc cela produit toutes les listes possibles avec 1 orme supprimé)
  • (1 #. 2 |@-/\ ] , {.)ceci calcule la somme magique en ajoutant le premier orme à l'entrée ] , {.et en appliquant la différence abs |@-/aux infixes de longueur 2 2 ...\, et en additionnant le résultat 1 #..
  • [:<./ renvoie le min
Jonas
la source
2

05AB1E , 11 7 octets

Réponse de Port de @xnor Jelly .
-4 octets grâce à @Emigna et @Grimy .

{2ô`αß·

Essayez-le en ligne.

Alternative de 7 octets qui ne fonctionne que dans la version héritée de 05AB1E (nécessiterait une avant ¥dans la nouvelle version):

{2ôø¥W·

Essayez-le en ligne.

Explication:

{        # 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
la source
1
7 octets en héritage: {2ôø¥W·ou 8 avec en réécriture.
Emigna
2
7 octets en non-hérité:{2ô`αW·
Grimmy
@Emigna Smart, merci!
Kevin Cruijssen
@Grimy Merci aussi!
Kevin Cruijssen
1

C ++ (gcc)

programme complet: 138 octets

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

Essayez-le en ligne!

fonction principale: 84 octets

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

Essayez-le en ligne!

Utilisant également l'algorithme xnor expliqué dans son article sur Python 2.

movatica
la source
0

Fusain , 20 octets

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

Essayez-le en ligne! Le lien est vers la version détaillée du code. Il s'avère que j'utilise l'idée de @ NickKennedy. Explication:

   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
la source
0

Java 8 , 235 octets

Un port de la réponse et de l'algorithme 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]));}}

Essayez-le en ligne!

Java 10 , non prouvé, 222 octets

Avec Java 10, je devrais être en mesure de remplacer le côté gauche de la déclaration du scanner avec var, bien que je ne puisse pas le compiler en ligne et donc je ne peux que l'ajouter comme un jeu-questionnaire. Désolé.

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]));}}
Poussière de diamant
la source
1
AFAIK vous pouvez simplement avoir une fonction comme votre soumission, comme la façon dont les autres réponses ont fait. Pas besoin d'inclure la classe environnante, l'interface, etc.
Tau