Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
"Friday" Puzzle 2017-04-19
# Full on brute force
def f(r,s)
(1..r.size).reduce([]){|c,n| c + r.combination(n).select{|c| c.reduce(&:+) == s }}.sort_by{|c| c.size }
end
# Minor optimization for very large arrays of small numbers seeking a sum that is small
# via limiting the combination sizes we consider based on min and max numbers necessary
# to reach the sum from either end of the spectrum. Probably a cleaner way to find the
# min and max n, but couldn't be bothered.
def f(r,s)
numbers = r.sort
maxn = 0
sum = 0
begin
sum += numbers[maxn]
maxn += 1
end while sum < s
minn = 0
sum = 0
begin
minn += 1
sum += numbers[-1*minn]
end while sum < s
(minn..maxn).reduce([]){|c,n| c + r.combination(n).select{|c| c.reduce(&:+) == s }}.sort_by{|c| c.size }
end
def assertF(n,r,s,o)
raise "Test failed #{n}" unless f(r,s) == o
end
def testF
assertF(1, [1,2,3,4,5], 5, [[5],[1,4],[2,3]])
assertF(2, [1,2,3,4,5,6,7,8,9,10], 9, [[9],[1,8],[2,7],[3,6],[4,5],[1,2,6],[1,3,5],[2,3,4]])
assertF(3, [1,2,2,3,3,5,6,7,8,9,10], 12, [[3,9],[2,10],[5,7],[2,10],[3,9],[1,5,6],[2,2,8],[2,3,7],[2,3,7],[2,3,7],[3,3,6],[2,3,7],[1,2,9],[1,2,9],[1,3,8],[1,3,8],[2,2,3,5],[1,2,3,6],[1,2,3,6],[1,2,3,6],[1,2,3,6],[1,3,3,5],[2,2,3,5],[1,2,2,7]])
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment