On Fri, 01 Sep 2006 22:01:41 +0900, Ruby Quiz wrote:

> The three rules of Ruby Quiz:
> 
> 1.  Please do not post any solutions or spoiler discussion for this quiz until
> 48 hours have passed from the time on this message.
> 
> 2.  Support Ruby Quiz by submitting ideas as often as you can:
> 
> http://www.rubyquiz.com/
> 
> 3.  Enjoy!
> 
> Suggestion:  A [QUIZ] in the subject of emails about the problem helps everyone
> on Ruby Talk follow the discussion.  Please reply to the original quiz message,
> if you can.
> 
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
> 
> by Shane Emmons
> 
> Write a program that tells whether a given integer is happy. A happy number is
> found using the following process: Take the sum of the squares of its digits,
> and continue iterating this process until it yields 1, or produces an infinite
> loop. 
> 
> For example the number 7:
> 
> 	7^2 = 49
> 	4^2 + 9^2 = 97
> 	9^2 + 7^2 = 130
> 	1^2 + 3^2 + 0^2 = 10
> 	1^2 + 0^2 = 1
> 
> If a number is not happy than it is obviously unhappy. Now that you have this
> program, what is the largest happy number you can find? What is the happiest
> number between 1 and 1,000,000. I define the happiest number as the smallest
> number that finds the most other happy numbers with it, i.e. 7 found four other
> numbers (49, 97, 130, and 10) making it a rank 4 in happiness.
> 
> If you find all these examples trivial, write you program so that it will find
> happy numbers in other bases such as base 2 or 16. From there you can extend the
> program so that it finds happy bases (other than 2 and 4). A happy bases is a
> base where all numbers are happy. Good luck.

require 'enumerator'
require 'jcode'


module Happy
  #1 is a success terminator, from Wolfram's MathWorld
  FAIL_TERMINATORS=[0, 4, 16, 20, 37, 42, 58, 89, 145]

  def internal_happy? number
    return 0 if number==1
    return false if FAIL_TERMINATORS.include? number
    it=Enumerable::Enumerator.new(number.to_s,:each_char)
    newnumber=it.inject(0) { |partial_sum,char| partial_sum+(char.to_i)**2 }
    x=happy?(newnumber)
    return x+1 if x
    return false
  end

  @@memo=Hash.new

  def happy? number
    return @@memo[number] || @@memo[number]=internal_happy?(number)
  end
end

include Happy

#there is no largest happy number because any 10**n is happy for any n.
#since ruby can represent all integers, there's no "largest number I can 
#find" (given enough RAM)

#to find the happiest number between 1 and 1_000_000, we use the 
#following code (which takes advantage of the memoization that I have 
#included)

minhappy=[]
1_000_001.times do |n|
  puts "Progress #{n}" if n%1000==0
  if x=happy?(n)
    if  minhappy[x]==nil or minhappy[x]>n
      minhappy[x]=n
    end
  end
end

puts minhappy.last

#after a long time running, this prints that
#the happiest number is 78999

#by clearing the memoization hash and adding a strategically placed
#puts, I can see this computes happiness for the following
#numbers: [78999, 356, 70, 49, 97, 130, 10, 1]

--Ken Bloom

-- 
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/