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/