12
\$\begingroup\$

Introduction

Our goal is to efficiently find the maximum of a large amount of (redundant) data.

We define the outer product of vectors \$A\$ and \$B\$ as a matrix containing the products of all entries of \$A\$ with each entry of \$B\$. (see outer Product)

$$ A\otimes B := A\cdot B^T = \left(\begin{array}{rrr} A(1)\cdot B(1) & A(1)\cdot B(2) & \ldots & A(1)\cdot B(M)\\ A(2)\cdot B(1) & A(2)\cdot B(2) & \ldots & A(2)\cdot B(M)\\ \ldots & & & \ldots \\ A(N)\cdot B(1) & A(N)\cdot B(2) & \ldots & A(N)\cdot B(M)\\ \end{array}\right) $$

Here \$A\$ has \$N\$ entries (size \$N\$) and \$B\$ has \$M\$ entries.

In this way, the outer product of \$K\$ vectors yields a \$K\$-dimensional array (tensor of order \$K\$). If \$N_1,N_2,\ldots,N_K\$ are the sizes of the vectors, we get a total of \$N_1\cdot N_2\cdot\ldots\cdot N_K\$ products.

Example: $$ \left(\begin{array}{r}1\\ 2\\ 0\end{array}\right)\otimes \left(\begin{array}{r}1\\ 3\end{array}\right)\otimes \left(\begin{array}{r}-5\\ 7\end{array}\right)= \left(\begin{array}{rr|rr|rr}-5 & 7 & -10 & 14 & 0 & 0\\ -15 & 21 & -30 & 42 & 0 & 0\end{array}\right) $$

The result is a \$3\$-dimensional array consisting of three \$2\times2\$ slices. We want to determine the maximum of the array, which is \$42\$ here.
An alternative formulation is: Find the maximum of all products that contain exactly one number from each vector.

Of course, we can do all the multiplications and keep track of the maximum. However, it is possible to use only a number of operations that depends linearly on the length of the input sequence (total number of vector entries). This means that we can, for example, process an input of \$13\$ vectors each of size \$37\$ in less than one second on a common computer.
Thus, the problem reads:

Challenge

  • "Determine the maximum of the outer product of given integer-valued vectors. Ensure that the algorithm runs in linear time with respect to the length of the input sequence."
  • The input contains at least one vector.
  • This is , so shortest answer in bytes wins!

Test cases

We leave the input format to the free decision. In the test cases we use \$,\$ to separate vector entries and \$;\$ to separate vectors. So the example above is coded as: \$\quad 1,2,0;1,3;-5,7\$

  • \$0,1,2\qquad ->\qquad 2\$
  • \$-2,-1,-2;1,2,3;-1,-2\qquad ->\qquad 12\$
  • \$-2,-1;-3,-4;-3,2,1;1,4,-4\qquad ->\qquad 96\$
  • \$-1,-2;3,4\qquad ->\qquad -3\$
  • \$-1,-2;1,-3,2;1,-1,-2\qquad ->\qquad 8\$
  • \$1,0,-2;0,-2,1;-2,1,0;-2,0,1;0,1,-2;1,-2,0;1,0,-2;0,-2,1;-2,1,0;-2,0,1;0,1,-2;1,-2,0;1,0,-2;0,-2,1;-2,1,0;-2,0,1;0,1,-2;1,-2,0;1,0,-2;0,-2,1;-2,1,0;-2,0,1;0,1,-2;1,-2,0;1,0,-2;0,-2,1;-2,1,0;-2,0,1;0,1,-2;1,-2,0;1,-2,0;1,0,1\qquad ->\qquad 1073741824\$
\$\endgroup\$
1
  • \$\begingroup\$ Welcome to PPCG :) \$\endgroup\$
    – l4m2
    Jan 3, 2023 at 16:30

10 Answers 10

9
\$\begingroup\$

JavaScript (Node.js), 84 bytes

f=([a,...x],m=1,n=1)=>a?f(x,Math.min(...q=a.flatMap(c=>[c*m,c*n])),Math.max(...q)):n

Try it online!

Keep trace of min and max

\$\endgroup\$
6
\$\begingroup\$

Jelly, 12 10 bytes

Ṃ,ṀƊ×þFɗ/Ṁ

Try it online!

-2 from using Ɗ and ɗ for grouping instead of separate lines

This submission is a monadic link. For input, use a list of the vectors (i.e. [[1,2,0],[1,3],[-5,7]]) as the first argument. This assumes [] is not valid input.

This is similar to @l4m2's algorithm, but it starts with the first vector instead of (1, 1).

Explanation:

This works by taking the (min, max) of the first vector and finding all products of either with elements of the second vector. The same thing happens with the result and the third vector, then that result and the fourth, etc. Then, the answer is the max of the last result.

Ṃ,ṀƊ×þFɗ/Ṁ
Ṃ          # List Minimum
 ,         # Pair
  Ṁ        # List Maximum
   Ɗ       # Group the last 3 links ("Ṃ", ",", and "Ṁ") as a monad
    ×þ     # Outer product
      F    # Flatten
       ɗ   # Group the last 3 links ("Ṃ,ṀƊ", "×þ", and "F") as a dyad
        /  # Reduce
         Ṁ # List Maximum

This is my first time using Jelly, so there is probably still room for further golfing.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ By using grouping quicks, you can get this down to 10 bytes \$\endgroup\$
    – emanresu A
    Jan 4, 2023 at 8:49
  • 2
    \$\begingroup\$ (Did you figure that out just as I posted the comment? lol) \$\endgroup\$
    – emanresu A
    Jan 4, 2023 at 8:50
  • 3
    \$\begingroup\$ Yeah, looks like we somehow posted nearly the same change within seconds of each other lol \$\endgroup\$ Jan 4, 2023 at 8:53
  • 1
    \$\begingroup\$ If I'm reading the challenge right, this isn't allowed due to the linear complexity restriction, but if there weren't a complexity restriction (or it was just with respect to the number of vectors), Ṣ.ị could replace Ṃ,ṀƊ for 9 bytes. Welcome to Jelly! \$\endgroup\$ Jan 5, 2023 at 9:27
