From: Kenneth Collins <pine29@...>
Date: 2005-12-13T04:08:26+09:00
Subject: Re: Calculating single-digit summands

Since only single digit summands are under consideration, I don't think 
optimizations are important for this. Here's a simple brute force 
approach that performs reasonably well. It considers all possible 
subsets of [1,2,3,4,5,6,7,8,9] and rejects any with the wrong depth or 
sum. For this solution I reused the powerset method I wrote for a recent 
Ruby Quiz.




class Array

  def sum
    inject { |sum,x| sum += x }
  end

  def powerset
    for element_map in 0...(1 << self.length) do
      subset = []
      each_with_index do |element, index|
        subset << element if element_map[index] == 1
      end
      yield subset
    end
  end

end

def calc(number, depth)
  puts "number = #{number}, depth = #{depth}"
  candidates = (1..9).inject([]) { |a,x| a << x }
  candidates.powerset { |subset|
    next unless subset.length == depth
    next unless subset.sum == number
    p subset
  }
end

# examples
(3..5).each { |depth|
  (10..20).each { |target| calc(target, depth) }
}

-- 
Posted via http://www.ruby-forum.com/.