Reply to thread

Message: [QUOTE="Hans Fugal, post: 4525570"] 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 [/QUOTE]

Verification