Pepitas de código

Es ^{una situación hipotética donde es} viernes por la noche, y has invitado a los amigos de golf habituales a participar en tu pasatiempo favorito: el golf de código. Sin embargo, como se trata de una tarea que drena el cerebro, debe recoger algo de alimento para el grupo para que pueda jugar al golf lo más posible de su código.

Ahora, la merienda favorita de todos son las nuggets de pollo, pero hay un problema: no hay un paquete único que cubra las necesidades de todos. Entonces, dado que ya tiene ganas de jugar al golf, decide crear un programa que descubra exactamente qué paquetes debe comprar para poder cubrir las necesidades de Nugget de todos.

Los tamaños de los paquetes de nugget de pollo están por todas partes, y dependiendo de dónde viva en el mundo, los tamaños estándar también cambian. Sin embargo, el [lugar que sirve pepitas] más cercano almacena los siguientes tamaños de paquetes de pepitas:

4, 6, 9, 10, 20, 40

Ahora puede notar que no puede ordenar ciertas combinaciones de pepitas. Por ejemplo, las 11pepitas no son posibles, ya que no existe una combinación que sea 11exactamente igual . Sin embargo, puede 43obtener 1 paquete de 20, 1 paquete de 10, 1 paquete de 9y 1 paquete de 4,

20 + 10 + 9 + 4 = 43 (597)

donde 597se cuadra cada término y se suma (sugerencia: la solución óptima tiene este como el valor más alto) . Por supuesto, hay otras formas de hacer 43, pero como sabes, cuantas más pepitas por paquete, más barato se vuelve por pepita. Por lo tanto, lo ideal es comprar el menor número de paquetes y en las mayores cantidades para minimizar su costo.

La tarea

Debe crear un programa o función que tome una lista de enteros correspondientes a los requisitos de cada persona. Luego debe calcular e imprimir la orden ^α más rentable para comprar las pepitas de pollo. El orden ^α más rentable es la combinación por la cual la suma de los cuadrados de cada cantidad es la más alta. Si no hay absolutamente ninguna manera de comprar las pepitas perfectamente, debe imprimir un valor Falsy tales como 0, False, Impossible!, o lo que está disponible en su idioma.

Ejemplo de E / S:

[2 7 12 4 15 3] => [20 10 9 4]
     1, 1, 2, 1 => False
  6 5 5 5 5 5 9 => 40
      [6, 4, 9] => 9 10
              1 => 0
            199 => 40, 40, 40, 40, 20, 10, 9
              2 => Impossible!

Aquí está la lista de soluciones ideales para los primeros 400. Tenga en cuenta que estos no están formateados como esperaría que fueran los suyos, cada uno tupletiene la forma (N lots of M).

Reglas

1. No hay lagunas estándar.
2. No se utilizan funciones integradas que realizan la totalidad o la mayoría de la tarea, como FrobeniusSolveen Mathematica.

^{α: para aclarar esto con un ejemplo, también podría hacer 43 haciendo 4 + 6 + 6 + 9 + 9 + 9 = 43 (319), pero esto no sería óptimo y, por lo tanto, una salida incorrecta, ya que la suma de los cuadrados es menor que la combinación que anoté en la introducción. Esencialmente, mayor suma de cuadrados = menor costo = más rentable.}

Pyth, 26 25 bytes

