Wyzwanie polega na znalezieniu maksymalnej liczby, jaką można uzyskać z listy liczb całkowitych za pomocą podstawowych operatorów arytmetycznych (dodawanie, odejmowanie, mnożenie, jednoznaczna negacja)

Wejście

Lista liczb całkowitych

Wynik

Maksymalny wynik przy użyciu każdej liczby całkowitej w wartości wejściowej.

Kolejność wprowadzania nie ma znaczenia, wynik powinien być taki sam.

Nie musisz generować pełnej operacji, tylko wynik.

Przykłady

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))

Zasady

• Najkrótszy kod wygrywa

• Standard „luki” stosuje się

• Możesz używać tylko operatorów + * - (dodawanie, mnożenie, odejmowanie, jednoargumentowe negowanie)

• Kod powinien działać, dopóki wynik może być przechowywany na 32-bitowej liczbie całkowitej.

• Każde przepełnienie należy do Ciebie.

Mam nadzieję, że jest to wystarczająco jasne, to moja pierwsza propozycja wyzwania Code Golf.

C - 224 bajty - Czas działania 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);}

Zabawnie było widzieć tylko rozwiązania czasu wykładniczego dla problemu z czasem liniowym, ale przypuszczam, że był to logiczny sposób postępowania, ponieważ nie było żadnych punktów premiowych za posiadanie algorytmu, który jest anagramem logarytmu.

Po przekonwertowaniu liczb ujemnych na dodatnie i odrzuceniu zer, najwyraźniej najbardziej interesuje nas mnożenie. Chcemy zmaksymalizować logarytm ostatecznej liczby.

log (a + b) <log (a) + log (b) z wyjątkiem sytuacji, gdy a = 1 lub b = 1, więc są to jedyne przypadki, w których jesteśmy zainteresowani dodaniem czegoś razem. Ogólnie lepiej jest dodać 1 do mniejszej liczby, ponieważ powoduje to większy wzrost logarytmu, tj. Większy procentowy wzrost, niż dodanie 1 do dużej liczby. Istnieją cztery możliwe scenariusze, od najbardziej uporządkowanych do najmniej preferowanych, do wykorzystania:

1. Dodanie jednego do 2 daje + log .405 [log (3) - log (2)]
2. Łączenie ich w trójki daje + log .366 na jeden [log (3) / 3]
3. Wykonanie 2 z nich daje + log .347 na jeden [log (2) / 2]
4. Dodanie jednego do liczby 3 lub wyższej daje + log .288 lub mniej [log (4) - log (3)]

Program śledzi liczbę jedynek, liczbę dwójek i minimalną liczbę większą niż 2, i przewija listę najbardziej lub najmniej preferowanych sposobów korzystania z nich. Na koniec mnoży wszystkie pozostałe liczby.

Haskell, 126 znaków

jest to po prostu brutalne wymuszanie, z wyjątkiem ignorowania znaku wejścia i ignorowania odejmowania i jednoznacznej negacji.

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

ten kod jest bardzo wolny. kod rekurencyjnie oblicza f dla każdego podsekwencji wejścia cztery razy _{(z wyjątkiem [] i samego wejścia)} . ale hej, to jest golf golfowy.

SWI-Prolog - 250

O rany, spędziłem na tym zdecydowanie za dużo czasu.

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.

Wywoływany z wiersza poleceń (np.):

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

(Bez szczególnego powodu uważam, że to niesamowite, że nazwa mojej gry w golfa oznacza „garnek pomidorowy”).

Wersja bez golfa:

% 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.

Wyjaśnienie:

1. Weź tablicę jako argument.
2. Uzyskaj wszystkie permutacje tablicy.
3. Znajdź układ operatorów do dodania do tablicy. (Odbywa się to za pomocą programowania dynamicznego, sprawdzając, czy lepiej, jeśli połączymy pierwsze dwa elementy, czy nie.)
4. Sprawdź to w porównaniu z naszą bieżącą wartością maksymalną. Jeśli jest lepiej, wymień go.
5. Poinformuj program, że nie powiodło się, aby nadal sprawdzał, ale następnie zaprzeczaj temu (używając ignorelub \+), aby predykat mógł wrócić truei kontynuować.
6. Dostajemy ciąg predykatów zamiast liczby, więc przypisz je za pomocą, isa następnie napisz.

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)

Niegolfowane i komentowane:

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
)

Nieco inne podejście, niż uświadomienie sobie, że największa odpowiedź zawsze może być wyrażona jako iloczyn sum.

Tak blisko, ale doszło do mnie głupota biblioteki (permutacje zwracają Iterator zamiast Seq, okropne wnioskowanie o pustych sekwencjach, Array.update zwracające Unit).

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

Wyjaśnienie

1. Unary Negate należy rozsądnie wykorzystać do konwersji wszystkich liczb ujemnych na dodatnie
2. Znajdź wszystkie możliwe kombinacje liczb
3. Użycie partycji całkowitej do znalezienia wszystkich zestawów mocy o danej permutacji
4. Znajdź iloczyn sum
5. Zwraca maksimum iloczynu sum

Haskell - 295 290 265 246 203 189 182 bajtów

Wreszcie działa! Również teraz jest to brutalna siła, a nie dynamiczne rozwiązanie.

Podziękowania dla dumnego skarbu za niektóre wskazówki dotyczące gry w golfa.

Prawdopodobnie nie jest to w pełni golfowe rozwiązanie, ponieważ tak naprawdę jestem do bani w golfa, ale jest to najlepsze, co mogę wymyślić (i wygląda na skomplikowane, więc mam to za sobą):

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

Nowe przypadki testowe:

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

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

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

Objaśnienie rozwiązania:

mainFunkcja po prostu staje się wejście i prowadzi gz nim.

g pobiera dane wejściowe i zwraca maksimum wszystkich możliwych kombinacji sum i kolejności list.

# jest funkcją, która oblicza sumy na takiej liście:

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

GolfScript (52 znaki)

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

Demo online

analiza feersum jest całkiem dobra, ale można ją posunąć dalej, jeśli celem jest golf, a nie wydajność. W pseudokodzie:

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