I wrote it and then added some lookup table optimizations which resulted
in a 1.5 speedup when executed over the numbers 1 through 10,000.
First the naive:
#!/usr/bin/ruby
# Ruby happy number quiz solution. September 2006
# Hans Fugal
class Happy
def initialize
@happy_numbers = { 1 => 0 }
end
def happy(n)
return true if n == 1
x = n
rank = 0
loop do
sum = 0
while x > 0
x, r = x.divmod(10)
sum += r**2
end
rank += 1
if [0, 1, 4, 16, 20, 37, 42, 58, 89, 145].include?(sum)
if sum == 1
@happy_numbers[n] = rank
return true
else
return false
end
end
x = sum
end
end
def rank(x)
raise ArgumentError, "#{x} is unhappy." unless happy(x)
return @happy_numbers[x]
end
end
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
Now the optimized:
#!/usr/bin/ruby
# Ruby happy number quiz solution. September 2006
# Hans Fugal
require 'set'
class Happy
def initialize
@happy_numbers = { 1 => 0 }
@unhappy_numbers = Set.new
end
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
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 [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
def rank(x)
raise ArgumentError, "#{x} is unhappy." unless happy(x)
return @happy_numbers[x]
end
end
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