Tantangannya adalah untuk menemukan jumlah maksimum yang bisa Anda dapatkan dari daftar bilangan bulat menggunakan operator aritmatika dasar (penambahan, substraksi, perkalian, negasiasi unary)

Memasukkan

Daftar bilangan bulat

Keluaran

Hasil maksimal menggunakan setiap bilangan bulat dalam intput.

Urutan input tidak masalah, hasilnya harus sama.

Anda tidak perlu menampilkan operasi penuh, hanya hasilnya.

Contohnya

Input : 3 0 1
Output : 4 (3 + 1 + 0)

Input : 3 1 1 2 2
Output : 27 ((2+1)*(2+1)*3))

Input : -1 5 0 6
Output : 36 (6 * (5 - (-1)) +0)

Input : -10 -10 -10
Output : 1000 -((-10) * (-10) * (-10))

Input : 1 1 1 1 1
Output : 6 ((1+1+1)*(1+1))

Aturan

• Kode terpendek menang

• Berlaku "celah" standar

• Anda hanya dapat menggunakan + * - operator (penambahan, perkalian, substraksi, negasiasi unary)

• Kode harus berfungsi selama hasilnya dapat disimpan pada Integer 32 bit.

• Setiap perilaku overflow terserah Anda.

Saya harap ini cukup jelas, ini adalah saran tantangan Code Golf pertama saya.

C - 224 byte - Waktu berjalan O (n)

o=0,w=0,n[55],t,*m=n,*p=n;main(r){for(;scanf("%d",++p);t<3?--p,w+=t/2,o+=t&1:t<*m|m==n?m=p:9)t=*p=abs(*p);t=o<w?o:w;o-=t;w-=t;t+=o/3;for(o%3?o%3-2?t?t--,w+=2:++*m:w++:9;t--;)r*=3;for(r<<=w;--p>n;)r*=*p;printf("%d",r>1?r:o);}

Sangat lucu melihat hanya solusi waktu eksponensial untuk masalah waktu linear, tetapi saya kira itu adalah cara logis untuk melanjutkan karena tidak ada poin bonus untuk benar-benar memiliki algoritma, yang merupakan anagram logaritma.

Setelah mengonversi angka negatif ke angka positif dan nol, jelas kami lebih tertarik pada perkalian. Kami ingin memaksimalkan logaritma angka terakhir.

log (a + b) <log (a) + log (b) kecuali ketika a = 1 atau b = 1, jadi itu adalah satu-satunya kasus di mana kami tertarik untuk menambahkan sesuatu bersama-sama. Secara umum lebih baik menambahkan 1 ke angka yang lebih kecil, karena hal itu menyebabkan peningkatan logaritma yang lebih besar, yaitu peningkatan persentase yang lebih besar, daripada menambahkan 1 ke angka yang besar. Ada empat skenario yang mungkin, yang dipesan paling tidak disukai, untuk memanfaatkannya:

1. Menambahkan satu ke 2 memberi + log .405 [log (3) - log (2)]
2. Menggabungkan yang menjadi tiga menghasilkan + log .366 per satu [log (3) / 3]
3. Membuat 2 dari yang memberi + log .347 per satu [log (2) / 2]
4. Menambahkan satu ke nomor 3 atau lebih tinggi memberi + log .288 atau kurang [log (4) - log (3)]

Program ini melacak jumlah yang, jumlah dua, dan jumlah minimum lebih besar dari 2, dan mencatat daftar cara yang paling tidak disukai untuk menggunakan yang. Akhirnya, itu mengalikan semua angka yang tersisa.

Haskell, 126 karakter

ini hanya brute-forcing, dengan pengecualian mengabaikan tanda input dan mengabaikan pengurangan dan negasi unary.

import Data.List
f[x]=abs x::Int
f l=maximum$subsequences l\\[[],l]>>= \p->[f p+f(l\\p),f p*f(l\\p)]
main=interact$show.f.read

kode ini sangat lambat. kode menghitung f secara rekursi pada setiap urutan input empat kali _{(kecuali untuk [] dan input itu sendiri)} . tapi hei, ini kode golf.

SWI-Prolog - 250

Oh nak, aku menghabiskan terlalu lama untuk ini.

o(A,B,A+B).
o(A,B,A-B).
o(A,B,A*B).
t([],0).
t([A,B|T],D):-t(T,Q),o(A,B,C),o(C,Q,D).
t([A|T],C):-t(T,Q),o(A,Q,C).
a(A):-t(A,B),n(C),B>C,retract(n(C)),assert(n(B)).
m(A):-assert(n(0)),\+p(A),n(R),R2 is R,write(R2).
p(A):-permutation([0|A],B),a(B),0=1.

Dipanggil dari baris perintah (mis.):

> swipl -s filename.pl -g "m([1, 1, 1, 1, 1])" -t halt
6

(Tanpa alasan tertentu, saya merasa luar biasa karena fungsi golf saya menyebut "pot tomat.")

Versi tidak disatukan:

% Possible operations
operation(Left, Right, Left + Right).
operation(Left, Right, Left - Right).
operation(Left, Right, Left * Right).

