Optimizing my spell casts!

Question

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.

Answer 1

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).

Answer 2

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

Answer 3

GolfScript, 55 characters

[[]]\{{+}+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]]

Answer 4

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.

Answer 5

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}}