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 :).
fuente
Respuestas:
Jalea, 6 bytes
Pruébalo en línea!
Usar la fuerza bruta es igualmente corto:
Cómo funciona
fuente
En serio , 6 bytes
Pruébalo en línea!
Explicación:
fuente
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í
fuente
MATL , 6 bytes
Código:
Mi primera respuesta MATL :)
Explicación:
Pruébalo en línea!
fuente
Mathematica,
3017 bytes-13 bytes por murphy
Función, la entrada es vector1 (lista), vector2 (lista) Varias revisiones:
fuente
Sort@#.Reverse@Sort@#2&
Sort@#.Sort[#2,#>#2&]&
Sort@#.-Sort@-#2&
Sort@#.SortBy[#2,-#&]
Pyth -
148 bytesCreo que descubrí el truco.
Pruébelo en línea aquí .
fuente
Julia,
3225 bytesEsta es una función anónima que acepta dos matrices y devuelve un entero. Para llamarlo, asignarlo a una variable y hacer
f(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!
fuente
Javascript ES6, 69 bytes
Wow, esto es demasiado largo.
fuente
|i
lugar de&&i
Perl 6,
3330 bytesfuente
{sum @^a.sort Z*[R,] @^b.sort}((1,3,-5),(-2,4,1)).say
CJam, 11 bytes
Pruébalo en línea!
fuente
Python, 139 bytes
fuente
b = sorted(b)
convierte enb=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
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 eln
parámetro es innecesario (muchos otros envíos lo omiten por completo).C ++, 124 bytes
sin golf:
Al principio solía
std::greater<int>()
ordenar,b
pero simplemente invertir el orden en la suma es más fácil.fuente
Haskell, 59 bytes
fuente
RETORNO , 29 bytes
Try it here.
Reemplace cualquier
␆␃␄␇
con sus contrapartes no imprimibles.Lambda anónima que deja resultado en stack2. Uso:
Explicación
fuente
J, 14 bytes
Utiliza el mismo principio que los demás.
Explicación
fuente