e+Zo.aNf!-TCM"  
("./sQ

Tenga en cuenta que hay algunos caracteres no imprimibles. Pruébelo en línea: demostración . Es bastante lento (pero no tan lento como mi solución de 26 bytes).

Explicación:

                          implicit: Q = input list
                     sQ   sum(Q)
                   ./     generate all integer partitions
       f                  filter for partitions T, which satisfy:
             "   ("          string containing chars with the ASCII-values of 4,6,9,10,20,40
           CM                convert each char to the ASCII-value
         -T                  remove this numbers from T
        !                    and check, if the resulting list is empty
    o                      order the remaining subsets N by:
     .aN                      the vector length of N (sqrt of sum of squares)
  +Z                       insert 0 at the beginning
 e                         print the last element

Pyth, 32 bytes

e+Zo.aNfqsTsQysm*]d/sQdCM"  
(

Tenga en cuenta que hay algunos caracteres no imprimibles. Pruébelo en línea: demostración Esta versión es mucho más rápida. Encuentra la solución para la entrada [6,7,8]en aproximadamente un segundo y la solución para la entrada [30]en aproximadamente 90 segundos.

Explicación:

                                 implicit: Q = input list
                          "...(  the string containing chars with the ASCII-values of 4,6,9,10,20,40
                        CM       convert each char to the ASCII-value
                m                map each number d to:
                  ]d                create the list [d]
                 *  /sQd            and repeat it sum(Q)/d times
               s                 unfold
              y                  generate all subsets
        f                        filter for subsets T, which satisfy:
         qsTsQ                      sum(Q) == sum(T)
    o                            order the remaining subsets N by:
     .aN                            the vector length of N (sqrt of sum of squares)
  +Z                             insert 0 at the beginning
 e                               print the last element

Perl, 175 153

sub f{my$n=$_[0];if(!$n){return 1;}foreach$o(40,20,9,10,6,4){if($n>=$o&&f($n-$o)){print"$o ";return 1;}}return 0;}$n+=$_ for@ARGV;if(!f($n)){print":(";}

Toma su entrada de los argumentos del programa. Imprime a :( si no puede encontrar una solución perfecta.

Código sin golf:

sub f
{
    my $n = $_[0];
    if(!$n)
    {
        return 1;
    }
    foreach $o(40,20,9,10,6,4)
    {
        if($n>=$o&&f($n-$o))
        {
            print "$o ";
            return 1;
        }
    }
    return 0;
}

$n += $_ for @ARGV;
if(!f($n))
{
    print ":(";
}

PD: Esta es probablemente la primera entrada que no toma 10 minutos 1 2;)

Compruébalo aquí.

CJam, 45 29 28 bytes

q~:+_[40K9A6Z)U]m*_::+@#=0-p

Tenga en cuenta que este enfoque es muy lento y requiere mucha memoria.

Pruébelo en línea en el intérprete de CJam .

Se puede acelerar significativamente a un costo de 5 bytes:

q~:+_40/4+[40K9A6Z)U]m*_::+@#=0-p

La complejidad sigue siendo exponencial en la suma de la entrada, pero esto debería manejar casos de prueba hasta 159 con el intérprete en línea y hasta 199 con el intérprete de Java en un par de segundos.

Pruébelo en línea en el intérprete de CJam .

Idea

Una compra óptima (suma máxima de cuadrados) es una compra válida (número correcto de pepitas) que tiene la mayor cantidad de 40 's posible, luego la mayor cantidad posible de 20 ' s, luego la mayor cantidad de 9 's posible (por ejemplo, 9 9es preferible sobre 10 4 4) y así sucesivamente para 10 's, 6 ' sy 4 's.

En este enfoque, generamos el producto cartesiano de N copias de la matriz [40 20 9 10 6 4 0] , donde N es el número deseado de pepitas. N es un límite superior (malo) para la cantidad de compras que tenemos que hacer. En la versión acelerada del código, usamos N / 40 + 4 en su lugar.

Debido a cómo se ordena la matriz, el producto cartesiano comenzará con el vector [40 ... 40] y finalizará con el vector [0 ... 0] . Calculamos el índice del primer vector que tiene la suma correcta (que también tendrá la suma óptima de cuadrados), recuperamos el elemento de matriz correspondiente, eliminamos los ceros que sirvieron como marcadores de posición e imprimimos el resultado.

Si no se puede encontrar ningún vector, el índice será -1 , por lo que recuperamos [0 ... 0] , que imprimirá una matriz vacía en su lugar.

Código

q~                            e# Read from STDIN and evaluate the input.
  :+                          e# Push N, the sum of all elements of the resulting array.
     [40K9A6Z)U]              e# Push B := [40 20 9 10 6 4 0].
    _           m*            e# Push B**N, the array of all vectors of dimension N
                              e# and coordinates in B.
                  _::+        e# Copy and replace each vector by its sum.
                      @#      e# Get the first index of N.
                        =     e# Retrieve the corresponding element.
                         0-p  e# Remove 0's and print.