4
\$\begingroup\$

Wolfram Language (Mathematica), 29 bytes

Max@*Fold[{#2Min@#,#2Max@#}&]

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Python 3.8 (pre-release), 85 bytes

Port of @l4m2's JavaScript answer

f=lambda x,y=1,z=1:x and f(x[1:],min(q:=sum(([c*y,c*z]for c in x[0]),[])),max(q))or z

Try it online!

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 11 10 bytes

1$vsß‚yδ*Z

Port of @EvanBailey's Jelly answer, which in turn uses the same approach as @l4m2's Javascript answer, so make sure to upvote both of them as well!

Input as a list of lists.

Try it online or verify all test cases (with brute-force verify .»â€˜Pà in the footer for the smaller test cases).

Explanation:

1           # Push 1
 $          # Push another 1, and the input-list
  v         # Pop the input-list, and loop over each inner list `y`:
   s        #  Swap so the current list is at the top
            #  (or simply swap the two 1s on the stack in the very first iteration)
    ß       #  Pop and push the minimum (1 remains 1)
     ‚      #  Pair the top two values together
            #  ([1,1] in the first iteration; [max,min] in every other iteration)
       δ    #  Apply double-vectorized
      y     #  on this pair and list `y`:
        *   #   Multiply
         Z  #  Push the flattened maximum (without popping the list of lists)
            # (after the loop, the final flattened maximum that's on top of the stack is
            # output implicitly as result)

It runs in \$O(\sum L)\$, where \$L\$ is the length of each individual list.

In term of iterations, it'll do \$\sum(6L)-2L_n\$, where \$6\$ comes from \$2\$ (for \$[min,max]\$) times \$3\$ (once for the double-vectorized to create the list; and then once each to retrieve the flattened maximum and minimum of this list of lists); minus \$2\$ times the length of the last list \$L_n\$, since we won't retrieve its minimum. E.g. input [[1,2,0],[1,3],[-5,7]] has \$6\times3+6\times2+6\times2-2\times2=38\$ iterations and an input of \$13\$ lists of size \$37\$ each has \$13\times6\times37-2\times37=2812\$ iterations.

\$\endgroup\$
7
  • 2
    \$\begingroup\$ Thx for the 13 37-vectors ! \$\endgroup\$
    – Sebastian
    Jan 4, 2023 at 12:58
  • \$\begingroup\$ I'm slightly confused about where the K× comes from in your time complexity. Isn't each iteration linear in the length of the two relevant vectors, meaning the whole thing is linear in $\sum A_n$? \$\endgroup\$ Jan 4, 2023 at 22:33
  • 1
    \$\begingroup\$ @KevinCruijssen Correct me if I'm wrong, but in the example of 13 size-37 lists, wouldn't each vector take 74 steps to construct the double-vectorized product (since it has length 2*37=74), 74 steps to calculate the maximum, and possibly 74 steps to calculate the minimum for a total of only 222 steps per iteration or 2,886 overall? \$\endgroup\$ Jan 5, 2023 at 8:38
  • 2
    \$\begingroup\$ Yes, in \$\mathcal{O}\$-notation additive and multiplicative constants are ignored. The number of operations has to be in \$c+a\sum A_n\$ for some constant \$a,c\$. \$\endgroup\$
    – Sebastian
    Jan 5, 2023 at 11:57
  • 1
    \$\begingroup\$ @Sebastian & EvanBailey, thanks for the clarifications! I've edited the O-complexity mentioned in my answer, and also TIL for next time. :) \$\endgroup\$ Jan 5, 2023 at 13:57
2
\$\begingroup\$

Charcoal, 19 bytes

⊞υ¹FA≔⁺×ι⌊υ×ι⌈υυI⌈υ

Try it online! Link is to verbose version of code. Explanation: Another port of @l4m2's algorithm.

⊞υ¹

Start with a minimum and maximum of 1.

FA

Loop over the input vectors.

≔⁺×ι⌊υ×ι⌈υυ

Multiply the current vector by both the minimum and maximum so far.

I⌈υ

Output the final maximum.

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

Haskell, 80 bytes

r a=[minimum a,maximum a]
f=last.foldl1(\a b->r$map product$sequence[a,b]).map r

Try it online!

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

Haskell, 50 bytes

m.foldl1(\x->((*)<$>[minimum x,m x]<*>))
m=maximum

Attempt This Online!

-2 bytes thanks to @ Unrelated String.

A port of my Mathematica answer.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ m=maximum seems to save 2 bytes. \$\endgroup\$ Jan 5, 2023 at 9:30
2
\$\begingroup\$

Vyxal 14 11 bytes

?ƒλ₍gGẊvΠ;G

Try it online!

Any improves welcome! For input needs always list of vectors,
so first test case should be [[0,1,2]]

Explanation

?      # Get input
ƒ      # Begin reduce list of vectors by lambda
λ      # Open lambda
₍gG    # [min, max] of current vector
Ẋ      # Cartesian product with previous vector
vΠ     # Vectorised product
;G     # Close lambda and print total max
\$\endgroup\$
1
\$\begingroup\$

R, 42 bytes

function(L)max(Reduce(`%o%`,Map(range,L)))

Try it online!

Using outer instead of '%o%' is equivalent. Fortunately, range returns a vector of c(min,max) instead of max - min as you might otherwise expect. Based, as many others, on l4m2's answer

Also, random note, range automatically flattens lists.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.