Minimales Skalarprodukt

Die Inspiration für dieses Code-Golf-Problem ist der Code-Jam-Wettbewerb von Google . Die Prämisse hinter dem Problem ist, bei der Eingabe von zwei Vektoren unterschiedlicher Länge den minimal möglichen Skalar zu finden. Ein Skalar kann mit der folgenden Formel gefunden werden:

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

Das Problem ist jedoch, dass abhängig von der Reihenfolge der Ziffern im Eingabefall (siehe unten) mehrere Werte für den Skalar gefunden werden können. Ihr Ziel ist es, die minimal mögliche skalare Ganzzahllösung zu bestimmen, indem Sie die eingegebenen Fallnummern in die Gleichung einfügen und danach auflösen. Sie dürfen jede Zahl in der Eingabe nur einmal verwenden und müssen alle Zahlen verwenden.

Gestatten Sie mir ein Beispiel mit den folgenden Vektoren.

Eingang

3
1 3 -5
-2 4 1

Ausgabe

-25

Die erste Ganzzahl in der Zeile gibt die Anzahl der Zahlen n in jedem Vektor an. In diesem Fall haben wir drei Zahlen in jedem Vektor.

Die Anzahl n kann mit jedem Testfall variieren, es gibt jedoch immer zwei Vektoren.

In der Beispieleingabe wäre das minimale Skalarprodukt -25.

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

Regeln

• Sie dürfen jede Ganzzahl in beiden Vektoren nur einmal verwenden.
• Sie müssen alle Ganzzahlen in den Vektoren verwenden.
• Ihre Ausgabe darf nur das Endprodukt enthalten
• Ich wähle die Lösung mit der geringsten Codemenge, die allen oben aufgeführten Spezifikationen entspricht, in einer beliebigen Sprache aus!

Tipp: Sie müssen dieses Problem nicht brutal erzwingen, es sei denn, Ihr Code wird dadurch kürzer. Es gibt eine spezielle Methode, um den minimalen überspannenden Skalar zu finden :).

Gelee, 6 Bytes

ṢṚ×Ṣ}S

Probieren Sie es online!

Brute Force ist ebenso kurz:

Œ!×S€Ṃ

Wie es funktioniert

ṢṚ×Ṣ}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.

Im Ernst , 6 Bytes

,SR,S*

Probieren Sie es online!

Erläuterung:

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

APL, 15 Bytes

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

Dies ist eine dyadische Funktion, die Arrays links und rechts akzeptiert und eine Ganzzahl zurückgibt. Es verwendet den gleichen Ansatz wie meine Julia- Antwort : Punktprodukt der sortierten Arrays, eines absteigend und eines aufsteigend.

Probieren Sie es hier aus

MATL , 6 Bytes

Code:

SiSP*s

Meine erste Antwort auf MATL :)

Erläuterung:

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

Probieren Sie es online!

Mathematica, 30 17 Bytes

-13 Bytes von Murphy

Sort@#.-Sort@-#2&

Funktion, Eingabe ist vector1 (Liste), vector2 (Liste) Mehrere Revisionen:

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 Bytes

Ich glaube, ich habe den Trick herausgefunden.

s*VSQ_SE

Probieren Sie es hier online aus .

Julia, 32 25 Bytes

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

Dies ist eine anonyme Funktion, die zwei Arrays akzeptiert und eine Ganzzahl zurückgibt. Um es aufzurufen, weisen Sie es einer Variablen zu und machen f(x)(y).

Für die Eingaben x und y berechnen wir einfach das Skalarprodukt von x in umgekehrter Reihenfolge mit y sortiert. Wir erhalten x in umgekehrter Reihenfolge, indem wir alle Werte negieren, sortieren und dann erneut negieren.

7 Bytes gespart dank Dennis!

Javascript ES6, 69 Bytes

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

Wow, das ist viel zu lang.

Perl 6, 33 30 Bytes

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

CJam, 11 Bytes

q~$\$W%.*:+

Probieren Sie es online!

Python, 139 Bytes

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 Bytes

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

ungolfed:

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

Zuerst habe ich std::greater<int>()für die Sortierung verwendet, baber es ist einfacher, die Reihenfolge in der Summe umzukehren.

Haskell, 59 Bytes

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

RETURN , 29 Bytes

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

Try it here.

Ersetzen Sie alle ␆␃␄␇ durch ihre nicht druckbaren Gegenstücke.

Anonymes Lambda, das das Ergebnis auf stack2 verlässt. Verwendung:

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

Erläuterung

[                                 ]  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 Bytes

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

Verwendet das gleiche Prinzip wie die anderen.

Erläuterung

+/@(*|.)&(/:~)  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