[SUMMARY] Happy Numbers (#93)

Discussion in 'Ruby' started by Ruby Quiz, Sep 7, 2006.

  1. Ruby Quiz

    Ruby Quiz Guest

    I posted a link to some additional information early in the quiz discussion that
    expanded on the definition provided by the quiz:

    http://mathworld.wolfram.com/HappyNumber.html

    According to that document, you can tell that a number is unhappy if the sum of
    the squares of the digits ever reaches 0, 4, 16, 20, 37, 42, 58, 89, or 145.
    That's really just a different way to find the repeat pattern mentioned in the
    quiz:

    0: 0
    4: 16 37 58 89 145 42 20 4
    16: 37 58 89 145 42 20 4 16
    20: 4 16 37 58 89 145 42 20
    37: 58 89 145 42 20 4 16 37
    42: 20 4 16 37 58 89 145 42
    58: 89 145 42 20 4 16 37 58
    89: 145 42 20 4 16 37 58 89
    145: 42 20 4 16 37 58 89 145

    Here's the code I used to generate the above list, which just loops over the sum
    of the squares until a repeat is found:

    #!/usr/bin/env ruby -w

    [0, 4, 16, 20, 37, 42, 58, 89, 145].each do |n|
    print "#{n}: "

    seen = {n => true}
    loop do
    sum = n.to_s.split("").inject(0) { |tot, d| tot + d.to_i ** 2 }

    print "#{sum} "
    if seen[sum]
    puts
    break
    else
    seen[sum] = true
    n = sum
    end
    end
    end

    The advantage of using the list is that you don't need to wait for the pattern
    to start repeating and thus you find answers quicker.

    Let's examine a solution that uses these numbers and another couple of
    optimizations. Here's my own code, strongly influenced by Simon Kroeger's
    solution:

    #!/usr/bin/env ruby -w

    UNHAPPY = [0, 4, 16, 20, 37, 42, 58, 89, 145].freeze

    happy = Hash.new do |found, num|
    digits = num.to_s.split("").sort.map { |d| d.to_i }.
    delete_if { |d| d.zero? }
    happiness = digits.inject(0) { |sum, d| sum + d * d }
    found[num] = if happiness == 1
    true
    elsif UNHAPPY.include? happiness
    false
    else
    found[happiness]
    end
    end

    (1..100_000).each { |n| p n if happy[n] }

    This is the standard Hash memoization pattern Ruby Quiz regulars are probably
    pretty familiar with by now. By creating a Hash and providing a block that can
    calculate the values from the keys, we ensure that Ruby will only run the code
    the first time it is needed. All other access is a simple Hash lookup and
    generally quite fast since Ruby's Hash is written in C.

    The Hash block is where you will find all the hard work for this solution. The
    first step taken there is to convert the number into an Array of digits and you
    will find two more optimizations in this conversion. First note the final call
    to delete_if(). Zero squared is still zero and adding zero has no effect, so we
    can safely strip those out of the digits. That can take a number like 1,000,000
    down to just the digit list of [1], skipping a fair amount of busy work.

    The second optimization in here is the call to sort(). This consolidates what
    we need to store in the Hash a good deal. The numbers 123 and 321 both involve
    the same calculations, so we normalize digit order and take advantage of the
    ability to skip several calculations.

    From there the block gets almost boring. A happiness rating is figured, which
    is just the sum of the digit squares. That rating is then checked for a known
    happy or unhappy value. If found, the Hash can set and return true or false.
    Otherwise the answer is determined by recursing to find the happiness of the
    sum.

    This solution ends with a trivial iteration to print all happy numbers between
    one and 100,000.

    My code just checked whether or not a given number is happy. The quiz mentioned
    other challenges and most people took them on. One such challenge involved
    finding out just how happy a number really is. Here's the start of some
    optimized code from Hans Fugal that does just that:

    require 'set'

    class Happy
    def initialize
    @happy_numbers = { 1 => 0 }
    @unhappy_numbers = Set.new
    end

    # ...

    You can see that Hans intends to track both happy and unhappy numbers. Happy
    numbers will be stored in a Hash with the number as the key and the value being
    the happiness rank for that number. Unhappy numbers will be a Set of numbers.

    Note that you can't just use the keys for the happy numbers Hash to determine if
    a number is unhappy. Not being in that list may just mean the number hasn't
    been checked yet.

    Here's the beginning of the method that does all the work:

    # ...

    def happy(x)
    return true if @happy_numbers.has_key?(x)
    return false if @unhappy_numbers.include?(x)

    path = [x]
    loop do
    sum = 0
    while x > 0
    x, r = x.divmod(10)
    sum += r**2
    end

    # ...

    This method is used to check if a number is happy, but it squirrels away the
    happiness rank for the number as it finds the answer. You can see that it
    begins with checks that short-circuit the process when the result is already
    known. If the result is not yet known, the code enters a loop() to figure it
    out.

    The path variable will eventually hold each step from the original number, to
    the squares sum that is known to be happy or unhappy. It begins with just what
    we currently know: the number itself.

    The first bit of code in the loop() is a digit splitter and squares summation
    all-in-one. It divides the digits out and adds them to a running sum as it
    goes. This is quite a bit quicker than the multiple iterators used to do the
    same in my code.

    Once we have a sum, it's time to check it for happiness:

    # ...

    if @unhappy_numbers.include?(sum)
    return false
    elsif @happy_numbers.has_key?(sum)
    r = @happy_numbers[sum]
    path.each_with_index do |x,i|
    @happy_numbers[x] = r + path.size - i
    end
    return true
    end

    path.push sum

    # ...

    If the sum is unhappy, we know all we need to know and the result is immediately
    returned to the user.

    If the sum is happy, we need to add all steps on the current path to the happy
    numbers Hash. Their rank is the rank of the sum we found plus their distance
    from the end of the current path. With that saved, true is returned to the
    calling code.

    If we didn't find the number in either place it is just another step on the path
    and push() is called to reflect this.

    Now we need the exit condition for the loop():

    # ...

    if [0, 1, 4, 16, 20, 37, 42, 58, 89, 145].include?(sum)
    if sum == 1
    s = path.size
    path.each_with_index do |x,i|
    @happy_numbers[x] = s - i - 1
    end
    return true
    else
    path.each do |x|
    @unhappy_numbers.add x
    end
    return false
    end
    end

    x = sum
    end
    end

    # ...

    This final bit of code checks for the known happy and unhappy sums. If the
    number is happy, we again place each step in the path in the happy numbers Hash
    according to their distance from the end of the path. If the number is unhappy,
    all steps in the path are added to the unhappy numbers Set.

    If the code makes it through all of that with no results, the current number is
    switched out for the squares sum and the code loop()s to find the answer.

    The method we just digested saved the number's happiness rank, so we now need a
    way to get it back out:

    # ...

    def rank(x)
    raise ArgumentError, "#{x} is unhappy." unless happy(x)
    return @happy_numbers[x]
    end
    end

    # ...

    This method first ensures the number has been ranked with a call to happy().
    Once it is known to be in the Hash, it's a simple lookup to locate and return a
    rank.

    Here's the user interface code Hans included with the solution, which will give
    the happiness rank for any numbers passed via STDIN:

    # ...

    haphap = Happy.new
    ARGF.each_line do |l|
    l.scan(/\d+/) do |token|
    x = token.to_i
    if haphap.happy(x)
    puts "#{x} is happy with rank #{haphap.rank(x)}"
    end
    end
    end

    Be sure and walk the other solutions. Many nice examples were given for finding
    happy bases. Daniel Martin even sent in a great NArray solution for that.

    My thanks to all happy coders who got to play with happy numbers, allowing me to
    write this happy summary.

    Tomorrow you all get a chance to earn double-O status, if your code is small
    enough and accurate...
    Ruby Quiz, Sep 7, 2006
    #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. Ruby Quiz

    [SUMMARY] LCD Numbers (#14)

    Ruby Quiz, Jan 13, 2005, in forum: Ruby
    Replies:
    2
    Views:
    114
    James Edward Gray II
    Jan 16, 2005
  2. Ruby Quiz

    [QUIZ] Happy Numbers (#93)

    Ruby Quiz, Sep 1, 2006, in forum: Ruby
    Replies:
    45
    Views:
    720
    Matthew Moss
    Sep 7, 2006
  3. Daniel Martin
    Replies:
    1
    Views:
    167
    Daniel Martin
    Sep 6, 2006
  4. Glen F. Pankow

    [QUIZ SOLUTION] Happy Numbers (#93)

    Glen F. Pankow, Sep 6, 2006, in forum: Ruby
    Replies:
    3
    Views:
    237
    James Edward Gray II
    Sep 6, 2006
  5. Rick DeNatale

    [QUIZ SOLUTION] Happy Numbers (#93)

    Rick DeNatale, Sep 6, 2006, in forum: Ruby
    Replies:
    0
    Views:
    95
    Rick DeNatale
    Sep 6, 2006
Loading...

Share This Page