# Optimizing my spell casts!

I'm a young wizard, and I try very hard to not waste mana during my magical encounters.
I have X spells available at any given time and each one of them have its own mana cost Y.
X,Y being positive integers strictly lower than 11.
As a beginner, my mana pool fluctuates a lot (it is always lower than 11), and I need help to cast as few spells as possibles (scrolls are expensive, ya know) while emptying my mana pool. If you can't find any spell combination which matches exactly my mana pool's size, you shall then offer me closest (and cheaper) one.

I came to you and your infinite wisdom to help me become the greatest dark wizard. I shall not be disappointed.

INPUT style (because style is everything):
Y;a b c d e f
Y is the size of the mana pool. (a,b,c,d,e,f) are the spells. There are 6 spells, first one costs 'a' mana, second spell costs 'b' mana, etc.

INPUT : 4;1 2 3 3 7 6
I have 4 manas available, and 6 spells available. Two spells cost 1 mana, 1 spell costs 2 mana, two spells cost 3 mana, etc.

OUTPUT : (3,1)

INPUT : 3;1 3 5 2 10
OUTPUT : (3)

INPUT : 8 ; 4 1 9
OUTPUT : (4,1)

INPUT : 4;1 2 2 3
OUTPUT : (2,2),(1,3)

You shall output every combination of spells, but there is no need to distinct spells which are the same cost.

The shortest incantation to whatever machine you desire will be granted a profusion of thanks, and a whip of destiny.

• I think I miss the point or maybe I just don't understand your examples: first example: I find 7 spells - can you clarify? Also the last one: why wouldn't the correct output be (4)? It has less spells as (2,2) and the puzzle states "I need help to cast as few spells as possibles". Does it also mean that we have to output all solutions if there are multiple solutions with same number of spells? Commented Nov 19, 2013 at 12:32
• Obviously, I messed up my inputs and outputs, this is presumably fixed. For the latest question, Yes, you shall output every combination that has the same amount of spells. Thanks. Commented Nov 19, 2013 at 13:45
• are the input/output formats given, or anything goes as well it's a number + array of numbers => 2d array of numbers? Commented Nov 19, 2013 at 13:50
• I'd be accomodating, as long as both the output and the input of your scroll of ambiguous language (brainfck) are clear and readable. Commented Nov 19, 2013 at 13:54
• or, can we even write a function with two arguments instead of a whole program? Or even an expression? Commented Nov 19, 2013 at 13:54

## APL (87)

↑∪m/⍨t=⌊/t←⊃∘⍴¨m←m/⍨t=⌈/t←+/¨m←{a/⍨⊃i≥+/a←k[⍵]}¨⊃,/g,{z/⍨∧/¨2>/¨z←,⍳⍵/⍴k}¨1↓g←⍳⍴k←1↓i←⎕


The input format is an APL list, where the first element is the mana pool and the rest of the elements are the spells. The output has each possible combination of spells on a separate line.

⎕:    4, 1 2 3 3 7 6
3 1
⎕:    3, 1 3 5 2 10
3
⎕:    8, 4 1 9
1 4
⎕:    4, 1 2 2 3
2 2
3 1


Explanation:

• k←1↓i←⎕: read a list from the input, and store it in i. Drop the first element (mana) and store the rest in k.
• 1↓g←⍳⍴k: generate a list from 1 to the length of k, and store it in g. Drop the first element, giving [2..len k].
• {...}¨: For each of these, get the indices of each unique combination in k of length ⍵:
• z←,⍳⍵/⍴k: get a ⍵-dimensional matrix of indices of length k, flatten it, and store it in z.
• ∧/¨2>/¨: for each coordinate in each index, see if all coordinates for the Nth dimension are higher than those for the N-1th dimension.
• z/⍨: select from z those elements for which the above holds true
• ⊃,/g,: because the above does not work for one-dimensional vectors, add g to the front. We now have a list of lists of lists (because of the foreach) of all unique indices into k. Concatenate the lists together and de-enclose (so we end up with a list of lists).
• {...}¨: for each possible list of coordinates, look up the corresponding combination of values in k, and filter out those that are too expensive:
• a←k[⍵]: look up the current combination in k and store it in a.
• a/⍨⊃i≥+/a: select a only if the first item in i (the mana pool) is equal to or greater than the sum of the elements of a.
• m←: store all combinations of spells that do not exceed the mana limit in m.
• m←m/⍨t=⌈/t←+/¨m: select from m only those combinations whose sum is equal to the sum of the most expensive combination, and store it in m again.
• m/⍨t=⌊/t←⊃∘⍴¨m: select from m only those combinations whose length is equal to the length of the shortest combination.
• ↑∪: remove any duplicates, and convert to a matrix (to display each combination on a separate line).
• This is arcane! Perfect for a wizard... Commented Nov 22, 2013 at 1:45

