From: Christer Nilsson <janchrister.nilsson@...>
Date: 2005-12-05T07:50:40+09:00
Subject: Weird Numbers (#57) Solution

This was really a good and enjoyable exercise. I learnt a lot. One of 
the best solutions is made by Leavengood. I would like to point out a 
small error. 36.calc_divisors returns [1,2,3,4,6,6,9,12,18,36]. 6 is 
reckoned twice. This seems to have no implication on the result though.

  def calc_divisors
    res=[1]
    2.upto(Math.sqrt(self).floor) do |i|
      if self % i == 0
        res << i
      end
    end
    res.reverse.each do |i|
      res << self / i
    end
    res
  end

The part I appreciate most is the beautiful and fast handling of the 
binary set:

  def sum_in_subset?(a)
    if self < 0
      false
    elsif a.include?(self)
      true
    else
      if a.length == 1
        false
      else
        f = a.first
        remaining = a[1..-1]
        (self - f).sum_in_subset?(remaining) or
                   sum_in_subset?(remaining)
      end
    end
  end

I also learnt that Ruby is really quick once you leave the debugger!

Here is my solution. It is short but slow.

def divisors(n) (1..n.div(2)).collect {|i| i if n.modulo(i)==0}.compact 
end
def sum(arr) arr.inject(0) {|sum,element| sum+element} end

def subset?(n, divisors)
  arr=[]
  divisors.each do |i|
    arr.concat arr.collect {|j| i+j}
    arr << i
    arr.uniq!
    return true if arr.member?(n)
  end
  false
end

def weird(n)
  return if n.modulo(2)==1
  coll = divisors(n)
  diff = sum(coll)-n
  return if diff <= 0
  return n unless subset?(diff,coll)
end

def all_weird(n) (1..n).collect {|i| weird(i)}.compact end

    assert_equal [1,2,3,4,6], divisors(12)
    assert_equal [1,2,5,7,10,14,35], divisors(70)
    assert_equal 16, sum(divisors(12))
    assert_equal 74, sum(divisors(70))
    assert_equal true, subset?(12,divisors(12))
    assert_equal false, subset?(70,divisors(70))
    assert_equal false, subset?(4,divisors(70))
    assert_equal nil, weird(2)
    assert_equal nil, weird(12)
    assert_equal nil, weird(20)
    assert_equal 70, weird(70)
    assert_equal [70], all_weird(70)
    assert_equal [70,836], all_weird(836)

Christer

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