Julia, 126 bytes

r->(t=filter(i->all(j->j∈[4,6,9,10,20,40],i),partitions(sum(r)));show(!isempty(t)&&collect(t)[indmax(map(k->sum(k.^2),t))]))

Esto crea una función sin nombre que acepta una matriz como entrada e imprime una matriz o booleano en STDOUT, dependiendo de si existe una solución. Para llamarlo, dale un nombre, por ejemplo f=n->....

Ungolfed + explicación:

function f(r)
    # Nugget pack sizes
    packs = [4, 6, 9, 10, 20, 40]

    # Filter the set of arrays which sum to the required number of nuggets
    # to those for which each element is a nugget pack
    t = filter(i -> all(j -> j ∈ packs, i), partitions(sum(r)))

    # Print the boolean false if t is empty, otherwise print the array of
    # necessary nugget packs for which the sum of squares is maximal
    show(!isempty(t) && collect(t)[indmax(map(k -> sum(k.^2), t))])
end

Ejemplos:

julia> f([1])
false

julia> f([2,7,12,4,15,3])
[20,10,9,4]

Python 3 - 265 caracteres

import itertools as i
n=list(map(int,input().split(',')));m=[]
for f in range(1,9):
 for j in range(6*f):
  for x in i.combinations((4,6,9,10,20,40,)*f,j+1):
   if sum(n)==sum(x):m.append(x)
if m!=[]:v=[sum(l**2for l in q)for q in m];print(m[v.index(max(v))])
else:print(0)

Mostrando espaciado:

import itertools as i
n=list(map(int,input().split(',')));m=[]
for f in range(1,5):
 for j in range(6*f):
\tfor x in i.combinations((4,6,9,10,20,40,)*f,j+1):
\t if sum(n)==sum(x):m.append(x)
\t\tif m!=[]:v=[sum(l**2for l in q)for q in m];print(m[v.index(max(v))])
else:print(0)

Pasa todos los casos de prueba

Nota: No sé si esto pasará todos los casos porque es muy lento ... Pero debería ...

JavaScript, 261 256 261

d="length";function g(a){for(z=y=0;y<a[d];z+=+a[y++]);return z}x=[40,20,10,9,6,4];l=prompt().split(",");o=g(l);p=[];for(i=0;i<x[d];i++)r=g(p),s=r+x[i],(s<o-3||s==o)&&p.push(x[i]),(i==x[d]-1||40<o-r)&&r+x[i]<o-3&&(i=-1,0==i||o-r<p[p[d]-1]&&p.pop());g(p)==o&&p||0

No estoy seguro de si esto está bien, parece funcionar, pero seguramente me faltan cosas.

Sin embargo, no parece ser lento, hasta 123456que sale [40 x 3086, 10, 6]casi de inmediato.

Explicación:

Iterando sobre los tamaños de pepita (el más grande primero)

• Si la suma de la pila más el tamaño de la pepita es menor que el objetivo - 3 -> empujarlo en una pila
• Si quedan más de 40 -> reinicie el contador de bucle
• Si la suma de la pila es mayor que la meta cuando se alcanzó el último tamaño de pepita -> pop el último elemento, restablezca el contador de bucle
• Si la suma de la pila se suma, devuélvala; de lo contrario, devuelva 0

Para 199 | 1 la pila construida se ve así

i | stack
0   [40]
0   [40, 40]
0   [40, 40, 40]
0   [40, 40, 40, 40]
0   [40, 40, 40, 40]
1   [40, 40, 40, 40, 20]
2   [40, 40, 40, 40, 20, 10]
3   [40, 40, 40, 40, 20, 10, 9]
4   [40, 40, 40, 40, 20, 10, 9]
5   [40, 40, 40, 40, 20, 10, 9]
==> [40, 40, 40, 40, 20, 10, 9]

Para 1

i | stack
0   []
1   []
2   []
3   []
4   []
5   []
==> 0