Encuentra la operación máxima

12

El desafío es encontrar el número máximo que puede obtener de una lista de enteros utilizando operadores aritméticos básicos (suma, resta, multiplicación, negación unaria)

Entrada

Una lista de enteros

Salida

El resultado máximo con cada número entero en la entrada.

El orden de entrada no importa, el resultado debe ser el mismo.

No necesita generar la operación completa, solo el resultado.

Ejemplos

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

Reglas

  • El código más corto gana

  • Se aplican "lagunas" estándar

  • Solo puede usar operadores + * - (suma, multiplicación, sustracción, negación unaria)

  • El código debería funcionar siempre que el resultado se pueda almacenar en un entero de 32 bits.

  • Cualquier comportamiento de desbordamiento depende de usted.

Espero que esto sea suficientemente claro, esta es mi primera sugerencia de desafío de Code Golf.

CNicolas
fuente
Uno de sus ejemplos es utilizar una operación que no está permitida: si se pretende que la negación unaria esté en su lista blanca, entonces la resta no es realmente necesaria.
Peter Taylor
Negación unaria editada y agregada. La resta se mantiene en la lista blanca.
CNicolas
1
¿Tiene que ser un programa completo o es una función suficiente?
ThreeFx
Programa completo Aún mejor si se puede ejecutar en línea, pero obviamente no es obligatorio
CNicolas
@INSeed ¿Debo agregar una forma de ejecutar en línea?
orgulloso Haskeller

Respuestas:

9

C - 224 bytes - Tiempo de ejecución 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);}

Fue divertido ver solo soluciones de tiempo exponencial para un problema de tiempo lineal, pero supongo que era la forma lógica de proceder ya que no había puntos de bonificación por tener un algoritmo, que es un anagrama de logaritmo.

Después de convertir números negativos a positivos y descartar ceros, claramente estamos interesados ​​principalmente en la multiplicación. Queremos maximizar el logaritmo del número final.

log (a + b) <log (a) + log (b) excepto cuando a = 1 o b = 1, por lo que unos son el único caso en el que estamos interesados ​​en agregar algo juntos. En general, es mejor agregar un 1 a un número más pequeño, porque eso causa un mayor aumento en el logaritmo, es decir, un aumento porcentual mayor, que sumar 1 a un número grande. Existen cuatro escenarios posibles, ordenados de mayor a menor preferencia, para utilizarlos:

  1. Agregar uno a 2 da + log .405 [log (3) - log (2)]
  2. La combinación de unos en tres da + log .366 por uno [log (3) / 3]
  3. Hacer un 2 de unos da + log .347 por uno [log (2) / 2]
  4. Agregar uno a un número 3 o superior da + log .288 o menos [log (4) - log (3)]

El programa realiza un seguimiento de la cantidad de unidades, la cantidad de dos y la cantidad mínima mayor que 2, y baja por la lista de las formas más preferibles de utilizarlas. Finalmente, multiplica todos los números restantes.

Feersum
fuente
6

Haskell, 126 caracteres

esto es solo fuerza bruta, con la excepción de ignorar el signo de la entrada e ignorar la resta y la negación unaria.

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

Este código es extremadamente lento. el código calcula recursivamente f en cada subsecuencia de la entrada cuatro veces (excepto [] y la entrada en sí) . pero bueno, es código golf.

orgulloso Haskeller
fuente
5

SWI-Prolog - 250

Oh chico, pasé demasiado tiempo en esto.

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.

Llamado desde la línea de comando (por ejemplo):

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

(Sin ninguna razón en particular, me pareció increíble que los nombres de mis funciones de golf deletrearan "maceta de tomate").

Versión sin golf:

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

Explicación:

  1. Toma una matriz como argumento.
  2. Obtenga todas las permutaciones de la matriz.
  3. Encuentre algún arreglo de operadores para agregar a la matriz. (Esto se realiza mediante programación dinámica, para ver si es mejor si combinamos los dos primeros elementos o no).
  4. Comprueba esto con nuestro valor máximo actual. Si es mejor, reemplácelo.
  5. Dígale al programa que fallamos para que siga comprobando, pero luego niegue eso (usando ignoreo \+) para permitir que el predicado en general regrese truey continúe.
  6. Se nos da una cadena de predicados, en lugar de un número, así que asígnela usando isy luego escríbala.
Eric
fuente
4

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 y comentó:

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
)

Un enfoque ligeramente diferente, al darse cuenta de que la respuesta más grande siempre se puede expresar como un producto de sumas.

Tan cerca, pero un montón de estupidez de biblioteca (permutaciones devuelve un iterador en lugar de una inferencia de tipo Seq, horrible en secuencias vacías, Array.update return Unit) me hizo entrar.

paradigma
fuente
3

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

Explicación

  1. Unary Negate debe usarse juiciosamente para convertir todos los números negativos a positivos
  2. Encuentra todas las permutaciones posibles de los números
  3. Uso de la partición entera para encontrar todos los conjuntos de potencia de una permutación dada
  4. Encuentra el producto de las sumas
  5. Devuelve el máximo del producto de las sumas.
Abhijit
fuente
3

Haskell - 295 290 265 246 203 189 182 bytes


Finalmente funciona! También ahora es una fuerza bruta en lugar de una solución dinámica.


Gracias a proudhaskeller por algunos de los consejos de golf.

Probablemente esta no sea una solución completa para el golf porque en realidad soy un asco en el golf, pero es lo mejor que puedo encontrar (y parece complicado, así que lo conseguí):

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

Nuevos casos de prueba:

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

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

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

Explicación de la solución:

La mainfunción solo recibe una entrada y se ejecuta gcon ella.

g toma la entrada y devuelve el máximo de todas las combinaciones posibles de sumas y órdenes de lista.

# es la función que calcula las sumas en una lista como esta:

a = [1,0,0,1]
b = [1,1,1,2,2]
a#b = [2,1,4]
ThreeFx
fuente
Esto parece una solución basada en el rendimiento.
orgulloso Haskeller
¿Puedes escribir nuevas líneas en lugar de ;cuando sea posible? no cambia el recuento de bytes, pero ayuda enormemente a la legibilidad
orgulloso haskeller
@proudhaskeller No tenía idea de cómo aplicar esta fuerza bruta, así que tuve que
pensar en
mi consejo para jugar al golf: 1) alinee todas las funciones que se usan solo una vez (a menos que usen patrones o protecciones). 2) puede implementar d como d n=[0,2,1]!!no d n=mod(3-n)3. 3) haga oy gtome la longitud de la lista en lugar de tomar la lista en sí misma, ya que solo dependen de la longitud (obviamente, esto se mantiene siempre que no estén en línea). 4) reemplazar otherwisecon 0<1. 5) haz la última definición de r be r$o x:y. 6) quite el a@y reemplace a con x:y. buena suerte con tu golf!
orgulloso Haskeller
Su algoritmo da la respuesta incorrecta para [3,3,3,2,2,2,1,1,1]. Ejecuté su código y devuelve 216 (el resultado más grande que pude obtener fue 729).
Brilliand
1

GolfScript (52 caracteres)

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

Demostración en línea

El análisis de Feersum es bastante bueno, pero puede llevarse más lejos si el objetivo es jugar golf en lugar de eficiencia. En pseudocódigo:

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
Peter Taylor
fuente