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.
fuente
Respuestas:
C - 224 bytes - Tiempo de ejecución O (n)
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:
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.
fuente
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.
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.
fuente
SWI-Prolog - 250
Oh chico, pasé demasiado tiempo en esto.
Llamado desde la línea de comando (por ejemplo):
(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:
Explicación:
ignore
o\+
) para permitir que el predicado en general regresetrue
y continúe.is
y luego escríbala.fuente
Scala, 134
Ungolfed y comentó:
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.
fuente
Python 278 (O (n!))
Explicación
fuente
Haskell -
295 290 265 246 203 189182 bytesFinalmente 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í):
Nuevos casos de prueba:
Explicación de la solución:
La
main
función solo recibe una entrada y se ejecutag
con 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:fuente
;
cuando sea posible? no cambia el recuento de bytes, pero ayuda enormemente a la legibilidadd n=[0,2,1]!!n
od n=mod(3-n)3
. 3) hagao
yg
tome 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) reemplazarotherwise
con0<1
. 5) haz la última definición de r ber$o x:y
. 6) quite ela@
y reemplace a conx:y
. buena suerte con tu golf!GolfScript (52 caracteres)
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:
fuente