Forum: Ruby Weird Numbers (#57)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
James G. (Guest)
on 2005-12-08 16:40
(Received via mailing list)
In reading through all the interesting solutions to this quiz, I noticed
two
things.  Some solutions were easy to follow and have clever ways to do
the work.
Others were very fast, thanks to good optimizations.  Let's examine one
of each.

First, here is Brian Schroeder's complete solution (minus a line I
removed):

	#!/usr/bin/ruby

	# Break early version, checking if a number is weird
	def weird_number(n)
	  sum = 0
	  subset_sums = Hash.new
	  subset_sums[0] = true
	  for d in 1...n
	    next unless n % d == 0
	    # Calculate sum of all divisors
	    sum += d
	    # Calculate sums for all subsets
	    subset_sums.keys.each do | s |
	      return false if s + d == n
	      subset_sums[s + d] = true
	    end
	  end
	  sum > n
	end

	def weird_numbers(range)
	  range.select { | n | weird_number(n) }
	end

	# Argument parsing
	raise "Input exactly one number" unless ARGV.length == 1

	max = ARGV[0].to_i

	# Call it
	puts weird_numbers(1..max)

This code is not blazing fast, but it's easy to follow and a unique
approach.
That's worth a look, I think.

All the action is in weird_number(), which just returns true or false to
indicate if the passed argument is indeed weird.  It begins by
initializing an
overall sum variable and a Hash for subset_sums.  Notice that 0 is added
to
subset_sums here.  We will look at that more in a bit.  (All the values
of this
Hash are set to true, but they are really unused.  Brian just wanted the
unique
property of Hash keys.)

The method then walks from 1 to the number, looking for divisors.  When
a
divisor is found, it's added to the sum and then added to each previous
subset_sum (or just 0 on the first occurrence).  Each time a new
subset_sum is
generated, the total is checked against the number itself.  This allows
the code
to return an early false, when it finds a match.

If none of the subset_sums short-circuited the process, a final check is
made to
ensure that the overall sum exceeds the number.  When it does, a weird
number is
found.

The rest of Brian's code is just argument parsing, the search through
the range
of numbers, and output.  This is very simple stuff.

I might suggest one change and that would be that printing the numbers
as they
are found makes the wait a little less tedious, I think.  That's an easy
fix.
The last line of code can be switched to:

	(1..max).each { |n| puts n if weird_number n }

Brian's code needs over a minute to find the weird numbers from 1 to
10,000.
That's the downside.  If you want to do it faster, you have to find some
shortcuts and some submitters found great ones.

Let's switch gears to Ryan L.'s code, which can do the same
calculation
in under a second.  It starts with a simple helper method:

	class Array
	  def sum
	    inject(0) do |result, i|
	      result + i
	    end
	  end
	end

	# ...

I assume the standard Ruby idiom for summation needs little
introduction.  Let's
move on to the heart of the algorithm:

	# ...

	class Integer
	  def weird?
	    # No odd numbers are weird within reasonable limits.
	    return false if self % 2 == 1
	    # A weird number is abundant but not semi-perfect.
	    divisors = calc_divisors
	    abundance = divisors.sum - 2 * self
	    # First make sure the number is abundant.
	    if abundance > 0
	      # Now see if the number is semi-perfect. If it is, it isn't
weird.
	      # First thing see if the abundance is in the divisors.
	      if divisors.include?(abundance)
	        false
	      else
	        # Now see if any combination sums of divisors yields the
abundance.
	        # We reject any divisors greater than the abundance and reverse
the
	        # result to try and get sums close to the abundance sooner.
	        to_search = divisors.reject{|i| i > abundance}.reverse
	        sum = to_search.sum
	        if sum == abundance
	          false
	        elsif sum < abundance
	          true
	        else
	          not abundance.sum_in_subset?(to_search)
	        end
	      end
	    else
	      false
	    end
	  end

	  # ...

Finding out if a number is weird requires a fair amount of processing.
We need
all of the divisors (a lot of work to find on big numbers), subset sums
for
those divisors, etc.  However, we know some things about weird numbers
that can
be tested faster.  If less work rules out that process some of the time,
it can
add up to a big win.

First of all, there are no known odd weird numbers, so we might as well
toss out
half of the set right off the bat.  (It's possible there are some very
large odd
weird numbers, but we would have trouble calculating those anyway.)
Going a
step further, there are simple mathematical formulas to determine if a
number is
abundant or semi-perfect.  We can use those to quickly eliminate many
numbers,
because weird numbers are always abundant and never semi-perfect.  If we
make it
that far, we will still have to do the work, but that allows us to skip
a good
deal of numbers that would have cost us time.

	  # ...

	  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.uniq
	  end

	  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
	end

	# ...

There are even shortcuts to be found in the work itself.  The biggest is
in
calculating divisors.  You can just find those between 1 and the square
root of
the number, then use those to get the rest.  Also, when checking divisor
sums,
work with the big numbers first, to get totals closer to the actual
number that
may rule it out quickly.

Another interesting option, much debated in the quiz solution thread, is
the
ability to add a cache to the program.  If a weird number is added to
the cache
when found, future queries can be lightning quick.  Here's a nice bit of
code
Ryan added just to shut me up about the merits of caching (a noble
goal!):

	# ...

	class WeirdCache
	  def initialize(filename='.weirdcache')
	    @filename = filename
	    if test(?e, filename)
	      @numbers = IO.readlines(filename).map do |i|
	        i.chomp.to_i
	      end
	    else
	      @numbers=[]
	    end
	    @added = false
	  end

	  def each(&block)
	    @numbers.each(&block)
	  end

	  def <<(i)
	    @added = true
	    @numbers << i
	  end

	  def save
	    if @added
	      File.open(@filename, File::RDWR|File::CREAT|File::TRUNC) do
|file|
	        file.puts @numbers
	      end
	    end
	  end
	end

	# ...

Nothing tricky there.  We just have a container for numbers with the
ability to
save it out to disk.  You can see that it is reloaded upon creation.

Finally, here's the code that ties all this together:

	# ...

	if $0 == __FILE__
	  if ARGV.length < 1
	    puts "Usage: #$0 <upper limit>"
	    exit(1)
	  end

	  puts "Weird numbers up to and including #{ARGV[0]}:"
	  start = Time.now
	  cache = WeirdCache.new
	  at_exit {cache.save}
	  limit = ARGV[0].to_i
	  i = 69
	  cache.each do |i|
	    if i <= limit
	      puts i
	    end
	  end
	  (i+1).upto(limit) do |j|
	    if j.weird?
	      cache << j
	      puts j
	    end
	  end
	  puts "This took #{Time.now - start} seconds"
	end

Notice the nice use of variable scoping there.  The variable i is set to
69
before the cache is walked.  (Another optimization.  70 is the first
weird
number, so we can safely skip anything before that.)  Numbers in the
cache will
replace i, leaving it holding the highest known weird number.  Then, if
the
limit is higher than that, the code only needs to calculate from there
up.

I've barely scratched the surface of the solutions here.  There were
many more
gems hidden in them.  I do recommend browsing the source of the others
for
picking up new tricks.

My thanks to all who solved this problem, took my abuse about caching,
and
especially to Ryan for building what I pestered him for.

We have two back-to-back quizzes for all you gamers out there coming up
next.
First, Kalah anyone?
This topic is locked and can not be replied to.