[SUMMARY] Weird Numbers (#57)

Discussion in 'Ruby' started by Ruby Quiz, Dec 8, 2005.

  1. Ruby Quiz

    Ruby Quiz Guest

    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 Leavengood'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?
    Ruby Quiz, Dec 8, 2005
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. dorayme
    Replies:
    1
    Views:
    613
    richard
    Jan 21, 2011
  2. richard
    Replies:
    0
    Views:
    578
    richard
    Jan 21, 2011
  3. richard
    Replies:
    0
    Views:
    613
    richard
    Jan 21, 2011
  4. Beauregard T. Shagnasty

    Re: A Weird Appearance for a Weird Site

    Beauregard T. Shagnasty, Jan 21, 2011, in forum: HTML
    Replies:
    1
    Views:
    435
    Captain Paralytic
    Jan 21, 2011
  5. David Segall
    Replies:
    0
    Views:
    628
    David Segall
    Jan 22, 2011
Loading...

Share This Page