From: Kenneth Collins <pine29@...>
Date: 2005-12-05T13:29:18+09:00
Subject: Re: Weird Numbers (#57) Solution

Wow, I got a lot from looking at the other solutions. Thanks especially 
to Ed, Ryan, Jannis and Christian. I see that the single biggest 
performance gain comes from using a recursive sum_in_subset? method such 
as that found in Ed's solution. I've borrowed from his code for this 
fairly simple and straightforward resubmission. It doesn't perform as 
well as the faster solutions, but it's much, much faster than my first 
submission.

#!/usr/bin/env ruby
#
# Ruby Quiz Weird Numbers solution.
# Uses recursive sum_in_subset? approach borrowed from
# other solutions.
#

class Integer

  def weird?
    divisors = self.divisor_list
    abundancy = divisors.inject { |total,x| total += x } - self
    return false unless abundancy > 0
    smalldivisors = divisors.reverse.select { |j| j <= abundancy }
    return false if sum_in_subset?(smalldivisors, abundancy)
    return true
  end

  def sum_in_subset?(list, target)
    return false if target < 0
    return true if list.include?(target)
    return false if list.length == 1
    first = list.first
    rest = list[1..-1]
    sum_in_subset?(rest, target-first) or sum_in_subset?(rest, target)
  end

  def divisor_list
    list = []
    (1..Math.sqrt(self).to_i).each do |x|
      if self % x == 0
        list << x
        list << (self / x) unless x == 1 or (self / x) == x
      end
    end
    return list.sort
  end

end

####################

unless ARGV.length == 1
  puts "Usage: #{$0} <max_value>"
end
max_value = ARGV.shift.to_i
(1..max_value).each { |n| puts n if n.weird? }

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