Re: [QUIZ SOLUTION] Happy Numbers (#93)

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 Quiz 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

-- 
Karl von Laudermann - karlvonl(a)rcn.com - http://www.geocities.com/~karlvonl 
#!/usr/bin/env ruby
require "complex";w=39;m=2.0;w.times{|y|w.times{|x|c=Complex.new((m*x/w)-1.5,
(2.0*y/w)-1.0);z=c;e=false;49.times{z=z*z+c;if z.abs>m then e=true;break;end}
print(e ?"  ":"@@");puts if x==w-1;}}