% Possible ways to transform
transform([], 0).
transform([A, B|T], D) :- transform(T, Q), operation(A, B, C), operation(C, Q, D).
transform([A|T], C) :- transform(T, Q), operation(A, Q, C).

% Throw the given array through every possible transformation and update the max
all_transforms(A) :- transform(A, B), n(C), B>C, retract(n(C)), assert(n(B)).

% Find all the permutations and transformations, then fail and continue execution.
prog(A) :- assert(n(0)), !, permutation([0|A], B), all_transforms(B), fail.

% End the program
finished :- n(R), write(R), nl, R2 is R, write(R2), nl.

% Run the program
main(A) :- ignore(prog(A)), finished.

Penjelasan:

1. Ambil dalam array sebagai argumen.
2. Dapatkan semua permutasi dari array.
3. Temukan beberapa pengaturan operator untuk ditambahkan ke array. (Ini dilakukan melalui pemrograman dinamis, melihat apakah lebih baik jika kita menggabungkan dua elemen pertama atau tidak.)
4. Periksa ini dengan nilai maksimal kami saat ini. Jika lebih baik, ganti saja.
5. Beri tahu program kami gagal sehingga terus memeriksa, tetapi kemudian negasikan bahwa (menggunakan ignoreatau \+) untuk membiarkan predikat keseluruhan kembali truedan melanjutkan.
6. Kami diberi serangkaian predikat, bukan angka, jadi tetapkan menggunakan isdan kemudian tulis.

Scala, 134

print(args.map(Math abs _.toInt)./:(Seq(Array(0)))((l,a)=>l.map(a+:_)++l.flatMap(_.permutations.map{r=>r(0)+=a;r}))map(_.product)max)

Tidak dikoleksi & berkomentar:

print(
  args
    .map(Math abs _.toInt)                     // to int, ignoring -
    .foldLeft(Seq(Array(0))){ (list,num) =>    // build up a list of sums of numbers
      list.map(num+:_) ++                      // either add the new number to the list
      list.flatMap(_.permutations.map{ copy =>
        copy(0)+=num                           // or add it to one of the elements
        copy
      })
    }
    .map(_.product) // take the maximum of the the products-of-sums
    .max
)

Pendekatan yang sedikit berbeda, dari menyadari bahwa jawaban terbesar selalu dapat dinyatakan sebagai produk penjumlahan.

Begitu dekat, tetapi sekelompok kebodohan perpustakaan (permutasi mengembalikan Iterator bukannya Seq, inferensi tipe mengerikan pada urutan kosong, Array.update kembali Unit) lakukan saya.

Python 278 (O (n!))

from itertools import*
def f(n):
 f,n,m=lambda n:[(n,)]+[(x,)+y for x in range(1,n)for y in f(n-x)],map(abs,map(int,n.split())),0
 for p,j in product(permutations(n),f(len(n))):
  i=iter(p)
  m=max(m,reduce(lambda e,p:e*p,(sum(zip(*zip([0]*e,i))[1])for e in j)))
 return m

Penjelasan

1. Unary Negate harus digunakan secara bijaksana untuk mengubah semua angka negatif menjadi positif
2. Temukan semua kemungkinan permutasi angka
3. Menggunakan partisi Integer untuk menemukan semua set daya permutasi yang diberikan
4. Temukan produk penjumlahannya
5. Kembalikan maksimum produk dari jumlah

Haskell - 295 290 265 246 203 189 182 byte

Akhirnya berhasil! Juga sekarang ini adalah kekuatan kasar daripada solusi dinamis.

Terima kasih kepada proudhaskeller untuk beberapa tips bermain golf.

Ini mungkin bukan solusi yang sepenuhnya golf karena saya benar-benar payah dalam bermain golf, tetapi ini adalah yang terbaik yang bisa saya lakukan (dan itu terlihat rumit, jadi saya dapat hal itu untuk saya):

import Data.List
main=interact$show.g.read
g x=maximum[product$a#b|a<-sequence$replicate(length x-1)[0,1],b<-permutations x]
(a:b)#(c:d:e)|a>0=b#(c+d:e)|0<1=c:b#(d:e)
_#x=x

Kasus uji baru:

[1,1,1,2,2]
12

[1,1,3,3,3]
54

[1,1,1,1,1,1,1,1,5,3]
270

Penjelasan solusi:

The mainFungsi hanya mendapat masukan dan berjalan gdengan itu.

g mengambil input dan mengembalikan maksimal semua kemungkinan kombinasi jumlah dan daftar pesanan.

# adalah fungsi yang menghitung jumlah dalam daftar seperti ini:

a = [1,0,0,1]
b = [1,1,1,2,2]
a#b = [2,1,4]

GolfScript (52 karakter)

~]0-{abs}%.1-.1,or@,@,-,-1%{!\$.0=3<@+{()}1if+}/{*}*

Demo online

Analisis feersum cukup bagus tetapi bisa diambil lebih jauh jika tujuannya adalah bermain golf daripada efisiensi. Dalam pseudo-code:

filter zeros from input and replace negatives with their absolute value
filter ones to get A[]
count the ones removed to get C
while (C > 0) {
    sort A
    if (A[0] < 3 || C == 1) A[0]++
    else A.append(1)
    C--
}
fold a multiply over A