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
···
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:
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 = 1If 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
endinclude 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==nil or minhappy>n
minhappy=n
end
end
endputs 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/