### Ruby, 114 113 characters

x,y=eval gets
(d=0..10).find{|r|d.find{|c|s=y.sort.combination(c).select{|s|s.reduce(:+)==x-r}.uniq
p s if s[0]}}


Input: a two-element array of the wizard mana and the spell list, formatted a one-line JSON.

Output: a 2D array of the spell lists, formatted as a one-line JSON, or nil if the wizard can cast no spell.

I especially love x,y = eval gets. So dangerous and evil, yet so powerful and simple. Perfect for golfing.

Both sort and uniq are neccessary. Otherwise, this will produce duplicates for input like [4, [1, 3, 1]]. I'm not happy about this.

find is a useful method for control flow. Its return value is not as useful here, though. Length-wise, it comes on par with any?, which return value is even less useful.

Examples:

> [4, [1, 2, 3, 3, 7, 6]]
# [[1, 3]]
> [3, [1, 3, 5, 2, 10]]
# [[3]]
> [8, [4, 1, 9]]
# [[1, 4]]
> [4, [1, 2, 2, 3]]
# [[1, 3], [2, 2]]
> [4, [5, 6, 7]]
# nil

• Couldn't you use map instead of find? Also, .reduce(:+), no & needed Commented Nov 21, 2013 at 19:48
• map doesn't stop at the first positive result. It would print all possibilities, grouped by mana cost and size. Thanks for the second advice. Commented Nov 21, 2013 at 20:26

[[]]\{{+}+1$%|}/.@{1$0+{+}*.@>!*100*\,-~}+:s%$0={\s=}+,  Try it online. > 4 [1 1 2 3 3 7 6] [[1 3]] > 3 [1 3 5 2 10] [[3]] > 8 [4 1 9] [[4 1]] > 4 [1 2 2 3] [[2 2] [1 3]]  ### Haskell (GHC), 172 167 143 chars import Data.List import GHC.Exts f(x:y)=head.groupWith length.last.groupWith sum.filter((<=x).sum).nub$subsequences y
main=interact$show.f.read  Deobfuscated: import Data.List import GHC.Exts f (x:xs) = head . groupWith length . last . groupWith sum . filter ((<= x) . sum) . nub$ subsequences xs

main = interact (show . f . read)

• Input format: bracketed list with head as available mana, tail as avaliable spells (e.g. [4,1,2,3,3,7,6]).
• Output format: bracketed list of lists, each sublist representing one possible set of spells.

Straightforward solution: grab the powerset of the input, then reduce that down by filtering for combinations we have sufficient mana for, etc.

# Mathematica 131

There must be shorter ways, but this is what I was able to come up with.

l=Length;
f[{a_,b_}]:=Select[t=Cases[s=SortBy[Union@Cases[Subsets[b],x_/;0<Tr@x<a+1:>{x,Tr@x}],Last],
{x_,s[[-1,2]]}:> x],l@#==l@t[[1]]&]


f[{4, {1, 2, 3, 7, 6}}]


{{1, 3}}

f[{3, {1, 3, 5, 2, 10}}]


{{3}}

f[{8, {4, 1, 9}}]


{{4, 1}}

f[{4, {1, 2, 2, 3}}]


{{1, 3}, {2, 2}}