--Apple-Mail-9-892176321
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
charset=US-ASCII;
delsp=yes;
format=flowed
This is my first ruby quiz solution since Quiz #1 : ) Thanks, it was
fun.
Moses
--Apple-Mail-9-892176321
Content-Transfer-Encoding: 7bit
Content-Type: text/x-ruby-script;
x-unix-mode=0644;
name="test_weird.rb"
Content-Disposition: attachment;
filename=test_weird.rb
require 'test/unit'
require 'weird'
class TestWeird < Test::Unit::TestCase
def test_proper_divisors
assert_equal [1], 11.proper_divisors
assert_equal [1, 2, 3, 4, 6], 12.proper_divisors
assert_equal [1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45], 90.proper_divisors
end
def test_find_partition_from
assert_equal nil, 2.send
find_partition_from, [1])
assert_equal [2], 2.send
find_partition_from, [2])
assert_equal [4,1], 5.send
find_partition_from, [4, 3, 2, 1])
assert_equal [175, 70, 50, 35, 14, 5, 1], 350.send
find_partition_from, 350.proper_divisors.reverse)
end
def test_abundant
assert_equal [12, 18, 20, 24], (1..25).find_all { |i| i.abundant? }
assert 945.abundant?, "945 not abundant" # test an odd one for good measure, no real reason why
end
def test_semiperfect
assert_equal [6, 12, 18, 20, 24], (1..25).find_all { |i| i.semiperfect? }
end
def test_weird
assert 70.weird?, "70 not weird"
assert !90.weird?, "90 weird"
end
def test_weird_numbers
assert_equal [70, 836], weird_numbers_less_than(1000)
assert_equal [], weird_numbers_less_than(70)
end
end
--Apple-Mail-9-892176321
Content-Transfer-Encoding: 7bit
Content-Type: text/x-ruby-script;
x-unix-mode=0644;
name="weird.rb"
Content-Disposition: attachment;
filename=weird.rb
module Enumerable
# syntactic sugar
def sum
inject(0) { |sum, element| sum += element }
end
end
module Weird
# Returns proper divisors of `self`, i.e. all divisors except `self`.
# Optimization: cached to improve speed - only small benefit for `weird_numbers_less_than`.
def proper_divisors
@proper_divisors ||= calculate_proper_divisors.freeze
end
# True if `self` is abundant, i.e. < the sum of its proper divisors
def abundant?
self < proper_divisors.sum
end
# True if `self` is semiperfect, i.e. at least one subset of `self`'s divisors forms a partition of `self`
def semiperfect?
!find_partition_from(proper_divisors.reverse).nil?
end
# True if self is a weird number, i.e. abundant and not semiperfect.
# Optimization: tests `abundant?` first because it's a lot faster.
def weird?
abundant? and not semiperfect?
end
# Syntactic sugar for Kernel's `weird_numbers_less_than` method below
def even?
self % 2 == 0
end
protected
# Finds one partition of `self` composed of integers taken without replacement from
# `set`. Only finds one, because all we need to know is whether there are any.
#
# Assumptions: set is sorted in decreasing order
# Protected because I want to call it from a unit test via `send`.
def find_partition_from(set)
return nil if set.empty? # recursion termination condition: no partition found
# find index of largest number < self in set (which is assume sorted in decreasing order)
start = nil
set.each_with_index do |element, index|
return [element] if element == self # recursion termination condition: partition found
if element < self # found largest number < self
start = index
break
end
end
# recursively construct partition
partition = nil
unless start.nil?
start.upto(set.length-1) do |index|
break unless partition.nil?
biggest, tailset = set[index], set[(index+1)..-1]
partition = (self - biggest).find_partition_from(tailset)
partition.insert(0, biggest) unless partition.nil?
end
end
partition
end
private
# Actually calculates (i.e. not cached) and returns all proper divisors of `self`.
# Optimization: it turned out that inserting the divisors in sorted order was slower,
# at least the way I tried it. Uniq does not pose much of a burden either.
def calculate_proper_divisors
return [] if self == 1
result = [1]
2.upto(Math.sqrt(self).floor) do |candidate|
# add both candidate and quotient, since they are both divisors
result << candidate << (self / candidate) if self % candidate == 0
end
result.sort.uniq # uniq is needed for perfect squares
end
end
class Fixnum; include Weird; end
class Bignum; include Weird; end # optimistic about CPU power!
# Optimization: `check_odd` parameter: there are no odd weird numbers < 10**19 [Weisstein, 2005], so
# in general you should leave this flag at its default value of `false`. This provides a modest speedup
# (something like a factor of 1.5. I think the reason it's not more is there are few odd abundant numbers).
#
# [Weisstein, 2005] Eric W. Weisstein. "Weird Number." From MathWorld--A Wolfram Web Resource.
#
http://mathworld.wolfram.com/WeirdNumber.html
def weird_numbers_less_than(n, check_odd = false)
(1...n).find_all { |number| (check_odd or number.even?) and number.weird? }
end
if __FILE__ == $0
p weird_numbers_less_than(ARGV[0].to_i, (ARGV[1] == 'check_odd'))
end
--Apple-Mail-9-892176321
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
charset=US-ASCII;
delsp=yes;
format=flowed
The three rules of Ruby Quiz:
1. Please do not post any solutions or spoiler discussion for this
quiz until
48 hours have passed from the time on this message.
2. Support Ruby Quiz by submitting ideas as often as you can:
http://www.rubyquiz.com/
3. Enjoy!
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
=-=-=-=-=-=-=
by Martin DeMello
A weird number is defined as a number, n, such that the sum of all
its divisors
(excluding n itself) is greater than n, but no subset of its
divisors sums up to
exactly n.
Write a program to find all the weird numbers less than a given input.
--Apple-Mail-9-892176321--
