Producto escalar mínimo

16

Producto escalar mínimo

La inspiración para este problema de código de golf es de la competencia de código jam de Google . La premisa detrás del problema es, dada la entrada de dos vectores de diferentes longitudes, encontrar el escalar mínimo posible. Se puede encontrar un escalar usando la siguiente fórmula:

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

Sin embargo, el problema es que se pueden encontrar múltiples valores para el escalar dependiendo del orden de los números en el caso de entrada (visto a continuación). Su objetivo es determinar la mínima solución de entero escalar posible al conectar los números de caso de entrada en la ecuación y resolverla. Puede usar cada número en la entrada solo una vez, y debe usar todos los números.

Permítanme proporcionar un ejemplo con los siguientes vectores.

Entrada

3
1 3 -5
-2 4 1

Salida

-25

El primer número entero en la línea representa el número de números, n, en cada vector. En este caso, tenemos tres números en cada vector.

El número n puede variar con cada caso de prueba, pero siempre habrá dos vectores.

En la entrada de ejemplo, el producto escalar mínimo sería -25.

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

Reglas

  • Solo puede usar cada número entero en ambos vectores una vez.
  • Debe usar todos los enteros en los vectores.
  • Su salida solo debe incluir el producto final
  • ¡Seleccionaré la solución con la menor cantidad de código, que siga todas las especificaciones enumeradas anteriormente, en cualquier idioma!

Sugerencia: No necesita forzar este problema por fuerza bruta, a menos que acorte su código. Hay un método específico involucrado en encontrar el escalar mínimo de expansión :).

baseman101
fuente
Realmente no quiero estropear a nadie, así que no abras esto a menos que ya sepas la respuesta. Esto es tan conocido que es divertido. en.m.wikipedia.org/wiki/Rearrangement_inequality
orgulloso Haskeller

Respuestas:

8

Jalea, 6 bytes

ṢṚ×Ṣ}S

Pruébalo en línea!

Usar la fuerza bruta es igualmente corto:

Œ!×S€Ṃ

Cómo 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.
Dennis
fuente
5

APL, 15 bytes

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

Esta es una función diádica que acepta matrices a la izquierda y a la derecha y devuelve un entero. Utiliza el mismo enfoque que mi respuesta de Julia : producto de puntos de las matrices ordenadas, uno descendente y otro ascendente.

Pruébalo aquí

Alex A.
fuente
5

MATL , 6 bytes

Código:

SiSP*s

Mi primera respuesta MATL :)

Explicación:

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

Pruébalo en línea!

Adnan
fuente
1
¡Me alegra ver esto! :-)
Luis Mendo
4

Mathematica, 30 17 bytes

-13 bytes por murphy

Sort@#.-Sort@-#2&

Función, la entrada es vector1 (lista), vector2 (lista) Varias revisiones:

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*)
CalculadoraFeline
fuente
solución inteligente!
baseman101
2
Sort@#.Reverse@Sort@#2&
alephalpha
Sort@#.Sort[#2,#>#2&]&
Murphy
1
Sort@#.-Sort@-#2&
murphy
O para su solución 1,Sort@#.SortBy[#2,-#&]
CalculatorFeline
2

Julia, 32 25 bytes

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

Esta es una función anónima que acepta dos matrices y devuelve un entero. Para llamarlo, asignarlo a una variable y hacerf(x)(y) .

Para las entradas x e y , simplemente calculamos el producto de punto de x ordenado en orden inverso con y ordenado. Obtenemos x en orden inverso al negar todos los valores, ordenar y luego negar nuevamente.

¡Guardado 7 bytes gracias a Dennis!

Alex A.
fuente
2

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, esto es demasiado largo.

Mama Fun Roll
fuente
Creo que intentar reutilizar la función de clasificación le está costando 3 bytes.
Neil
Hice más golf. ¿Mejor?
Mama Fun Roll
Probablemente pueda guardar un byte en |ilugar de&&i
ETHproductions
Thx @ETHproductions
Mama Fun Roll
Sí, en eso estaba pensando.
Neil
2

Perl 6, 33 30 bytes

{sum @^a.sort Z*@^b.sort.reverse}
Teclas de acceso rápido
fuente
¿Por qué no{sum @^a.sort Z*[R,] @^b.sort}((1,3,-5),(-2,4,1)).say
Aleks-Daniel Jakimenko-A.
1

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
rebelde
fuente
1
Puede guardar algunos bytes eliminando espacios al lado de iguales, por ejemplo, se b = sorted(b)convierte en b=sorted(b)(2 bytes guardados). También puede poner varias declaraciones en la misma línea separándolas con un punto y coma, por ejemploa=list(reversed(sorted(a)));b=sorted(b);res=0
charredgrass
@charredgrass Soy nuevo aquí. ¿Cuál es la necesidad de guardar cada byte posible? Estaba tratando de hacerlo legible.
rebelde
Bienvenido a PPCG entonces! Esta pregunta es una competencia de código de golf donde el objetivo es escribir código para completar el desafío en la menor cantidad de bytes posible, lo que generalmente significa un código menos legible.
charredgrass
¡@charredgrass lo consiguió!
Rebelde
2
Mucho más corto: lambda a,b,s=sorted:sum(x*y for x,y in zip(s(a)[::-1],s(b))). No requerimos que se nombren los envíos de funciones (por lo que un lambda sin nombre es válido), y el nparámetro es innecesario (muchos otros envíos lo omiten por completo).
Mego
1

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

sin golf:

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

Al principio solía std::greater<int>()ordenar, bpero simplemente invertir el orden en la suma es más fácil.

Karl Napf
fuente
1

Haskell, 59 bytes

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

RETORNO , 29 bytes

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

Try it here.

Reemplace cualquier ␆␃␄␇ con sus contrapartes no imprimibles.

Lambda anónima que deja resultado en stack2. Uso:

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

Explicación

[                                 ]  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
Mama Fun Roll
fuente
0

J, 14 bytes

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

Utiliza el mismo principio que los demás.

Explicación

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