Produit scalaire minimum

L'inspiration pour ce problème de golf de code vient de la compétition de jam de code de Google . La prémisse derrière le problème est, étant donné l'entrée de deux vecteurs de longueurs variables, de trouver le scalaire minimum possible. Un scalaire peut être trouvé en utilisant la formule suivante:

x1 * y1 + x2 * y2 + ... + xn * yn

Le problème, cependant, est que plusieurs valeurs pour le scalaire peuvent être trouvées en fonction de l'ordre des chiffres dans le cas d'entrée (voir ci-dessous). Votre objectif est de déterminer la solution d'entier scalaire minimale possible en branchant les nombres de cas d'entrée dans l'équation et en les résolvant. Vous ne pouvez utiliser chaque numéro de l'entrée qu'une seule fois et devez utiliser tous les numéros.

Permettez-moi de fournir un exemple avec les vecteurs suivants.

Contribution

3
1 3 -5
-2 4 1

Production

-25

Le premier entier de la ligne représente le nombre de nombres, n, dans chaque vecteur. Dans ce cas, nous avons trois nombres dans chaque vecteur.

Le nombre n peut varier avec chaque cas de test, mais il y aura toujours deux vecteurs.

Dans l'exemple d'entrée, le produit scalaire minimum serait -25.

(-5 * 4) + (1 * 1) + (3 * -2) = 25

Règles

• Vous ne pouvez utiliser chaque entier dans les deux vecteurs qu'une seule fois.
• Vous devez utiliser tous les entiers dans les vecteurs.
• Votre sortie ne doit inclure que le produit final
• Je vais sélectionner la solution avec le moins de code, qui suit toutes les spécifications énumérées ci-dessus, dans n'importe quelle langue!

Astuce: vous n'avez pas besoin de forcer brutalement ce problème, sauf s'il raccourcit votre code. Il existe une méthode spécifique impliquée dans la recherche du scalaire couvrant minimum :).

Gelée, 6 octets

ṢṚ×Ṣ}S

Essayez-le en ligne!

L'utilisation de la force brute est également courte:

Œ!×S€Ṃ

Comment ça fonctionne

ṢṚ×Ṣ}S  Main link. Arguments: u (vector), v (vector)

Ṣ       Sort the components of u.
 Ṛ      Reverse.
   Ṣ}   Sort the components of v.
  ×     Multiply the results, element by element.
     S  Compute the sum of the products.

Sérieusement , 6 octets

,SR,S*

Essayez-le en ligne!

Explication:

,SR,S*
,SR     input first vector, sort, reverse
   ,S   input second vector, sort
     *  dot product

APL, 15 octets

{+/⍺[⍒⍺]×⍵[⍋⍵]}

Il s'agit d'une fonction dyadique qui accepte les tableaux à gauche et à droite et renvoie un entier. Il utilise la même approche que ma réponse Julia : produit scalaire des tableaux triés, un descendant et un ascendant.

Essayez-le ici

MATL , 6 octets

Code:

SiSP*s

Ma première réponse MATL :)

Explication:

S       # Sort the first array
 iS     # Take the second array and sort it
   P    # Flip the array
    *   # Multiply both arrays with each other
     s  # Sum of the result

Essayez-le en ligne!

Mathematica, 30 17 octets

-13 octets par murphy

Sort@#.-Sort@-#2&

Fonction, l'entrée est vector1 (liste), vector2 (liste) Plusieurs révisions:

Plus@@(Sort@#*Reverse@Sort@#2)&(*me*)
Total[Sort@#*Reverse@Sort@#2]& 
Sort@#.Reverse@Sort@#2&        (*alephalpha*)
Sort@#.Sort[#2,#>#2&]&         (*murphy*)
Sort@#.SortBy[#2,-#&]          (*me*)
Sort@#.-Sort@-#2&              (*murphy*)

Pyth - 14 8 octets

Je pense que j'ai compris l'astuce.

s*VSQ_SE

Essayez-le en ligne ici .

Julia, 32 25 octets

x->y->-sort(-x)⋅sort(y)

Il s'agit d'une fonction anonyme qui accepte deux tableaux et renvoie un entier. Pour l'appeler, affectez-le à une variable et faitesf(x)(y) .

Pour les entrées x et y , nous calculons simplement le produit scalaire de x trié dans l'ordre inverse avec y trié. Nous obtenons x dans l'ordre de tri inverse en annulant toutes les valeurs, en triant, puis en annulant à nouveau.

7 octets enregistrés grâce à Dennis!

Javascript ES6, 69 octets

a=>b=>a.sort((x,y)=>x-y).map((x,y)=>i+=b.sort((x,y)=>y-x)[y]*x,i=0)|i

Wow, c'est beaucoup trop long.

Perl 6, 33 30 octets

{sum @^a.sort Z*@^b.sort.reverse}

CJam, 11 octets

q~$\$W%.*:+

Essayez-le en ligne!

Python, 139 octets

def mdp(n, a, b):
    a = list(reversed(sorted(a)))
    b = sorted(b)
    res = sum([a[i] * b[i] for i in range(len(a))])
    return res

C ++, 124 octets

#include<algorithm>
int m(int*a,int*b,int n){std::sort(a,a+n);std::sort(b,b+n);int r=0;while(--n>=0)r+=a[n]**b++;return r;}

non golfé:

#include<algorithm>
int m(int*a,int*b,int n){
 std::sort(a,a+n);
 std::sort(b,b+n);
 int r=0;
 while(--n>=0)
  r+=a[n]*(*b++);
return r;
}

Au début, j'ai utilisé std::greater<int>()pour le tri, bmais simplement inverser l'ordre dans la somme est plus facile.

Haskell, 59 octets

import Data.List
v?u=sum$zipWith(*)(sort v)$reverse$sort u

RETOUR , 29 octets

[{␆␃}\{␆}␄␅[¤¥][×␌]#}␁[¤][+]#]

Try it here.

Remplacez-les ␆␃␄␇par leurs homologues non imprimables.

Lambda anonyme qui laisse le résultat sur stack2. Usage:

""{1 3 0 5-}""{0 2- 4 1}[{␆␃}\{␆}␄␅[¤¥][×␌]#}␁[¤][+]#]!

Explication

[                                 ]  lambda
 {␆␃}                              sort and reverse first stack
       \{␆}                         sort second stack
            ␄␅                     transpose and flatten
               [  ][  ]#             while loop
                ¤¥                     check if 2 items exist in stack
                    ×                  if so, multiply top 2 items
                     ␌                 and push to stack2
                        }␁          switch to stack2
                           [¤][+]#   sum stack2

J, 14 octets

+/@(*|.)&(/:~)

Utilise le même principe que les autres.

Explication

+/@(*|.)&(/:~)  Input: x on LHS and y on RHS
        &(/:~)  Sort both x and y
     |.         Reverse the sorted y
    *           Multiply the sorted x and reversed sorted y elementwise
+/@             Reduce the products using addition and return