"Friday" Puzzle 2017-04-19

summation_sets.rb

# 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