Here’s my solution. Writing a method that can determine whether a number

is

happy, and how happy it is, is fairly simple. Once the method exists,

it’s

fairly trivial to write short programs that use the method to determine

the

happiness of a number, or to find the highest happy number or the

happiest

number in a range, as requested by the quiz. But the Ruby Q. generally

requests that you write a program, not a single method, so I decided to

write a

program that can perform all of these tasks, depending on the input

parameter.

And handle bases other than ten if desired, to boot.

Once I decided to do that, it made sense to optimize the method over

multiple

runs, by memoizing results, and taking algorithmic shortcuts based on

previously

memoized results. So my get_happy method is a bit more complicated than

it was

originally, due to the optimizations.

Of course, once I added optimizations, I introduced bugs. They were

subtle and a

bit tricky to track down. But they basically boiled down to this

question: Is 1

a happy number, and if so, how happy? It’s obvious that when you perform

one

iteration of the happiness algorithm, the next number in the sequence

has a

happiness value of one less than the current number. For example, take

the

sequence used in the quiz description. It starts with 7, which is

finally stated

to have a happiness value of 4. The remaining numbers in the sequence,

49, 97,

130, and 10, thus have happiness values of 3, 2, 1, and 0 respectively.

So, is 1 happy? If the definition of a happy number is that the

algorithm

evenually reaches 1, then yes it is. What is its happiness value? It

could

arguably be 0, because the algorithm goes to 1 right away, without

generating

any other happy numbers. But, any number with a happiness value of 0,

such as

10, has 1 as its next iterated value, which means that, according to the

paragraph above, 1 should have a happiness value of 1 less than 0, which

would

be -1. So is 1’s happiness value 0 or -1?

I guess it’s an arbitrary choice. But until I realized what was going

on, I had

a bug in which a number’s happiness value would either be correct, or 1

higher

than correct, depending on whether or not it was being calculated based

on a

previous memoized intermediate value. I had originally set 1’s happiness

value

to 0, but this caused 10’s value to be calculated as 1 instead of 0,

because it

was 1 higher than the happiness value of the next number in the

sequence, which

was of course 1, whose happiness is 0. This happened only when 10’s

happiness

value was memoized during another number’s sequence, but not when 10

itself had

been passed into the get_happy method. Then I naively changed 1’s

happiness

value to -1, to try to fix this. But this didn’t work either, since -1

is my

magic value meaning “unhappy”, so all numbers were determined to be

unhappy

since 1’s memoized value returned as -1 in the first optimization. So I

changed

1’s happiness value back to 0, and unconditionally decreased all

numbers’

happiness values by 1, which also turned out to be wrong.

When I finally understood what was going on, I realized that the correct

fix was

to add the “(temp != 1)” conditional in the first “if” statement, and

the “ret

-= 1” line if the algorithm has iterated all the way to 1. At this

point, 1’s

happiness value isn’t actually used in the algorithm for computing any

other

number’s happiness. It’s only ever used if get_happy is called on the

value 1

itself. And at last, the program works! (At least, I’m pretty sure it

does )

#!/usr/bin/env ruby

# =Description

# This program determines the happiness of a number, or the happiest

number and

# highest happy number in a range of numbers.

# A number’s happiness is determined as follows: Sum the squares of the

number’s

# individual digits. Repeat this process with the result, until a value

of 1 is

# reached, or until a value is repeated, thus indicating a loop that

will never

# reach 1. A number for which 1 is reached is “happy”. The number of

other

# numbers generated besides 1 and the original number is its happiness

value.

# =Usage

# happy.rb num1[-num2][:base]

# happy.rb takes a single argument. If the argument is a single number,

that

# number’s happiness value is displayed, or the number is said to be

unhappy.

# If the argument is a range of numbers, such as “1-400”, the happiness

value of

# the happiest number (lowest number breaking ties) in that range is

returned.

# If the argument ends with a colon and a number, such as “50:8” or

“1-100:2”,

