# Happy Numbers (#93)

**URL:** <https://www.ruby-forum.com/t/happy-numbers-93/67869>\
**Category:** Ruby\
**Created:** [September 7, 2006, 2:58pm UTC](https://www.ruby-forum.com/t/happy-numbers-93/67869 "2006-09-07T14:58:52Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [September 7, 2006, 2:58pm UTC](https://www.ruby-forum.com/t/happy-numbers-93/67869/1 "2006-09-07T14:58:52Z")

</div>

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 Q. 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 F. 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 M. 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…