Le défi est de trouver le nombre maximum que vous pouvez obtenir à partir d'une liste d'entiers à l'aide d'opérateurs arithmétiques de base (addition, soustraction, multiplication, négation unaire)

Contribution

Une liste d'entiers

Production

Le résultat maximum en utilisant chaque entier dans l'entrée.

L'ordre d'entrée n'a pas d'importance, le résultat doit être le même.

Vous n'avez pas besoin de sortir l'opération complète, juste le résultat.

Exemples

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

Règles

• Victoires de code les plus courtes

• Des «failles» standard s'appliquent

• Vous ne pouvez utiliser que les opérateurs + * - (addition, multiplication, soustraction, négation unaire)

• Le code doit fonctionner tant que le résultat peut être stocké sur un entier 32 bits.

• Tout comportement de débordement dépend de vous.

J'espère que c'est assez clair, c'est ma première suggestion de défi Code Golf.

C - 224 octets - Temps d'exécution 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);}

C'était amusant de ne voir que des solutions de temps exponentiel pour un problème de temps linéaire, mais je suppose que c'était la façon logique de procéder car il n'y avait pas de points bonus pour avoir réellement un algorithme, qui est une anagramme de logarithme.

Après avoir converti les nombres négatifs en zéros positifs et en éliminant les zéros, nous sommes clairement principalement intéressés par la multiplication. Nous voulons maximiser le logarithme du nombre final.

log (a + b) <log (a) + log (b) sauf quand a = 1 ou b = 1, donc ceux-ci sont le seul cas où nous sommes intéressés à ajouter quelque chose ensemble. En général, il est préférable d'ajouter un 1 à un plus petit nombre, car cela provoque une augmentation plus importante du logarithme, c'est-à-dire une augmentation en pourcentage plus importante, que d'ajouter 1 à un grand nombre. Il y a quatre scénarios possibles, classés du moins au moins préférables, pour en utiliser:

1. Ajouter un à un 2 donne + log .405 [log (3) - log (2)]
2. La combinaison de trois en trois donne + log .366 par un [log (3) / 3]
3. Faire 2 unités donne + log .347 par un [log (2) / 2]
4. Ajouter un à un nombre 3 ou supérieur donne + log .288 ou moins [log (4) - log (3)]

Le programme enregistre le nombre de uns, le nombre de deux et le nombre minimum supérieur à 2, et descend la liste des moyens les plus préférables d'utiliser ceux-ci. Enfin, il multiplie tous les nombres restants.

Haskell, 126 caractères

c'est juste un forçage brut, à l'exception d'ignorer le signe de l'entrée et d'ignorer la soustraction et la négation unaire.

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

ce code est extrêmement lent. le code calcule récursivement f sur chaque sous-séquence de l'entrée quatre fois _{(sauf pour [] et l'entrée elle-même)} . mais bon, c'est du golf de code.

SWI-Prolog - 250

Oh mon garçon, j'ai passé trop de temps là-dessus.

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.

Appelé à partir de la ligne de commande (par exemple):

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

(Pour aucune raison particulière, j'ai trouvé génial que mes noms de fonction golfés épellent "pot de tomate".)

Version non golfée:

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

Explication:

1. Prenez un tableau comme argument.
2. Obtenez toutes les permutations du tableau.
3. Trouvez un arrangement d'opérateurs à ajouter au tableau. (Cela se fait via une programmation dynamique, pour voir s'il est préférable de combiner ou non les deux premiers éléments.)
4. Vérifiez cela par rapport à notre valeur maximale actuelle. Si c'est mieux, remplacez-le.
5. Dites au programme que nous avons échoué afin qu'il continue de vérifier, puis annulez cela (en utilisant ignoreou \+) pour laisser le retour global du prédicat trueet continuer.
6. On nous donne une chaîne de prédicats, au lieu d'un nombre, alors affectez-la en utilisant ispuis écrivez-la.

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)

Non golfé et commenté:

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
)

Une approche légèrement différente, de se rendre compte que la plus grande réponse peut toujours être exprimée comme un produit de sommes.

Si proche, mais un tas de stupidité de bibliothèque (permutations renvoie un Iterator au lieu d'une inférence de type Seq, horrible sur des séquences vides, Array.update retournant Unit) m'a fait entrer.

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

Explication

1. Unary Negate doit être judicieusement utilisé pour convertir tous les nombres négatifs en positifs
2. Trouver toutes les permutations possibles des nombres
3. Utilisation de la partition Integer pour trouver tous les jeux de puissance d'une permutation donnée
4. Trouver le produit des sommes
5. Renvoyer le maximum du produit des sommes

Haskell - 295290265246203189182182 octets

Fonctionne enfin! C'est aussi maintenant une force brute plutôt qu'une solution dynamique.

Merci à proudhaskeller pour certains des conseils de golf.

Ce n'est probablement pas une solution entièrement jouée au golf parce que j'aime vraiment jouer au golf, mais c'est le mieux que je puisse trouver (et cela semble compliqué, donc j'ai compris cela pour moi):

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

Nouveaux cas de test:

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

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

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

Explication de la solution:

La mainfonction obtient juste une entrée et s'exécute gavec elle.

g prend l'entrée et renvoie le maximum de toutes les combinaisons possibles de sommes et d'ordres de liste.

# est la fonction qui calcule les sommes dans une liste comme celle-ci:

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

GolfScript (52 caractères)

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

Démo en ligne

L'analyse de feersum est assez bonne, mais elle peut être poussée plus loin si l'objectif est le golf plutôt que l'efficacité. En 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