Produk Skalar Minimum

Inspirasi untuk masalah golf kode ini berasal dari kompetisi kode jam Google . Premis di balik masalah ini adalah, mengingat input dari dua vektor dengan panjang yang bervariasi, temukan skalar minimum yang mungkin. Skalar dapat ditemukan menggunakan rumus berikut:

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

Masalahnya, bagaimanapun, adalah bahwa beberapa nilai untuk skalar dapat ditemukan tergantung pada urutan angka dalam kasus input (lihat di bawah). Tujuan Anda adalah untuk menentukan solusi integer skalar minimum yang mungkin dengan memasukkan angka kasus input ke dalam persamaan dan menyelesaikannya. Anda dapat menggunakan setiap angka dalam input hanya sekali, dan harus menggunakan semua nomor.

Izinkan saya untuk memberikan contoh dengan vektor-vektor berikut.

Memasukkan

3
1 3 -5
-2 4 1

Keluaran

-25

Bilangan bulat pertama pada garis mewakili jumlah angka, n, dalam setiap vektor. Dalam hal ini, kami memiliki tiga angka di setiap vektor.

Angka n dapat bervariasi dengan setiap test case, tetapi akan selalu ada dua vektor.

Pada input contoh, produk skalar minimum adalah -25.

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

Aturan

• Anda hanya dapat menggunakan setiap bilangan bulat di kedua vektor satu kali.
• Anda harus menggunakan semua bilangan bulat di vektor.
• Output Anda hanya harus mencakup produk akhir
• Saya akan memilih solusinya dengan jumlah kode paling sedikit, yang mengikuti semua spesifikasi yang tercantum di atas, dalam bahasa apa pun!

Petunjuk: Anda tidak perlu memaksa masalah ini, kecuali jika itu membuat kode Anda lebih pendek. Ada metode khusus yang terlibat dalam menemukan skalar spanning minimum :).

Jelly, 6 byte

ṢṚ×Ṣ}S

Cobalah online!

Menggunakan brute force sama pendeknya:

Œ!×S€Ṃ

Bagaimana itu bekerja

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

Serius , 6 byte

,SR,S*

Cobalah online!

Penjelasan:

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

APL, 15 byte

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

Ini adalah fungsi diad yang menerima array di kiri dan kanan dan mengembalikan integer. Ia menggunakan pendekatan yang sama dengan jawaban Julia saya : produk titik dari array yang diurutkan, satu turun dan satu naik.

Coba di sini

MATL , 6 byte

Kode:

SiSP*s

Jawaban MATL pertama saya :)

Penjelasan:

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

Cobalah online!

Mathematica, 30 17 byte

-13 byte oleh murphy

Sort@#.-Sort@-#2&

Fungsi, input adalah vector1 (daftar), vector2 (daftar) Beberapa revisi:

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 byte

Saya pikir saya sudah tahu caranya.

s*VSQ_SE

Cobalah online di sini .

Julia, 32 25 byte

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

Ini adalah fungsi anonim yang menerima dua array dan mengembalikan integer. Untuk menyebutnya, tetapkan ke variabel dan lakukan f(x)(y).

Untuk input x dan y , kita cukup menghitung produk titik dari x diurutkan dalam urutan terbalik dengan y diurutkan. Kami mendapatkan x dalam urutan terbalik dengan meniadakan semua nilai, mengurutkan, lalu meniadakan lagi.

Disimpan 7 byte berkat Dennis!

Javascript ES6, 69 byte

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

Wow, ini terlalu lama.

Perl 6, 33 30 byte

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

CJam, 11 Bytes

q~$\$W%.*:+

Cobalah online!

Python, 139 byte

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 byte

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

Pada awalnya saya digunakan std::greater<int>()untuk menyortir btetapi hanya membalik urutan dalam penjumlahan lebih mudah.

Haskell, 59 byte

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

KEMBALI , 29 byte

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

Try it here.

Ganti apa saja ␆␃␄␇ dengan rekan-rekan mereka yang tidak diinginkan.

Lambda anonim yang meninggalkan hasil di stack2. Pemakaian:

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

Penjelasan

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

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

Menggunakan prinsip yang sama dengan yang lain.

Penjelasan

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