Минимальный скалярный продукт

Источником вдохновения для решения этой проблемы является гольф- конкурс Google . Причиной проблемы является, учитывая вход двух векторов различной длины, найти минимально возможный скаляр. Скаляр можно найти по следующей формуле:

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

Проблема, однако, заключается в том, что можно найти несколько значений для скаляра в зависимости от порядка чисел во входном регистре (см. Ниже). Ваша цель состоит в том, чтобы определить минимально возможное скалярное целочисленное решение, вставив входные числа наблюдений в уравнение и найдя для него решение. Вы можете использовать каждое число на входе только один раз, и должны использовать все числа.

Позвольте мне привести пример со следующими векторами.

вход

3
1 3 -5
-2 4 1

Выход

-25

Первое целое число в строке представляет количество чисел n в каждом векторе. В этом случае у нас есть три числа в каждом векторе.

Число n может варьироваться в зависимости от каждого теста, но всегда будет два вектора.

В приведенном примере минимальное скалярное произведение будет равно -25.

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

правила

• Вы можете использовать каждое целое число в обоих векторах только один раз.
• Вы должны использовать все целые числа в векторах.
• Ваш вывод должен включать только конечный продукт
• Я выберу решение с наименьшим количеством кода, которое соответствует всем перечисленным выше спецификациям, на любом языке!

Подсказка: вам не нужно грубо форсировать эту проблему, если она не делает ваш код короче. Существует определенный метод поиска минимального охватывающего скаляра :).

Желе, 6 байт

ṢṚ×Ṣ}S

Попробуйте онлайн!

Использование грубой силы одинаково коротко:

Œ!×S€Ṃ

Как это устроено

ṢṚ×Ṣ}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.

Серьезно , 6 байт

,SR,S*

Попробуйте онлайн!

Объяснение:

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

APL, 15 байт

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

Это двоичная функция, которая принимает массивы слева и справа и возвращает целое число. Он использует тот же подход, что и мой ответ Джулии : скалярное произведение отсортированных массивов, одного по убыванию и одного по возрастанию.

Попробуй здесь

MATL , 6 байтов

Код:

SiSP*s

Мой первый ответ MATL :)

Объяснение:

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

Попробуйте онлайн!

Mathematica, 30 17 байт

-13 байтов от Murphy

Sort@#.-Sort@-#2&

Функция, input это vector1 (список), vector2 (список) Несколько ревизий:

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 байт

Я думаю, я понял трюк.

s*VSQ_SE

Попробуйте это онлайн здесь .

Юлия, 32 25 байт

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

Это анонимная функция, которая принимает два массива и возвращает целое число. Чтобы вызвать его, назначьте его переменной и выполните f(x)(y).

Для входов x и y мы просто вычисляем скалярное произведение x, отсортированное в обратном порядке по y . Мы получаем x в обратном порядке, отрицая все значения, сортируя и снова отрицая.

Сэкономили 7 байт благодаря Денису!

Javascript ES6, 69 байт

a=>b=>a.sort((x,y)=>x-y).map((x,y)=>i+=b.sort((x,y)=>y-x)[y]*x,i=0)|i

Вау, это слишком долго.

Perl 6, 33 30 байт

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

CJam, 11 байт

q~$\$W%.*:+

Попробуйте онлайн!

Python, 139 байт

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 байта

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

Сначала я использовал std::greater<int>()для сортировки, bно проще поменять порядок в суммировании.

Haskell, 59 байт

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

ВОЗВРАТ , 29 байт

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

Try it here.

Заменить любой ␆␃␄␇ их непечатными копиями.

Анонимная лямбда, которая оставляет результат на stack2. Использование:

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

объяснение

[                                 ]  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 байт

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

Использует тот же принцип, что и другие.

объяснение

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