Elija entre un conjunto de pesos existente para hacer una suma objetivo

9

Cuando hago levantamiento de pesas, quiero hacer un peso específico uniendo varias placas a una barra.

Tengo los siguientes platos:

  • 6 platos de 1 kg cada uno
  • 6 platos de 2.5 kg cada uno
  • 6 platos de 5 kg cada uno
  • 6 platos de 10 kg cada uno

La barra en sí pesa 10 kg.

Solo se permite unir las placas en pares: están unidas en cada extremo de la barra, y la disposición en los dos extremos debe ser completamente simétrica (por ejemplo, unir dos placas de 5 kg en un extremo y una placa de 10 kg en el otro extremo está prohibido por razones de seguridad).

Haga un programa o una función que me diga cuántas placas de cada tipo tengo que usar para obtener un peso total dado. La entrada es un entero mayor que 11; la salida es una lista / matriz / cadena de 4 números. Si es imposible combinar placas existentes para obtener el peso objetivo, generar una matriz cero / vacía, una cadena no válida, lanzar una excepción o algo así.

Si hay varias soluciones, el código debe generar solo una (no haga que el usuario elija, está demasiado ocupado con otras cosas).

Casos de prueba:

12 -> [2 0 0 0] - 2 plates of 1 kg plus the bar of 10 kg
13 -> [0 0 0 0] - a special-case output that means "impossible"
20 -> [0 0 2 0] - 2 plates of 5 kg + bar
20 -> [0 4 0 0] - a different acceptable solution for the above
21 -> [6 2 0 0] - 6 plates of 1 kg + 2 plates of 2.5 kg + bar
28 -> [0 0 0 0] - impossible
45 -> [0 2 6 0] - a solution for a random number in range
112 -> [2 4 6 6] - a solution for a random number in range
121 -> [6 6 6 6] - maximal weight for which a solution is possible

Si su código genera los números en el orden opuesto (desde la placa pesada hasta la liviana), especifique esto explícitamente para evitar confusiones.

anatolyg
fuente
1
¿No es esto un engaño de la pregunta mínima de conteo de monedas ? No creo que el mismo algoritmo codicioso falle, excepto con la restricción de 6 de un tipo de placa. Creo que podría no ser suficiente diferencia, pero no estoy seguro.
FryAmTheEggman
1
El algoritmo codicioso no funciona (no sin modificación, al menos) exactamente porque los números son limitados
anatolyg
Relacionado , pero ese es ASCII
AdmBorkBork
Sí, la razón por la que publiqué fue porque no estaba seguro de que la modificación fuera lo suficientemente significativa. Publiqué para tratar de obtener comentarios de la comunidad, y eliminaré mi comentario si parece que la comunidad no está de acuerdo conmigo.
FryAmTheEggman
¿Podemos generar todas las soluciones en lugar de solo una?
Luis Mendo

Respuestas:

5

Jalea , 22 bytes

4ṗạµ×2,5,10,20S€+⁵iƓịḤ

Pruébalo en línea! o verificar todos los casos de prueba .

Cómo funciona

4ṗạµ×2,5,10,20S€+⁵iƓịḤ  Main link. No arguments

4                       Set the left argument and initial return value to 4.
 ṗ                      Take the Cartesian power of [1, 2, 3, 4] and 4, i.e.,
                        generate all 4-tuples of integers between 1 and 4.
  ạ                     Take the absolute difference of all integers in the
                        4-tuples and the integer 4. This maps [1, 2, 3, 4] to
                        [3, 2, 1, 0] and places [0, 0, 0, 0] at index 0.
   µ                    Begin a new, monadic chain. Argument: A (list of 4-tuples)
     2,5,10,20          Yield [2, 5, 10, 20].
    ×                   Perform vectorized multiplication with each 4-tuple in A.
              S€        Sum each resulting 4-tuple.
                +⁵      Add 10 to each sum.
                   Ɠ    Read an integer from STDIN.
                  i     Find its first index in the array of sums (0 if not found).
                     Ḥ  Unhalve; yield the list A, with all integers doubled.
                    ị   Retrieve the 4-tuple at the proper index.
Dennis
fuente
6

MATL , 29 28 bytes

4t:qEZ^!"[l2.5AX]@Y*10+G=?@.

Para las entradas que no tienen solución, esto produce una salida vacía (sin error).

Pruébalo en línea!

Explicación

4           % Push 4
t:q         % Duplicate 4 and transform into range [0 1 2 3]
E           % Multiply by 2: transform into [0 2 4 6]
Z^          % Cartesian power. Each row is a "combination" of the four numbers
!           % Transpose
"           % For each column
  [l2.5AX]  %   Push [1 2.5 5 10]
  @         %   Push current column
  Y*        %   Matrix multiply. Gives sum of products
  10+       %   Add 10
  G=        %   Compare with input: are they equal?
  ?         %   If so
    @       %     Push current column, to be displayed
    .       %     Break loop
            %   Implicit end
            % Implicit end
            % Implicit display
Luis Mendo
fuente
5

Mathematica, 70 bytes

