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
