| Bytes | Lang | Time | Link |
|---|---|---|---|
| 275 | Python3 | 251006T190640Z | Ajax1234 |
| 131 | Mathematica | 131127T001458Z | DavidC |
| 143 | Haskell GHC | 131124T122649Z | FireFly |
| 055 | GolfScript | 131123T093017Z | Howard |
| nan | Ruby | 131119T150340Z | John Dvo |
| 087 | APL | 131119T173246Z | marinus |
Python3, 275 bytes
def f(Y,s):
q,r=[(0,[])],[]
for i,a in q:
r+=[((Y-sum(u for _,u in a),sum(u for u,_ in a)),a)]
if i>=len(s):continue
q+=[(i+1,a)];A=a+[(i,s[i])]
if sum(u for _,u in A)<=Y:q+=[(i+1,A)]
m=min(r,key=lambda x:x[0])[0]
return{tuple(u for _,u in b)for a,b in r if a==m}
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}}
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.
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]]
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
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 ini. Drop the first element (mana) and store the rest ink.1↓g←⍳⍴k: generate a list from1to the length ofk, and store it ing. Drop the first element, giving[2..len k].{...}¨: For each of these, get the indices of each unique combination inkof length⍵:z←,⍳⍵/⍴k: get a⍵-dimensional matrix of indices of lengthk, flatten it, and store it inz.∧/¨2>/¨: for each coordinate in each index, see if all coordinates for theNth dimension are higher than those for theN-1th dimension.z/⍨: select fromzthose elements for which the above holds true
⊃,/g,: because the above does not work for one-dimensional vectors, addgto the front. We now have a list of lists of lists (because of the foreach) of all unique indices intok. 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 ink, and filter out those that are too expensive:a←k[⍵]: look up the current combination inkand store it ina.a/⍨⊃i≥+/a: selectaonly if the first item ini(the mana pool) is equal to or greater than the sum of the elements ofa.
m←: store all combinations of spells that do not exceed the mana limit inm.m←m/⍨t=⌈/t←+/¨m: select frommonly those combinations whose sum is equal to the sum of the most expensive combination, and store it inmagain.m/⍨t=⌊/t←⊃∘⍴¨m: select frommonly 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).