16
\$\begingroup\$

Minimum Scalar Product

The inspiration for this code golf problem is from Google's code jam competition. The premise behind the problem is, given the input of two vectors of varying lengths, find the minimum possible scalar. A scalar can be found using the following formula:

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

The problem, however, is that multiple values for the scalar can be found depending on the order of the numerals in the input case (seen below). Your goal is to determine the minimum possible scalar integer solution by plugging in the input case numbers into the equation and solving for it. You may use every number in the input only once, and must use all of the numbers.

Allow me to provide an example with the following vectors.

Input

3
1 3 -5
-2 4 1

Output

-25

The first integer on the line represents the number of numbers, n, in each vector. In this case, we have three numbers in each vector.

The number n may vary with each test case, but there will always be two vectors.

In the example input, the minimum scalar product would be -25.

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

Rules

  • You may only use each integer in both vectors once.
  • You must use all integers in the vectors.
  • Your output must only include the final product
  • I'll select the solution with the least amount of code, which follows all of the specifications listed above, in any language!

Hint: You don't need to brute force this problem, unless it makes your code shorter. There is a specific method involved in finding the minimum spanning scalar :).

\$\endgroup\$

15 Answers 15

8
\$\begingroup\$

Jelly, 6 bytes

ṢṚ×Ṣ}S

Try it online!

Using brute force is equally short:

Œ!×S€Ṃ

How it works

ṢṚ×Ṣ}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.
\$\endgroup\$
6
\$\begingroup\$

Seriously, 6 bytes

,SR,S*

Try it online!

Explanation:

,SR,S*
,SR     input first vector, sort, reverse
   ,S   input second vector, sort
     *  dot product
\$\endgroup\$
5
\$\begingroup\$

APL, 15 bytes

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

This is a dyadic function that accepts arrays on the left and right and returns an integer. It uses the same approach as my Julia answer: dot product of the sorted arrays, one descending and one ascending.

Try it here

\$\endgroup\$
5
\$\begingroup\$

MATL, 6 bytes

Code:

SiSP*s

My first MATL answer :)

Explanation:

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

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ I'm glad to see this! :-) \$\endgroup\$ – Luis Mendo Mar 12 '16 at 10:05
4
\$\begingroup\$

Mathematica, 30 17 bytes

-13 bytes by murphy

Sort@#.-Sort@-#2&

Function, input is vector1(list),vector2(list) Several revisions:

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*)
\$\endgroup\$
  • \$\begingroup\$ clever solution! \$\endgroup\$ – baseman101 Mar 12 '16 at 4:49
  • 2
    \$\begingroup\$ Sort@#.Reverse@Sort@#2& \$\endgroup\$ – alephalpha Mar 12 '16 at 6:36
  • \$\begingroup\$ Sort@#.Sort[#2,#>#2&]& \$\endgroup\$ – murphy Mar 12 '16 at 21:21
  • 1
    \$\begingroup\$ Sort@#.-Sort@-#2& \$\endgroup\$ – murphy Mar 12 '16 at 21:33
  • \$\begingroup\$ Or for your solution 1, Sort@#.SortBy[#2,-#&] \$\endgroup\$ – CalculatorFeline Mar 12 '16 at 21:45
2
\$\begingroup\$

Pyth - 14 8 bytes

I think I figured out the trick.

s*VSQ_SE

Try it online here.

\$\endgroup\$
2
\$\begingroup\$

Julia, 32 25 bytes

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

This is an anonymous function that accepts two arrays and returns an integer. To call it, assign it to a variable and do f(x)(y).

For inputs x and y, we simply compute the dot product of x sorted in reverse order with y sorted. We get x in reverse sorted order by negating all values, sorting, then negating again.

Saved 7 bytes thanks to Dennis!

\$\endgroup\$
2
\$\begingroup\$

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, this is way too long.

\$\endgroup\$
  • \$\begingroup\$ I think trying to reuse the sort function is costing you 3 bytes. \$\endgroup\$ – Neil Mar 12 '16 at 20:35
  • \$\begingroup\$ I did more golfing. Better? \$\endgroup\$ – Mama Fun Roll Mar 12 '16 at 20:43
  • \$\begingroup\$ You can probably save a byte with |i instead of &&i \$\endgroup\$ – ETHproductions Mar 13 '16 at 1:36
  • \$\begingroup\$ Thx @ETHproductions \$\endgroup\$ – Mama Fun Roll Mar 13 '16 at 1:38
  • \$\begingroup\$ Yes, that's what I was thinking of. \$\endgroup\$ – Neil Mar 13 '16 at 10:58
2
\$\begingroup\$

Perl 6, 33 30 bytes

{sum @^a.sort Z*@^b.sort.reverse}
\$\endgroup\$
  • \$\begingroup\$ Why not {sum @^a.sort Z*[R,] @^b.sort}((1,3,-5),(-2,4,1)).say \$\endgroup\$ – Aleks-Daniel Jakimenko-A. May 8 '16 at 15:16
1
\$\begingroup\$

CJam, 11 Bytes

q~$\$W%.*:+

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ You can save a few bytes by removing spaces next to equals, for instance b = sorted(b) turns into b=sorted(b) (2 bytes saved). You can additionally put multiple statements on the same line by separating them with a semicolon, for instance a=list(reversed(sorted(a)));b=sorted(b);res=0 \$\endgroup\$ – charredgrass Jul 13 '16 at 4:01
  • \$\begingroup\$ @charredgrass I'm new here. What's the need to save every possible byte? I was trying to make it readable. \$\endgroup\$ – rebelliard Jul 13 '16 at 4:02
  • \$\begingroup\$ Welcome to PPCG then! This question is a code-golf competition where the goal is to write code to complete the challenge in the fewest bytes possible, which usually means less readable code. \$\endgroup\$ – charredgrass Jul 13 '16 at 4:21
  • \$\begingroup\$ @charredgrass got it! \$\endgroup\$ – rebelliard Jul 13 '16 at 4:30
  • 2
    \$\begingroup\$ Much shorter: lambda a,b,s=sorted:sum(x*y for x,y in zip(s(a)[::-1],s(b))). We don't require function submissions to be named (so an unnamed lambda is valid), and the n parameter is unnecessary (many other submissions omit it entirely). \$\endgroup\$ – Mego Jul 13 '16 at 5:40
1
\$\begingroup\$

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

At first i used std::greater<int>() for the sort in b but just reversing the order in the summation is easier.

\$\endgroup\$
1
\$\begingroup\$

Haskell, 59 bytes

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

RETURN, 29 bytes

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

Try it here.

Replace any ␆␃␄␇ with their unprintable counterparts.

Anonymous lambda that leaves result on stack2. Usage:

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

Explanation

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

J, 14 bytes

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

Uses the same principle as the others.

Explanation

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

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.