Apilamiento de cajas pesadas

27

Tienes un montón de cajas pesadas y quieres apilarlas en la menor cantidad de pilas posibles. El problema es que no puede apilar más cajas en una caja de las que puede soportar, por lo que las cajas más pesadas deben ir en la parte inferior de una pila.

El reto

Entrada : Una lista de pesos de cajas, en kg enteros.

Salida : una lista de listas que describen las pilas de cajas. Esto debe usar la menor cantidad de pilas posibles para la entrada. Para ser una pila válida, el peso de cada caja en la pila debe ser mayor o igual a la suma del peso de todas las cajas que se encuentran arriba.

Ejemplos de pilas válidas

(En orden de abajo hacia arriba)

  • [3]
  • [1, 1]
  • [3, 2, 1]
  • [4, 2, 1, 1]
  • [27, 17, 6, 3, 1]
  • [33, 32, 1]
  • [999, 888, 99, 11, 1]

Ejemplos de pilas inválidas

(En orden de abajo hacia arriba)

  • [1, 2]
  • [3, 3, 3]
  • [5, 5, 1]
  • [999, 888, 777]
  • [4, 3, 2]
  • [4321, 3000, 1234, 321]

Ejemplos de casos de prueba

1

IN: [1, 2, 3, 4, 5, 6, 9, 12]
OUT: [[12, 6, 3, 2, 1], [9, 5, 4]]

2

IN: [87, 432, 9999, 1234, 3030]
OUT: [[9999, 3030, 1234, 432, 87]]

3

IN: [1, 5, 3, 1, 4, 2, 1, 6, 1, 7, 2, 3]
OUT: [[6, 3, 2, 1], [7, 4, 2, 1], [5, 3, 1, 1]]

4 4

IN: [8, 5, 8, 8, 1, 2]
OUT: [[8, 8], [8, 5, 2, 1]]

Reglas y supuestos

  • Se aplican las reglas estándar de E / S y las lagunas prohibidas
  • Use cualquier formato conveniente para E / S
    • Las pilas pueden describirse de arriba a abajo o de abajo hacia arriba, siempre y cuando sea consistente.
    • El orden de las pilas (en lugar de las cajas dentro de esas pilas) no importa.
    • También puede tomar cuadros de entrada como una lista clasificada previamente. El orden no es particularmente importante para la entrada, siempre que el problema general no se resuelva con la clasificación en sí.
  • Si hay más de una configuración óptima de pilas, puede generar cualquiera de ellas
  • Puede suponer que hay al menos una caja y que todas las cajas pesan al menos 1 kg
  • Debe soportar pesos de hasta 9.999 kg, como mínimo.
  • Debe admitir hasta 9,999 cajas en total, como mínimo.
  • Las cajas con el mismo peso no se pueden distinguir, por lo que no es necesario anotar en qué caja se utilizó.

¡Feliz golf! ¡Buena suerte!

Carne de res
fuente
2
¿Podemos tomar los pesos en orden? (ya sea ascendente o descendente)
Arnauld
44
"Debe admitir hasta 9,999 cajas en total, como mínimo". ¿Cómo se interpreta el "soporte" aquí? ¿Significa simplemente que el programa debería ser capaz de tomar ese tamaño de entrada, o significa que el programa debería proporcionar la respuesta en un tiempo razonable? Si es lo último, debería haber casos de prueba mucho más grandes.
Joel
1
Caso de prueba sugerido: [8, 8, 8, 5, 1]->[[8, 8], [8, 5, 1]]
Hiatsu
3
O incluso mejor: [8, 5, 8, 8, 1, 2]->[[8, 8], [8, 5, 2, 1]]
Hiatsu
2
@Arnauld, ya que de lo contrario eso agregaría un código de clasificación poco interesante a una respuesta, voy a decir que , puede tomar las entradas en orden ordenado.
Beefster

Respuestas:

5

Jalea , 19 bytes

Œ!ŒṖ€ẎṖÄ>ḊƲ€¬ȦƊƇLÞḢ

Pruébalo en línea!

Obvio -3 gracias a Nick Kennedy ...

De arriba hacia abajo.

Explicación:

