Soy un joven mago, y trato mucho de no desperdiciar maná durante mis encuentros mágicos.
Tengo X hechizos disponibles en cualquier momento y cada uno de ellos tiene su propio coste de maná.
Y, X, Y son enteros positivos estrictamente inferiores a 11.
Como principiante, mi reserva de maná fluctúa mucho (siempre es inferior a 11). , y necesito ayuda para lanzar la menor cantidad de hechizos posibles (los pergaminos son caros, ya sabes) mientras vacío mi reserva de maná. Si no puedes encontrar ninguna combinación de hechizos que coincida exactamente con el tamaño de mi reserva de maná, entonces me ofrecerás la más cercana (y más barata).
Vine a ti y a tu infinita sabiduría para ayudarme a convertirme en el mejor mago oscuro. No me decepcionaré.
Estilo INPUT (porque el estilo lo es todo):
Y; abcdef
Y es el tamaño del grupo de maná. (a, b, c, d, e, f) son los hechizos. Hay 6 hechizos, el primero cuesta 'a' maná, el segundo hechizo cuesta 'b' maná, etc.
ENTRADA: 4; 1 2 3 3 7 6
Tengo 4 manas disponibles y 6 hechizos disponibles. Dos hechizos cuestan 1 maná, 1 hechizo cuesta 2 maná, dos hechizos cuestan 3 maná, etc.
SALIDA: (3,1)
ENTRADA: 3; 1 3 5 2 10
SALIDA: (3)
ENTRADA: 8; 4 1 9
SALIDA: (4,1)
ENTRADA: 4; 1 2 2 3
SALIDA: (2,2), (1,3)
Debes sacar todas las combinaciones de hechizos, pero no hay necesidad de hechizos distintos que tengan el mismo costo.
El conjuro más corto para cualquier máquina que desee recibirá una profusión de agradecimientos y un látigo de destino.
Respuestas:
GolfScript, 55 caracteres
Pruébalo en línea .
fuente
APL (87)
El formato de entrada es una lista APL, donde el primer elemento es el grupo de maná y el resto de los elementos son los hechizos. La salida tiene cada combinación posible de hechizos en una línea separada.
Explicación:
k←1↓i←⎕
: lee una lista de la entrada y la almacenai
. Suelta el primer elemento (maná) y almacena el restok
.1↓g←⍳⍴k
: genera una lista de1
hasta la longitudk
y la almacena eng
. Suelta el primer elemento, dando[2..len k]
.{
...}¨
: Para cada uno de estos, obtenga los índices de cada combinación única enk
longitud⍵
:z←,⍳⍵/⍴k
: obtener una⍵
matriz dimensional de índices de longitudk
, aplanarla y almacenarlaz
.∧/¨2>/¨
: para cada coordenada en cada índice, vea si todas las coordenadas para laN
dimensión th son más altas que las de laN-1
dimensión th.z/⍨
: seleccione dez
aquellos elementos para los cuales lo anterior es verdadero⊃,/g,
: como lo anterior no funciona para vectores unidimensionales, agregueg
al frente. Ahora tenemos una lista de listas de listas (debido al foreach) de todos los índices únicos enk
. Concatenar las listas juntas y cerrarlas (de modo que terminamos con una lista de listas).{
...}¨
: para cada posible lista de coordenadas, busque la combinación correspondiente de valoresk
y filtre los que son demasiado caros:a←k[⍵]
: busque la combinación actualk
y guárdelaa
.a/⍨⊃i≥+/a
: seleccionea
solo si el primer elemento eni
(el grupo de maná) es igual o mayor que la suma de los elementos dea
.m←
: almacena todas las combinaciones de hechizos que no excedan el límite de maná enm
.m←m/⍨t=⌈/t←+/¨m
: seleccionem
solo aquellas combinaciones cuya suma sea igual a la suma de la combinación más cara y almacénelam
nuevamente.m/⍨t=⌊/t←⊃∘⍴¨m
: seleccionem
solo aquellas combinaciones cuya longitud sea igual a la longitud de la combinación más corta.↑∪
: elimine cualquier duplicado y conviértalo en una matriz (para mostrar cada combinación en una línea separada).fuente
Rubí,
114113 caracteresEntrada: una matriz de dos elementos del asistente de maná y la lista de hechizos, formateado un JSON de una línea.
Salida: una matriz 2D de las listas de hechizos, formateada como un JSON de una línea, o
nil
si el asistente no puede lanzar hechizos.En especial me encanta
x,y = eval gets
. Tan peligroso y malvado, pero tan poderoso y simple. Perfecto para jugar al golf.Ambos
sort
yuniq
son necesarios. De lo contrario, esto producirá duplicados para entradas como[4, [1, 3, 1]]
. No estoy contento con esto.find
Es un método útil para controlar el flujo. Sin embargo, su valor de retorno no es tan útil aquí. En cuanto a la longitud, está a la parany?
, cuyo valor de retorno es aún menos útil.Ejemplos:
fuente
map
lugar defind
? Además,.reduce(:+)
no es&
necesariomap
no se detiene en el primer resultado positivo. Imprimiría todas las posibilidades, agrupadas por costo de maná y tamaño. Gracias por el segundo consejo.Haskell (GHC),
172 167143 caracteresDesobuscado:
[4,1,2,3,3,7,6]
).Solución directa: tome el conjunto de potencia de la entrada, luego reduzca eso filtrando las combinaciones para las que tenemos suficiente maná, etc.
fuente
Mathematica 131
Debe haber formas más cortas, pero esto es lo que pude encontrar.
fuente