Produto Escalar Mínimo

A inspiração para esse problema do código de golfe é a competição do Google Code Jam . A premissa por trás do problema é que, dada a entrada de dois vetores de comprimentos variados, encontre o escalar mínimo possível. Um escalar pode ser encontrado usando a seguinte fórmula:

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

O problema, no entanto, é que vários valores para o escalar podem ser encontrados, dependendo da ordem dos números no caso de entrada (visto abaixo). Seu objetivo é determinar a solução mínima possível de número inteiro escalar, inserindo os números dos casos de entrada na equação e resolvendo-os. Você pode usar todos os números da entrada apenas uma vez e deve usar todos os números.

Permita-me fornecer um exemplo com os seguintes vetores.

Entrada

3
1 3 -5
-2 4 1

Resultado

-25

O primeiro número inteiro na linha representa o número de números, n, em cada vetor. Nesse caso, temos três números em cada vetor.

O número n pode variar com cada caso de teste, mas sempre haverá dois vetores.

Na entrada de exemplo, o produto escalar mínimo seria -25.

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

Regras

• Você só pode usar cada número inteiro nos dois vetores uma vez.
• Você deve usar todos os números inteiros nos vetores.
• Sua saída deve incluir apenas o produto final
• Selecionarei a solução com a menor quantidade de código, que segue todas as especificações listadas acima, em qualquer idioma!

Dica: você não precisa fazer força bruta nesse problema, a menos que ele reduza seu código. Existe um método específico envolvido na localização do escalar de abrangência mínimo :).

Gelatina, 6 bytes

ṢṚ×Ṣ}S

Experimente online!

Usar força bruta é igualmente curto:

Œ!×S€Ṃ

Como funciona

ṢṚ×Ṣ}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ério , 6 bytes

,SR,S*

Experimente online!

Explicação:

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

APL, 15 bytes

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

Essa é uma função diádica que aceita matrizes à esquerda e à direita e retorna um número inteiro. Ele usa a mesma abordagem da minha resposta Julia : produto pontilhado das matrizes classificadas, uma descendente e outra ascendente.

Experimente aqui

MATL , 6 bytes

Código:

SiSP*s

Minha primeira resposta MATL :)

Explicação:

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

Experimente online!

Mathematica, 30 17 bytes

-13 bytes por murphy

Sort@#.-Sort@-#2&

Função, entrada é vetor1 (lista), vetor2 (lista) Várias revisões:

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

Eu acho que descobri o truque.

s*VSQ_SE

Experimente online aqui .

Julia, 32 25 bytes

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

Esta é uma função anônima que aceita duas matrizes e retorna um número inteiro. Para chamá-lo, atribua-o a uma variável e façaf(x)(y) .

Para as entradas x e y , simplesmente calculamos o produto escalar de x classificado na ordem inversa com y classificado. Nós temos x na ordem inversa da classificação negando todos os valores, classificando e depois negando novamente.

Economizou 7 bytes graças a 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

Uau, isso é muito longo.

Perl 6, 33 30 bytes

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

CJam, 11 bytes

q~$\$W%.*:+

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

No começo, eu usei std::greater<int>()para classificar, bmas apenas reverter a ordem no somatório é mais fácil.

Haskell, 59 bytes

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

RETURN , 29 bytes

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

Try it here.

Substitua qualquer ␆␃␄␇ por seus equivalentes não imprimíveis.

Lambda anônima que deixa o resultado na pilha2. Uso:

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

Explicação

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

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

Usa o mesmo princípio que os outros.

Explicação

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