# the number after the colon specifies the base of the first number(s).

An

# unspecified base implies base ten.

require ‘rdoc/usage’

#==============================================================================

# ----- Global variables -----

#==============================================================================

$hap_map = {} # Hash for memoization of happiness values

#==============================================================================

# ----- Instance methods -----

#==============================================================================

class String

# Indicates whether the string is a valid number of the specified

base.

def is_num_of_base?(base)

# sub() call removes leading zeros for comparison

self.sub(/\A0+/, ‘’).downcase == self.to_i(base).to_s(base).downcase

end

end

class Integer

# Pretty-print string including base, if base is not 10

def pretty(base)

self.to_s(base) + ((base == 10) ? “” : " (base #{base})")

end

end

#==============================================================================

# ----- Global methods -----

#==============================================================================

# This method returns the happiness value of the given number. A value

of -1

# indicates that the number is unhappy.

def get_happy(num, base=10)

$hap_map[num] = 0 if num == 1 # Handles trivial case

return $hap_map[num] if $hap_map[num]

ret = 0

done = false

inters = []

temp = num

until done

digits = temp.to_s(base).split(//).map{|c| c.to_i(base)}

temp = digits.inject(0) {|sum, d| sum + d**2}

ret += 1

```
if (temp != 1) && $hap_map[temp]
# Optimization; use knowledge stored in $hap_map
if $hap_map[temp] == -1
ret = -1
done = true
else
ret += $hap_map[temp]
done = true
end
else
if temp == 1
ret -= 1 # Don't count 1 as an intermediate happy number
done = true
elsif inters.include?(temp)
ret = -1
done = true
else
inters << temp
end
end
```

end

$hap_map[num] = ret

# Optimization

if ret == -1

# If num is not happy, none of the intermediates are happy either

inters.each {|n| $hap_map[n] = -1}

else

# If num is happy, each intermediate has a happiness value

determined by

# its position in the array

inters.each_index {|idx| $hap_map[inters[idx]] = (ret - 1) - idx}

end

return ret

end

# nums is a range of integers. This method returns two values: the

happiest

# number, and the highest happy number, in the range. Two nil values

will be

# returned if there are no happy numbers in the range.

def get_superlatives(nums, base)

happiest_num = nil

happiest_ness = nil

highest = nil

nums.each do |n|

happy = get_happy(n, base)

next if happy == -1

highest = n

```
if (!happiest_ness) || (happy > happiest_ness)
happiest_num = n
happiest_ness = happy
end
```

end

return happiest_num, highest

end

#==============================================================================

# ----- Script start -----

#==============================================================================

if ARGV.size != 1

RDoc.usage(‘Usage’, ‘Description’)

end

# Parse arg

ARGV[0] =~ /\A([\d\w]+)(?:-([\d\w]+))?(?::(\d+))?\Z/

num1, num2, base = $1, $2, $3

# Ensure legal arg

RDoc.usage(‘Usage’, ‘Description’) unless num1

# Fill in defaults

base = 10 unless base

num2 = num1 unless num2

# Convert numbers from strings to numeric values

base = base.to_i

[num1, num2].each do |s|

unless s.is_num_of_base?(base)

puts “Error: #{s} is not a valid base #{base} number”

exit

end

end

num1 = num1.to_i(base)

num2 = num2.to_i(base)

# Calculate and print results

if num1 == num2

happiness = get_happy(num1, base)

print num1.pretty(base)

if happiness == -1

print " is not happy.\n"

else

print " has a happiness of #{happiness}\n"

end

else

if num1 > num2

num1, num2 = num2, num1

end

happiest, highest = get_superlatives((num1…num2), base)

if !highest

puts “None of those numbers are happy.”

else

puts "The happiest number is " + happiest.pretty(base) +

“, with a happiness of #{get_happy(happiest, base)}”

```
puts "The highest happy number is " + highest.pretty(base) +
", with a happiness of #{get_happy(highest, base)}"
```

end

end