Select[FrobeniusSolve[{2,5,10,20},2#-20],AllTrue[EvenQ@#&&#<7&]][[1]]&

Función anónima. Toma un número como entrada y genera una lista o errores y devuelve {}[[1]]si no hay solución.

LegionMammal978
fuente
4

Jalea, 25 bytes

×2,5,10,20S+⁵⁼³
4ṗ4’ÇÐfḢḤ

Pruébalo aquí.

Lynn
fuente
2,5,10,20->2,5,⁵,20
Leaky Nun
realmente ... no es ,una diada? Toda mi vida es una mentira
Leaky Nun
@LeakyNun ,es una diada, pero también se puede usar para literales. 2,5,⁵,20sin embargo, no es literal ( 2,5y 20son, pero ,, y ,son átomos), por lo que necesitaría algo para combinar los enlaces.
Dennis
3

Python 3, 112 bytes

lambda n:[i for i in[[i//4**j%4*2for j in range(4)]for i in range(256)]if i[0]+2.5*i[1]+5*i[2]+10*i[3]+10==n][0]

Una función anónima que toma la entrada, a través del argumento, de la masa objetivo y devuelve el número de cada placa como una lista. Si no existe una solución, se produce un error. Esto es pura fuerza bruta.

Cómo funciona

lambda n                                   Anonymous function with input target mass n
...for i in range(256)                     Loop for all possible arrangement indices i
[i//4**j%4*2for j in range(4)]             Create a base-4 representation of the index i,
                                           and multiply each digit by 2 to map from
                                           (0,1,2,3) to (0,2,4,6)
[...]                                      Package all possible arrangements in a list
...for i in...                             Loop for all possible arrangements i
i...if i[0]+2.5*i[1]+5*i[2]+10*i[3]+10==n  Return i if it gives the target mass
[...]                                      Package all solutions in a list
:...[0]                                    Return the first list element. This removes any
                                           multiple solutions, and throws an error if there
                                           being no solutions results in an empty list

Pruébalo en Ideone

TheBikingViking
fuente
2

Brachylog , 50 bytes

,L##l4,L:{.~e[0:3]}a:[2:5:10:20]*+:10+?,L:{:2*.}a.

Devuelve falsecuando no es posible.

Fatalizar
fuente
1

Pyth, 34 31 25 bytes

h + fqQ +; s * VT [1 2.5 5;) yMM ^ U4 4] * 4] 0 
yMh + fqQ +; s * VT [2 5; y;) ^ U4 4] * 4] 0
yMhfqQ +; s * VT [2 5; y;) ^ U4 4

Banco de pruebas.

Errores de imposibilidad.

Esto es esencialmente una fuerza bruta.

Esto es bastante rápido, ya que solo hay 256 arreglos posibles.

Monja permeable
fuente
1

Scala, 202 bytes

Decidí que Scala no recibe mucho amor aquí, así que presento una solución (probablemente no óptima) en Scala.

def w(i:Int){var w=Map(20->0,10->0,5->0,2->0);var x=i-10;while(x>0){
var d=false;for(a<-w.keys)if(a<=x & w(a)<6 & !d){x=x-a;w=w.updated(a,w(a)+2);d=true;}
if(!d){println(0);return;}}
println(w.values);}

El programa sale en orden inverso y con basura adicional en comparación con las soluciones posteriores. Cuando no se encuentra una solución, imprime 0.

Nota: Podría no eliminar ninguno de los saltos de línea o espacios porque Scala es tonto, así que creo que para reducir el tamaño, el método tiene que ser hecho de nuevo a menos que me haya perdido algo obvio.

ejaszewski
fuente
1

APL, 40 bytes

{2×(4⍴4)⊤⍵⍳⍨10+2×,⊃∘.+/↓1 2.5 5 10∘.×⍳4}

En ⎕IO ← 0. En inglés:

  1. 10+2×,∘.+⌿1 2.5 5 10∘.×⍳4: construya la matriz de todos los pesos posibles, calculando la suma externa 4D de los pesos por tipo de peso;
  2. ⍵⍳⍨: busca el índice de lo dado. Si no se encuentra, el índice es 1 + el recuento de la matriz en el paso 1;
  3. (4⍴4)⊤: representa el índice en la base 4, es decir, calcula la coordenada del peso dado en el espacio 4D;
  4. : lleva el resultado al espacio del problema, donde las coordenadas deben interpretarse como la mitad del número de placas.

Ejemplo: {2 × (4⍴4) ⊤⍵⍳⍨10 + 2 ×, ⊃∘. + / ↓ 1 2.5 5 10∘. × ⍳4} 112 2 4 6 6

Bonificación : dado que APL es un lenguaje de matriz, se pueden probar varios pesos a la vez. En este caso, el resultado se transpone:

      {2×(4⍴4)⊤⍵⍳⍨10+2×,⊃∘.+/↓1 2.5 5 10∘.×⍳4}12 13 20 21 28 45 112 121
2 0 0 6 0 0 2 6
0 0 0 2 0 2 4 6
0 0 2 0 0 2 6 6
0 0 0 0 0 2 6 6
lstefano
fuente
1

JavaScript (ES6), 109 bytes

n=>`000${[...Array(256)].findIndex((_,i)=>i+(i&48)*9+(i&12)*79+(i&3)*639+320==n*32).toString(4)*2}`.slice(-4)

Devoluciones 00-2por error. Solución alternativa que devuelve undefinedel error, también 109 bytes:

n=>[...Array(256)].map((_,i)=>`000${i.toString(4)*2}`.slice(-4)).find(s=>+s[0]+s[1]*2.5+s[2]*5+s[3]*10+10==n)
Neil
fuente