Minimalna iloczyn skalarny

Inspiracją do rozwiązania tego problemu z golfem jest konkurs Google jam jam . Założeniem problemu jest, biorąc pod uwagę wejście dwóch wektorów o różnej długości, znalezienie minimalnego możliwego skalara. Skalar można znaleźć za pomocą następującej formuły:

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

Problem polega jednak na tym, że można znaleźć wiele wartości skalara w zależności od kolejności cyfr w przypadku wprowadzania (patrz poniżej). Twoim celem jest ustalenie minimalnego możliwego skalarnego rozwiązania liczb całkowitych poprzez podłączenie liczb przypadków wejściowych do równania i ich rozwiązanie. Możesz użyć każdej liczby na wejściu tylko raz i musisz użyć wszystkich liczb.

Pozwólcie, że podam przykład z następującymi wektorami.

Wejście

3
1 3 -5
-2 4 1

Wynik

-25

Pierwsza liczba całkowita w linii reprezentuje liczbę liczb, n, w każdym wektorze. W tym przypadku mamy trzy liczby w każdym wektorze.

Liczba n może się różnić w każdym przypadku testowym, ale zawsze będą dwa wektory.

W przykładowym danych wejściowych minimalny iloczyn skalarny wynosiłby -25.

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

Zasady

• Możesz użyć tylko jednej liczby całkowitej w obu wektorach.
• Musisz użyć wszystkich liczb całkowitych w wektorach.
• Twój wynik musi zawierać tylko produkt końcowy
• Wybiorę rozwiązanie z najmniejszą ilością kodu, zgodną ze wszystkimi powyższymi specyfikacjami, w dowolnym języku!

Wskazówka: nie musisz brutalnie wymuszać tego problemu, chyba że spowoduje to skrócenie kodu. W znalezieniu minimalnego skalara obejmującego jest określona metoda :).

Galaretka, 6 bajtów

ṢṚ×Ṣ}S

Wypróbuj online!

Używanie brutalnej siły jest równie krótkie:

Œ!×S€Ṃ

Jak to działa

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

Poważnie , 6 bajtów

,SR,S*

Wypróbuj online!

Wyjaśnienie:

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

APL, 15 bajtów

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

Jest to funkcja dynamiczna, która akceptuje tablice po lewej i prawej stronie i zwraca liczbę całkowitą. Wykorzystuje to samo podejście, co moja odpowiedź Julii : iloczyn iloczynu posortowanych tablic, jednego malejącego i jednego rosnącego.

Wypróbuj tutaj

MATL , 6 bajtów

Kod:

SiSP*s

Moja pierwsza odpowiedź MATL :)

Wyjaśnienie:

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

Wypróbuj online!

Mathematica, 30 17 bajtów

-13 bajtów przez murphy

Sort@#.-Sort@-#2&

Funkcja, dane wejściowe to wektor1 (lista), wektor2 (lista) Kilka wersji:

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 bajtów

Myślę, że wymyśliłem sztuczkę.

s*VSQ_SE

Wypróbuj online tutaj .

Julia, 32 25 bajtów

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

Jest to anonimowa funkcja, która akceptuje dwie tablice i zwraca liczbę całkowitą. Aby go wywołać, przypisz go do zmiennej i zrób f(x)(y).

Do wejścia x i y , po prostu obliczać iloczyn skalarny x sortowane w kolejności odwrotnej do z y sortowane. Otrzymujemy x w odwrotnej kolejności, negując wszystkie wartości, sortując, a następnie ponownie negując.

Zaoszczędzono 7 bajtów dzięki Dennisowi!

JavaScript ES6, 69 bajtów

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

Wow, to za długo.

Perl 6, 33 30 bajtów

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

CJam, 11 bajtów

q~$\$W%.*:+

Wypróbuj online!

Python, 139 bajtów

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 bajty

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

bez golfa:

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

Na początku używałem std::greater<int>()sortowania, bale po prostu odwrócenie kolejności w podsumowaniu jest łatwiejsze.

Haskell, 59 bajtów

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

ZWROT , 29 bajtów

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

Try it here.

Wymień dowolny ␆␃␄␇ ich niedrukowalne odpowiedniki.

Anonimowa lambda, która pozostawia wynik na stosie2. Stosowanie:

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

Wyjaśnienie

[                                 ]  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 bajtów

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

Stosuje tę samą zasadę, co pozostałe.

Wyjaśnienie

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