On Sun, 03 Sep 2006 14:31:09 +0000, Ken Bloom wrote:

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


Since the order of digits in the number doesn't matter, here's code to
generate digits whose numbers are in nondecreasing order. This makes the
"happiest number" test finish almost instantly when the numbers are
generated this way:

   #generates all numbers in the given range whose digits are in 
   #nondecreasing order. the order in which the numbers are generated is 
   #undefined, so it's possible for 123 to appear before 23, for 
   #example.
   def nondec_digits(range,&b)
      yield 0 if range.first<=0
      (1..9).each { |x| noninc_digits_internal(x,x,range,&b) }
   end

   def nondec_digits_internal(last,accum,range,&b)
      (last..9).each do |x|
	 iaccum=accum*10+x
	 b.call(iaccum) if range.include?(iaccum)
	 noninc_digits_internal(x,iaccum,range,&b) if iaccum<=range.last
      end
   end



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