Die Herausforderung besteht darin, die maximale Anzahl, die Sie aus einer Liste von Ganzzahlen erhalten können, mithilfe von arithmetischen Grundoperatoren (Addition, Subtraktion, Multiplikation, unäre Negation) zu finden.

Eingang

Eine Liste von ganzen Zahlen

Ausgabe

Das maximale Ergebnis bei Verwendung jeder Ganzzahl in der Eingabe.

Die Eingabereihenfolge spielt keine Rolle, das Ergebnis sollte dasselbe sein.

Sie müssen nicht die gesamte Operation ausgeben, sondern nur das Ergebnis.

Beispiele

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

Regeln

• Kürzester Code gewinnt

• Standard "Schlupflöcher" gelten

• Sie dürfen nur + * - Operatoren verwenden (Addition, Multiplikation, Subtraktion, unäre Negation)

• Der Code sollte funktionieren, solange das Ergebnis auf einer 32-Bit-Ganzzahl gespeichert werden kann.

• Jedes Überlaufverhalten liegt bei Ihnen.

Ich hoffe das ist klar genug, dies ist mein erster Code Golf Challenge Vorschlag.

C - 224 Bytes - Laufzeit 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);}

Es war amüsant, nur Exponentialzeitlösungen für ein lineares Zeitproblem zu sehen, aber ich nehme an, es war die logische Vorgehensweise, da es keine Bonuspunkte gab, wenn man tatsächlich einen Algorithmus hatte, der ein Anagramm des Logarithmus ist.

Nachdem wir negative Zahlen in positive Zahlen umgewandelt und Nullen verworfen haben, sind wir offensichtlich hauptsächlich an der Multiplikation interessiert. Wir wollen den Logarithmus der endgültigen Zahl maximieren.

log (a + b) <log (a) + log (b), außer wenn a = 1 oder b = 1 ist. Nur in diesen Fällen möchten wir also etwas addieren. Im Allgemeinen ist es besser, eine 1 zu einer kleineren Zahl zu addieren, da dies zu einem größeren Anstieg des Logarithmus führt, dh zu einem größeren prozentualen Anstieg, als eine 1 zu einer großen Zahl zu addieren. Es gibt vier mögliche Szenarien, die für die Verwendung am besten geeignet sind:

1. Wenn man eins zu einer 2 addiert, erhält man + log .405 [log (3) - log (2)]
2. Die Kombination von Einsen zu Dreien ergibt + log .366 pro Einsen [log (3) / 3]
3. Aus Einsen eine 2 zu machen, ergibt + log .347 pro Einsen [log (2) / 2]
4. Addiert man eins zu einer Zahl von 3 oder höher, erhält man + log .288 oder weniger [log (4) - log (3)]

Das Programm verfolgt die Anzahl der Einsen, die Anzahl der Zweien und die Mindestanzahl von mehr als 2 und geht die Liste der am wenigsten bevorzugten Arten der Verwendung der Einsen durch. Schließlich multipliziert es alle verbleibenden Zahlen.

Haskell, 126 Zeichen

Dies ist nur brachial, mit der Ausnahme, dass das Vorzeichen der Eingabe ignoriert und Subtraktion und unäre Negation ignoriert werden.

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

Dieser Code ist extrem langsam. Der Code berechnet f viermal rekursiv für jede Untersequenz der Eingabe _{(mit Ausnahme von [] und der Eingabe selbst)} . aber hey, es ist Code Golf.

SWI-Prolog - 250

Oh Mann, ich habe viel zu lange damit verbracht.

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.

Aufgerufen von der Kommandozeile (zB):

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

(Ohne besonderen Grund fand ich es großartig, dass meine Namen für die Golf-Funktion "Tomatentopf" bedeuten.)

Ungolfed-Version:

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

Erläuterung:

1. Nehmen Sie ein Array als Argument.
2. Holen Sie sich alle Permutationen des Arrays.
3. Suchen Sie nach einer Anordnung von Operatoren, die dem Array hinzugefügt werden sollen. (Dies geschieht über dynamische Programmierung, um festzustellen, ob es besser ist, die ersten beiden Elemente zu kombinieren oder nicht.)
4. Überprüfen Sie dies anhand unseres aktuellen Maximalwerts. Wenn es besser ist, ersetzen Sie es.
5. Sagen Sie dem Programm, dass wir gescheitert sind, damit es weiter überprüft, aber negieren Sie das (mit ignoreoder \+), damit das Prädikat insgesamt zurückkehrt trueund fortfährt.
6. Statt einer Zahl erhalten wir eine Folge von Prädikaten. Weisen Sie sie also mit zu isund schreiben Sie sie dann.

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)

Ungolfed & kommentiert:

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
)

Ein etwas anderer Ansatz als die Erkenntnis, dass die größte Antwort immer als Produkt von Summen ausgedrückt werden kann.

So nah dran, aber eine Menge Dummheit in der Bibliothek (Permutationen liefern einen Iterator anstelle einer Seq, schreckliche Typinferenz auf leere Sequenzen, Array.update returning Unit) hat mich reingelegt.

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

Erläuterung

1. Unary Negate sollte mit Bedacht verwendet werden, um alle negativen Zahlen in positive umzuwandeln
2. Finde alle möglichen Permutationen der Zahlen
3. Verwenden der Ganzzahlpartition, um alle Potenzsätze einer bestimmten Permutation zu finden
4. Finden Sie das Produkt der Summen
5. Geben Sie das Maximum des Produkts der Summe zurück

Haskell - 295 290 265 246 203 189 182 Bytes

Endlich klappt es! Auch jetzt ist es eher eine rohe Kraft als eine dynamische Lösung.

Vielen Dank an proudhaskeller für einige der Golftipps.

Dies ist wahrscheinlich keine vollständige Golflösung, da ich eigentlich am Golfen scheiße bin, aber es ist das Beste, was ich mir einfallen lassen kann (und es sieht kompliziert aus, also habe ich das für mich in Ordnung gebracht):

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

Neue Testfälle:

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

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

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

Lösungserklärung:

Die mainFunktion bekommt nur eine Eingabe und läuft gdamit.

g Nimmt die Eingabe und gibt das Maximum aller möglichen Kombinationen von Summen und Listenreihenfolgen zurück.

# ist die Funktion, die die Summen in einer Liste wie folgt berechnet:

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

GolfScript (52 Zeichen)

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

Online-Demo

Die Analyse von feersum ist ziemlich gut, aber sie kann weiterentwickelt werden, wenn das Ziel eher Golf als Effizienz ist. Im Pseudocode:

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