Œ!ŒṖ€ẎṖÄ>ḊƲ€¬ȦƊƇLÞḢ  Arguments: S (e.g. [1, 2, 3, 4, 5])
Œ!                   Permutations (e.g. [..., [4, 1, 5, 2, 3], ...])
    €                Map link over left argument (e.g. [..., [..., [[4, 1], [5], [2, 3]], ...], ...])
  ŒṖ                  Partitions (e.g. [..., [[4, 1], [5], [2, 3]], ...])
     Ẏ               Concatenate elements (e.g. [..., ..., [[4, 1], [5], [2, 3]], ..., ...])
               Ƈ     Filter by link (e.g. [..., [[1, 3], [2], [4], [5]], ...])
              Ɗ       Create >=3-link monadic chain (e.g. [[1], [], [0]])
           €           Map link over left argument (e.g. [[1], [], [0]])
          Ʋ             Create >=4-link monadic chain (e.g. [1])
      Ṗ                  Remove last element (e.g. [4])
       Ä                 Cumulative sum (e.g. [4])
         Ḋ               [Get original argument] Remove first element (e.g. [1])
        >                Greater than (vectorizes) (e.g. [1])
            ¬          Logical NOT (vectorizes) (e.g. [[0], [], [1]])
             Ȧ         Check if non-empty and not containing zeroes after flattening (e.g. 0)
                 Þ   Sort by link (e.g. [[[1, 2, 3], [4, 5]], ..., [[5], [4], [3], [2], [1]]])
                L     Length (e.g. 4)
                  Ḣ  Pop first element (e.g. [[1, 2, 3], [4, 5]])
Erik el Outgolfer
fuente
¿Alguna posibilidad de una versión menos compacta con explicación? Aprendo un montón de eso.
John Keates
1
@JohnKeates Se agregó uno.
Erik the Outgolfer
5

JavaScript (Node.js),  139122116  bytes

Espera la entrada ordenada en orden ascendente.

f=(A,s=[],[n,...a]=A,r)=>n?s.some((b,i,[...c])=>n<eval(b.join`+`)?0:f(A,c,a,c[i]=[n,...b]))?S:r?0:f(A,[...s,[]]):S=s

Pruébalo en línea!

Comentado

f = (                        // f is a recursive function taking:
  A,                         //   A[] = input array
  s = [],                    //   s[] = list of stacks, initially empty
  [n,                        //   n   = next weight to process
      ...a] = A,             //   a[] = array of remaining weights
  r                          //   r   = recursion flag
) =>                         //
  n ?                        // if n is defined:
    s.some((b, i,            //   for each stack b[] at position i in s[],
                  [...c]) => //   using c[] as a copy of s[]:
      n < eval(b.join`+`) ?  //     if n is not heavy enough to support all values in b[]:
        0                    //       abort
      :                      //     else:
        f(                   //       do a recursive call:
          A, c, a,           //         using A[], c[] and a[]
          c[i] = [n, ...b]   //         with n prepended to c[i]
        )                    //       end of recursive call
    ) ?                      //   end of some(); if successful:
      S                      //     return S[]
    :                        //   else:
      r ?                    //     if this is a recursive call:
        0                    //       do nothing
      :                      //     else:
        f(A, [...s, []])     //       try again with an additional stack
  :                          // else:
    S = s                    //   success: save the solution in S[]
Arnauld
fuente
2

Python 3.8 (prelanzamiento) , 178 bytes

f=lambda b,s=[[]]:(a for i in range(len(s))if b[0]>=sum(s[i])for a in f(b[1:],s[:i]+[[b[0]]+s[i]]+s[i+1:]+[[]]))if b else[s]
g=lambda a:(c:=sorted(f(a),key=len)[0])[:c.index([])]

Pruébalo en línea!

Ahora funciona en todas las entradas posibles. (Se agota el tiempo de espera en TIO con más de diez cuadros, pero calcula una respuesta correcta)

Hiatsu
fuente
2
list(reversed(sorted(a)))Se puede escribir sorted(a)[::-1]para golf.
Joel
Pensarías que ya lo sabría, especialmente porque hago muchas otras indexaciones. Gracias.
Hiatsu
Solo como un comentario secundario, si no fuera por el golf, sería mejor escribir en su sorted(a, reverse=True)lugar.
Joel